Проект нового города предполагает застройку в виде решетки размером $$$n \times m$$$ клеток. На пересечении $$$i$$$-й строки и $$$j$$$-го столбца будет располагаться дом на $$$t_{i,j}$$$ жильцов.
Три дома в клетках $$$(i, j)$$$, $$$(i + a, j)$$$ и $$$(i, j + b)$$$ образуют хороший треугольник, подходящий для линии общественного транспорта, если:
Вы можете изменить план застройки, увеличив или уменьшив все $$$t_{i,j}$$$ на одно и то же целое число $$$d$$$. Если $$$t_{i,j}$$$ при этом должно опуститься ниже нуля, считайте его равным нулю. Обозначим за $$$T + d$$$ матрицу значений $$$t_{i,j} + d$$$, а за $$$\triangle(T + d)$$$ — количество хороших треугольников при застройке города соответствующим образом.
Найдите $$$$$$\sum\limits_{d=-\infty}^{+\infty} \triangle(T + d) \text{,}$$$$$$ или, иными словами — суммарное количество хороших треугольников по всем возможным планам застройки.
В первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$m$$$ — количество строк и столбцов решетки, соответственно ($$$1 \le n, m \le 1000$$$).
В $$$i$$$-й из следующих $$$n$$$ строк перечислены $$$m$$$ целых чисел $$$t_{i,j}$$$ — количество этажей в каждом доме $$$i$$$-й строки решетки ($$$1 \le t_{i,j} \le 10^9$$$).
Выведите единственное целое число — количество троек клеток, удовлетворяющих поставленным условиям.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи |
| 0 | – | примеры из условия | |
| 1 | 8 | $$$t_{i,j} \le 2$$$ для всех $$$i$$$, $$$j$$$ | |
| 2 | 13 | $$$n \le 2$$$ | |
| 3 | 17 | $$$n, m \le 50$$$, $$$t_{i,j} \le 50$$$ | 0 |
| 4 | 17 | $$$n, m \le 500$$$ | 0, 3 |
| 5 | 20 | $$$t_{i,j}$$$ сгенерированы случайно и равномерно | 0 |
| 6 | 25 | нет | 0 – 5 |
3 33 1 11 2 11 1 1
2
2 45 4 3 24 3 2 1
6
В этой задаче большой размер входных данных, поэтому может быть полезно использовать ускоренный ввод и вывод.
| Innopolis Open 2024. Отборочный этап 2 |
|---|
| Закончено |
