Masala #YDAXIPWHMQ

Xotira 64 MB Vaqt 2000 ms Qiyinchiligi 8 %

3.0 (Baholar 3)

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.

Kiruvchi ma'lumotlar:

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)$ .

Chiquvchi ma'lumotlar:

Yagona qatorda 2 ta son chop eting: massivning maksimal summasi va minimal operatsiyalar soni

Misollar

#	input.txt	output.txt
1	6 -1 7 -5 -2 6 -8	29 3
2	5 2 -2 0 -4 -7	15 1

Izoh:

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 Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin