Pagini recente » Cod sursa (job #2216188) | Cod sursa (job #1366123) | Cod sursa (job #1511816) | Cod sursa (job #2262472) | Cod sursa (job #2527870)
#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;
}