Cod sursa(job #483202)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 7 septembrie 2010 12:21:58
Problema BMatrix Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <stdio.h>
#include <stack>
#define Nmax 202
#define mp make_pair
#define h first
#define c second

using namespace std;

stack< pair<int,int> > Stack;
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],y0a[Nmax][Nmax],y0b[Nmax][Nmax];
int dla[Nmax],dlb[Nmax],dca[Nmax],dcb[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 y0[][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, y0[i][j]=y0[i-1][j]+1;
			else x0[i][j]=0,  y0[i][j]=0;
}

void solve_lin(int a[][Nmax], int y0[][Nmax],int dla[]){
	int i,j,col;
	
	for(i=1;i<=N;++i){
		while( ! Stack.empty() ) Stack.pop();
		dla[i]=dla[i-1];
		
		for(j=1;j<=M;++j){
			col=j;
			while( !Stack.empty() && Stack.top().h >= y0[i][j] ){
				col=Stack.top().c;
				Stack.pop();
			}
			Stack.push(mp(y0[i][j],col));
			dla[i]=Maxim(dla[i],y0[i][j]*(j-col+1));
		}
	}
}
void solve_col(int a[][Nmax], int x0[][Nmax],int dca[]){
	int i,j,lin;
	
	for(j=1;j<=M;++j){
		while( ! Stack.empty() ) Stack.pop();
		dca[j]=dca[j-1];
		
		for(i=1;i<=N;++i){
			lin=i;
			while( !Stack.empty() && Stack.top().h >= x0[i][j] ){
				lin=Stack.top().c;
				Stack.pop();
			}
			Stack.push(mp(x0[i][j],lin));
			dca[j]=Maxim(dca[j],x0[i][j]*(i-lin+1));
		}
	}
}

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,y0a);
	bordez(b,x0b,y0b);
	
	solve_lin(a,y0a,dla);
	solve_lin(b,y0b,dlb);
	solve_col(a,x0a,dca);
	solve_col(b,x0b,dcb);
	
	for(i=1;i<N;++i) rez=Maxim(rez,dla[i]+dlb[N-i]);
	for(j=1;j<M;++j) rez=Maxim(rez,dca[j]+dcb[M-j]);
	
	printf("%d\n",rez);
	fclose(stdin); fclose(stdout);
	return 0;
}