分数: 466 分
问题陈述
高桥正在计划通过选择单张照片进行摄影之旅 K \times K 观光区域的方形区域表示为 N \times N 网格。该单元格位于 i从顶部开始的第行和 j左数第 列的风景得分为 A_{i,j}.
这里,一个 K \times K 区域是指所有 K \times K 行中的单元格 r 到行 r+K-1 和来自专栏 c 转至专栏 c+K-1,其中整数 r, c 的选择使得 1 \leq r \leq N-K+1 和 1 \leq c \leq N-K+1.
青木经营着一家竞争对手的旅游公司,他知道高桥选择了哪个区域,然后精确地选择该区域内的一个单元格,将其风景得分更改为 0 (所有其他单元格的风景分数保持不变)。 Aoki 必须执行此操作,并且可以选择分数已经为的单元格 0。青木选择的单元格是为了使操作后区域内的风景总得分最小。
风景总分 青木手术后区域内的 K \times K 细胞被称为 满意。高桥考虑到青木的破坏,选择了满意度最大化的区域。求满意度的最大值。
约束
- 1 \leq K \leq N \leq 1000
- 0 \leq A_{i,j} \leq 10^9
- 所有输入值均为整数。
输入
输入按以下格式给出:
N K
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
- 第一行包含两个用空格分隔的整数: N,区域的边长,以及 K,所选正方形的边长。
- 以下各项 N 行,其中 i- 第行 (1 \leq i \leq N),包含 N 整数 A_{i,1}, A_{i,2}, \ldots, A_{i,N} 以空格分隔。 A_{i,j} 代表该单元格中的风景得分 i从顶部开始的第行和 j左起第 列。
输出
打印,作为一行上的单个整数,当青木进行最佳破坏时,高桥可以达到的最大满意度。
样本输入 1
3 2 1 2 3 4 5 6 7 8 9
示例输出 1
19
示例输入 2
4 4 0 2 5 1 4 0 3 6 7 8 0 2 1 9 4 0
示例输出 2
43
示例输入 3
5 3 8 1 6 2 9 3 5 7 4 1 9 2 4 8 3 6 0 5 7 2 1 8 3 9 4
示例输出 3
37
示例输入 4
8 4 12 7 3 15 8 6 14 2 9 11 5 4 13 10 1 16 6 14 2 12 7 15 3 8 10 1 16 9 5 11 4 13 8 13 7 3 14 2 12 6 4 15 10 1 16 9 5 11 14 2 12 6 8 13 7 3 5 11 4 16 10 1 15 9
示例输出 4
132
示例输入 5
1 1 1000000000
示例输出 5
0