记录编号	588330	评测结果	AAAAA
题目名称	不重叠正方形	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	1.423 s
提交时间	2024-05-28 20:16:15	内存使用	100.97 MiB

#include<bits/stdc++.h>
using namespace std;
long long m,n,k,maxx,nm[1502][1502],mr[1502][1502],r[1502][1502],ls[1502][1502],rs[1502][1502],lx[1502][1502],rx[1502][1502];
int main(){
    freopen("zfx.in","r",stdin);
    freopen("zfx.out","w",stdout);
    cin>>n>>k;
    m=n;
    for(int i=1;i<=m;++i)
        for(int j=1;j<=n;++j){
            cin>>nm[i][j];
            mr[i][j]=mr[i-1][j]+mr[i][j-1]-mr[i-1][j-1]+nm[i][j];
            r[i][j]=mr[i][j]-mr[i-k][j]-mr[i][j-k]+mr[i-k][j-k];
        }
    for(int i=k;i<=m;i++){
        for(int j=k;j<=n;j++){
            ls[i][j]=max(r[i][j],max(ls[i-1][j],ls[i][j-1]));
        }
    }
    for(int i=k;i<=m;++i)
        for(int j=n-k+1;j>=1;--j)
            rs[i][j]=max(r[i][j+k-1],max(rs[i-1][j],rs[i][j+1]));
    for(int i=m-k+1;i>=1;--i)
        for(int j=k;j<=n;++j)
            lx[i][j]=max(r[i+k-1][j],max(lx[i+1][j],lx[i][j-1]));
    for(int i=m-k+1;i>=1;--i)
        for(int j=n-k+1;j>=1;--j)
            rx[i][j]=max(r[i+k-1][j+k-1],max(rx[i+1][j],rx[i][j+1]));
    for(int i=k;i+k<=m;++i)
        for(int j=k;j+k<=n;++j){
            maxx=max(ls[m][j]+rs[i][j+1]+rx[i+1][j+1],maxx);
            maxx=max(ls[i][j]+rs[m][j+1]+lx[i+1][j],maxx);
            maxx=max(ls[i][n]+lx[i+1][j]+rx[i+1][j+1],maxx);
            maxx=max(ls[i][j]+rs[i][j+1]+lx[i+1][n],maxx);
        }
    for(int i=2*k;i+k<=m;++i)
        for(int j=k;j<=n;++j){
            maxx=max(maxx,ls[i-k][n]+lx[i+1][n]+r[i][j]);
        }
    for(int j=2*k;j+k<=n;++j)
        for(int i=k;i<=m;++i){
            maxx=max(maxx,ls[m][j-k]+rs[m][j+1]+r[i][j]);
        }
    cout<<maxx;
}