Masala #O1MEEOTYIG
Maksimal yig‘indini minimal qilish
Sizga n ta musbat butun sonlardan tashkil topgan massiv berilgan. Siz ushbu massivni uzluksiz bo‘laklarga bo‘lib, kamida 1 va maksimal k ta bo‘lakga ajratishingiz mumkin. Maqsad — bo‘laklar orasidagi eng katta yig‘indini imkon qadar kichraytirish. Boshqacha aytganda, bo‘lish tartibini shunday tanlangki, har bir bo‘lakdagi elementlar yig‘indisi orasidan maksimal qiymat minimal bo‘lsin.
Birinchi qator: ikkita butun son n va k (1 ≤ n ≤ 2*10^5, 1 ≤ k ≤ n).
Ikkinchi qator: n ta ijobiy butun son a1 a2 ... an (1 ≤ ai ≤ 10^12) — massiv elementlari.
Bitta butun son — minimal mumkin bo‘lgan maksimal bo‘lak yig‘indisi.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
5 3 7 2 5 10 8 |
14 |
Eng yaxshi taqsimlash — [7,2,5], [10], [8] bo‘lib, bo‘lak yig‘indilari 14,10,8 va maksimal = 14. Kamroq bo‘laklarda maksimal katta bo‘ladi, ko‘p bo‘laklarda kamayadi; eng yaxshi natija 14
Telegram kanalimizga obuna bo'ling