Cod sursa(job #637802)

Utilizator ChallengeMurtaza Alexandru Challenge Data 20 noiembrie 2011 16:46:26
Problema DreptPal Scor 10
Compilator cpp Status done
Runda .com 2011 Marime 1.1 kb
#include <fstream>

using namespace std;

const char InFile[]="dreptpal.in";
const char OutFile[]="dreptpal.out";
const int MaxN=1024;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,M,sol,st,dr,V[MaxN][MaxN],A[MaxN][MaxN];

int main()
{
	fin>>N>>M;
	for(register int i=1;i<=N;++i)
	{
		for(register int j=1;j<=M;++j)
		{
			fin>>V[i][j];
		}
	}
	fin.close();

	for(register int i=1;i<=N;++i)
	{
		st=dr=1;
		for(register int j=1;j<=M;++j)
		{
			if(j<=dr)
			{
				A[i][j]=min(A[i][st+dr-j],dr-j);
				if(j+A[i][j]>=dr)
				{
					for(st=dr=j;st>1 && dr<M && V[i][st-1]==V[i][dr+1];--st,++dr,++A[i][j]);
				}
			}
			else
			{
				for(st=dr=j;st>1 && dr<M && V[i][st-1]==V[i][dr+1];--st,++dr,++A[i][j]);
			}
		}
		for(register int j=1;j<=M;++j)
		{
			A[i][j]=1+(A[i][j]<<1);
		}
	}

	for(int j=1;j<=M;++j)
	{
		for(register int i1=1;i1<=N;++i1)
		{
			int val=A[i1][j];
			sol=max(sol,val);
			for(register int i2=i1+1;i2<=N;++i2)
			{
				val=min(val,A[i2][j]);
				sol=max(sol,(i2-i1+1)*val);
			}
		}
	}

	fout<<sol;
	fout.close();
	return 0;
}