Cod sursa(job #712911)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 13 martie 2012 21:48:58
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb

#include <cstdio>
#include <fstream>
#include <algorithm>

using namespace std;

#define N 1024

int a[N][N],bst[N][N],n,m,sol,x[N],y[N],z[N];

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

void solve ()
{
	for(int i=1;i<=n;++i)
	{
		int lf=1,rt=1;
		bst[i][1]=1;
		for(int j=2;j<=m;++j)
			if(j>rt)
			{
				bst[i][j]=1;
				int ft=j-1,bk=j+1;
				for(;a[i][ft]==a[i][bk]&&ft&&bk<=m;++bk)
				{
					++bst[i][j];
					--ft;
				}
				lf=ft+1;
				rt=bk-1;
			}
			else
			{
				int mid=(lf+rt)>>1;
				if(bst[i][2*mid-j]<=rt-j)
					bst[i][j]=min(bst[i][2*mid-j],n-j);
				else
				{
					bst[i][j]=rt-j+1;
					int ft=j-bst[i][j],bk=j+bst[i][j];
					for(;a[i][ft]==a[i][bk]&&ft&&bk<=m;++bk)
					{
						++bst[i][j];
						--ft;
					}
					lf=ft+1;
					rt=bk-1;
				}
			}
		}
	for(int j=1;j<=m;++j)
	{
		x[0]=0;
		int ft=0;
		for(int i=1;i<=n;++i)
		{
			for(;ft&&bst[i][j]<=bst[x[ft]][j];--ft);
			y[i]=x[ft];
			x[++ft]=i;
		}
		x[0]=n+1;
		ft=0;
		for(int i=n;i;--i)
		{
			for(;ft&&bst[i][j]<=bst[x[ft]][j];--ft);
			z[i]=x[ft];
			x[++ft]=i;
		}
		for(int i=1;i<=n;++i)
			sol=max(sol,(z[i]-y[i]-1)*(2*bst[i][j]-1));
	}
}

void out ()
{
	freopen ("dreptpal.out","w",stdout);
	printf("%d",sol);
}

int main ()
{
	read ();
	solve ();
	out ();
	return 0;
}