← 返回题目列表

AtCoder · awc0068_e

E. 选择拍照地点

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

分数: 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