记录编号	588490	评测结果	WWAWW
题目名称	不重叠正方形	最终得分	20
用户昵称	郑霁桓	是否通过	未通过
代码语言	C++	运行时间	0.759 s
提交时间	2024-06-02 19:16:16	内存使用	35.41 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[1005][1005],b[1005][1005],s,nmp,as;
struct nm{
    long long v,x,y;
}c[1005*1005];
bool cp(nm x,nm y){
    return x.v>y.v;
}
bool dfs(long long a1,long long a2,long long s,long long pp){
    for(int i=pp;i<=nmp;i++){
        if(a1==0){
            if(dfs(i,0,c[i].v,i+1)){
                return true;
            }
        }else if(a2==0){
            if(abs(c[i].x-c[a1].x)<m&&abs(c[i].y-c[a1].y)<m){
                continue;
            }
            if(dfs(a1,i,s+c[i].v,i+1)){
                return true;
            }
        }else{
            if(abs(c[i].x-c[a1].x)<m&&abs(c[i].y-c[a1].y)<m){
                continue;
            }
            if(abs(c[i].x-c[a2].x)<m&&abs(c[i].y-c[a2].y)<m){
                continue;
            }
            as=s+c[i].v;
            return true;
        }
    }
}
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++){
            scanf("%lld",&a[i][j]);
            b[i][j]=b[i][j-1]+b[i-1][j]-b[i-1][j-1]+a[i][j];
        }
    }
    for(int i=m,k=1;i<=n;i++){
        for(int j=m;j<=n;j++,k++,nmp++){
            c[k].v=b[i][j]-b[i][j-m]-b[i-m][j]+b[i-m][j-m];
            c[k].x=i;
            c[k].y=j; 
        }
    }
    sort(c+1,c+nmp+1,cp);
    dfs(0,0,0,1);
    cout<<as;
    return 0;
}