记录编号	193513	评测结果	AAAAAAAAAA
题目名称	[HAOI 2007]理想的正方形	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.903 s
提交时间	2015-10-14 20:34:55	内存使用	19.62 MiB

#include<cstdio>
#include<iostream>
using namespace std;
int q[10006],head,tail,ai,bi,n,a[1005][1005];
int f[1005][1005],g[1005][1005],k[1005][1005],p[1005][1005];
inline int in(){
	char c=getchar();
	int x=0;
	while(c<'0'||c>'9')c=getchar();
	for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';
	return x;
}
void init(){
    ai=in(); bi=in(); n=in();
	for(int i=1;i<=ai;++i) for(int j=1;j<=bi;++j) a[i][j]=in();
}
int Max(int x,int y){
	return (x>y)?x:y;
}
int Min(int x,int y){
	return (x>y)?y:x;
}
void Get_Max(){
	for(int j=1;j<=bi;++j){
	  head=tail=1; q[tail]=1;
	  f[1][j]=a[1][j];
	  for(int i=2;i<=ai;++i){
	    f[i][j]=a[i][j];
		if(i-q[head]+1>n) head++;
		while(tail>=head&&a[i][j]>a[q[tail]][j]) tail--;
		q[++tail]=i;
		f[i][j]=Max(f[i][j],a[q[head]][j]);
	  }
	}
	for(int i=1;i<=ai;++i){
	  tail=head=1; q[tail]=1;
	  g[i][1]=a[i][1];
      for(int j=2;j<=bi;++j){
		g[i][j]=a[i][j];
		if(j-q[head]+1>n) head++;
		while(tail>=head&&f[i][j]>f[i][q[tail]]) tail--;
		q[++tail]=j;
		g[i][j]=Max(g[i][j],f[i][q[head]]);
      }
	}
}
void Get_Min(){
	for(int j=1;j<=bi;++j){
	  head=tail=1; q[tail]=1;
	  k[1][j]=a[1][j];
	  for(int i=2;i<=ai;++i){
	    k[i][j]=a[i][j];
		if(i-q[head]+1>n) head++;
		while(tail>=head&&a[i][j]<a[q[tail]][j]) tail--;
		q[++tail]=i;
		k[i][j]=Min(k[i][j],a[q[head]][j]);
	  }
	}
	for(int i=1;i<=ai;++i){
	  tail=head=1; q[tail]=1;
	  p[i][1]=a[i][1];
      for(int j=2;j<=bi;++j){
		p[i][j]=a[i][j];
		if(j-q[head]+1>n) head++;
		while(tail>=head&&k[i][j]<k[i][q[tail]]) tail--;
		q[++tail]=j;
		p[i][j]=Min(p[i][j],k[i][q[head]]);
      }
	}
}
void Get_Ans(){
	int ans=0x7fffffff;
	for(int i=1;i<=ai;++i)
	 for(int j=1;j<=bi;++j)
		if(i>=n&&j>=n) ans=Min(ans,g[i][j]-p[i][j]);
	printf("%d",ans);
}
int main(){
	freopen("square.in","r",stdin);
	freopen("square.out","w",stdout);
	init();
	Get_Max(); Get_Min(); Get_Ans();
	getchar();getchar();
}