Masala #YDAXIPWHMQ
Maksimal summa
Muhammadqodir Ozodbek tomondan tug'ilgan kuniga berilgan uzunligi \(n\) massiv bilan o'ynab o'tirgandi. Lekin zerikib ketdi, shuning uchun u yangi bir o'yin topdi. U bir urinishda istalgan \(l\) va \(r\) (\(1 \leq l \leq r \leq n\)) oralig'ini tanlaydi va o'sha oraliqdagi hamma sonlarni \(-1\) ga ko'paytiradi.
Masalan, \(n = 6\) va massiv esa \([-1, 7, -5, -2, 6, -8]\) bo'lsin. Agar u \(l =3\) va \(r = 4\) oraliqni tanlab tepadagi operatsiyasini bajarsa massiv bunday holatga keladi: \([-1, 7, 5, 2, 6, -8]\).
Muhammadqodirning maqsadi esa massivning summasini maksimallashtirish va buni iloji boricha minimal operatsiyalar yordamida bajarish.
Birinchi qatorda \(n\) (\(1 \leq n \leq 10^5\)) massiv uzunligi.
Ikkinchi qatorda \(n\) ta son, \(a_1, a_2, ..., a_n (-10^9 \leq a_i \leq 10^9)\).
Yagona qatorda 2 ta son chop eting: massivning maksimal summasi va minimal operatsiyalar soni
| # | input.txt | output.txt |
|---|---|---|
| 1 |
6 -1 7 -5 -2 6 -8 |
29 3 |
| 2 |
5 2 -2 0 -4 -7 |
15 1 |
Birinchi testda massiv \([-1, 7, -5, -2, 6, -8] \) ko'rinishida. Birinchi operatsiyada \(l = 1\) va \(r = 1\) oraliqni tepadagi operatsiya bajarilsa massiv \([1, 7, -5, -2, 6, -8]\) holatiga keladi. Keyin \(l = 3\) va \(r = 5\) uchun operatsiya bajarilsa massiv \([1, 7, 5, 2, 6, -8]\) ko'rinishida bo'ladi. Va ohirida \(l = 6\) va \(r = 6\) uchun operatsiya bajarilganda massiv \([1, 7, 5, 2, 6, 8]\) ga teng bo'ladi. Bu massivning summasi 29 ga teng va 3 ta operatsiya bilan bu ishni bajardik.
Telegram kanalimizga obuna bo'ling