比赛 2024.5.23练习赛 评测结果 AWWWW
题目名称 不重叠正方形 最终得分 20
用户昵称 健康铀 运行时间 1.478 s
代码语言 C++ 内存使用 26.38 MiB
提交时间 2024-05-23 21:21:02
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int ans,n,m,nm[1010][1010],mr[1010][1010],r[1010][1010],ls[1010][1010],rs[1010][1010],zx[1010][1010],rx[1010][1010];
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>>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-m][j]-mr[i][j-m]+mr[i-m][j-m];
        }
    }
    for(int i=m;i<=n;i++){
        for(int j=m;j<=n;j++){
            ls[i][j]=max(r[i][j],max(ls[i][j-1],ls[i-1][j]));
        }
        
    }
    for(int i=m;i<=n;i++){
        for(int j=1;j<=n-m+1;j++){
            rs[i][j]=max(r[i][j+m-1],max(rs[i-1][j],rs[i][j+1]));
        }
    }
    for(int i=n-m+1;i>=1;i--){
        for(int j=m;j<=n;j++){
            zx[i][j]=max(r[i+m-1][j],max(zx[i+1][j],ls[i][j-1]));
        }
    }
    for(int i=n-m+1;i>=1;i--){
        for(int j=n-m+1;j<=1;j--){
            rx[i][j]=max(r[i+m-1][j+m-1],max(rx[i+1][j],rx[i][j+1]));
        }
    }
    for(int i=m;i<=n-m;i++){
        for(int j=m;j<=n-m;j++){
           ans=max(rx[i+1][j+1]+rs[i][j+1]+ls[n][j],ans);
           ans=max(ls[i][j]+rs[n][j+1]+zx[i+1][j],ans);
           ans=max(ls[i][n]+zx[i+1][j]+rx[i+1][j+1],ans);
           ans=max(ls[i][j]+rs[i][j+1]+zx[i+1][n],ans);
        }
    }
    for(int i=m*2;i<=n-m;i++){
        for(int j=m;j<=n;j++){
            ans=max(ls[i-m][n]+zx[i+1][n]+r[i][j],ans);
        }
    }
    for(int j=m*2;j<=n-m;j++){
        for(int i=m;i<=n;i++){
            ans=max(ls[n][j-m]+rs[n][j+1]+r[i][j],ans);
        }
    }
    cout<<ans;
    return 0;
}