Cod sursa(job #217931)

Utilizator Data 30 octombrie 2008 21:41:48
Problema BMatrix Scor 28
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
using namespace std;
#include <cstdio>
#include <vector>
#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
int rez,N,M;int A[N_MAX],B[N_MAX];bool V[N_MAX][N_MAX];int 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];memcpy(V,aux,sizeof(aux));swap(N,M);}II void make(int V[]){int stv[N_MAX],stvt[N_MAX];
int St[N_MAX][N_MAX],Dr[N_MAX][N_MAX];FOR(i,1,N){memset(stv,0,sizeof(stv));memset(stvt,0,sizeof(stvt));FOR(j,1,M){for(;NR[i][j] < stv[stv[0]] && stv[0];--stv[0]);
if(NR[i][j] > stv[stv[0]]){stv[++stv[0]] = NR[i][j];stvt[stv[0]] = j;}if(stvt[stv[0]])St[i][j] = j-stvt[stv[0]];}memset(stv,0,sizeof(stv));
memset(stvt,0,sizeof(stvt));FOR(jj,1,M){int j = M-jj+1;for(;NR[i][j] < stv[stv[0]] && stv[0];--stv[0]);if(NR[i][j] > stv[stv[0]])
{stv[++stv[0]] = NR[i][j];stvt[stv[0]] = j;}if(stvt[stv[0]])Dr[i][j] = stvt[stv[0]]-j;}}FOR(i,1,N){V[i] = V[i-1];FOR(j,1,M)V[i] = max(V[i],(Dr[i][j]+St[i][j]+1)*NR[i][j] );
}}II void solve(){FOR(i,1,N)FOR(j,1,M)if(V[i][j] == false)NR[i][j] = NR[i-1][j] + 1;else NR[i][j] = 0;make(A);memset(NR,0,sizeof(NR));
FOR(i,1,N)FOR(j,1,M)if(V[N-i+1][j] == false)NR[i][j] = NR[i-1][j] + 1;else NR[i][j] = 0;make(B);}II void print(){bool ok(false);if(rez)ok = true;FOR(i,1,N-1)rez = max(rez,A[i]+B[N-i]);
if(ok)printf("%d\n",rez);}int main(){scan();solve();print();rotate();solve();print();return 0;}