记录编号	607106	评测结果	AAAAA
题目名称	3971.不重叠正方形	最终得分	100
用户昵称	李奇文	是否通过	通过
代码语言	C++	运行时间	0.664 s
提交时间	2025-10-05 16:49:29	内存使用	34.12 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+5;
int n,m,a[N][N],pre[N][N],sum[N][N]; 
int tl[N][N],tr[N][N],bl[N][N],br[N][N]; 
signed main(){ 
	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]}); 
    int 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;
    return 0;
}