Cod sursa(job #637156)

Utilizator loginLogin Iustin Anca login Data 20 noiembrie 2011 12:27:15
Problema DreptPal Scor 0
Compilator cpp Status done
Runda .com 2011 Marime 0.97 kb
# include <fstream>
# include <iostream>
# define DIM 1003
# define max(a,b) (a>b?a:b)
using namespace std;
int n, m, a[DIM][DIM], b[DIM][DIM], sol, v[DIM], vs[DIM], vd[DIM];

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 s, d;
	sol=n;
	for(int i=1;i<=n;++i)	
		for(int j=1;j<=m;++j)
		{
			b[j][i]=1;
			s=j-1;d=j+1;
			while (s && d<=m && a[i][s]==a[i][d])
				--s, ++d, b[j][i]+=2;
			if (d-j>2)j=d-1;
			sol=max(sol,b[j][i]);
		}
	int dr;
	for (int i=1;i<=m;++i)
	{
		dr=1;
		v[0]=0;
		v[dr]=1;
		for(int j=2;j<=n;++j)
		{
			while (b[i][v[dr]]>=b[i][j] && dr)--dr;
			vs[j]=j-v[dr];
			v[++dr]=j;
		}
		dr=1;
		v[0]=n+1;
		v[dr]=n;
		for(int j=n-1;j;--j)
		{
			while (b[i][v[dr]]>=b[i][j] && dr)--dr;
			vd[j]=v[dr]-j;
			v[++dr]=j;
		}
		for(int j=1;j<=n;++j)
			sol=max(sol,(vs[j]+vd[j]-1)*b[i][j]);
	}
}

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