Cod sursa(job #755961)

Utilizator GrimpowRadu Andrei Grimpow Data 8 iunie 2012 12:11:36
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <cstdio>
#include <bitset>
using namespace std;
#define N 205

int m,n;
bitset< N > a[N],e;
int lin1[N],lin2[N],col1[N],col2[N];

inline void citire()
{
	scanf("%d%d\n",&m,&n);
	char c[N];
	for(int i=1; i<=m; ++i)
	{
		fgets(c+1,N-1,stdin);
		for(int j=1; j<=n; ++j)
		{
			if(c[j]=='1')
				a[i][j]=1;
			else
				a[i][j]=0;
		}
	}
}

inline void rezolva()
{
	int cat;
	int c;
	for(int i=1; i<=m; ++i)
	{
		e.reset();
		for(int j=i; j<=m; ++j)
		{
			cat=0;
			for(int k=1; k<=n; ++k)
			{
				if(a[j][k]==1)
					e[k]=1;
				if(e[k]==0)
					++cat;
				if(e[k]==1 || k==n)
				{
					c=k-cat+1;
					cat*=(j-i+1);
					if(col1[k]<cat)
						col1[k]=cat;
					if(col2[c]<cat)
						col2[c]=cat;
					if(lin1[j]<cat)
						lin1[j]=cat;
					if(lin2[i]<cat)
						lin2[i]=cat;
					cat=0;
				}
			}
		}
	}

	for(int i=2; i<=m; ++i)
	{
		if(lin1[i]<lin1[i-1])
			lin1[i]=lin1[i-1];
	}
	for(int i=2; i<=n; ++i)
	{
		if(col1[i]<col1[i-1])
			col1[i]=col1[i-1];
	}
	for(int i=m-1; i>0; --i)
	{
		if(lin2[i]<lin2[i+1])
			lin2[i]=lin2[i+1];
	}
	for(int i=n-1; i>0; --i)
	{
		if(col2[i]<col2[i+1])
			col2[i]=col2[i+1];
	}

	int rez=0;
	for(int i=1; i<m; ++i)
	{
		if(lin1[i]+lin2[i+1]>rez)
			rez=lin1[i]+lin2[i+1];
	}
	for(int i=1; i<n; ++i)
	{
		if(col1[i]+col2[i+1]>rez)
			rez=col1[i]+col2[i+1];
	}
	
	printf("%d\n",rez);
}

int main()
{
	freopen("bmatrix.in","r",stdin);
	freopen("bmatrix.out","w",stdout);

	citire();
	rezolva();

	return 0;
}