e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Задачі

Разбиение на k подмассивов

Разбиение на k подмассивов

Задан массив из n элементов и число k. Разбейте заданный массив на k подмассивов (которые содержат в себе все элементы). Вычислим максимум среди сумм элементов всех k подмассивов. Разбиение следует провести так, чтобы это значение было как можно меньшим. Найдите этот максимум.

Входные данные

Первая строка содержит два числа n и k (n106, 1kn). Вторая строка содержит n натуральных чисел, каждое из которых не более 109.

Выходные данные

Выведите наименьшее возможное значение среди максимумов сумм элементов всех k подмассивов.

prb9020.gif

Пояснение

Для первого примера оптимальным разбиением будет {1, 2}, {3}, {4}. Максимум сумм элементов среди всех подмассивов равен 4, который является наименьшим возможным для 3 подмассивов.

Для второго примера оптимальным разбиением будет {1, 2, 3, 4}, {2, 3, 4}, {2, 3, 1}. Максимум сумм элементов среди всех подмассивов равен 10, который является наименьшим возможным для 3 подмассивов.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4 3
1 2 3 4
Вихідні дані #1
4
Вхідні дані #2
10 3
1 2 3 4 2 3 4 2 3 1
Вихідні дані #2
10