Cod sursa(job #1813899)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 23 noiembrie 2016 14:51:39
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
# include <iostream>
# include <fstream>

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

# include <cassert>

using namespace std;

# define MAX_N 200
int l1[1 + MAX_N + 1][1 + MAX_N + 1];
int l2[1 + MAX_N + 1][1 + MAX_N + 1];
int mat[1 + MAX_N + 1][1 + MAX_N + 1];
int s[1 + MAX_N + 1][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 drept( int (*v)[1 + MAX_N + 1], int n, int m )
{
    int i, j, mx;

    mx = 0;
    for ( i = 1; i <= n; i ++ ) {
        mx = max( mx, skyline( m, v[i], i ) );
    }

    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 >> ch;
            l1[i][j] = ( ch == '0' ) * ( l1[i - 1][j] + 1 );
            l2[j][i] = ( ch == '0' ) * ( l2[j - 1][i] + 1 );
        }
    }

    mx = 0;
    for ( k = 1; k < n; k ++ )
        mx = max( mx, drept( l1, k, m ) + drept( &l1[k], n - k, m  ) );
    for ( k = 1; k < m; k ++ )
        mx = max( mx, drept( l2, k, n ) + drept( &l2[k], m - k, n  ) );

    fout << mx;

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

    return 0;
}