Məsələlər
Разбиение на k подмассивов
Разбиение на k подмассивов
Задан массив из $n$ элементов и число $k$. Разбейте заданный массив на $k$ подмассивов (которые содержат в себе все элементы). Вычислим максимум среди сумм элементов всех $k$ подмассивов. Разбиение следует провести так, чтобы это значение было как можно меньшим. Найдите этот максимум.
\InputFile
Первая строка содержит два числа $n$ и $k~(n \le 10^6, 1 \le k \le n)$. Вторая строка содержит $n$ натуральных чисел, каждое из которых не более $10^9$.
\OutputFile
Выведите наименьшее возможное значение среди максимумов сумм элементов всех $k$ подмассивов.
\includegraphics{https://static.e-olymp.com/content/fa/fa4249eaba38a60e358e745a9a784883ce10a68c.gif}
\Example
Для первого примера оптимальным разбиением будет $\{1, 2\}, \{3\}, \{4\}$. Максимум сумм элементов среди всех подмассивов равен $4$, который является наименьшим возможным для $3$ подмассивов.
Для второго примера оптимальным разбиением будет $\{1, 2, 3, 4\}, \{2, 3, 4\}, \{2, 3, 1\}$. Максимум сумм элементов среди всех подмассивов равен $10$, который является наименьшим возможным для $3$ подмассивов.
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