Разделение массива с минимальной суммой
Дано
n целых чисел и целое число k. Нужно разбить массив на k смежных частей таким образом, чтобы максимальная сумма среди этих частей была как можно меньше.Входные данные
Первая строка входных данных содержит два целых числа
n (1 ≤ n ≤ ) и k (1 ≤ k ≤ n).В следующей строке заданы через пробел целые числа ( ≤ ≤ ).
Выходные данные
Необходимо вывести минимально возможное значение максимальной суммы среди выбранных подмассивов.
Примеры
Входные данные | Выходные данные |
5 2
1 2 3 6 2 | 8 |
5 3
1 2 10 3 2 | 10 |
Пояснение
[1 2 3] [6 2]⇒ максимальная сумма подмассива: 6 + 2 = 8
[1 2] [10] [3 2]⇒ максимальная сумма подмассива: 10
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB