Cod sursa(job #635384)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 19 noiembrie 2011 11:00:14
Problema DreptPal Scor 100
Compilator cpp Status done
Runda .com 2011 Marime 1.28 kb
#include <cstdio>
#define nmax 1010

int n, m, v[nmax][nmax], a[nmax][nmax], len[nmax], s[nmax], sol, right[nmax], left[nmax];

int min(int a, int b)
{
	if (a>b) a=b;
	return a;
}

void palindrom(int a[nmax])
{
	int i, left, right;
	for (i=1; i<=m; i++) len[i]=1;
	left=right=0;
	for (i=1; i<=m; i++)
	{
		if (right>i) 
			len[i]=min(len[left+right-i], right-i+1);
		if (i+len[i]-1>=right)
		{
			right=i+len[i]-1;
			left=i-len[i]+1;
			while (a[left-1]==a[right+1] && right<m && left>1)
			{
				left--;
				right++;
				len[i]++;
			}
		}
	}
}

int main()
{
	freopen("dreptpal.in","r",stdin);
	freopen("dreptpal.out","w",stdout);
	scanf("%d %d", &n, &m);
	int i, j, x, dr;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++) scanf("%d", &a[i][j]);
	for (i=1; i<=n; i++)
	{
		palindrom(a[i]);
		for (j=1; j<=m; j++) v[i][j]=len[j];
	}
	for (j=1; j<=m; j++)
	{
		dr=0;
		s[0]=0;
		for (i=1; i<=n; i++)
		{
			while (v[i][j]<=v[s[dr]][j] && dr>0) dr--;
			left[i]=i-s[dr];
			s[++dr]=i;
		}
		dr=0;
		s[0]=n+1;
		for (i=n; i>0; i--)
		{
			while (v[i][j]<=v[s[dr]][j] && dr>0) dr--;
			right[i]=s[dr]-i;
			s[++dr]=i;
		}
		for (i=1; i<=n; i++) 
		{
			x=left[i]+right[i]-1;
			x*=(2*v[i][j]-1);
			if (x>sol) sol=x;
		}
	}
	printf("%d\n",sol);
}