Cod sursa(job #1467084)

Utilizator BLz0rDospra Cristian BLz0r Data 2 august 2015 18:42:57
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.79 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;

#define Nmax 202

FILE *f = fopen ( "bmatrix.in", "r" );
FILE *g = fopen ( "bmatrix.out", "w" );

// v = matricea pe care lucrez
// aux = matrice pentru rotit
// LimSus[i][j] = cat de mult pot urca, numai pe elem de 0 de pe pozitia (i,j)
// LimSus[i][j] = cat de mult pot cobora, numai pe elem de 0 de pe pozitia (i,j)
// SolSus[x] = aria celui mai mare dreptunghi plin de 0 care are latura de jos pe linia i
// SolJos[x] = aria celui mai mare dreptunghi plin de 0 care are latura de sus pe linia i

int LimSus[Nmax][Nmax], LimJos[Nmax][Nmax];
int SolSus[Nmax], SolJos[Nmax];
int N, M, BestSol = -1;
char v[Nmax][Nmax], aux[Nmax][Nmax];

stack < pair < int, int > > St;

void Citire(){
    fscanf ( f, "%d%d%*c", &N, &M );

    for ( int i = 1; i <= N; ++i )
       fscanf ( f, "%s%*c", v[i]+1 );

}

void ClearStack (){
    while ( !St.empty() )
        St.pop();
}

void Precalc (){

    memset ( LimSus, 0, sizeof (LimSus) );
    memset ( LimJos, 0, sizeof (LimJos) );

    for ( int i = 1, k = N; i <= N; ++i, --k ){
        for ( int j = 1; j <= M; ++j ){
            if ( v[i][j] == '0' )
                LimSus[i][j] = LimSus[i-1][j] + 1;
            if ( v[k][j] == '0' )
                LimJos[k][j] = LimJos[k+1][j] + 1;
        }
    }
}

void Roteste (){

    for ( int i1 = 1, i2 = N; i1 <= N; ++i1, --i2 )
        for ( int j = 1; j <= M; ++j )
            aux[j][i2] = v[i1][j];

    memcpy( v, aux, sizeof (aux) );

    swap ( N, M );
}

void GetUpper (){

    memset ( SolSus, 0, sizeof (SolSus) );

    ClearStack();
    for ( int i = 1; i <= N; ++i ){
        SolSus[i] = SolSus[i-1];
        for ( int j = 1; j <= M; ++j ){
            int last = j;

            while ( !St.empty() && LimSus[i][j] < LimSus[i][St.top().first] ){
                SolSus[i] = max ( SolSus[i], LimSus[i][St.top().first] * (j- St.top().second) );
                last = St.top().second;
                St.pop();
            }

            if ( LimSus[i][j] == 0 )
                continue;

            if ( St.empty() )
                St.push ( make_pair ( j, last ) );
            else if ( LimSus[i][St.top().first] < LimSus[i][j] )
                St.push ( make_pair ( j, last ) );
        }

        while ( !St.empty() ){
            SolSus[i] = max ( SolSus[i], LimSus[i][St.top().first] * ( M - St.top().second + 1 ) );
            St.pop();
        }
    }

}

void GetLower (){

    memset ( SolJos, 0, sizeof(SolJos) );

    ClearStack();
    for ( int i = N; i >= 1; --i ){
        SolJos[i] = SolJos[i+1];
        for ( int j = 1; j <= M; ++j ){
            int last = j;

            while ( !St.empty() && LimJos[i][j] < LimJos[i][St.top().first] ){
                SolJos[i] = max ( SolJos[i], LimJos[i][St.top().first] * (j - St.top().second) );
                last = St.top().second;
                St.pop();
            }

            if ( LimJos[i][j] == 0 )
                continue;

            if ( St.empty() )
                St.push ( make_pair ( j, last ) );
            else if ( LimJos[i][St.top().first] < LimJos[i][j] )
                St.push ( make_pair ( j, last ) );
        }

        while ( !St.empty() ){
            SolJos[i] = max ( SolJos[i], LimJos[i][St.top().first] * ( M - St.top().second + 1 ) );
            St.pop();
        }
    }

}

void Rezolva(){

    GetUpper();
    GetLower();

    for ( int i = 1; i < N; ++i )
        BestSol = max ( BestSol, SolSus[i] + SolJos[i+1] );

}

void Scrie(){
    fprintf ( g, "%d", BestSol );
}

int main(){

    Citire();

    Precalc();
    Rezolva();

    Roteste();

    Precalc();
    Rezolva();

    Scrie();

    return 0;
}