Cod sursa(job #1467019)

Utilizator BLz0rDospra Cristian BLz0r Data 2 august 2015 16:56:33
Problema BMatrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.39 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)
// CelMaiSt[x] = primul element din stanga lui x, mai mic decat el
// CelMaiDr[x] = primul element din dreapta lui x, mai mic decat el
// 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 CelMaiSt[Nmax], CelMaiDr[Nmax], SolSus[Nmax], SolJos[Nmax];
int N, M, BestSol = -1;
char v[Nmax][Nmax], aux[Nmax][Nmax];

stack < 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 ){
        for ( int j = 1; j <= M; ++j ){
            int last = j;

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

            CelMaiSt[j] = j;

            while ( !St.empty() && LimSus[i][j] <= LimSus[i][St.top()] ){
                last = St.top();
                St.pop();
            }

            CelMaiSt[j] = CelMaiSt[last];
            St.push(j);

        }

        ClearStack();

        for ( int j = M; j >= 1; --j ){
            int last = j;

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

            CelMaiDr[j] = j;

            while ( !St.empty() && LimSus[i][j] <= LimSus[i][St.top()] ){
                last = St.top();
                St.pop();
            }

            CelMaiDr[j] = CelMaiDr[last];
            St.push(j);

        }

        for ( int j = 1; j <= M; ++j )
            SolSus[i] = max ( SolSus[i], LimSus[i][j] * (CelMaiDr[j] - CelMaiSt[j] + 1) );

    }
}

void GetLower (){

    memset(SolJos, 0, sizeof(SolJos) );
    ClearStack();
    for ( int i = 1; i <= N; ++i ){
        for ( int j = 1; j <= M; ++j ){
            int last = j;

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

            CelMaiSt[j] = j;

            while ( !St.empty() && LimJos[i][j] <= LimJos[i][St.top()] ){
                last = St.top();
                St.pop();
            }

            CelMaiSt[j] = CelMaiSt[last];
            St.push(j);

        }

        ClearStack();

        for ( int j = M; j >= 1; --j ){
            int last = j;

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

            CelMaiDr[j] = j;

            while ( !St.empty() && LimJos[i][j] <= LimJos[i][St.top()] ){
                last = St.top();
                St.pop();
            }

            CelMaiDr[j] = CelMaiDr[last];
            St.push(j);

        }

        for ( int j = 1; j <= M; ++j )
            SolJos[i] = max ( SolJos[i], LimJos[i][j] * (CelMaiDr[j] - CelMaiSt[j] + 1) );

    }
}

void Rezolva(){

    GetUpper();
    GetLower();

    for ( int i = 1, j = N; i <= N; ++i, --j ){
        SolSus[i] = max ( SolSus[i-1], SolSus[i] );
        SolJos[j] = max ( SolJos[j+1], SolJos[j] );
    }

    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;
}