记录编号	82977	评测结果	AAAAAAAAAA
题目名称	[HAOI 2007]理想的正方形	最终得分	100
用户昵称	ranto	是否通过	通过
代码语言	C++	运行时间	7.277 s
提交时间	2013-11-28 20:11:42	内存使用	3.28 MiB

#include <fstream>
#include <list>

using namespace std;

ifstream in("square.in");
ofstream out("square.out");

struct node 
{
	long num;
	int posi;
};

class mqueue
{
private:
	list<node> nlist;
	long lenth;
public:
	typedef list<node>::iterator iterator;
	typedef node type;
	void set(long _lenth){lenth=_lenth;}
	void pushmax(node n);
	void pushmin(node n);
	mqueue::iterator max(long p);
	mqueue::iterator min(long p);
	void clear() {nlist.clear();}
};

node make(long num, long posi)
{
	node ret;
	ret.num=num;
	ret.posi=posi;
	return ret;
}

void mqueue::pushmax(node n)
{
	list<node>::reverse_iterator it(nlist.rbegin());
	while(it!=nlist.rend())
	{
		if(it->num<=(n.num))
		{
			nlist.pop_back();
			it=nlist.rbegin();
			continue;
		}
		break;
	}
	nlist.push_back(n);
	return ;
}

void mqueue::pushmin(node n)
{
	list<node>::reverse_iterator it(nlist.rbegin());
	while(it!=nlist.rend())
	{
		if(it->num>=(n.num))
		{
			nlist.pop_back();
			it=nlist.rbegin();
			continue;
		}
		break;
	}
	nlist.push_back(n);
	return ;
}

mqueue::iterator mqueue::max(long p)
{
	list<node>::iterator it(nlist.begin());
	while(p-(it->posi)>=lenth)
	{
		nlist.pop_front();
		it=nlist.begin();
	}
	return it;
}
	
mqueue::iterator mqueue::min(long p)
{
	list<node>::iterator it(nlist.begin());
	while(p-(it->posi)>=lenth)
	{
		nlist.pop_front();
		it=nlist.begin();
	}
	return it;
}

int a,b,n;
long **f;
long **maxn;
long **minn;
mqueue maxl;
mqueue minl;

void input();
void proc();
void output();

int main()
{
	input();
	proc();
	output();
	return 0;
}

void input()
{
	in>>a>>b>>n;
	maxl.set(n);
	minl.set(n);
	f=new long* [a];
	for(int i=0;i!=a;++i)
	{
		f[i]=new long [b];
		for(int j=0;j!=b;++j)
		{
			in>>f[i][j];
		}
	}
	return ;
}

void proc()
{
	maxn=new long* [a];
	minn=new long* [a];
	for(int i=0;i!=a;++i)
	{
		maxn[i]=new long [b-n+1];
		minn[i]=new long [b-n+1];
	}
	for(int i=0;i!=a;++i)
	{
		int j(0);
		for(;j!=n;++j)
		{
			maxl.pushmax(make(f[i][j], j));
			minl.pushmin(make(f[i][j], j));
		}
		maxn[i][0]=maxl.max(n-1)->num;
		minn[i][0]=minl.min(n-1)->num;
		for(;j!=b;++j)
		{
			maxl.pushmax(make(f[i][j], j));
			minl.pushmin(make(f[i][j], j));
			maxn[i][j-n+1]=maxl.max(j)->num;
			minn[i][j-n+1]=minl.min(j)->num;
		}
		maxl.clear();
		minl.clear();
	}
	/*for(int i=0;i!=a;++i)
	{
		for(int j=0;j!=b-n+1;++j)
		{
			out<<maxn[i][j]<<' ';
		}
		out<<endl;
	}
	for(int i=0;i!=a;++i)
	{
		for(int j=0;j!=b-n+1;++j)
		{
			out<<minn[i][j]<<' ';
		}
		out<<endl;
	}*/
	for(int k=0;k<b-n+1;++k)
	{
		int j(0);
		for(;j!=n;++j)
		{
			maxl.pushmax(make(maxn[j][k], j));
			minl.pushmin(make(minn[j][k], j));
		}
		maxn[0][k]=maxl.max(n-1)->num;
		minn[0][k]=minl.min(n-1)->num;
		for(;j!=a;++j)
		{
			maxl.pushmax(make(maxn[j][k], j));
			minl.pushmin(make(minn[j][k], j));
			maxn[j-n+1][k]=maxl.max(j)->num;
			minn[j-n+1][k]=minl.min(j)->num;
		}
		maxl.clear();
		minl.clear();
	}
	return ;
}

void output()
{
	long res(1<<30);
	for(int i=0;i!=a-n+1;++i)
	{
		for(int j=0;j!=b-n+1;++j)
		{
			register long ltemp(maxn[i][j]-minn[i][j]);
			if(ltemp<res)
			{
				res=ltemp;
			}
		}
	}
	out<<res<<endl;
	return ;
}