Cod sursa(job #635999)

Utilizator swift90Ionut Bogdanescu swift90 Data 19 noiembrie 2011 16:14:49
Problema DreptPal Scor 50
Compilator cpp Status done
Runda .com 2011 Marime 1.61 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int nr[1010][1010],pal[1010][1010];
int N,M,Sol;
typedef pair<int,int> PII;
PII S[1010],lung[1010];
void calc_pal(int lin){
	int i,j;
	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;
		}
	}
}
void calc_h(int C){
	int i,st=1,arie=0;
	S[1].first=pal[1][C];
	S[1].second=1;
	for(i=2;i<=N;++i){
		while(S[st].first>pal[i][C] && st>0){
			lung[S[st].second].first=i-S[st].second-1;
			S[st].first=S[st].second=0;
			--st;
		}
		S[++st].first=pal[i][C];
		S[st].second=i;
	}
	while(st>0){
		lung[S[st].second].first=N-S[st].second;
		S[st].first=S[st].second=0;
		--st;
	}
	S[1].first=pal[N][C];
	S[1].second=N;
	st=1;
	for(i=N-1;i>0;--i){
		while(S[st].first>pal[i][C] && st>0){
			lung[S[st].second].second=S[st].second-i-1;
			S[st].first=S[st].second=0;
			--st;
		}
		S[++st].first=pal[i][C];
		S[st].second=i;
	}
	while(st>0){
		lung[S[st].second].second=S[st].second-1;
		S[st].first=S[st].second=0;
		--st;
	}
	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);
	int i,j;
	scanf("%d%d",&N,&M);
	for(i=1;i<=N;++i){
		for(j=1;j<=M;++j)
			scanf("%d",&nr[i][j]);
	}
	for(i=1;i<=N;++i)
		calc_pal(i);
	
	for(i=1;i<=M;++i)
		calc_h(i);
	printf("%d\n",Sol);
	fclose(stdin);
	fclose(stdout);
	return 0;
}