记录编号	246937	评测结果	AAAAAAAAAA
题目名称	[HAOI 2007]修筑绿化带	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	1.533 s
提交时间	2016-04-07 18:08:33	内存使用	15.71 MiB

#include<cstdio>
const int maxn=1005;
int fer[maxn][maxn];
int getfer[maxn][maxn];//getfer[i][j]:fer[i][j]为左上角，getx*gety总肥沃
int lostfer[maxn][maxn];
int minrow[maxn][maxn];
int getsum(int x1,int y1,int x2,int y2){
	return fer[x2][y2]+fer[x1-1][y1-1]-fer[x1-1][y2]-fer[x2][y1-1];
} 
struct queue{
	int q[maxn],index[maxn];
	int head,tail,k;	
	void clear(int _len){
		head=tail=0;k=_len;
	}
	void add(int x,int i){
		while(head!=tail&&index[head]+k<=i)head++;
		while(head!=tail&&q[tail-1]>=x)tail--;
		q[tail]=x;
		index[tail++]=i;
	}
	int min(){
		return q[head];
	}
}q1;
int main(){
	freopen("parterre.in","r",stdin);
	freopen("parterre.out","w",stdout);
	int allx,ally,getx,gety,lostx,losty;
	scanf("%d %d %d %d %d %d",&allx,&ally,&getx,&gety,&lostx,&losty);
	for(int i=1;i<=allx;++i){
		for(int j=1;j<=ally;++j){
			scanf("%d",&fer[i][j]);
			fer[i][j]=fer[i][j]+fer[i-1][j]+fer[i][j-1]-fer[i-1][j-1];
		}
	}
	for(int i=1;i+getx-1<=allx;++i){
		for(int j=1;j+gety-1<=ally;++j){
//			getfer[i][j]=fer[i+getx-1][j+gety-1]-fer[i-1][j+gety-1]\
//						-fer[i+getx-1][j-1]+fer[i-1][j-1];
			getfer[i][j]=getsum(i,j,i+getx-1,j+gety-1);
		}
	}
	for(int i=1;i+lostx-1<=allx;++i){
		for(int j=1;j+losty-1<=ally;++j){
			lostfer[i][j]=getsum(i,j,i+lostx-1,j+losty-1);
		}
	}
	int limx=getx-lostx-1,limy=gety-losty-1;
	for(int i=1;i+lostx-1<=allx;++i){
		q1.clear(limy);
		for(int j=1;j+losty-1<=ally;++j){
			q1.add(lostfer[i][j],j);
			if(j-limy+1>=1){
				minrow[i][j-limy+1]=q1.min();
			//	printf("%d ",minrow[i][j-limy+1]);
			}
		}//printf("\n");
	}
	int ans=0,tmp;
	for(int j=1;minrow[1][j]!=0;++j){
		q1.clear(limx);
		for(int i=1;minrow[i][1]!=0;++i){
			q1.add(minrow[i][j],i);
			if(i-limx>=1){
				tmp=getfer[i-limx][j-1]-q1.min();
				if(tmp>ans){
					ans=tmp;
			//		printf("%d %d\n",getfer[i-limx+1][j],q1.min());
				}
			}
		}
	}
	printf("%d",ans);
	//对于每个左上角坐标，求出以之为左上角limx*limy中min{lostfer[i][j]} 
	//先对每个坐标i,j向右延伸limy到i,j+limy-1求最小值记为minrow[i][j] 
/*	for(int i=1;i+getx-1<=allx;++i){
		for(int j=1;j+gety-1<=ally;++j){
			printf("%d ",lostfer[i][j]);
		}printf("\n"); 
	}*/
	fclose(stdin);fclose(stdout);
	return 0;
}