Cod sursa(job #1806870)

Utilizator robx12lnLinca Robert robx12ln Data 15 noiembrie 2016 19:25:01
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.43 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int n, m, a[205][205], d[205][205], sol, b[205][205];
int st[2][205];
char s[205];
int maximal_area( int i1, int i2, int j1, int j2 ){
    int r = 0;
    for( int i = i1; i <= i2; i++ ){
        int maxim = 0;
        int k = 0;
        for( int j = j1; j <= j2; j++ ){
            if( d[i][j] > st[0][k] ){
                k++;
                st[0][k] = d[i][j];
                st[1][k] = j;
            }else{
                int pos = 0;
                while( d[i][j] <= st[0][k] && k > 0 ){
                    if( maxim < st[0][k] * (j - st[1][k]) ){
                        maxim = st[0][k] * (j - st[1][k]);
                    }
                    pos = st[1][k];
                    k--;
                }
                if( d[i][j] != 0 ){
                    k++;
                    st[0][k] = d[i][j];
                    st[1][k] = pos;
                }
            }
        }
        while( k > 0 ){
            if( maxim < st[0][k] * (j2 + 1 - st[1][k]) ){
                maxim = st[0][k] * (j2 + 1 - st[1][k]);
            }
            k--;
        }
        r = max( r, maxim );
    }
    return r;
}
void rotesc_90(){
    for( int i = 1; i <= n; i++ ){
        for( int j = 1; j <= m; j++ ){
            b[j][n - i + 1] = a[i][j];
        }
    }
    memset( a, 0, sizeof(a) );
    memcpy( a, b, sizeof(b) );
}
int main(){
    fin >> n >> m;
    for( int i = 1; i <= n; i++ ){
        fin >> s;
        for( int j = 1; j <= m; j++ ){
            a[i][j] = (s[j - 1] - '0');
        }
    }
    for( int i = 1; i <= n; i++ ){
        for( int j = 1; j <= m; j++ ){
            if( a[i][j] == 0 ){
                d[i][j] = d[i - 1][j] + 1;
            }
        }
    }
    for( int j = 1; j < m; j++ ){
        int aria = maximal_area( 1, n, 1, j ) + maximal_area( 1, n, j + 1, m );
        sol = max( sol, aria );
    }
    rotesc_90();
    memset( d, 0, sizeof(d) );
    swap( n, m );
    for( int i = 1; i <= n; i++ ){
        for( int j = 1; j <= m; j++ ){
            if( a[i][j] == 0 ){
                d[i][j] = d[i - 1][j] + 1;
            }
        }
    }
    for( int j = 1; j < m; j++ ){
        int aria = maximal_area( 1, n, 1, j ) + maximal_area( 1, n, j + 1, m );
        sol = max( sol, aria );
    }
    fout << sol << "\n";
    return 0;
}