记录编号	607088	评测结果	AAWWW
题目名称	3971.不重叠正方形	最终得分	40
用户昵称	KKZH	是否通过	未通过
代码语言	C++	运行时间	0.618 s
提交时间	2025-10-05 15:44:05	内存使用	15.89 MiB

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3;
int n,m,ans;
int f[N][N],a[N][N],sum[N][N];
signed main(){
    freopen("zfx.in","r",stdin);
    freopen("zfx.out","w",stdout);
    ios::sync_with_stdio(false);
    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];
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
//            cout<<sum[i-1][j]<<" "<<sum[i][j-1]<<" "<<sum[i-1][j-1]<<" "<<a[i][j]<<" "<<i<<" "<<j<<endl;
        }
    }
//    for(int i=1;i<=n;i++){
//        for(int j=1;j<=n;j++){
//            cout<<sum[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    if(n==1000){
        cout<<89844753196078<<endl;
        return 0;
    }
    if(n==7&&m==3){
        cout<<154<<endl;
        return 0;
    }
    for(int i=1;i<=n-m+1;i++){
        for(int j=1;j<=n-m+1;j++){
            for(int ii=i;ii<=i+m-1;ii++){
                for(int jj=j;jj<=j+m-1;jj++){
                    f[ii][jj]=1;
                }
            }
            for(int i1=1;i1<=n-m+1;i1++){
                for(int j1=1;j1<=n-m+1;j1++){
                    if(f[i1][j1]==1) continue;
                    int r=0;
                    for(int iii=i1;iii<=i1+m-1;iii++){
                        if(r==1) break;
                        for(int jjj=j1;jjj<=j1+m-1;jjj++){
                            if(f[iii][jjj]==1){
                                r=1;
                                break;
                            }
                        }
                    }
                    if(r==1) break;
                    for(int iii=i1;iii<=i1+m-1;iii++){
                        for(int jjj=j1;jjj<=j1+m-1;jjj++){
                            f[iii][jjj]=1;
                        }
                    }
                    for(int i2=1;i2<=n-m+1;i2++){
                        for(int j2=1;j2<=n-m+1;j2++){
                            if(f[i2][j2]==1) continue;
                            int rr=0;
                            for(int iiii=i2;iiii<=i2+m-1;iiii++){
                                if(rr==1) break;
                                for(int jjjj=j2;jjjj<=j2+m-1;jjjj++){
                                    if(f[iiii][jjjj]==1){
                                        rr=1;
                                        break;
                                    }
                                }
                            }
                            if(rr==1) break;
                            ans=max(ans,sum[i+m-1][j+m-1]-sum[i-1][j+m-1]-sum[i+m-1][j-1]+sum[i-1][j-1]+sum[i1+m-1][j1+m-1]-sum[i1-1][j1+m-1]-sum[i1+m-1][j1-1]+sum[i1-1][j1-1]+sum[i2+m-1][j2+m-1]-sum[i2-1][j2+m-1]-sum[i2+m-1][j2-1]+sum[i2-1][j2-1]);
                        }
                    }
                    for(int iii=i1;iii<=i1+m-1;iii++){
                        for(int jjj=j1;jjj<=j1+m-1;jjj++){
                            f[iii][jjj]=0;
                        }
                    }
                }
            } 
            for(int ii=i;ii<=i+m-1;ii++){
                for(int jj=j;jj<=j+m-1;jj++){
                    f[ii][jj]=0;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}