Cod sursa(job #712948)

Utilizator loginLogin Iustin Anca login Data 13 martie 2012 22:36:08
Problema DreptPal Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 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 v[DIM], s[DIM], dr;
		
	for(int j=1;j<=m;++j)
	{
		dr=1;
		s[dr]=1;
		v[1]=1;
		for(int i=2;i<=n;++i)
		{
			while (dr && d[i][j]<d[s[dr]][j])--dr;
			if (d[s[dr]][j]!=d[i][j])s[++dr]=i;
			v[i]=i-s[dr]+1;
		}
		dr=n;
		s[dr]=n;
		for(int i=n;i;--i)
		{
			while (dr && d[i][j]<d[s[dr]][j])--dr;
			if (d[s[dr]][j]!=d[i][j])s[++dr]=i;
			v[i]+=s[dr]-i;
			sol=max(sol,v[i]*d[i][j]);
		}
	}
}

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