Pagini recente » Cod sursa (job #1633302) | Istoria paginii runda/kys | Cod sursa (job #1633430) | Cod sursa (job #365230) | Cod sursa (job #334584)
Cod sursa(job #334584)
#include <algorithm>
using namespace std;
#define DIM 201
int n, m, rez, max0, max1, a[ DIM ][ DIM ], z[ DIM ][ DIM ], sol0[ DIM ][ DIM ], sol1[ DIM ][ DIM ];
void calc_sol0() {
int i, j, k, zero;
for( i = 1; i <= n; ++ i )
for( j = 1; j <= m; ++ j )
if( !a[ i ][ j ] ) {
zero = z[ i ][ j ] = z[ i ][ j - 1 ] + 1;
for( k = i; k > 0 && !a[ k ][ j ]; -- k ) {
zero = min( zero, z[ k ][ j ] );
sol0[ i ][ j ] = max( sol0[ i ][ j ], zero * ( i - k + 1 ) );
}
}
}
void calc_sol1() {
int i, j, k, zero;
for( i = n; i > 0; -- i )
for( j = m; j > 0; -- j )
if( !a[ i ][ j ] ) {
zero = z[ i ][ j ] = z[ i ][ j + 1 ] + 1;
for( k = i; k <= n && !a[ k ][ j ]; ++ k ) {
zero = min( zero, z[ k ][ j ] );
sol1[ i ][ j ] = max( sol1[ i ][ j ], zero * ( k - i + 1 ) );
}
}
}
void read() {
int i, j;
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';
}
}
void solve() {
int i, j, k;
calc_sol0();
calc_sol1();
for( k = 2; k <= n; ++ k ) {
max0 = max1 = 0;
for( i = 1; i < k; ++ i )
for( j = 1; j <= m; ++ j )
max0 = max( max0, sol0[ i ][ j ] );
for( i = k; i <= n; ++ i )
for( j = 1; j <= m; ++ j )
max1 = max( max1, sol1[ i ][ j ] );
rez = max( rez, max0 + max1 );
}
for( k = 2; k <= m; ++ k ) {
max0 = max1 = 0;
for( i = 1; i <= n; ++ i )
for( j = 1; j < k; ++ j )
max0 = max( max0, sol0[ i ][ j ] );
for( i = 1; i <= n; ++ i )
for( j = k; j <= m; ++ j )
max1 = max( max1, sol1[ i ][ j ] );
rez = max( rez, max0 + max1 );
}
printf( "%d", rez );
}
int main() {
freopen( "bmatrix.in", "r", stdin );
freopen( "bmatrix.out", "w", stdout );
read();
solve();
return 0;
}