Pagini recente » Rating Lodina Razan (RaKaRe99) | Monitorul de evaluare | Cod sursa (job #1924317) | Cod sursa (job #1444188) | Cod sursa (job #2527874)
#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 ] ;
int areas [ 5 ] [ NMAX + 5 ] ;
/// dp [ 1 ] -> stanga - dreapta
/// dp [ 2 ] -> dreapta - stanga
/// dp [ 1 ] -> sus - jos
/// dp [ 2 ] -> jos - sus
inline int do_that_shit_bruh ( int n, int m )
{
int i, i1, j, j1, amx = 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 )
{
stack < int > s ;
amx = 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 )
amx = max ( amx, ( dr [ j ] - st [ j ] - 1 ) * dp [ 1 ] [ i ] [ j ] ) ;
areas [ 1 ] [ i ] = amx ;
amx = 0 ;
while ( ! s.empty () )
s.pop () ;
///Bottom line
dp [ 2 ] [ i ] [ 0 ] = - 1 ;
s.push ( 0 ) ;
for ( j = 1 ; j <= m ; ++ j )
{
while ( ! s.empty () && dp [ 2 ] [ i ] [ j ] <= dp [ 2 ] [ i ] [ s.top () ] )
s.pop () ;
st [ j ] = s.top () ;
s.push ( j ) ;
}
while ( ! s.empty () )
s.pop () ;
s.push ( m + 1 ) ;
dp [ 2 ] [ i ] [ m + 1 ] = - 1 ;
for ( j = m ; j >= 1 ; -- j )
{
while ( ! s.empty () && dp [ 2 ] [ i ] [ j ] <= dp [ 2 ] [ i ] [ s.top () ] )
s.pop () ;
dr [ j ] = s.top () ;
s.push ( j ) ;
}
for ( j = 1 ; j <= m ; ++ j )
amx = max ( amx, ( dr [ j ] - st [ j ] - 1 ) * dp [ 2 ] [ i ] [ j ] ) ;
areas [ 2 ] [ i ] = amx ;
}
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 )
{
stack < int > s ;
amx = 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 )
amx = max ( amx , ( dr [ i ] - st [ i ] - 1 ) * dp [ 1 ] [ i ] [ j ] ) ;
areas [ 3 ] [ j ] = amx ;
amx = 0 ;
while ( ! s.empty () )
s.pop () ;
///Bottom line
dp [ 2 ] [ 0 ] [ j ] = - 1 ;
s.push ( 0 ) ;
for ( i = 1 ; i <= n ; ++ i )
{
while ( ! s.empty () && dp [ 2 ] [ i ] [ j ] <= dp [ 2 ] [ s.top () ] [ j ] )
s.pop () ;
st [ i ] = s.top () ;
s.push ( i ) ;
}
while ( ! s.empty () )
s.pop () ;
s.push ( n + 1 ) ;
dp [ 2 ] [ n + 1 ] [ j ] = - 1 ;
for ( i = n ; i >= 1 ; -- i )
{
while ( ! s.empty () && dp [ 2 ] [ i ] [ j ] <= dp [ 2 ] [ s.top () ] [ j ] )
s.pop () ;
dr [ i ] = s.top () ;
s.push ( i ) ;
}
for ( i = 1 ; i <= n ; ++ i )
amx = max ( amx , ( dr [ i ] - st [ i ] - 1 ) * dp [ 2 ] [ i ] [ j ] ) ;
areas [ 4 ] [ j ] = amx ;
amx = 0 ;
}
for ( i = 1 ; i <= n ; ++ i )
for ( i1 = i + 1 ; i1 <= n ; ++ i1 )
ans = max ( ans , areas [ 1 ] [ i ] + areas [ 2 ] [ i1 ] ) ;
for ( j = 1 ; j <= m ; ++ j )
for ( j1 = j + 1 ; j1 <= m ; ++ j1 )
ans = max ( ans , areas [ 3 ] [ j ] + areas [ 4 ] [ j1 ] ) ;
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", do_that_shit_bruh ( n, m ) ) ;
return 0;
}