记录编号	107644	评测结果	AAAAAAAAAA
题目名称	[IOI 1999]矩形地块（A Strip of Land）	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	5.036 s
提交时间	2014-06-28 19:31:42	内存使用	6.90 MiB

#include<iostream>
#include<cstdio>
#include<deque>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEN=710,INF=0x7fffffff/2;
int N,M,C;
int ans=0;
int board[SIZEN][SIZEN]={0};
int mn[SIZEN]={0},mx[SIZEN]={0};
class MNQUE{
public:
	deque<pair<int,int> > s;
	void del_front(int x){
		if(s.size()&&s.front().first==x) s.pop_front();
	}
	int top(void){
		return s.front().second;
	}
	void push(int x,int v){
		while(s.size()&&s.back().second>=v) s.pop_back();
		s.push_back(make_pair(x,v));
	}
};
int now_maxlen(void){
	int i=1,j=1,ans=0;
	MNQUE nowmn,nowmx;
	while(i<=N){
		nowmn.push(i,mn[i]),nowmx.push(i,-mx[i]);
		while(j<=i&&-nowmx.top()-nowmn.top()>C){
			nowmn.del_front(j),nowmx.del_front(j);
			j++;
		}
		ans=max(ans,i-j+1);
		i++;
	}
	return ans;
}
void test_left(int y1){
	for(int i=1;i<=N;i++) mx[i]=-INF,mn[i]=INF;
	int temp=M;
	for(int y2=y1;y2<y1+100&&y2<=M;y2++){
		for(int i=1;i<=N;i++) mx[i]=max(mx[i],board[i][y2]),mn[i]=min(mn[i],board[i][y2]);
		if(temp*(y2-y1+1)<=ans) continue;
		temp=now_maxlen();
		ans=max(ans,temp*(y2-y1+1));
	}
}
void work(void){
	for(int i=1;i<=M;i++) test_left(i);
}
void read(void){
	scanf("%d%d%d",&M,&N,&C);
	for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) scanf("%d",&board[i][j]);
}
int main(){
	freopen("land.in","r",stdin);
	freopen("land.out","w",stdout);
	read();
	work();
	printf("%d\n",ans);
	return 0;
}