Cod sursa(job #636207)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 19 noiembrie 2011 17:46:46
Problema DreptPal Scor 50
Compilator cpp Status done
Runda .com 2011 Marime 1.47 kb
#include <stdio.h>
#define NMAX 1005
#define LMAX 20005
inline int cif(char x)
{
	return x>='0' && x<='9';
}
int n,m,A[NMAX][NMAX],rez;
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;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
		{
			a=b=j;
			while (a-1>0 && b+1<=m && A[i][a-1]==A[i][b+1])
				a--,b++;
			B[i][j]=a;
		}
}
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;
}