记录编号	248118	评测结果	AAAAAAAAAAAAAAA
题目名称	巨大的牛棚	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.210 s
提交时间	2016-04-10 07:53:27	内存使用	11.96 MiB

#include<cstdio>
#include<cctype>
const int maxn=1005;
int max(int a,int b){
	return a>b?a:b;
}
int min(int a,int b){
	return a<b?a:b;
}
int read(){
	int x;char ch;
	while(ch=getchar(),!isdigit(ch));
	x=ch-48;
	while(ch=getchar(),isdigit(ch))x=x*10+ch-48;
	return x;
}
bool tree[maxn][maxn];
int f[maxn][maxn],left[maxn][maxn],right[maxn][maxn];
int main(){
	freopen("bigbrn.in","r",stdin);
	freopen("bigbrn.out","w",stdout);
	int n,t;scanf("%d %d",&n,&t);
	for(int i=1;i<=t;++i){
		tree[read()][read()]=true;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			f[i][j]=tree[i][j]?0:f[i-1][j]+1;
		}
	}
	for(int i=1;i<=n;++i){
		right[0][i]=n;
		left[0][i]=1;
	}
	for(int i=1;i<=n;++i){
		int lo=0;
		for(int j=1;j<=n;++j){
			if(tree[i][j])lo=j;
			left[i][j]=tree[i][j]?0:max(lo+1,left[i-1][j]);
		}
	}
	for(int i=1;i<=n;++i){
		int hi=n+1;
		for(int j=n;j>=1;--j){
			if(tree[i][j])hi=j;
			right[i][j]=tree[i][j]?n+1:min(hi-1,right[i-1][j]);
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
		//	printf("%d ",right[i][j]);
			ans=max(ans,min(f[i][j],right[i][j]+1-left[i][j]));			
		}//printf("\n");
	}
	printf("%d\n",ans);
	fclose(stdin);fclose(stdout);
	return 0;
}