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

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1010;
int n,m,a[N][N];
ll pre[N][N],sum[N][N];
ll tl[N][N],tr[N][N],bl[N][N],br[N][N];
int main()
{
    freopen("zfx.in","r",stdin);
    freopen("zfx.out","w",stdout);
    
    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<<endl;
    return 0;
}