Codeforces Round #804 (Div. 2)
00:27:23 |
Educational Codeforces Round 131 (Rated for Div. 2)
5 өдрийн дараа |
Codeforces Round #805 (Div. 3)
7 өдрийн дараа |
Codeforces Round #806 (Div. 4)
9 өдрийн дараа |
B. Кайса ба баганууд
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Кайса элсэн чихрийн бодлогыг бодоод одоо гэртээ харьж байна.
Кайса зам зууртаа гар утасны тоглоом тоглон явж байна. Тэр тоглоомонд $0$-ээс $n$ дугаартай $(n + 1)$ багана байв. $0$ дугаартай багана тэг ѳндѳртэй, $i$ $(i > 0)$ дугаартай багана $h_{i}$ ѳндѳртэй. Тоглоомын зорилго нь $n$-р баганад зѳвхѳн байгаа баганаасаа дараагийн багана бүрт харайсаар очих юм ($k$ дугаартай баганаас зѳвхѳн $k + 1$ дугаартай багана руу л үсэрч болно). Энэ шилжилт хийх бүрт түүний энерги $h_{k} - h_{k + 1}$ (хэрвээ энэ утга сѳрѳг байвал энерги нь багасна) хэмжээгээр нэмэгднэ. Тоглогч аль ч агшинд сѳрѳг биш энергитэй байх ёстой.
Анх Кайса $0$ багана дээр байхад $0$ энергитэй байна. Энэ тоглоом нэгэн онцгой боломжийг ѳгдѳг: ганц доллар тѳлѳѳд дуртай баганыхаа ѳндрийг нэгээр ѳсгѳж болно. Кайса энэхүү боломжийг хэдэн ч удаа ашиглах боломжтой ч тэр үүнд их мѳнгѳ зориулахыг хүсэхгүй байлаа. Түүнд тоглоомыг давахын тулд хамгийн багадаа хэдэн доллар шаардлагатай вэ?
Оролт
Эхний мѳр $n$ $(1 ≤ n ≤ 10^{5})$ бүхэл тоог агуулна. Дараагийн мѳр багануудын ѳндѳр болох $n$ ширхэг бүхэл тоо $h_{1}$, $h_{2}$, ..., $h_{n}$ $(1 ≤ h_{i} ≤ 10^{5})$ агуулна.
Гаралт
Кайсагийн тѳлѳх ёстой хамгийн бага долларын хэмжээ болох бүхэл тоог хэвлэ.
Орчуулсан: Sugardorj
Жишээ тэстүүд
Оролт
5 3 4 3 2 4
Гаралт
4
Оролт
3 4 4 4
Гаралт
4
Тэмдэглэл
Эхний жишээний хувьд $4$ доллар тѳлѳѳд $0$ дугаартай баганы ѳндрийг $4$ нэгжээр ѳсгѳхѳд сүүлийн багана хүртэл явж чадна.