Cod sursa(job #637862)

Utilizator ChallengeMurtaza Alexandru Challenge Data 20 noiembrie 2011 17:14:01
Problema DreptPal Scor 50
Compilator cpp Status done
Runda .com 2011 Marime 1.55 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];
char *buffer;

inline int number()
{
	while(!('0'<=*buffer && *buffer<='9'))
	{
		++buffer;
	}

	int sol=0;
	while('0'<=*buffer && *buffer<='9')
	{
		sol*=10;
		sol+=*buffer-'0';
		++buffer;
	}
	return sol;
}

int main()
{
	streambuf *pbuf=fin.rdbuf();
	fin.seekg(0, ios::end);
	unsigned short int BUFFERSIZE=(int)(fin.tellg());
	buffer=new char[BUFFERSIZE];
	fin.seekg(0, ios::beg);
	pbuf->sgetn(buffer,BUFFERSIZE);
	fin.close();

	N=number();
	M=number();
	for(register int i=1;i<=N;++i)
	{
		for(register int j=1;j<=M;++j)
		{
			V[i][j]=number();
		}
	}

	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)
	{
		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;
}