Cod sursa(job #636201)

Utilizator swift90Ionut Bogdanescu swift90 Data 19 noiembrie 2011 17:44:56
Problema DreptPal Scor 50
Compilator cpp Status done
Runda .com 2011 Marime 2.74 kb
#include<cstdio>
#include<fstream>
#include<algorithm>
using namespace std;
const long long PRIM = 1000000007LL;
const long long MOD = 1500000001LL;
int nr[1010][1010],pal[1010][1010];
long long st[1010],dr[1010],put[1010];
int N,M,Sol;
typedef pair<int,int> PII;
PII S[1010],lung[1010];
inline int minim(int a,int b){
	return a<b?a:b;
}
void calc_pal(int lin){
	int i,p,u,mij;
	long long x,y,pre;
	/*for(i=1;i<=M;++i){
		for(j=0;i-j>0 && i+j<=M;++j){
			if(nr[lin][i-j]==nr[lin][i+j])
				pal[lin][i]=j;
			else
				break;
		}
	}*/
	for(i=1;i<=M;++i){
		dr[i]=(dr[i-1]+nr[lin][i]*put[i-1])%MOD;
		st[M-i+1]=(st[M-i+2]+nr[lin][M-i+1]*put[i-1])%MOD;
	}
	for(i=1;i<=M;++i){
		p=0;
		if(i-1<M-i){
			u=i-1;
			pre=M-i-i+1;
			while(p<u){
				mij=(p+u+1)>>1;
				x=dr[i-1]-dr[i-mij-1];
				if(x<0)
					x+=MOD;
				y=st[i+1]-st[i+mij+1];
				if(y<0)
					y+=MOD;
				x*=put[pre];
				x%=MOD;
				if(x==y)
					p=mij;
				else
					u=mij-1;
			}
		}
		else{
			u=M-i;
			pre=(i<<1)-M-1;
			while(p<u){
				mij=(p+u+1)>>1;
				x=dr[i-1]-dr[i-mij-1];
				if(x<0)
					x+=MOD;
				y=st[i+1]-st[i+mij+1];
				if(y<0)
					y+=MOD;
				y*=put[pre];
				y%=MOD;
				if(x==y)
					p=mij;
				else
					u=mij-1;
			}
		}
		pal[lin][i]=p;
	}
}
void calc_h(int C){
	int i,ss=1,arie=0;
	S[1].first=pal[1][C];
	S[1].second=1;
	for(i=2;i<=N;++i){
		while(S[ss].first>pal[i][C] && ss>0){
			lung[S[ss].second].first=i-S[ss].second-1;
			//S[ss].first=S[ss].second=0;
			--ss;
		}
		S[++ss].first=pal[i][C];
		S[ss].second=i;
	}
	while(ss>0){
		lung[S[ss].second].first=N-S[ss].second;
		//S[ss].first=S[ss].second=0;
		--ss;
	}
	S[1].first=pal[N][C];
	S[1].second=N;
	ss=1;
	for(i=N-1;i>0;--i){
		while(S[ss].first>pal[i][C] && ss>0){
			lung[S[ss].second].second=S[ss].second-i-1;
			//S[ss].first=S[ss].second=0;
			--ss;
		}
		S[++ss].first=pal[i][C];
		S[ss].second=i;
	}
	while(ss>0){
		lung[S[ss].second].second=S[ss].second-1;
		//S[ss].first=S[ss].second=0;
		--ss;
	}
	for(i=1;i<=N;++i){
		if((lung[i].first+lung[i].second+1) * (2*pal[i][C]+1)>arie)
			arie=(lung[i].first+lung[i].second+1) * (2*pal[i][C]+1);
		lung[i].first=lung[i].second=0;
	}
	if(arie>Sol)
		Sol=arie;
}
int main(){
	//freopen("dreptpal.in","r",stdin);
	//freopen("dreptpal.out","w",stdout);
	ifstream f("dreptpal.in");
	ofstream g("dreptpal.out");
	int i,j;
	//scanf("%d%d",&N,&M);
	f>>N>>M;
	for(i=1;i<=N;++i){
		for(j=1;j<=M;++j)
			//scanf("%d",&nr[i][j]);
			f>>nr[i][j];
	}
	put[0]=1;
	for(i=1;i<=M;++i){
		put[i]=put[i-1]*PRIM;
		put[i]%=MOD;
	}
	for(i=1;i<=N;++i)
		calc_pal(i);
	
	for(i=1;i<=M;++i)
		calc_h(i);
	//printf("%d\n",Sol);
	g<<Sol<<'\n';
	fclose(stdin);
	fclose(stdout);
	return 0;
}