Cod sursa(job #1003892)

Utilizator dariusdariusMarian Darius dariusdarius Data 1 octombrie 2013 19:13:46
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int a[1005][1005];
int p[1005][1005];
void pali(int i,int m)
{
	a[i][0]=-1;a[i][m+1]=-2;
	int r=0,c=0;
	for(int j=1;j<=m;j++)
	{
		int jp=2*c-j;
		if(j<r)
			p[i][j]=min(r-j,p[i][jp]);
		else
			p[i][j]=0;
		while(a[i][j+p[i][j]+1]==a[i][j-p[i][j]-1])
			p[i][j]++;
		if(j+p[i][j]>r)
		{
			r=j+p[i][j];
			c=j;
		}
	}
}
int st[1005];
int left[1005];
int right[1005];
int main()
{
	freopen("dreptpal.in","r",stdin);
	freopen("dreptpal.out","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
		pali(i,m);
	}
	int ans=0;
	for(int j=1;j<=m;j++)
	{
		int top=0;st[top]=0;
		for(int i=1;i<=n;i++)
		{
			while(top && p[i][j]<=p[st[top]][j])
				top--;
			left[i]=st[top]+1;
			st[++top]=i;
		}
		top=0;st[top]=n+1;
		for(int i=n;i>=1;i--)
		{
			while(top && p[i][j]<=p[st[top]][j])
				top--;
			right[i]=st[top]-1;
			st[++top]=i;	
		}
		for(int i=1;i<=n;i++)
		{
			ans=max(ans,(right[i]-left[i]+1)*(p[i][j]*2+1));
			//fprintf(stderr,"%d %d %d %d\n",i,j,left[i],right[i]);
		}
	}
	printf("%d\n",ans);
	return 0;
}