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

#include<bits/stdc++.h>
#define ll long long
#define N 1502
using namespace std;
ll n,k,maxx,a[N][N],b[N][N],c[N][N],d[N][N],e[N][N],f[N][N],g[N][N];
int main(){
    freopen("zfx.in","r",stdin);
    freopen("zfx.out","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j){
            cin>>a[i][j];
            b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
            c[i][j]=b[i][j]-b[i-k][j]-b[i][j-k]+b[i-k][j-k];
        }
    for(int i=k;i<=n;i++)
    for(int j=k;j<=n;j++) d[i][j]=max(c[i][j],max(d[i-1][j],d[i][j-1]));
    for(int i=k;i<=n;++i)
    for(int j=n-k+1;j>=1;--j)
    e[i][j]=max(c[i][j+k-1],max(e[i-1][j],e[i][j+1]));
    for(int i=n-k+1;i>=1;--i)
    for(int j=k;j<=n;++j)
    f[i][j]=max(c[i+k-1][j],max(f[i+1][j],f[i][j-1]));
    for(int i=n-k+1;i>=1;--i)
    for(int j=n-k+1;j>=1;--j)
    g[i][j]=max(c[i+k-1][j+k-1],max(g[i+1][j],g[i][j+1]));
    for(int i=k;i+k<=n;++i)
    for(int j=k;j+k<=n;++j){
        maxx=max(d[n][j]+e[i][j+1]+g[i+1][j+1],maxx);
        maxx=max(d[i][j]+e[n][j+1]+f[i+1][j],maxx);
        maxx=max(d[i][n]+f[i+1][j]+g[i+1][j+1],maxx);
        maxx=max(d[i][j]+e[i][j+1]+f[i+1][n],maxx);
    }
    for(int i=2*k;i+k<=n;++i)
    for(int j=k;j<=n;++j) maxx=max(maxx,d[i-k][n]+f[i+1][n]+c[i][j]);
    for(int j=2*k;j+k<=n;++j)
    for(int i=k;i<=n;++i) maxx=max(maxx,d[n][j-k]+e[n][j+1]+c[i][j]);
    cout<<maxx<<endl;
}