Cod sursa(job #1806854)

Utilizator robx12lnLinca Robert robx12ln Data 15 noiembrie 2016 18:57:38
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 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;
int st[2][205];
char s[205];
int maximal_area( int i1, int i2, int j1, int j2 ){
    int r = 0;
    memset( d, 0, sizeof(d) );
    for( int i = i1; i <= i2; i++ ){
        for( int j = j1; j <= j2; j++ ){
            if( a[i][j] == 0 ){
                d[i][j] = d[i - 1][j] + 1;
            }
        }
    }
    for( int i = i1; i <= i2; i++ ){
        int maxim = 0;
        int k = 0;
        for( int j = j1; j <= j2 + 1; 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;
                }
            }
        }
        r = max( r, maxim );
    }
    return r;
}
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');
            if( a[i][j] == 0 ){
                d[i][j] = d[i - 1][j] + 1;
            }
        }
    }
    for( int i = 1; i < n; i++ ){
        int aria = maximal_area( 1, i, 1, m ) + maximal_area( i + 1, n, 1, m );
        sol = max( sol, aria );
    }
    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;
}