Cod sursa(job #1253049)

Utilizator xtreme77Patrick Sava xtreme77 Data 31 octombrie 2014 19:05:40
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
/*
 * Code by Spiromanul
 */

#include <fstream>
#include <cstring>
#include <algorithm>
#include <cstdlib>

const char IN  [ ] = "bmatrix.in" ;
const char OUT [ ] = "bmatrix.out" ;
const int MAX = 214 ;

using namespace std;

ifstream fin  ( IN ) ;
ofstream fout ( OUT ) ;

int left_stanga [ MAX ] , right_dreapta [ MAX ] , height [ MAX ] , st [ MAX ] , MAT [ MAX ] [ MAX ] , sus [ MAX ] , jos [ MAX ] , aux [ MAX ] [ MAX ] , aux2 [ MAX ] [ MAX ] ;

char buff [ MAX ] ;

inline void solve ( int mat [ ] [ MAX ] , int *arr , int lin , int col )
{
    memset ( height , 0 , sizeof ( height ) ) ;
    for ( int i = 1 ; i <= lin ; ++ i )
    {
        for ( int j = 1 ; j <= col ; ++ j )
            if ( ! mat [ i ] [ j ] )
                height [ j ] ++ ;
                else height [ j ] = 0 ;
        int vf = 0 ;
        st [ vf ] = 0 ;
        for ( int j = 1 ; j <= col ; ++ j )
        {
            while ( vf >= 1 and height [ st [ vf ] ] >= height [ j ] )
                -- vf ;
            left_stanga [ j ] = st [ vf ] ;
            st [ ++ vf ] = j ;
        }
        vf = 0 ;
        st [ vf ] = col + 1  ;
        for ( int j = col ; j >= 1 ; -- j )
        {
            while ( vf >= 1 and height [ st [ vf ] ] >= height [ j ] )
                -- vf ;
            right_dreapta [ j ] = st [ vf ] ;
            st [ ++ vf ] = j ;
        }
        arr [ i ] = arr [ i - 1 ] ;
        // do the job
        for ( int j = 1 ; j <= col ; ++ j )
            arr [ i ] = max ( arr [ i ] , ( right_dreapta [ j ] - left_stanga [ j ] - 1 ) * height [ j ] ) ;

    }
}

int bussiness ( int mat [ ] [ MAX ] , int lin , int col )
{
    memset ( sus , 0 , sizeof ( sus ) ) ;
    memset ( jos , 0 , sizeof ( jos ) ) ;
    solve ( mat , sus , lin , col ) ;
    for ( int i = 1 ; i <= lin ; ++ i )
        for ( int j = 1 ; j <= col ; ++ j )
            aux [ lin - i + 1 ] [ j ] = mat [ i ] [ j ] ;
    solve ( aux , jos , lin , col ) ;
    int ce_trebuie = 1 , ham_ham = lin ;
    for ( ; ce_trebuie < ham_ham ; ++ ce_trebuie , -- ham_ham )
        swap ( jos [ ce_trebuie ] , jos [ ham_ham ] ) ;
    ce_trebuie = 0 ;
    for ( int i = 1 ; i <= lin ; ++ i )
        ce_trebuie = max ( ce_trebuie , sus [ i ] + jos [ i + 1 ] ) ;
    return ce_trebuie ;
}

int main(              )
{
    int n , m ;
    fin >> n >> m ;
    for ( int i = 1 ; i <= n ; ++ i )
    {
        fin >> buff ;
        for ( int j = 0 ; j < m ; ++ j )
            MAT [ i ] [ j + 1 ] = buff [ j ] - '0' ;
    }
    int sol1 = bussiness( MAT , n , m ) ;
    for ( int i = 1 ; i <= n ; ++ i )
        for ( int j = 1 ; j <= m ; ++ j )
            aux2 [ j ] [ i ] = MAT [ i ] [ j ] ;
    int sol2 = bussiness( aux2 , m , n ) ;
    fout << max ( sol1 , sol2 ) << '\n' ;
    return 0;
}