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

#include<bits/stdc++.h>
#define int long long
#define N 1145
#define bianli for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
using namespace std;
int n,m,a[N][N],ans;
int pre[N][N],sum[N][N],tl[N][N],tr[N][N],bl[N][N],br[N][N];
signed main(){
    freopen("zfx.in","r",stdin);freopen("zfx.out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    bianli cin>>a[i][j];
    bianli 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]});
    bianli{
        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][j]+bl[1][j-1]+tr[i-1][j]);
            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]);
        } 
    } 
    cout<<ans;
    return 0;
}