Бригады и кварталы

В городе начали ремонтировать главную улицу. Улица состоит из n подряд идущих кварталов, и для каждого квартала известна «сложность ремонта» — положительное число.

Мэр хочет распределить работу между ровно k бригадами. Каждая бригада берёт один непрерывный кусок кварталов (то есть кварталы каждой бригады идут подряд), и все кварталы должны быть разобраны без пропусков.

Нагрузка бригады — сумма сложностей кварталов, которые ей достались. Мэр хочет сделать так, чтобы самая загруженная бригада была как можно менее загруженной.

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

Важно: суммы могут не помещаться в 32-битный тип (как на олимпиадах), используйте 64-битные целые. В Python это не проблема.

Формат ввода

• В первой строке: два целых числа n и k (1 ≤ k ≤ n ≤ 3000).
• Во второй строке: n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 1000000).

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

Ограничения

• 1 ≤ k ≤ n ≤ 3000
• 1 ≤ ai ≤ 1000000
• Время: 1 секунда, память: 256 МБ.

Пример Ввод:

5 2
7 2 5 10 8

Вывод:

18

Пояснение: можно разделить как [7,2,5] и [10,8]. Максимум из сумм равен max(14, 18) = 18, и лучше сделать нельзя.

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

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

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

• Поставьте границы поиска: lo = max(a) (меньше нельзя, один квартал обязан влезть) и hi = sum(a) (все кварталы одной бригаде).
• Для середины mid проверьте, сколько отрезков нужно при ограничении суммы <= mid:
• идите по массиву, накапливайте сумму;
• если s + a[i] > mid, начинайте новый отрезок.
• если встретили a[i] > mid, сразу «нельзя».
• Если получилось сделать <= k отрезков, то ответ <= mid (можно добавить разрезы и получить ровно k, так как все ai > 0 и k <= n).
• Иначе ответ > mid.

Мини-сниппет проверки перехода: if s + x > mid: cnt += 1; s = x

Сложность: проверка O(n), бинарный поиск по сумме даёт O(n * log(sum a)) — проходит при n до 3000.

Частая ошибка: проверять «ровно k» отрезков. Нужно «не больше k»: лишние разрезы всегда можно добавить внутри отрезка.