Description：

给一个 $n\times m$ 的网格，每个位置有权值，从中选出 $3$ 个不相交的大小为 $k\times k$ 的正方形，最大化权值和。

$1\leqslant n,m\leqslant1500$

Solution：

把一个矩形分成三部分，最多只有以下六种可能。

于是求出以每个点为左上角 $/$ 左下角 $/$ 右上角 $/$ 右下角的 $k\times k$ 的矩形的最大值，这个可以用二维前缀最大值来 $O(n^2)$ 求，还要预处理某条线右边 $/$ 左边选一个 $k\times k$ 的矩形的最大值，然后暴枚边界线即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m,k;

#define MAXN 1510

int val[MAXN][MAXN];

int s[MAXN][MAXN];

int lu[MAXN][MAXN],ld[MAXN][MAXN],ru[MAXN][MAXN],rd[MAXN][MAXN];

int main()

{

	scanf("%d%d%d",&n,&m,&k);

	for(int i = 1;i <= n;++i)for(int j = 1;j <= m;++j)scanf("%d",&val[i][j]);

	for(int i = 1;i <= n;++i)for(int j = 1;j <= m;++j)s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + val[i][j];

	for(int i = n;i >= k;--i)for(int j = m;j >= k;--j)s[i][j] = s[i][j] - s[i - k][j] - s[i][j - k] + s[i - k][j - k];

	for(int i = k;i <= n;++i)for(int j = k;j <= m;++j)lu[i][j] = max(s[i][j],max(lu[i - 1][j],lu[i][j - 1]));

	for(int i = n;i >= k;--i)for(int j = k;j <= m;++j)ld[i][j] = max(s[i][j],max(ld[i + 1][j],ld[i][j - 1]));

	for(int i = k;i <= n;++i)for(int j = m;j >= k;--j)ru[i][j] = max(s[i][j],max(ru[i - 1][j],ru[i][j + 1]));

	for(int i = n;i >= k;--i)for(int j = m;j >= k;--j)rd[i][j] = max(s[i][j],max(rd[i + 1][j],rd[i][j + 1]));

	int ans = 0;

	for(int i = k;i <= n - k;++i)for(int j = k;j <= m - k;++j)ans = max(ans,lu[i][j] + ru[i][j + k] + ld[i + k][m]);

	for(int i = k;i <= n - k;++i)for(int j = k + k;j <= m;++j)ans = max(ans,ru[i][j] + rd[i + k][j] + lu[n][j - k]);

	for(int i = k + k;i <= n;++i)for(int j = k;j <= m - k;++j)ans = max(ans,ld[i][j] + rd[i][j + k] + lu[i - k][m]);

	for(int i = k;i <= n - k;++i)for(int j = k;j <= m - k;++j)ans = max(ans,lu[i][j] + ld[i + k][j] + ru[n][j + k]);

	for(int i = k + k;i <= n - k;++i)for(int j = k;j <= m;++j)ans = max(ans,s[i][j] + lu[i - k][m] + ld[i + k][m]);

	for(int i = k;i <= n;++i)for(int j = k + k;j <= m - k;++j)ans = max(ans,s[i][j] + lu[n][j - k] + ru[n][j + k]);

	cout << ans << endl;

	return 0;

}