values и числа parts и spread. Массив нужно разрезать ровно на parts непустых непрерывных частей, каждый элемент попадает ровно в одну часть. Стоимость части — её **первый** элемент, стоимость нарезки — сумма стоимостей частей.
Есть условие: начала частей не должны разъезжаться далеко. Если вторая часть начинается с индекса i₁, а последняя — с индекса iₖ₋₁, то должно выполняться iₖ₋₁ − i₁ ≤ spread.
Верните минимальную стоимость допустимой нарезки.values=[4, 9, 2, 7, 1, 8], parts=3, spread=2 → 7
Режем на [4, 9], [2, 7], [1, 8]: вторая часть начинается с индекса 2, третья — с 4, разница 2 ≤ spread. Стоимость 4 + 2 + 1 = 7.
values=[5, 1, 6, 6, 1], parts=3, spread=1 → 12
Обе единицы взять нельзя: их индексы 1 и 4 отличаются на 3 > 1. Лучшее — [5], [1], [6, 6, 1] или [5, 1, 6], [6], [1]: стоимость 5 + 1 + 6 = 12.
values=[3, 3, 3, 3], parts=4, spread=2 → 12
values) ≤ 10⁵values[i] ≤ 10⁹parts ≤ len(values)parts − 2 ≤ spread ≤ len(values) − 2values=[4, 9, 2, 7, 1, 8], parts=3, spread=2
7
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 184 теста на сервере, включая скрытые.