Cod sursa(job #712935)

Utilizator loginLogin Iustin Anca login Data 13 martie 2012 22:26:24
Problema DreptPal Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
# include <fstream>
# include <iostream>
# define DIM 1003
using namespace std;
int n, m, a[DIM][DIM], d[DIM][DIM], sol;

void read ()
{
	ifstream fin ("dreptpal.in");
	fin>>n>>m;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			fin>>a[i][j];
}

void solve ()
{
	int crt, center, last;
	
	for(int i=1;i<=n;++i)
	{
		d[i][1]=1;
		last=1;
		center=1;
		for(int j=2;j<=m;++j)
		{
			crt=0;
			
			if (last<=j)
				d[i][j]=1;
			else
			{
				d[i][j]=min(d[i][center-(j-center)],2*(last-j)+1);
				crt=d[i][j]/2;
			}
			
			while (j-(crt+1)>0 && j+(crt+1)<=m && a[i][j-(crt+1)]==a[i][j+(crt+1)])
				++crt, d[i][j]+=2;
				
			if (j+crt>last)
			{
				last=j+crt;
				center=j;
			}
		}
	}
	
	int s[DIM], p[DIM], dr, st, q;
	
	for(int j=1;j<=m;++j)
	{
		st=dr=1;
		s[dr]=d[1][j];
		p[dr]=1;
		for(int i=2;i<=n;++i)
		{
			q=d[i][j];
			while (dr && q<s[dr])--dr;
			if (q!=s[dr])s[++dr]=q,p[dr]=i;
			if (st>dr)st=dr;
			while (st<dr && (i-p[st]+1)*s[st]<(i-p[st+1]+1)*s[st+1])++st;
			sol=max((i-p[st]+1)*s[st],sol);
		}
		st=dr=n;
		s[dr]=d[n][j];
		p[dr]=n;
		for(int i=n-1;i;--i)
		{
			q=d[i][j];
			while (dr && q<s[dr])--dr;
			if (q!=s[dr])s[++dr]=q,p[dr]=i;
			if (st>dr)st=dr;
			while (st<dr && (p[st]-i+1)*s[st]<(p[st+1]-i+1)*s[st+1])++st;
			sol=max((p[st]-i+1)*s[st],sol);
		}
	}
}

int main ()
{
	read ();
	solve ();
	ofstream fout ("dreptpal.out");
	fout<<sol;
	return 0;
}