Контест Middle Бинарный поиск обновлено
Разделить главы между редакторами
Условие
Книга состоит из n глав, в i-й главе aᵢ страниц. Главы нужно раздать k редакторам: каждому достаётся непрерывный отрезок глав (возможно, пустой), порядок глав сохраняется, каждая глава ровно у одного редактора. Все работают параллельно, время работы = число страниц у самого загруженного. Найдите минимально возможное время.
Ввод: в первой строке n и k (1 ≤ k ≤ n ≤ 2500), во второй n чисел (0 ≤ aᵢ ≤ 10⁹).
Вывод: минимальная возможная максимальная нагрузка.
Пример 1
Ввод:
5 2
7 2 5 10 8
Вывод:
18
Пример 2
Ввод:
3 3
1 2 3
Вывод:
3
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.