Cod sursa(job #2527870)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 20 ianuarie 2020 22:38:51
Problema BMatrix Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.52 kb
#include <stack>
#include <cstdio>

using namespace std;

const int NMAX = 2e2 ;
int a [ NMAX + 5 ] [ NMAX + 5 ] ;
int dp [ 3 ] [ NMAX + 5 ] [ NMAX + 5 ] ;
int st [ NMAX + 5 ] , dr [ NMAX + 5 ] ;

/// dp [ 1 ] -> stanga - dreapta
/// dp [ 2 ] -> dreapta - stanga

/// dp [ 1 ] -> sus - jos
/// dp [ 2 ] -> jos - sus

inline int solve ( int n , int m )
{
    int i , i1 , j , j1 , amx1 = 0 , amx2 = 0 , ans = 0 ;

    for ( j = 1 ; j <= m ; ++ j )
        for ( i = 1 ; i <= n ; ++ i )
            if ( ! a [ i ] [ j ] )
                dp [ 1 ] [ i ] [ j ] = dp [ 1 ] [ i - 1 ] [ j ] + 1 ;

    for ( j = m ; j >= 1 ; -- j )
        for ( i = n ; i >= 1 ; -- i )
            if ( ! a [ i ] [ j ] )
                dp [ 2 ] [ i ] [ j ] = dp [ 2 ] [ i + 1 ] [ j ] + 1 ;

    for ( i = 1 ; i <= n ; ++ i )
        for ( i1 = i + 1 ; i1 <= n ; ++ i1 )
        {
            stack < int > s ;
            amx1 = 0 ; amx2 = 0 ;

            /// Upper line

            dp [ 1 ] [ i ] [ 0 ] = - 1 ;
            s.push ( 0 ) ;

            for ( j = 1 ; j <= m ; ++ j )
            {
                while ( ! s.empty () && dp [ 1 ] [ i ] [ j ] <= dp [ 1 ] [ i ] [ s.top () ] )
                    s.pop () ;
                st [ j ] = s.top () ;
                s.push ( j ) ;
            }

            while ( ! s.empty () )
                s.pop () ;

            s.push ( m + 1 ) ;
            dp [ 1 ] [ i ] [ m + 1 ] = - 1 ;

            for ( j = m ; j >= 1 ; -- j )
            {
                while ( ! s.empty () && dp [ 1 ] [ i ] [ j ] <= dp [ 1 ] [ i ] [ s.top () ] )
                    s.pop () ;
                dr [ j ] = s.top () ;
                s.push ( j ) ;
            }

            for ( j = 1 ; j <= m ; ++ j )
                amx1 = max ( amx1 , ( dr [ j ] - st [ j ] - 1 ) * dp [ 1 ] [ i ] [ j ] ) ;

            while ( ! s.empty () )
                s.pop () ;

            ///Bottom line

            dp [ 2 ] [ i1 ] [ 0 ] = - 1 ;
            s.push ( 0 ) ;

            for ( j = 1 ; j <= m ; ++ j )
            {
                while ( ! s.empty () && dp [ 2 ] [ i1 ] [ j ] <= dp [ 2 ] [ i1 ] [ s.top () ] )
                    s.pop () ;
                st [ j ] = s.top () ;
                s.push ( j ) ;
            }

            while ( ! s.empty () )
                s.pop () ;

            s.push ( m + 1 ) ;
            dp [ 2 ] [ i1 ] [ m + 1 ] = - 1 ;

            for ( j = m ; j >= 1 ; -- j )
            {
                while ( ! s.empty () && dp [ 2 ] [ i1 ] [ j ] <= dp [ 2 ] [ i1 ] [ s.top () ] )
                    s.pop () ;
                dr [ j ] = s.top () ;
                s.push ( j ) ;
            }

            for ( j = 1 ; j <= m ; ++ j )
                amx2 = max ( amx2 , ( dr [ j ] - st [ j ] - 1 ) * dp [ 2 ] [ i1 ] [ j ] ) ;

            ans = max ( ans , amx1 + amx2 ) ;
        }


    for ( i = 1 ; i <= n ; ++ i )
        for ( j = 1 ; j <= m ; ++ j )
            if ( ! a [ i ] [ j ] )
                dp [ 1 ] [ i ] [ j ] = dp [ 1 ] [ i ] [ j - 1 ] + 1 ;

    for ( i = 1 ; i <= n ; ++ i )
        for ( j = m ; j >= 1 ; -- j )
            if ( ! a [ i ] [ j ] )
                dp [ 2 ] [ i ] [ j ] = dp [ 2 ] [ i ] [ j + 1 ] + 1 ;

    for ( j = 1 ; j <= m ; ++ j )
        for ( j1 = j + 1 ; j1 <= m ; ++ j1 )
        {
            stack < int > s ;
            amx1 = 0 ; amx2 = 0 ;

            /// Upper line

            dp [ 1 ] [ 0 ] [ j ] = - 1 ;
            s.push ( 0 ) ;

            for ( i = 1 ; i <= n ; ++ i )
            {
                while ( ! s.empty () && dp [ 1 ] [ i ] [ j ] <= dp [ 1 ] [ s.top () ] [ j ] )
                    s.pop () ;
                st [ i ] = s.top () ;
                s.push ( i ) ;
            }

            while ( ! s.empty () )
                s.pop () ;

            s.push ( n + 1 ) ;
            dp [ 1 ] [ n + 1 ] [ j ] = - 1 ;

            for ( i = n ; i >= 1 ; -- i )
            {
                while ( ! s.empty () && dp [ 1 ] [ i ] [ j ] <= dp [ 1 ] [ s.top () ] [ j ] )
                    s.pop () ;
                dr [ i ] = s.top () ;
                s.push ( i ) ;
            }

            for ( i = 1 ; i <= n ; ++ i )
                amx1 = max ( amx1 , ( dr [ i ] - st [ i ] - 1 ) * dp [ 1 ] [ i ] [ j ] ) ;

            while ( ! s.empty () )
                s.pop () ;

            ///Bottom line

            dp [ 2 ] [ 0 ] [ j1 ] = - 1 ;
            s.push ( 0 ) ;

            for ( i = 1 ; i <= n ; ++ i )
            {
                while ( ! s.empty () && dp [ 2 ] [ i ] [ j1 ] <= dp [ 2 ] [ s.top () ] [ j1 ] )
                    s.pop () ;
                st [ i ] = s.top () ;
                s.push ( i ) ;
            }

            while ( ! s.empty () )
                s.pop () ;

            s.push ( n + 1 ) ;
            dp [ 2 ] [ n + 1 ] [ j1 ] = - 1 ;

            for ( i = n ; i >= 1 ; -- i )
            {
                while ( ! s.empty () && dp [ 2 ] [ i ] [ j1 ] <= dp [ 2 ] [ s.top () ] [ j1 ] )
                    s.pop () ;
                dr [ i ] = s.top () ;
                s.push ( i ) ;
            }

            for ( i = 1 ; i <= n ; ++ i )
                amx2 = max ( amx2 , ( dr [ i ] - st [ i ] - 1 ) * dp [ 2 ] [ i ] [ j1 ] ) ;

            ans = max ( ans , amx1 + amx2 ) ;
        }

    return ans ;
}

int main()
{
    freopen ( "bmatrix.in" , "r" , stdin ) ;
    freopen ( "bmatrix.out" , "w" , stdout ) ;

    int n , m , i , j ;

    scanf ( "%d%d" , & n , & m ) ;

    for ( i = 1 ; i <= n ; ++ i )
        for ( j = 1 ; j <= m ; ++ j )
            scanf ( "%1d" , & a [ i ] [ j ] ) ;

    printf ( "%d" , solve ( n , m ) ) ;

    return 0;
}