比赛 国庆欢乐赛3 评测结果 AEEEE
题目名称 不重叠正方形 最终得分 20
用户昵称 梦那边的没好TM 运行时间 0.562 s
代码语言 C++ 内存使用 3.40 MiB
提交时间 2025-10-05 10:26:22
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define foru(a,b,c) for(ll a=b;a<=c;a++)

ll n,m,a[15][15],ans;
bool pd[15][15];

ll qiu(ll x,ll y){
    ll sum=0;
    foru(i,x,x+m-1){
        foru(j,y,y+m-1){
            sum+=a[i][j];
        }
    }
    return sum;
}

bool pengzhuang(ll x,ll y,ll u,ll v){
    foru(i,u,u+m-1){
        foru(j,v,v+m-1){
            pd[i][j]=0;
        }
    }
    foru(i,x,x+m-1){
        foru(j,y,y+m-1){
            pd[i][j]=1;
        }
    }
    foru(i,u,u+m-1){
        foru(j,v,v+m-1){
            if(pd[i][j])return 1;
        }
    }
    return 0;
}

int main(){
	freopen("zfx.in","r",stdin);
	freopen("zfx.out","w",stdout);
    cin>>n>>m;
    foru(i,1,n){
        foru(j,1,n){
            cin>>a[i][j];
        }
    }
    foru(i,1,n-m+1){
        foru(j,1,n-m+1){
            ll sum1=qiu(i,j);
            foru(x,1,n-m+1){
                foru(y,1,n-m+1){
                    if(pengzhuang(i,j,x,y)){
                        continue;
                    }
                    ll sum2=qiu(x,y);
                    foru(u,1,n-m+1){
                        foru(v,1,n-m+1){
                            if(pengzhuang(u,v,x,y)){
                                continue;
                            }
                            if(pengzhuang(i,j,u,v)){
                                continue;
                            }
                            ll sum3=qiu(u,v);
                            ans=max(ans,sum1+sum2+sum3);
                            if(ans==174)cerr<<i<<" "<<j<<" "<<x<<" "<<y<<" "<<u<<" "<<v<<endl;
                        }
                    }
                }
            }
        }
    }
    cout<<ans;
    return 0;
}