Cod sursa(job #483203)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 7 septembrie 2010 12:22:19
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <stdio.h>
#define Nmax 202

int a[Nmax][Nmax],b[Nmax][Nmax];
int Lxa[Nmax][Nmax], Lya[Nmax][Nmax], Lxb[Nmax][Nmax], Lyb[Nmax][Nmax];
int x0a[Nmax][Nmax],x0b[Nmax][Nmax],da[Nmax][Nmax],db[Nmax][Nmax];
int N,M;
char s[Nmax];

inline int Minim(int x,int y){ return x<y ? x:y; }
inline int Maxim(int x,int y){ return x>y ? x:y; }

void bordez(int a[][Nmax],int x0[][Nmax]){
	int i,j;
	for(i=0;i<=N+1;++i)
		a[i][0]=a[i][M+1]=1;
	for(j=0;j<=M+1;++j)
		a[0][j]=a[N+1][j]=1;
	
	for(i=1;i<=N;++i)
		for(j=1;j<=M;++j)
			if(!a[i][j] ) x0[i][j]=x0[i][j-1]+1;
			else x0[i][j]=0;
}

void solve(int a[][Nmax], int Lx[][Nmax], int Ly[][Nmax],int x0[][Nmax],int d[][Nmax]){
	int i,j,k,minx;
	
	for(i=1;i<=N;++i)
		for(j=1;j<=M;++j){
			if( !a[i][j] ){
				minx=x0[i][j];
				Lx[i][j]=x0[i][j]; Ly[i][j]=1;
				
				for(k=i-1; k>=1; --k){
					minx=Minim(minx,x0[k][j]);
					if( minx * (i-k+1) > Lx[i][j]*Ly[i][j] )
						Lx[i][j]=minx, Ly[i][j]=i-k+1;
				}
			}
				
			d[i][j]=Maxim(d[i-1][j-1],Maxim(d[i-1][j],d[i][j-1]));
			d[i][j]=Maxim(d[i][j],Lx[i][j]*Ly[i][j]);
			}
}

int main(){
	int i,j,rez=0;
	freopen("bmatrix.in","r",stdin);
	freopen("bmatrix.out","w",stdout);
	scanf("%d%d\n",&N,&M);
	for(i=1;i<=N;++i){
		scanf("%s",s);
		for(j=0;j<M;++j) a[i][j+1]=s[j]-'0';
	}
	for(i=N;i>=1;--i)
		for(j=M;j>=1;--j)
			b[N-i+1][M-j+1]=a[i][j];
	
	bordez(a,x0a);
	bordez(b,x0b);
	solve(a,Lxa,Lya,x0a,da);
	solve(b,Lxb,Lyb,x0b,db);

/*	for(i=1;i<=N;++i){
		for(j=1;j<=M;++j)
			printf("(%d,%d) ",Lxb[i][j],Lyb[i][j]);
		printf("\n");
	}*/
	
	for(i=1;i<=N;++i)
		for(j=1;j<=M;++j)
			rez=Maxim(rez,da[i][j]+ Maxim(db[N-i][M], db[N][M-j]));
	
	printf("%d\n",rez);
	fclose(stdin); fclose(stdout);
	return 0;
}