Cod sursa(job #639775)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 23 noiembrie 2011 22:40:50
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <stdio.h>
#define NMAX 1005
#define LMAX 20005
#define P 1000007
#define MOD 
inline int cif(char x)
{
	return x>='0' && x<='9';
}
int n,m,A[NMAX][NMAX],rez,H[NMAX],G[NMAX];
char line[LMAX];
struct stiva{int f,s;};
stiva E[NMAX];
short int B[NMAX][NMAX],C[NMAX][NMAX],D[NMAX][NMAX];
void read()
{
	scanf("%d%d\n",&n,&m);
	int i,j,poz;
	for (i=1; i<=n; i++)
	{
		fgets(line+1,LMAX,stdin);
		poz=0;
		for (j=1; j<=m; j++)
		{
			while (!cif(line[poz+1])) poz++;
			while (cif(line[poz+1])) {poz++; A[i][j]=A[i][j]*10+line[poz]-'0';}
		}
	}
}
inline int max(int x,int y)
{
	return x>y ? x : y;
}
inline int min(int x,int y)
{
	return x<y ? x : y;
}
void partI()
{
	int i,j,a,b,c,st,dr;
	for (i=1; i<=n; i++)
	{
		st=0; dr=0;
		for (j=1; j<=m; j++)
		{
			if (i>dr)
			{
				a=b=j;
				while (A[i][a-1]==A[i][b+1] && a-1>=1 && b+1<=m)
					a--,b++;
				st=a; dr=b;
				H[j]=st; G[j]=dr;
				B[i][j]=H[j];
			}
			else
			{
				a=st+(dr-j);
				b=H[a]; c=G[a];
				if (b>st)
				{
					H[j]=j-(a-b);
					G[j]=j+(a-b);
					B[i][j]=H[j];
				}
				else
				{
					a=j-(dr-j); b=dr;
					while (A[i][a-1]==A[i][b+1] && a-1>=1 && b+1<=m)
						a--,b++;
					st=a; dr=b;
					H[j]=a; G[j]=b;
					B[i][j]=H[j];
				}
			}
		}
	}
}
void partII()
{
	int i,j,r,act;
	for (j=1; j<=m; j++)
	{
		r=0;
		for (i=1; i<=n; i++)
		{
			act=i;
			while (B[i][j]>=E[r].f && r)
			{
				act=min(act,E[r].s);
				r--;
			}
			E[++r].f=B[i][j]; E[r].s=act;
			C[i][j]=act;
		}
		r=0;
		for (i=n; i>=1; i--)
		{
			act=i;
			while (B[i][j]>=E[r].f && r)
			{
				act=max(act,E[r].s);
				r--;
			}
			E[++r].f=B[i][j]; E[r].s=act;
			D[i][j]=act;
		}
		for (i=1; i<=n; i++)
			rez=max(rez,(D[i][j]-C[i][j]+1)*(2*(j-B[i][j])+1));
	}
}
int main()
{
	freopen("dreptpal.in","r",stdin);
	freopen("dreptpal.out","w",stdout);
	read();
	partI();
	partII();
	printf("%d\n",rez);
	return 0;
}