Cod sursa(job #462603)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 12 iunie 2010 01:06:42
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <stdio.h>
#define NMAX 205
int n,m;
char A[NMAX][NMAX];
int B[NMAX][NMAX],H[NMAX][NMAX],C[NMAX][NMAX],D[NMAX][NMAX],rez;
int E[NMAX],F[NMAX];
void read()
{
	scanf("%d%d\n",&n,&m);
	int i;
	for (i=1; i<=n; i++)
		fgets(A[i]+1,NMAX,stdin);
}
void compute1()
{
	int i,j;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
			if (A[i][j]-'0')
				B[i][j]=0;
			else
				B[i][j]=B[i][j-1]+1;
	for (i=1; i<=n; i++)
		for (j=m; j>=1; j--)
			if (A[i][j]-'0')
				H[i][j]=0;
			else
				H[i][j]=H[i][j+1]+1;
}
inline int min(int x,int y)
{
	return x<y ? x : y;
}
inline int max(int x,int y)
{
	return x>y ? x : y;
}
void compute2()
{
	int i,j,k,act;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
		{
			act=B[i][j];
			C[i][j]=act;
			for (k=i-1; k>=1; k--)
			{
				act=min(act,B[k][j]);
				if (!act)
					break ;
				C[i][j]=max(C[i][j],(i-k+1)*act);
			}
		}
	for (i=n; i>=1; i--)
		for (j=1; j<=m; j++)
		{
			act=H[i][j];
			D[i][j]=act;
			for (k=i+1; k<=n; k++)
			{
				act=min(act,H[k][j]);
				if (!act)
					break ;
				D[i][j]=max(D[i][j],(k-i+1)*act);
			}
		}
}
void solve()
{
	int i,j,best=0;
	for (i=2; i<=n; i++)
	{
		for (j=1; j<=m; j++)
			best=max(best,C[i-1][j]);
		E[i]=best;
	}
	best=0;
	for (i=n-1; i>=1; i--)
	{
		for (j=1; j<=m; j++)
			best=max(best,D[i+1][j]);
		F[i]=best;
	}
	for (i=2; i<=n; i++)//separator orizontala
		rez=max(rez,E[i]+F[i-1]);
	
	best=0;
	for (j=2; j<=m; j++)
	{
		for (i=1; i<=n; i++)
			best=max(best,C[i][j-1]);
		E[j]=best;
	}
	best=0;
	for (j=m-1; j>=1; j--)
	{
		for (i=1; i<=n; i++)
			best=max(best,D[i][j+1]);
		F[j]=best;
	}
	for (i=2; i<=m; i++) //separator verticala
		rez=max(rez,E[i]+F[i-1]);
}
int main()
{
	freopen("bmatrix.in","r",stdin);
	freopen("bmatrix.out","w",stdout);
	read();
	compute1();
	compute2();
	solve();
	printf("%d\n",rez);
	return 0;
}