Розбиття на k підмасивів#9020
Дано масив з елементів і число . Розбийте цей масив на підмасивів, використовуючи всі елементи початкового масиву (порядок елементів зберігається, кожен елемент повинен входити рівно в один підмасив).
Для кожного розбиття вираховується максимум сум елементів усіх підмасивів. Необхідно провести розбиття так, щоб цей максимум виявився найменшим можливим. Знайдіть це мінімально можливе значення.
Перша стрічка містить два цілих числа і k~(1 \le k \le n \le 10^6).
Друга стрічка містить натуральних чисел — елементи масиву. Кожне число не перевищує 10^9.
Виведіть найменше можливе значення максимальної суми серед усіх допустимих розбиттів масиву на підмасивів.
Для першого прикладу оптимальним розбиттям буде \{1, 2\}, \{3\}, \{4\}. Суми підмасивів: , , . Максимум серед них — , і це найменше можливе значення для k = 3.
Для другого прикладу оптимальним розбиттям буде \{1, 2, 3, 4\}, \{2, 3, 4\}, \{2, 3, 1\}. Суми підмасивів: , , . Максимум рівний — це найменше можливе значення для k = 3.
Приклад 1
Приклад 2