Masala D
Maksimal yig'indi
(To'liq vectorda ishlang)
Koordinata tekisligida n ta nuqtada mavjud. Dastlab siz x=0 nuqtada turibsiz. [1,n] oralig'ida butun nuqtalarda tangalar mavjud. Tanga manfiy qiymatga ega bo'lishi mumkin. Bir amalda bir yoki ikki katak o'nga surilishingiz mumkin. Qaysidir nuqtaga kelganda ushbu nuqtadagi tangani olishingiz lozim. Sizning vazifangiz x=n nuqtaga maksimal qiymatdagi tangalar bilan borishdan iborat.
Kiruvchi ma'lumotlar:
Birinchi qatorda natural son, n(1≤n≤10^5).
Ikkinchi qatorda tangalarni qiymatlari beriladi, xi( ∣ xi ∣≤10^9).
Chiquvchi ma'lumotlar:
Yagona qatorda javobni chiqaring.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 1 -2 3 |
4 |
| 2 |
4 1 -2 -3 3 |
2 |
Telegram kanalimizga obuna bo'ling