Описание задачи
Дана сетка чисел (стоимости участков). Найти квадратный участок размера S×S с минимальной
суммой.
Формат входных данных
cols rows
v11 v12 v13
v21 v22 v23
...
Query: S
Формат выходных данных
Price: минимальная_сумма
* (x1, y1)
* (x2, y2)
Если квадрат не помещается — Does not exist.
Примеры
Сетка 3×4
3 4
1 2 3
4 5 6
7 8 9
1 2 3
Query: 2
Price: 12
* (0,0)
Query: 3
Price: 45
* (0,0)
* (0,1)
Query: 10
Does not exist.
Ключевые моменты
- Координаты: x — горизонталь, y — вертикаль, (0,0) — левый верхний
- Оптимизация: префиксные суммы для O(1) подсчёта