AT_abc347_f [ABC347F] Non-overlapping Squares

题目描述

有一个 $N\times N$ 的网格，在第 $i$ 行第 $j$ 列（$1\leq i,j\leq N$）的格子上写有整数 $A_{i,j}$。

给定整数 $M$。请从网格中选择 $3$ 个互不重叠的 $M\times M$ 的子矩阵，使得所选子矩阵内所有整数之和的最大值尽可能大。

问题的严格定义
当整数 $6$ 元组 $(i_1, j_1, i_2, j_2, i_3, j_3)$ 满足以下 $3$ 个条件时，称其为“好 $6$ 元组”：

• $1\leq i_k\leq N-M+1\ (k=1,2,3)$
• $1\leq j_k\leq N-M+1\ (k=1,2,3)$
• 对于 $k\neq l\ (k,l\in\{1,2,3\})$，集合 $\{(i,j)\mid i_k\leq i<i_k+M,\ j_k\leq j<j_k+M\}$ 与 $\{(i,j)\mid i_l\leq i<i_l+M,\ j_l\leq j<j_l+M\}$ 没有交集

对于每个好 $6$ 元组 $(i_1, j_1, i_2, j_2, i_3, j_3)$，其对应的值为

$$\sum_{k=1}^{3} \sum_{i=i_k}^{i_k+M-1} \sum_{j=j_k}^{j_k+M-1} A_{i,j}$$

请你求出所有好 $6$ 元组中上述值的最大值。在本题的约束下，保证一定存在好 $6$ 元组。

输入格式

输入以如下格式从标准输入读入：

$N$ $M$
$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}$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

7 3
3 1 4 1 5 9 2
6 5 3 5 8 9 7
9 3 2 3 8 4 6
2 6 4 3 3 8 3
2 7 9 5 0 2 8
8 4 1 9 7 1 6
9 3 9 9 3 7 5

输出 #1

154

输入输出样例 #2

输入 #2

7 1
3 1 4 1 5 9 2
6 5 3 5 8 9 7
9 3 2 3 8 4 6
2 6 4 3 3 8 3
2 7 9 5 0 2 8
8 4 1 9 7 1 6
9 3 9 9 3 7 5

输出 #2

27

输入输出样例 #3

输入 #3

16 4
74 16 58 32 97 52 43 51 40 58 13 24 65 11 63 29
98 75 40 77 15 50 83 85 35 46 38 37 56 38 63 55
95 42 10 70 53 40 25 10 70 32 33 19 52 79 74 58
33 91 53 11 65 63 78 77 81 46 81 63 11 82 55 62
39 95 92 69 77 89 14 84 53 78 71 81 66 39 96 29
74 26 60 55 89 35 32 64 17 26 74 92 84 33 59 82
23 69 10 95 94 14 58 58 97 95 62 58 72 55 71 43
93 77 27 87 74 72 91 37 53 80 51 71 37 35 97 46
81 88 26 79 78 30 53 68 83 28 59 28 74 55 20 86
93 13 25 19 53 53 17 24 69 14 67 81 10 19 69 90
88 83 62 92 22 31 27 34 67 48 42 32 68 14 96 87
44 69 25 48 68 42 53 82 44 42 96 31 13 56 68 83
63 87 24 75 16 70 63 99 95 10 63 26 56 12 77 49
94 83 69 95 48 41 40 97 45 61 26 38 83 91 44 31
43 69 54 64 20 60 17 15 62 25 58 50 59 63 88 70
72 95 21 28 41 14 77 22 64 78 33 55 67 51 78 40

输出 #3

3295

说明/提示

数据范围

• $2\leq N\leq 1000$
• $1\leq M\leq N/2$
• $0\leq A_{i,j}\leq 10^9$
• 输入均为整数

样例解释 1

从给定的网格中，选择如下图所示的 $3\times3$ 的子矩阵 $3$ 个（对应 $(i_1, j_1, i_2, j_2, i_3, j_3)=(1,5,2,1,5,2)$），所选格子内的数之和为 $154$。

不存在满足题意且和大于等于 $155$ 的选法，因此输出 $154$。

样例解释 2

如下图所示的选法最优。

样例解释 3

如下图所示的选法最优。

由 ChatGPT 4.1 翻译