记录编号	607132	评测结果	AAAAA
题目名称	3971.不重叠正方形	最终得分	100
用户昵称	梦那边的美好ME	是否通过	通过
代码语言	C++	运行时间	0.687 s
提交时间	2025-10-05 17:34:36	内存使用	42.56 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll n,m,a[2000][2000];
ll pre[2000][2000],sum[2000][2000];
ll tl[2000][2000],tr[2000][2000],bl[2000][2000],br[2000][2000];

int main(){
//	freopen("in.in","r",stdin);
	freopen("zfx.in","r",stdin);
	freopen("zfx.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			pre[i][j]=pre[i-1][j]+pre[i][j-1]+a[i][j]-pre[i-1][j-1];
		}
	}
	for (int i=m;i<=n;i++){
		for (int j=m;j<=n;j++){
			sum[i][j]=pre[i][j]-pre[i-m][j]-pre[i][j-m]+pre[i-m][j-m];
		}
	}
	for (int i=m;i<=n;i++){
		for (int j=m;j<=n;j++){
			tl[i][j]=max({tl[i][j-1],tl[i-1][j],sum[i][j]});
		}
	}
	for (int i=m;i<=n;i++){
		for (int j=n-m+1;j>=1;j--){
			tr[i][j]=max({tr[i][j+1],tr[i-1][j],sum[i][j+m-1]});
		}
	}
	for (int i=n-m+1;i>=1;i--){
		for (int j=m;j<=n;j++){
			bl[i][j]=max({bl[i+1][j],bl[i][j-1],sum[i+m-1][j]});
		}
	}
	for (int i=n-m+1;i>=1;i--){
		for (int j=n-m+1;j>=1;j--){
			br[i][j]=max({br[i+1][j],br[i][j+1],sum[i+m-1][j+m-1]});
		}
	}
	ll ans=0;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			if (i-m>=m&&i+m<=n&&j>=m) ans=max(ans,sum[i][j]+tr[i-m][1]+br[i+1][1]);
			if (i>=m&&j-m>=m&&j+m-1<=n) ans=max(ans,sum[i][j]+bl[1][j-m]+br[1][j+1]);
			if (i-1>=m&&i+m-1<=n&&j-1>=m&&j+m-1<=n){
				ans=max(ans,br[i][j]+bl[i][j-1]+tr[i-1][1]);
				ans=max(ans,br[i][1]+tl[i-1][j-1]+tr[i-1][j]);
				ans=max(ans,br[1][j]+tl[i-1][j-1]+bl[i][j-1]);
				ans=max(ans,br[i][j]+bl[1][j-1]+tr[i-1][j]);
			}
		}
	}
	cout<<ans<<'\n';
	return 0;
}