Cod sursa(job #218144)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 31 octombrie 2008 23:19:19
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
using namespace std;

#include <cstdio>
#include <algorithm>
#define II inline
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define IN "bmatrix.in"
#define OUT "bmatrix.out"
#define N_MAX 1<<8
#define si short int

int rez,N,M;
si A[N_MAX],B[N_MAX];
bool V[N_MAX][N_MAX];
si NR[N_MAX][N_MAX];

II void scan()
{
	char aux;
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	scanf("%d%d\n",&N,&M);
	
	FOR(i,1,N)
	{
		FOR(j,1,M)
			scanf("%c",&aux),
			V[i][j] = aux-'0';
		scanf("%c",&aux);
	}	
}

II void rotate()
{
	bool aux[N_MAX][N_MAX];
	
	FOR(i,1,N)
	FOR(j,1,M)
		aux[j][N-i+1] = V[i][j]; 
	
	swap(N,M);
	
	memcpy(V,aux,sizeof(aux));	
	memset(A,0,sizeof(A));
	memset(B,0,sizeof(B));
}

II void make(si V[])
{
	si stv[N_MAX],stvt[N_MAX];
	si St[N_MAX][N_MAX],Dr[N_MAX][N_MAX];
	
	FOR(i,1,N)
	{
		stv[0] = 0; stvt[0] = 1;
		
		FOR(j,1,M)
		{
			if(NR[i][j] > stv[stv[0]])
				stv[++stv[0]] = NR[i][j],
				stvt[stv[0]] = j;
			else
			{
				for(;NR[i][j] < stv[stv[0]] && stv[0];--stv[0]);
				if(NR[i][j] > stv[stv[0]])
					stv[++stv[0]] = NR[i][j];
			}	
			St[i][j] = j-stvt[stv[0]]+1;
		}
		
		stv[0] = 0; stvt[0] = 1;
		
		FOR(jj,1,M)
		{
			int j = M-jj+1;
			if(NR[i][j] > stv[stv[0]])
				stv[++stv[0]] = NR[i][j],
				stvt[stv[0]] = j;
			else
			{
				for(;NR[i][j] < stv[stv[0]] && stv[0];--stv[0]);
				if(NR[i][j] > stv[stv[0]])
					stv[++stv[0]] = NR[i][j];
			}	
			
			Dr[i][j] = stvt[stv[0]]-j+1;
		}
		
	}
	
	FOR(i,1,N)
	FOR(j,1,M)
		V[i] = max((int)V[i],(St[i][j]-1+Dr[i][j]) * NR[i][j] );
	FOR(i,1,N)
		V[i] = max(V[i-1],V[i]);
}

II void count()
{
	FOR(i,1,N)
	FOR(j,1,M)
		NR[i][j] = (V[i][j] ? 0:NR[i-1][j] + 1);
}

II void solve()
{
	count();
	make(A);	
	
	FOR(i,1,N>>1)
	FOR(j,1,M)
		swap(V[i][j],V[N-i+1][j]);
	
	count();
	make(B);
	
}

II void print()
{
	bool ok(false);
	if(rez)
		ok = true;
	FOR(i,1,N)
		rez = max(rez,A[i]+B[N-i]);
	if(ok)
		printf("%d\n",rez);
}

int main()
{
	scan();
	solve();
	print();
	
	rotate();
	solve();
	print();
	
	return 0;
}