Cod sursa(job #1366957)

Utilizator Athena99Anghel Anca Athena99 Data 1 martie 2015 15:06:41
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <cassert>
#include <cstdio>

const int nmax= 200;

int n, m;
int v[nmax+1][nmax+1];
int x[nmax+1], y[nmax+1], a[nmax+1];

int st[nmax+1];

inline int max( int x, int y ) {
    if ( x>y ) return x;
    return y;
}

void rotate(  ) {
    int aux[nmax+1][nmax+1];
    for ( int i= 1; i<=n; ++i ) {
        for ( int j= 1; j<=m; ++j ) {
            aux[j][n-i+1]= v[i][j];
        }
    }

    n= n+m; m= n-m; n= n-m;
    for ( int i= 1; i<=n; ++i ) {
        for ( int j= 1; j<=m; ++j ) {
            v[i][j]= aux[i][j];
        }
    }
}

int maxarea( int x1, int x2 ) {
    int ans= 0;
    for ( int i= x1, cnt; i<=x2; ++i ) {
        cnt= 0;
        for ( int j= 1; j<=m; ++j ) {
            if ( i==x1 ) a[j]= 0;
            if ( v[i][j]==0 ) ++a[j];
            else a[j]= 0;

            for ( ; cnt>=1 && a[j]<=a[st[cnt]]; --cnt ) ;
            if ( cnt==0 ) x[j]= 1;
            else x[j]= st[cnt]+1;

            st[++cnt]= j;
        }

        cnt= 0;
        for ( int j= m; j>=1; --j ) {
            for ( ; cnt>=1 && a[j]<=a[st[cnt]]; --cnt ) ;
            if ( cnt==0 ) y[j]= m;
            else y[j]= st[cnt]-1;

            st[++cnt]= j;
            ans= max(ans, a[j]*(y[j]-x[j]+1));
        }
    }

    return ans;
}

int solve(  ) {
    int aux= 0;
    for ( int k= 2; k<=n; ++k ) {
        int max1= maxarea(1, k-1), max2= maxarea(k, n);
        if ( max1*max2!=0 && aux<max1+max2 ) {
            aux= max1+max2;
        }
    }

    return aux;
}

int main(  ) {
    assert( freopen( "bmatrix.in", "r", stdin) );
    assert( freopen( "bmatrix.out", "w", stdout ) );

    assert( scanf( "%d%d\n", &n, &m ) );
    for ( int i= 1; i<=n; ++i ) {
        char s;
        for ( int j= 1; j<=m; ++j ) {
            assert( scanf( "%c", &s ) );
            v[i][j]= s-'0';
        }
        assert( scanf( "%c", &s ) );
    }

    int sol1= solve(), sol2, sol;
    rotate();
    sol2= solve();
    sol= max(sol1, sol2);

    printf( "%d\n", sol );

    return 0;
}