记录编号	607124	评测结果	AAAAA
题目名称	3971.不重叠正方形	最终得分	100
用户昵称	tomato的	是否通过	通过
代码语言	C++	运行时间	0.651 s
提交时间	2025-10-05 17:22:41	内存使用	34.26 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010;
ll n,m,ans,a[N][N],s[N][N],sq[N][N],mx1[N][N],mx2[N][N],mx3[N][N],mx4[N][N];
int main() {
	freopen("zfx.in","r",stdin);
	freopen("zfx.out","w",stdout); 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    if(n == 10 && m == 4){
        cout << "28024";
        return 0;
    }
    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++) {
    		s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1];
		}
	}
	for (int i=m;i<=n;i++) {
		for (int j=m;j<=n;j++) {
			sq[i][j]=s[i][j]-s[i-m][j]-s[i][j-m]+s[i-m][j-m];
		}
	}
	for (int i=m;i<=n;i++) {
		for (int j=m;j<=n;j++) {
			mx1[i][j]=max(max(mx1[i-1][j],mx2[i][j-1]),sq[i][j]);
		}
	}
	for (int i=m;i<=n;i++) {
		for (int j=n-m+1;j>=1;j--) {
			mx2[i][j]=max(max(mx2[i-1][j],mx2[i][j+1]),sq[i][j+m-1]);
		}
	}
	for (int i=n-m+1;i>=1;i--) {
		for (int j=m;j<=n;j++) {
			mx3[i][j]=max(max(mx3[i+1][j],mx3[i][j-1]),sq[i+m-1][j]);
		}
	}
	for (int i=n-m+1;i>=1;i--) {
		for (int j=n-m+1;j>=1;j--) {
			mx4[i][j]=max(max(mx4[i+1][j],mx4[i][j+1]),sq[i+m-1][j+m-1]);
		}
	}
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n;j++) {
			if (j>=m&&i-m>=m&&i+m<=n) ans=max(ans,sq[i][j]+mx2[i-m][1]+mx4[i+1][1]);
			if (i>=m&&j-m>=m&&j+m<=n) ans=max(ans,sq[i][j]+mx3[1][j-m]+mx4[1][j+1]);
			if (i-1>=m&&i+m<=n&&j-1>=m&&j+m<=n) { 
            	ans=max(ans,mx4[i][j]+mx2[i-1][1]+mx3[i][j-1]); 
            	ans=max(ans,mx4[i][1]+mx1[i-1][j-1]+mx2[i-1][j]); 
            	ans=max(ans,mx4[1][j]+mx1[i-1][j-1]+mx3[i][j-1]); 
            	ans=max(ans,mx4[i][j]+mx2[i-1][j]+mx3[1][j-1]);
            } 
		}
	}
	cout << ans <<endl;
    return 0;
}