Cod sursa(job #829830)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 5 decembrie 2012 21:39:39
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
long n , m , ans ;
long up [ 207 ] [ 207 ] , c[ 207 ] , d [ 207 ] , s[ 207 ] , st [ 207 ] , dr [ 207 ] ; // s = stiva
char a [ 207 ] [ 207 ] , b [ 207 ] [ 207 ] ;
void rotate_line ( long i )
{
    for (long j = 1 ; j <= m / 2 ; ++ j )
    {
        swap(a [ i ] [ j ] , a [ i ] [ m + 1 - j ] ) ;
        swap(up [ i ] [ j ] , up [ i ] [ m + 1 - j ] ) ;
    }//swapez
}
void rotate ( )
{
    memset(b, 0, sizeof(b));
    for (long i = 1 ; i <= n ; ++ i )
        for (long j = 1 ; j <= m ; ++ j )
            b[ j ] [ n - i + 1 ] = a [ i ] [ j ] ;
    swap( n , m ) ;
    memset ( a , 0 , sizeof ( a ) ) ;
    memcpy ( a , b , sizeof ( a ) ) ;
}
void get (long i , long v [ ] )
{
    memset ( v, 0, sizeof ( v ) ) ;
    memset ( s, 0, sizeof ( s ) ) ;
    for (long j = 1 ; j <= m ; ++ j )
    {
        s [ ++ s [ 0 ] ] = j ;
        v [ j ]  = j;
        while (s [ 0 ] > 1 && up [ i ] [ s [ s [ 0 ] - 1 ] ] >= up [ i ] [ s [ s [ 0 ] ] ] )
        {
            v[ j ] = min ( v [ j ] , v [ s [ s [ 0 ] - 1 ] ] ) ;
            s [ s [ 0 ] - 1 ] = s [ s [ 0 ] ] ;
            -- s [ 0 ] ;
        }
    }
}
void calcul ( long v [ ] )
{
    memset ( v , 0 , sizeof ( v ) ) ;
    memset ( up , 0 , sizeof ( up ) ) ;
    for (long i = 1 ; i <= n ; ++ i )
        for (long j = 1 ; j <= m ; ++ j )
            if (a [ i ] [ j ]  == '0')
                up [ i ] [ j ] = 1 + up [ i - 1 ] [ j ] ;
    for (long i = 1 ; i <= n ; ++ i )
    {
        get ( i , st ) ;
        rotate_line ( i ) ;
        get ( i , dr ) ;
        for (long j = 1 ; j <= m ; ++ j )
            dr [ j ] = m - dr [ j ]  + 1 ;
        for (long j = 1 ; j <= m / 2 ; ++ j )
            swap ( dr [ j ] , dr [ m - j + 1 ] ) ;
        rotate_line(i );
        v [ i ] = v[i - 1] ;
        for (long j = 1 ; j <= m ; ++ j )
            if (a [ i ] [ j ]  == '0')
                v [ i ] = max ( v [ i ] , up [ i ] [ j ]  * (dr[ j ]  - st[ j ]  + 1 ) ) ;
    }
}
void rotate2 ( )
{
    rotate ( ) ; rotate ( ) ;
}
void calc_2 ( )
{
    calcul ( c ) ;//calculez c
    rotate2 ( ) ;//rotesc
    calcul ( d ) ;//calculez d
    for (long i = 1 ; i <= n / 2 ; ++ i )
        swap ( d [ i ] , d [ n + 1 - i ] ) ;//swapez
    for (long i = 1 ; i < n ; ++ i )
        ans = max ( ans , c [ i ] + d [ i + 1 ] ) ;//raspuns maxim
}
long solve ( )
 {
    calc_2 ( ) ;
    rotate ( ) ;
    calc_2 ( ) ;
    return ans;
 }
int main (  )
{
    freopen ( "bmatrix.in" , "r" , stdin ) ;
    freopen ( "bmatrix.out" , "w" , stdout ) ;
    scanf ( "%ld %ld\n" , & n , & m ) ;
    for (long i = 1 ; i <= n ; ++ i )
    {
        gets ( a [ i ] + 1 ) ;
        a [ i ] [ 0 ] = ' ' ;
    }
    printf ( "%ld\n" , solve ( ) ) ;
    return 0;
}