Pagini recente » Cod sursa (job #867334) | Cod sursa (job #2428726) | Cod sursa (job #437144) | Cod sursa (job #33929) | Cod sursa (job #829830)
Cod sursa(job #829830)
#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;
}