Единственное отличие усложненной и упрощенной версии это ограничение на \(k\).
Гильдонг любит наблюдать за животными, так он купил две камеры чтобы снимать на видео диких животных в лесу. Цвет одной камеры красный, а цвет другой камеры синий.
Гильдонг собирается снимать видео на протяжении \(n\) дней, с дня \(1\) по день \(n\). Лес разделен на \(m\) зон, пронумерованных от \(1\) до \(m\). Он будет использовать камеры следующим образом:
- На каждый нечетный день (\(1\)-й, \(3\)-й, \(5\)-й, ...), принести красную камеру в лес и записывать видео \(2\) дня.
- На каждый четный день (\(2\)-й, \(4\)-й, \(6\)-й, ...), принести синюю камеру в лес и записывать видео \(2\) дня.
- Если он начнет записывать на \(n\)-й день на одну из камер, камера будет записывать только один день.
Каждая камера снимает \(k\) последовательных зон леса. Например, если \(m=5\) и \(k=3\), он может поставить камеру чтобы наблюдать за одним из этих трех отрезков два дня: \([1,3]\), \([2,4]\), и \([3,5]\).
Гильдонг получил информацию о том, сколько животных видно в каждой зоне каждый день. Так как он хочет наблюдать за как можно большим числом животных, он хочет попросить вас найти лучший способ расставить эти две камеры в \(n\) дней. Обратите внимание, что если две камеры снимают одну и ту же зону в один и тот же день, все животные этой зоны должны быть учтены только один раз.