e-olymp
Məsələlər

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

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

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

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

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

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

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

Пояснение

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4 3
1 2 3 4
Çıxış verilənləri #1
4
Giriş verilənləri #2
10 3
1 2 3 4 2 3 4 2 3 1
Çıxış verilənləri #2
10