Cod sursa(job #488712)

Utilizator funkydvdIancu David Traian funkydvd Data 29 septembrie 2010 19:35:08
Problema BMatrix Scor 96
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 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];
char c[N];
inline void rezolva()
{
	int cat,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);
					col1[k]= max (col1[k], cat),col2[c]=max(col2[c],cat);
					lin1[j]=max(lin1[j],cat),lin2[i]=max(lin2[i],cat);
					cat=0;
				}
			}
		}
	}
	for(int i=2; i<=m; ++i) lin1[i]=max (lin1[i], lin1[i-1]);
	for(int i=2; i<=n; ++i) col1[i]=max (col1[i], col1[i-1]);
	for(int i=m-1; i>0; --i) lin2[i]=max (lin2[i],lin2[i+1]);
	for(int i=n-1; i>0; --i) col2[i]=max (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);
	scanf("%d%d\n",&m,&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;
	}
	rezolva();
	return 0;
}