# BZOJ4716 假摔

Posted by yjjr's blog on January 1, 2018

# code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1006;
int sum[maxn][maxn],n,m,lx,ly,k,a[maxn][maxn],ans,cnt;
struct node{int a,b,c,d,v;};
bool operator < (node a,node b){//重载运算符
if(a.v!=b.v)return a.v>b.v;
if(a.a!=b.a)return a.a>b.a;
if(a.b!=b.b)return a.b>b.b;
if(a.c!=b.c)return a.c>b.c;
if(a.d!=b.d)return a.d>b.d;
return 0;
}
inline int get(int a,int b,int c,int d){
return sum[c][d]-sum[a-1][d]-sum[c][b-1]+sum[a-1][b-1];
}
priority_queue<node> que;
map<node,int>mp;
int main()
{
rep(i,1,n)
rep(i,1,n)
rep(j,1,m)sum[i][j]=sum[i-1][j]+sum[i][j-1]+a[i][j]-sum[i-1][j-1];
rep(i,1,n-lx+1)
rep(j,1,m-ly+1)que.push((node){i,j,i+lx-1,j+ly-1,get(i,j,i+lx-1,j+ly-1)});//将xmin*ymin大小的矩阵扔进去
while(!que.empty()){
node x=que.top();que.pop();
if(mp.find(x)!=mp.end())continue;
mp[x]=1;++cnt;ans=x.v;
if(cnt==k)break;
if(x.c+1<=n)que.push((node){x.a,x.b,x.c+1,x.d,get(x.a,x.b,x.c+1,x.d)});
if(x.d+1<=m)que.push((node){x.a,x.b,x.c,x.d+1,get(x.a,x.b,x.c,x.d+1)});
}
printf("%d\n",ans+1);
return 0;
}