Описание задачи
Мы владеем клеткой (x, y). Нужно докупить прямоугольник W×H, содержащий эту
клетку, с минимальной стоимостью новых клеток.
Формат входных данных
cols rows
v11 v12 ...
v21 v22 ...
...
Query: x y width height
Логика
- Перебираем положения левого верхнего угла, покрывающие (x, y)
- Стоимость докупки = сумма(прямоугольник) - grid[y][x]
- Ищем минимум
Примеры
Сетка 3×4
3 4
1 2 3
4 5 6
7 8 9
1 2 3
Query: 1 1 2 2
Price: 7
* (0,0)
Прямоугольник в (0,0): [1,2,4,5] = 12. Минус своя клетка (5) = 7.
Query: 1 1 5 5
Does not exist.
Ключевые моменты
- Условие покрытия:
lx ≤ x < lx + Wиly ≤ y < ly + H - Используйте префиксные суммы