Грузовики по кварталам: минимизируй худший рейс

В городе вдоль одной длинной улицы подряд стоят n кварталов. Сегодня надо развезти коробки: в i-м квартале ждут a[i] коробок.

Диспетчер делит улицу на k подряд идущих участков (каждый участок — непустой отрезок кварталов). Один грузовик обслуживает ровно один участок и везёт суммарно все коробки с кварталов этого участка.

Диспетчер хочет, чтобы самый тяжёлый рейс (по числу коробок) был как можно легче.

Найди минимально возможное значение максимальной суммы на участке.

Важно: суммы могут не помещаться в 32-битный тип (как на ВсОШ). В Python это не проблема.

Формат ввода

В первой строке два целых числа n и k. Во второй строке n целых чисел a1, a2, ..., an.

Формат вывода

Выведи одно целое число — минимально возможную максимальную сумму коробок на одном участке.

Ограничения

• 2 ≤ n ≤ 8000
• 1 ≤ k ≤ n
• 1 ≤ ai ≤ 1 000 000
• Ответ может требовать 64-битные целые.

Пример

Ввод:

5 2
7 2 5 10 8

Вывод:

18

Пояснение: можно разделить как (7+2+5)=14 и (10+8)=18, тогда самый тяжёлый рейс равен 18, и меньше уже не получится.

Ключевое наблюдение: если мы фиксируем число X — максимальную допустимую сумму на одном участке, то можно быстро понять, реально ли разбить кварталы на участки так, чтобы сумма каждого была ≤ X. Причём это свойство монотонно: если получилось для X, то получится и для любого большего X. Значит, можно делать бинарный поиск по ответу.

Почему работает жадная проверка: чтобы уложиться в как можно меньше участков при заданном X, выгодно тянуть текущий участок максимально вправо, пока не переполнится. Тогда число участков будет минимальным из возможных — если даже так участков больше k, то никакое другое разбиение не спасёт.

План решения:

• Задай границы поиска:
• lo = max(a) (меньше нельзя: какой-то квартал не влезет).
• hi = sum(a) (точно можно: один участок на всё).
• Функция can(X):
• Идём слева направо, накапливаем сумму cur.
• Если cur + a[i] > X, начинаем новый участок (счётчик parts += 1, cur = a[i]).
• Если parts > k, сразу False, иначе в конце True.
• Мини-сниппет перехода: if cur + x <= X: cur += x else: parts += 1; cur = x.
• Бинарным поиском сужай [lo, hi] по ответу: если can(mid) — двигаем hi = mid, иначе lo = mid + 1.

Сложность: проверка can(X) за O(n), бинарный поиск делает около log(sum(a)) шагов, итого O(n log sum(a)).

Частая ошибка: требовать «ровно k участков». Нужно «не больше k»: если уложились в меньшее число, всегда можно дорезать участки (все a[i] > 0), не увеличивая максимальную сумму.