记录编号	57119	评测结果	AAAAAAAAAA
题目名称	[HAOI 2007]理想的正方形	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.226 s
提交时间	2013-04-06 14:47:56	内存使用	19.43 MiB

#include<iostream>
#include<cstdio>
#include<deque>
using namespace std;
const int SIZEN=1001;
class PAIR{
public:
	int ind;//下标
	int data;//数据
};
class MONO_QUEUE_MIN{
public:
	deque<PAIR> s;
	void insert(PAIR x){
		while(!s.empty()&&x.data<=s.back().data) s.pop_back();
		s.push_back(x);
	}
	void erase(int x){//删除下标为x的元素
		if(!s.empty()&&s.front().ind==x) s.pop_front();
		//否则前面删过了
	}
	int minima(void){
		return s.front().data;
	}
};
class MONO_QUEUE_MAX{
public:
	deque<PAIR> s;
	void insert(PAIR x){
		while(!s.empty()&&x.data>=s.back().data) s.pop_back();
		s.push_back(x);
	}
	void erase(int x){//删除下标为x的元素
		if(!s.empty()&&s.front().ind==x) s.pop_front();
		//否则前面删过了
	}
	int maxima(void){
		return s.front().data;
	}
};
//==============================================================
int n,m,p;//n*m的棋盘,p*p的正方形,三个数分别对应原题中的a,b,n
int board[SIZEN][SIZEN]={0};
//注意:下标是1~n
int comlinemin[SIZEN][SIZEN]={0};//行压缩,最小值
int comrowmin[SIZEN][SIZEN]={0};//行压缩后列压缩最小值
void compress_line_min(int x){//压缩第x行
	MONO_QUEUE_MIN s;
	PAIR temp;
	int i;
	for(i=1;i<=m;i++){
		temp.ind=i,temp.data=board[x][i];
		s.insert(temp);
		if(i>p)	s.erase(i-p);
		if(i>=p) comlinemin[x][i-p+1]=s.minima();
	}
}
void compress_row_min(int x){//压缩第x列
	MONO_QUEUE_MIN s;
	PAIR temp;
	int i;
	for(i=1;i<=n;i++){
		temp.ind=i,temp.data=comlinemin[i][x];
		s.insert(temp);
		if(i>p) s.erase(i-p);
		if(i>=p) comrowmin[i-p+1][x]=s.minima();
	}
}
void compress_min(void){
	int i;
	for(i=1;i<=n;i++) compress_line_min(i);
	for(i=1;i<=m;i++) compress_row_min(i);
}
//============================================================
int comlinemax[SIZEN][SIZEN]={0};//行压缩,最小值
int comrowmax[SIZEN][SIZEN]={0};//行压缩后列压缩最小值
void compress_line_max(int x){//压缩第x行
	MONO_QUEUE_MAX s;
	PAIR temp;
	int i;
	for(i=1;i<=m;i++){
		temp.ind=i,temp.data=board[x][i];
		s.insert(temp);
		if(i>p)	s.erase(i-p);
		if(i>=p) comlinemax[x][i-p+1]=s.maxima();
	}
}
void compress_row_max(int x){//压缩第x列
	MONO_QUEUE_MAX s;
	PAIR temp;
	int i;
	for(i=1;i<=n;i++){
		temp.ind=i,temp.data=comlinemax[i][x];
		s.insert(temp);
		if(i>p) s.erase(i-p);
		if(i>=p) comrowmax[i-p+1][x]=s.maxima();
	}
}
void compress_max(void){
	int i;
	for(i=1;i<=n;i++) compress_line_max(i);
	for(i=1;i<=m;i++) compress_row_max(i);
}
//=====================================================
void read(void){
	scanf("%d%d%d",&n,&m,&p);
	int i,j;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++) scanf("%d",&board[i][j]);
	}
}
void work(void){
	compress_min();
	compress_max();
	int i,j;
	int ans=-1;
	for(i=1;i<=n+1-p;i++){
		for(j=1;j<=m+1-p;j++){
			if(ans==-1) ans=comrowmax[i][j]-comrowmin[i][j];
			else ans=min(ans,comrowmax[i][j]-comrowmin[i][j]);
		}
	}
	printf("%d\n",ans);
}
int main(){
	freopen("square.in","r",stdin);
	freopen("square.out","w",stdout);
	read();
	work();
	return 0;
}