Pagini recente » Cod sursa (job #931544) | Clasament ONI 2018, Clasele 11-12 | Cod sursa (job #2441679) | Istoria paginii runda/28_februarie_simulare_oji_2024_clasele_11_12/clasament | Cod sursa (job #333604)
Cod sursa(job #333604)
# include <algorithm>
using namespace std;
# define DIM 201
int n, m, rez, max0, max1, a[ DIM ][ DIM ], z[ DIM ][ DIM ];
void init () {
int i, j;
for ( i = 1; i <= n; ++ i )
for ( j = 1; j <= m; ++ j )
z[ i ][ j ] = 0;
}
void solve () {
int c, i, j, k, l, zero;
char s[ DIM ];
scanf ( "%d%d\n", &n, &m );
for ( i = 1; i <= n; ++ i ) {
gets ( s );
for ( j = 1; j <= m; ++ j )
a[ i ][ j ] = s[ j - 1 ] - '0';
}
for ( l = 2; l <= n; ++ l ) {
init ();
max0 = max1 = 0;
for ( i = 1; i < l; ++ i )
for ( j = 1; j <= m; ++ j )
if ( !a[ i ][ j ] ) {
if ( !a[ i ][ j - 1 ] )
z[ i ][ j ] = z[ i ][ j - 1 ] + 1;
else
z[ i ][ j ] = 1;
zero = z[ i ][ j ];
for ( k = i; k > 0 && !a[ k ][ j ]; -- k )
max0 = max ( max0, ( i - k + 1 ) * min ( zero, z[ k ][ j ] ) );
}
for ( i = l; i <= n; ++ i )
for ( j = 1; j <= m; ++ j )
if ( !a[ i ][ j ] ) {
if ( !a[ i ][ j - 1 ] )
z[ i ][ j ] = z[ i ][ j - 1 ] + 1;
else
z[ i ][ j ] = 1;
zero = z[ i ][ j ];
for ( k = i; k >= l && !a[ k ][ j ]; -- k )
max1 = max ( max1, ( i - k + 1 ) * min ( zero, z[ k ][ j ] ) );
}
if ( max0 + max1 > rez )
rez = max0 + max1;
}
for ( c = 2; c <= m; ++ c ) {
init ();
max0 = max1 = 0;
for ( i = 1; i <= n; ++ i )
for ( j = 1; j < l; ++ j )
if ( !a[ i ][ j ] ) {
if ( !a[ i ][ j - 1 ] )
z[ i ][ j ] = z[ i ][ j - 1 ] + 1;
else
z[ i ][ j ] = 1;
zero = z[ i ][ j ];
for ( k = i; k > 0 && !a[ k ][ j ]; -- k )
max0 = max ( max0, ( i - k + 1 ) * min ( zero, z[ k ][ j ] ) );
}
for ( i = 1; i <= n; ++ i )
for ( j = l; j <= m; ++ j )
if ( !a[ i ][ j ] ) {
if ( !a[ i ][ j - 1 ] )
z[ i ][ j ] = z[ i ][ j - 1 ] + 1;
else
z[ i ][ j ] = 1;
zero = z[ i ][ j ];
for ( k = i; k >= l && !a[ k ][ j ]; -- k )
max1 = max ( max1, ( i - k + 1 ) * min ( zero, z[ k ][ j ] ) );
}
if ( max0 + max1 > rez )
rez = max0 + max1;
}
printf ( "%d", rez );
}
int main () {
freopen ( "bmatrix.in", "r", stdin );
freopen ( "bmatrix.out", "w", stdout );
solve ();
return 0;
}