Описание задачи
В сетке W×H нужно выкупить вертикальную полосу (от верха до низа) любой ширины, чтобы её
сумма была максимально близка к заданной P.
Типы запросов
? P— найти полосу с суммой ближе всего к P[x, y] = a— изменить цену клетки (x, y) на a
Формат входных данных
> Map:
cols rows
v11 v12 v13
v21 v22 v23
> Query:
? P
Формат выходных данных
Options: K
* start_col -> end_col: sum
Пример
Карта 3×2
> Map:
3 2
1 2 1
2 1 2
Query: ? 3
Options: 3
* 0 -> 0: 3
* 1 -> 1: 3
* 2 -> 2: 3
Колонка 0: 1+2=3. Колонка 1: 2+1=3. Колонка 2: 1+2=3.
Query: ? 6
Options: 2
* 0 -> 1: 6
* 1 -> 2: 6
Колонки 0-1: 3+3=6. Колонки 1-2: 3+3=6.
Ключевые моменты
- Суммы столбцов можно предвычислить
- Перебор всех диапазонов [i, j]: O(W²)
- Префиксные суммы для быстрого подсчёта