Cod sursa(job #638519)

Utilizator ChallengeMurtaza Alexandru Challenge Data 20 noiembrie 2011 21:59:15
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <stack>

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,p,V[MaxN][MaxN],A[MaxN][MaxN],S[MaxN],Sind;

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=j-A[i][j],dr=j+A[i][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)
	{
		Sind=0;
		for(register int i=1;i<=N;++i)
		{
			for(p=S[Sind];Sind&&A[i][j]<A[S[Sind]][j];--Sind)
			{
				sol=max(sol,A[S[Sind]][j]*(p-S[Sind-1]));
			}
			S[++Sind]=i;
		}
		for(p=S[Sind];Sind;--Sind)
		{
			sol=max(sol,A[S[Sind]][j]*(p-S[Sind-1]));
		}
	}

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