| Чемпионат КРОК 2012 - Раунд 1 |
|---|
| Закончено |
Рассмотрим квадрат k × k, разделенный на единичные квадратики, причем k ≥ 3 и нечетно. Начиная от левой верхней клетки, будем красить клетки в следующем порядке: двигаемся сначала вправо, затем вниз, затем влево, затем вверх, затем опять вправо и так далее. При этом движение в одном направлении заканчиваем в одном из двух случаев: мы добрались до стенки квадрата, или следующая после следующей клетки уже покрашена. Всю покраску заканчиваем, если при движении в любом из направлений, не удается закрасить ни одной клетки. Фигуру, состоящую из закрашенных клеток, назовем спиралью.
Примеры спиралей для k = 3, 5, 7, 9 можно видеть на рисунке. Имеется таблица n × m, в каждой ячейке которой находится число. Рассмотрим всевозможные спирали, образованные ячейками таблицы. Это означает, что мы рассматриваем спирали всевозможных размеров, которые не выходят за границы таблицы. Для каждой из спиралей найдем сумму чисел ячеек, из которых она образована. От вас требуется найти максимум из всех этих значений среди всех спиралей.
В первой строке записаны два целых числа n и m (3 ≤ n, m ≤ 500) — размеры таблицы.
В следующих n строках записано по m целых чисел, разделенных пробелами: j-ое число в i-ой строке aij ( - 1000 ≤ aij ≤ 1000) — число, записанное в j-ой ячейке i-ой строки таблицы.
Выведите одно число — максимальную сумму чисел среди всех спиралей.
6 5
0 0 0 0 0
1 1 1 1 1
0 0 0 0 1
1 1 1 0 1
1 0 0 0 1
1 1 1 1 1
17
3 3
1 1 1
1 0 0
1 1 1
6
6 6
-3 2 0 1 5 -1
4 -1 2 -3 0 1
-5 1 2 4 1 -2
0 -2 1 3 -1 2
3 1 4 -3 -2 0
-1 2 -1 3 1 2
13
В первом тестовом примере спираль с максимальной суммой будет покрывать все единички таблицы.
Во втором примере спираль может покрыть только шесть единичек.
