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

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

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

int main(){
	freopen("zfx.in","r",stdin);
	freopen("zfx.out","w",stdout);	
    ios::sync_with_stdio(0);cin.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;
}