Cod sursa(job #64773)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 5 iunie 2007 16:23:44
Problema BMatrix Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <stdio.h>
#define fin  "bmatrix.in"
#define fout "bmatrix.out"
#define Nmax 201

int N,M,ret,bst1[Nmax],bst2[Nmax];
char map[Nmax][Nmax];

void go(int a[Nmax],int b[Nmax]) {
int i,j,k,vf,v[Nmax];
int st[Nmax][2];

	for (i=0;i<=N;++i) 
		v[i]=a[i]=b[i]=0;
	
	for (i=1;i<=N;++i) 
	for (j=1,vf=0;j<=M;++j) {
		if (map[i][j]=='0')
			++v[j];
		else
			v[j]=0;
		
		st[++vf][0]=v[j];
		st[vf][1]=j;

		for ( k = vf ; k > 0 ; --k )
			if ( v[j] >= st[k][0] && ( j-st[k][1]+1 ) * st[k][0] > a[j] )
 				a[j] = ( j-st[k][1]+1 ) * st[k][0];

		for ( ; vf>1 && st[vf-1][0] >= st[vf][0] ; --vf )
			st[vf-1][0]=st[vf][0];	

		if ( a[j-1] > a[j] )
			a[j]=a[j-1];
	}

	for (i=1;i<=M;++i)
		v[i]=0;

	for (i=1;i<=N;++i) 
	for (j=M,vf=0;j>0;--j) {
		if (map[i][j]=='0')
			++v[j];
		else
			v[j]=0;
		
		st[++vf][0]=v[j];
		st[vf][1]=j;

		for ( k = vf ; k > 0 ; --k )
			if ( v[j] >= st[k][0] && ( st[k][1]-j+1 ) * st[k][0] > b[j] )
 				b[j] = ( st[k][1]-j+1 ) * st[k][0];

		for ( ; vf>1 && st[vf-1][0] >= st[vf][0] ; --vf )
			st[vf-1][0]=st[vf][0];	

		if ( b[j] < b[j+1] )
			b[j]=b[j+1];
	}

}

void inv(char map[Nmax][Nmax],int &N,int &M) {
int i,j;
char aux[Nmax][Nmax];
	for (i=1;i<=N;++i)
	for (j=1;j<=M;++j)
		aux[j][N-i+1]=map[i][j];
	N+=M; M=N-M; N-=M; 
	for (i=1;i<=N;++i)
	for (j=1;j<=M;++j)
		map[i][j]=aux[i][j];
}

int main() {
int i,j;
	freopen(fin,"r",stdin); freopen(fout,"w",stdout);

	scanf("%d%d",&N,&M);

	for (i=1;i<=N;++i) {
		fgetc(stdin);
		for (j=1;j<=M;++j)
			map[i][j]=fgetc(stdin);
	}

	go(bst1,bst2);
	for (i=2;i<=M;++i)
		if ( bst1[i-1] + bst2[i] > ret )
			ret=bst1[i-1]+bst2[i];
	
	inv(map,N,M);

	go(bst1,bst2);
	for (i=2;i<=M;++i) 
		if ( bst1[i-1] + bst2[i] > ret )
			ret=bst1[i-1]+bst2[i];
	printf("%d\n",ret);

	return 0;
}