← 返回题目列表

Codeforces · 173/C

C. 螺旋最大值

中文机器翻译题面 查看原题

让我们考虑一个 k × k 的正方形,分为单位正方形。请注意 k ≥ 3 并且为奇数。我们将从左上角的方块开始按以下顺序绘制方块:首先向右移动,然后向下,然后向左,然后向上,然后再次向右,依此类推。在以下两种情况之一中,我们完成了向某个方向的移动:要么我们已经到达了正方形的边界,要么已经到达了下一个正方形之后的下一个正方形。当我们无法向任何方向移动的时候,我们就完成了绘画,画了一个正方形。由所画的正方形组成的图形是一个螺旋线。

该图显示了 k = 3, 5, 7, 9 的螺旋示例。

你有一个 n × m 的表,它的每个单元格都包含一个数字。让我们考虑由表格单元格形成的所有可能的螺旋。这意味着我们考虑所有不超出表格边界的任何尺寸的螺旋。让我们求出形成螺旋的细胞数的总和。您必须找到所有螺旋中这些值的最大值。

输入

第一行包含两个整数 n 和 m (3 ≤ n, m ≤ 500) — 表的大小。

接下来的 n 行每行包含 m 个空格分隔的整数:第 i 行中的第 j 个数字 aij (- 1000 ≤ aij ≤ 1000) 是表格第 i 行第 j 个单元格中记录的数字。

输出

打印单个数字 — 所有螺旋中数字的最大总和。

示例

输入 #1

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

输出 #1

17

输入 #2

3 3
1 1 1
1 0 0
1 1 1

输出 #2

6

输入 #3

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

输出 #3

13

注意

在第一个示例中,具有最大和的螺旋将覆盖表中的所有 1。

在第二个示例中,螺旋可能仅覆盖六个 1。