103475: [Atcoder]ABC347 F - Non-overlapping Squares
Description
Score: $525$ points
Problem Statement
There is an $N\times N$ grid, and the cell at the $i$-th row from the top and the $j$-th column from the left $(1\leq i,j\leq N)$ contains the integer $A _ {i,j}$.
You are given an integer $M$. When choosing three non-overlapping $M\times M$ grids, find the maximum possible sum of the integers written in the chosen grids.
Formal definition of the problem
A $6$-tuple of integers $(i _ 1,j _ 1,i _ 2,j _ 2,i _ 3,j _ 3)$ is called a good $6$-tuple when it satisfies the following three conditions:- $1\leq i _ k\leq N-M+1\ (k=1,2,3)$
- $1\leq j _ k\leq N-M+1\ (k=1,2,3)$
- If $k\neq l\ (k,l\in\lbrace1,2,3\rbrace)$, the sets $\lbrace(i,j)\mid i _ k\leq i\lt i _ k+M\wedge j _ k\leq j\lt j _ k+M\rbrace$ and $\lbrace(i,j)\mid i _ l\leq i\lt i _ l+M\wedge j _ l\leq j\lt j _ l+M\rbrace$ do not intersect.
Constraints
- $2\leq N\leq 1000$
- $1\leq M\leq N/2$
- $0\leq A _ {i,j}\leq10 ^ 9$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$
$A _ {1,1}$ $A _ {1,2}$ $\ldots$ $A _ {1,N}$
$A _ {2,1}$ $A _ {2,2}$ $\ldots$ $A _ {2,N}$
$\vdots$ $\ \vdots$ $\ddots$ $\vdots$
$A _ {N,1}$ $A _ {N,2}$ $\ldots$ $A _ {N,N}$
Output
Print the answer.
Sample Input 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
Sample Output 1
154
From the given grid, if we choose three $3\times3$ grids as shown in the figure below (this corresponds to setting $(i _ 1,j _ 1,i _ 2,j _ 2,i _ 3,j _ 3)=(1,5,2,1,5,2)$), the sum of the numbers written in the chosen grids will be $154$.
There is no way to make the sum $155$ or greater while satisfying the conditions in the problem statement, so print $154$.
Sample Input 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
Sample Output 2
27
The following choice is optimal.
Sample Input 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
Sample Output 3
3295
The following choice is optimal.
Input
Output
问题描述
有一个$N\times N$的网格，从上数第$i$行、从左数第$j$列的单元格里包含整数$A _ {i,j}$。
给你一个整数$M$。当选择三个不重叠的$M\times M$网格时，找出写在所选网格中的整数的最大可能和。
问题的正式定义
一个由整数$(i _ 1,j _ 1,i _ 2,j _ 2,i _ 3,j _ 3)$组成的$6$元组被称为一个好的$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\lbrace1,2,3\rbrace)$，则集合$\lbrace(i,j)\mid i _ k\leq i\lt i _ k+M\wedge j _ k\leq j\lt j _ k+M\rbrace$和$\lbrace(i,j)\mid i _ l\leq i\lt i _ l+M\wedge j _ l\leq j\lt j _ l+M\rbrace$不相交。
约束条件
- $2\leq N\leq 1000$
- $1\leq M\leq N/2$
- $0\leq A _ {i,j}\leq10 ^ 9$
- 所有的输入值都是整数。
输入
从标准输入按照以下格式给出输入：
$N$ $M$
$A _ {1,1}$ $A _ {1,2}$ $\ldots$ $A _ {1,N}$
$A _ {2,1}$ $A _ {2,2}$ $\ldots$ $A _ {2,N}$
$\vdots$ $\ \vdots$ $\ddots$ $\vdots$
$A _ {N,1}$ $A _ {N,2}$ $\ldots$ $A _ {N,N}$
输出
输出答案。
样例输入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
从给定的网格中，如果我们将三个$3\times3$的网格选择如图所示（这对应于设置$(i _ 1,j _ 1,i _ 2,j _ 2,i _ 3,j _ 3)=(1,5,2,1,5,2)$），则写在所选网格中的数字之和为$154$。
无法在满足问题描述中的条件的情况下使和达到$155$或更大，因此输出$154$。
样例输入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
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 4