记录编号	455172	评测结果	AAAAAAAAAA
题目名称	[HAOI 2007]理想的正方形	最终得分	100
用户昵称	wumingshi	是否通过	通过
代码语言	C++	运行时间	5.296 s
提交时间	2017-10-01 14:53:14	内存使用	31.11 MiB

#include<cstdio>
#define N 1005
struct tree
{
	int maxn[N],minn[N];
}t[N<<2];
inline int max(const int &a,const int &b){return a>b?a:b;}
inline int min(const int &a,const int &b){return a<b?a:b;}
struct node
{
	int maxn,minn;
	node(){maxn=0,minn=1e9;}
	node(int _maxn,int _minn):maxn(_maxn),minn(_minn){}
	inline void update(const node x){maxn=max(maxn,x.maxn),minn=min(minn,x.minn);}
};
int n,m,k,ans=2e9;
void build(int l,int r,int wh,int now)
{
	if(l==r){scanf("%d",&t[now].maxn[wh]),t[now].minn[wh]=t[now].maxn[wh];return;}
	int mid=(l+r)>>1;
	build(l,mid,wh,now<<1);
	build(mid+1,r,wh,now<<1|1);
	t[now].maxn[wh]=max(t[now<<1].maxn[wh],t[now<<1|1].maxn[wh]);
	t[now].minn[wh]=min(t[now<<1].minn[wh],t[now<<1|1].minn[wh]);
}
node ask(int L,int R,int up,int down,int l,int r,int now)
{
	if(L<=l&&r<=R)
	{
		node ans;
		for(int i=up;i<=down;i++)
		  ans.update(node(t[now].maxn[i],t[now].minn[i]));
		return ans;
	}
	int mid=(l+r)>>1;node ans;
	if(L<=mid) ans.update(ask(L,R,up,down,l,mid,now<<1));
	if(R>mid) ans.update(ask(L,R,up,down,mid+1,r,now<<1|1));
	return ans;
}
int main()
{
	freopen("square.in","r",stdin);
	freopen("square.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	  build(1,m,i,1);
	for(int i=1;i<=n-k+1;i++)
	{
		for(int j=1;j<=m-k+1;j++)
		{
			node tmp=ask(j,j+k-1,i,i+k-1,1,m,1);
			ans=min(ans,tmp.maxn-tmp.minn);
			if(!ans) break;
		}
		if(!ans) break;
	}
	  
	printf("%d",ans);
	return 0;
}