Cod sursa(job #1813921)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 23 noiembrie 2016 15:03:08
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
# include <iostream>
# include <fstream>

# include <vector>
# include <algorithm>
# include <stack>

# include <cassert>

using namespace std;

# define MAX_N 200
int l1_1[1 + MAX_N + 1][1 + MAX_N + 1];
int l1_2[1 + MAX_N + 1][1 + MAX_N + 1];
int l2_1[1 + MAX_N + 1][1 + MAX_N + 1];
int l2_2[1 + MAX_N + 1][1 + MAX_N + 1];

char mat[1 + MAX_N + 1][1 + MAX_N + 1];
int s[1 + MAX_N + 1][1 + MAX_N + 1];

int dr_up[1 + MAX_N + 1];
int dr_dn[1 + MAX_N + 1];
int dr_lf[1 + MAX_N + 1];
int dr_rg[1 + MAX_N + 1];

int r[1 + MAX_N + 1];
int l[1 + MAX_N + 1];

int skyline( int n, int * h, int m )
{
    static int r[1 + MAX_N + 1];
    static int l[1 + MAX_N + 1];

    int v[1 + MAX_N + 1];
    v[0] = v[n + 1] = -1;
    for ( int i = 1; i <= n; i ++ )
        v[i] = min( m, h[i] );

    static vector<int> s;

    s.clear();
    s.push_back( 0 );
    for ( int i = 1; i <= n; i ++ ) {
        while ( v[s.back()] >= v[i] )
            s.pop_back();

        l[i] = i - s.back();
        s.push_back( i );
    }

    s.clear();
    s.push_back( n + 1 );
    for ( int i = n; i > 0; i -- ) {
        while ( v[s.back()] >= v[i] )
            s.pop_back();

        r[i] = s.back() - i;
        s.push_back( i );
    }

    int mx = 0;
    for ( int i = 1; i <= n; i ++ )
        mx = max( mx, min( m, v[i] ) * ( r[i] + l[i] - 1 ) );

    return mx;
}

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

    int n, m, k, i, j, mx;
    char ch;

    fin >> n >> m;

    for ( i = 1; i <= n; i ++ ) {
        for ( j = 1; j <= m; j ++ ) {
            fin >> mat[i][j];
            l1_1[i][j] = ( mat[i][j] == '0' ) * ( l1_1[i - 1][j] + 1 );
            l2_1[j][i] = ( mat[i][j] == '0' ) * ( l2_1[j - 1][i] + 1 );
        }
    }

    for ( i = n; i > 0; i -- ) {
        for ( j = m; j > 0; j -- ) {
            fin >> mat[i][j];
            l1_2[i][j] = ( mat[i][j] == '0' ) * ( l1_2[i + 1][j] + 1 );
            l2_2[j][i] = ( mat[i][j] == '0' ) * ( l2_2[j + 1][i] + 1 );
        }
    }

    for ( i = 1; i <= n; i ++ )
        dr_up[i] = max( dr_up[i - 1], skyline( m, l1_1[i], i ) );
    for ( i = 1; i <= m; i ++ )
        dr_lf[i] = max( dr_lf[i - 1], skyline( n, l2_1[i], i ) );

    for ( i = n; i > 0; i -- )
        dr_dn[i] = max( dr_dn[i + 1], skyline( m, l1_2[i], i ) );
    for ( i = m; i > 0; i -- )
        dr_rg[i] = max( dr_rg[i + 1], skyline( n, l2_2[i], i ) );

    mx = 0;
    for ( i = 1; i <= n; i ++ )
        mx = max( mx, dr_up[i] + dr_dn[i + 1] );
    for ( i = 1; i <= m; i ++ )
        mx = max( mx, dr_lf[i] + dr_rg[i + 1] );

    fout << mx;

    fin.close();
    fout.close();

    return 0;
}