Cod sursa(job #1344409)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 16 februarie 2015 18:19:37
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include<fstream>
#include<string>

using namespace std;

ifstream fin( "bmatrix.in" );
ofstream fout( "bmatrix.out" );

const int nmax = 200;
const int inf = 1 << 30;
int a1, a2, n, m;
int st[ nmax + 1 ], dr[ nmax + 1 ];
int z[ nmax + 1 ][ nmax + 2 ];
bool v[ nmax + 1 ][ nmax + 1 ], aux[ nmax + 1 ][ nmax + 1 ];

string s;

int dr_max( int x, int y ) {
    int zx, zy, shp, ans = 0;
    for( int i = 1; i <= n; ++ i ) {
        zx = z[ i ][ x - 1 ];
        z[ i ][ x - 1 ] = -inf;
        for( int j = x; j <= y; ++ j ) {
            int k = j - 1;
            while ( z[ i ][ k ] >= z[ i ][ j ] ) {
                k = st[ k ];
            }
            st[ j ] = k;
        }

        zy = z[ i ][ y + 1 ];
        z[ i ][ y + 1 ] = -inf;
        for( int j = y; j >= x; -- j ) {
            int k = j + 1;
            while ( z[ i ][ k ] >= z[ i ][ j ] ) {
                k = dr[ k ];
            }
            dr[ j ] = k;

            shp = z[ i ][ j ] * (dr[ j ] - st[ j ] - 1);
            if ( shp >= ans ) {
                ans = shp;
            }
        }

        z[ i ][ x - 1 ] = zx; z[ i ][ y + 1 ] = zy;
    }
    return ans;
}
int solve() {
    int ans, shp;
    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= m; ++ j ) {
            if ( v[ i ][ j ] == 1 ) {
                z[ i ][ j ] = 0;
            } else {
                z[ i ][ j ] = z[ i - 1 ][ j ] + 1;
            }
        }
    }
    ans = 0;
    for( int sep = 2; sep <= m + 1; ++ sep ) {
        shp = dr_max( 1, sep - 1 ) + dr_max( sep, m );
        if ( ans < shp ) {
            ans = shp;
        }
    }
    return ans;
}
int main() {
    int sol1, sol2, k;
    fin >> n >> m;
    for( int i = 1; i <= n; ++ i ) {
        fin >> s;
        s = "#" + s;
        for( int j = 1; j <= m; ++ j ) {
            aux[ i ][ j ] = v[ i ][ j ] = s[ j ] - '0';
        }
    }
    sol1 = solve();
    for( int i = 1; i <= m; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            v[ i ][ j ] = aux[ j ][ i ];
        }
    }
    k = n; n = m; m = k;
    sol2 = solve();
    if ( sol2 > sol1 ) {
        sol1 = sol2;
    }
    fout << sol1 << "\n";
    fin.close();
    fout.close();
    return 0;
}