Cod sursa(job #334584)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 27 iulie 2009 13:09:56
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <algorithm>
using namespace std;

#define DIM 201

int n, m, rez, max0, max1, a[ DIM ][ DIM ], z[ DIM ][ DIM ], sol0[ DIM ][ DIM ], sol1[ DIM ][ DIM ];

void calc_sol0() {

    int i, j, k, zero;

    for( i = 1; i <= n; ++ i )
        for( j = 1; j <= m; ++ j )
            if( !a[ i ][ j ] ) {

                zero = z[ i ][ j ] = z[ i ][ j - 1 ] + 1;
                for( k = i; k > 0 && !a[ k ][ j ]; -- k ) {

                    zero = min( zero, z[ k ][ j ] );
                    sol0[ i ][ j ] = max( sol0[ i ][ j ], zero * ( i - k + 1 ) );
                }
            }
}

void calc_sol1() {

    int i, j, k, zero;

    for( i = n; i > 0; -- i )
        for( j = m; j > 0; -- j )
            if( !a[ i ][ j ] ) {

                zero = z[ i ][ j ] = z[ i ][ j + 1 ] + 1;
                for( k = i; k <= n && !a[ k ][ j ]; ++ k ) {

                    zero = min( zero, z[ k ][ j ] );
                    sol1[ i ][ j ] = max( sol1[ i ][ j ], zero * ( k - i + 1 ) );
                }
            }
}

void read() {

    int i, j;
    char s[ DIM ];

    scanf( "%d%d\n", &n, &m );
    for( i = 1; i <= n; ++ i ) {

        gets( s );
        for( j = 1; j <= m; ++ j )
            a[ i ][ j ] = s[ j - 1 ] - '0';
    }
}

void solve() {

    int i, j, k;

    calc_sol0();
    calc_sol1();
    for( k = 2; k <= n; ++ k ) {

        max0 = max1 = 0;
        for( i = 1; i < k; ++ i )
            for( j = 1; j <= m; ++ j )
                max0 = max( max0, sol0[ i ][ j ] );
        for( i = k; i <= n; ++ i )
            for( j = 1; j <= m; ++ j )
                max1 = max( max1, sol1[ i ][ j ] );
        rez = max( rez, max0 + max1 );
    }
    for( k = 2; k <= m; ++ k ) {

        max0 = max1 = 0;
        for( i = 1; i <= n; ++ i )
            for( j = 1; j < k; ++ j )
                max0 = max( max0, sol0[ i ][ j ] );
        for( i = 1; i <= n; ++ i )
            for( j = k; j <= m; ++ j )
                max1 = max( max1, sol1[ i ][ j ] );
        rez = max( rez, max0 + max1 );
    }
    printf( "%d", rez );
}

int main() {

    freopen( "bmatrix.in", "r", stdin );
    freopen( "bmatrix.out", "w", stdout );

    read();
    solve();

    return 0;
}