Cod sursa(job #475117)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 6 august 2010 00:34:21
Problema BMatrix Scor 100
Compilator cpp Status done
Runda agora2004 Marime 1.73 kb
#include <cstdio>
#include <cstring>


#define file_in "bmatrix.in"
#define file_out "bmatrix.out"

int n,m;
char a[210][210];
int b[210][210];
int v[210];

void citire()
{
	int i;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d\n", &n, &m);
	for (i=0;i<n;++i)
		 fgets(a[i],m+2,stdin);
}

inline int min(int a, int b) { return a<b?a:b; }
inline int max(int a, int b) { return a>b?a:b; }

void solve()
{
	
	int i,j,x,rez,k,h;
	//preprocesare
	for (i=0;i<n;++i)
	{
		for (j=0;j<m;++j)
		     if (a[i][j]=='0')
				  v[j]++;
			 else
				 v[j]=0;
		for (j=0;j<m;++j)
		{
			if (i!=0 && j!=0)
				b[i][j]=max(b[i][j],b[i-1][j-1]);
			if (i!=0)
				b[i][j]=max(b[i][j],b[i-1][j]);
			if (j!=0)
				b[i][j]=max(b[i][j],b[i][j-1]);
			h=v[j];
			for (k=j;k>=0;--k)
			{
				b[i][j]=max(b[i][j],(j-k+1)*h);
				if (k!=0)
					h=min(h,v[k-1]);
			}
		}
	}
	
	//orizontal
	i=0;
	while(i<m)
		v[i++]=0;
	for (i=0;i<n;++i)
	{
		for (j=0;j<m;++j)
			  if (a[i][j]=='0')
				  v[j]++;
			 else
				 v[j]=0;
		for (j=1;j<m;++j)
		{
			x=0;
			h=v[j];
			for (k=j;k<m;++k)
			{
                x=max(x,(k-j+1)*h);
				if (k<m)
					h=min(h,v[k+1]);
			}
			rez=max(rez,x+b[n-1][j-1]);
		}
	}
	
	//vertical
	i=0;
	while(i<n)
		v[i++]=0;
	for (i=0;i<m;++i)
	{
		for (j=0;j<n;++j)
			  if (a[j][i]=='0')
				  v[j]++;
			 else
				 v[j]=0;
		for (j=1;j<n;++j)
		{
			x=0;
			h=v[j];
			for (k=j;k<n;++k)
			{
                x=max(x,(k-j+1)*h);
				if (k<n)
					h=min(h,v[k+1]);
			}
			rez=max(rez,x+b[j-1][m-1]);
		}
	}
		
	printf("%d\n", rez);
}

int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	
	return 0;
	
}