A. Алимхүү ба Талххүү

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Алимхүү ба Талххүү тоглоом тоглож байна. Эхлээд Алимхүү $n$ тоотой нэг бүлгийг Талххүүд ѳгсѳн, тэгээд тэд дараах даалгаврыг биелүүлж эхэллээ:

  • Талххүү ээлжиндээ нэг бүлэг тоог авч, бүлэг дэх бүх тооны нийлбэрийг оноон дээрээ нэмээд Алимхүүд ѳгнѳ.
  • Алимхүүгийн ээлжинд ганцхан тоотой бүлэг хүлээн авбал тэр бүлгийг шууд хаяна. Алимхүү ѳѳрийн ээлжиндээ нэгээс олон тоотой бүлэг хүлээн авбал түүнийг хоосон биш хоёр бүлэгт хуваан (ямар ч байсан хувааж чадна) тэдгээр бүлгүүдийг Талххүүд ѳгнѳ.

Залуус даалгаврыг гүйцэтгэсний дараа хамгийн ихдээ хэдэн оноотой болж чадах вэ?

Оролт

Эхний мѳр $n$ ($1 ≤ n ≤ 3*10^{5}$) бүхэл тоог агуулна. Хоёрдугаар мѳр анх Талххүүд ѳгсѳн бүлэг тоонууд болох $n$ бүхэл тоог $a_{1}$, $a_{2}$, ..., $a_{n}$ ($1 ≤ a_{i} ≤ 10^{6}$) агуулна.

Гаралт

Боломжит хамгийн их оноог хэвлэ.

Орчуулсан: Sugardorj

Жишээ тэстүүд

Оролт
3
3 1 5
Гаралт
26
Оролт
1
10
Гаралт
10

Тэмдэглэл

Эхний жишээний хувьд дараах үйлдлүүдийг авч үзье. Эхлээд Талххүү [3, 1, 5] бүлгийг хүлээн авч 9 оноог нэмээд Алимхүүд бүлгийг ѳгнѳ. Алимхүү [3, 1, 5] бүлгийг [3, 5] ба [1] болгож хуваагаад Талххүүд ѳгѳх хэрэгтэй. Талххүү [1] бүлгийг хүлээн авч 1 оноог нэмээд уг бүлгийг Алимхүүд ѳгнѳ (тэр үүнийг хаяна). Талххүү [3, 5] бүлгийг хүлээн авч 8 оноог нэмээд Алимхүүд ѳгнѳ. Алимхүү [3, 5] бүлгийг ганц боломжит хуваалтаар [5] ба [3] гэж хуваана. Тэгээд хоёр бүлгийг Талххүүд ѳгнѳ. Талххүү [5] бүлгийг хүлээж аваад 5 оноог нэмж Алимхүүд ѳгнѳ (тэр үүнийг хаяна). Талххүү [3] бүлгийг авч 3 оноог нэмээд Алимхүүд ѳгнѳ (тэр мѳн л хаяна). Эцэст нь Талххүү 9 + 1 + 8 + 5 + 3 = 26 оноог нэмж авчээ. Энэ хамгийн ашигтай үйлдлийн дараалал юм.

Сэтгэгдлүүдийг ачааллаж байна...