Pagini recente » Cod sursa (job #1580586) | Cod sursa (job #1969855) | Cod sursa (job #266422) | Cod sursa (job #418803) | Cod sursa (job #1366957)
#include <cassert>
#include <cstdio>
const int nmax= 200;
int n, m;
int v[nmax+1][nmax+1];
int x[nmax+1], y[nmax+1], a[nmax+1];
int st[nmax+1];
inline int max( int x, int y ) {
if ( x>y ) return x;
return y;
}
void rotate( ) {
int aux[nmax+1][nmax+1];
for ( int i= 1; i<=n; ++i ) {
for ( int j= 1; j<=m; ++j ) {
aux[j][n-i+1]= v[i][j];
}
}
n= n+m; m= n-m; n= n-m;
for ( int i= 1; i<=n; ++i ) {
for ( int j= 1; j<=m; ++j ) {
v[i][j]= aux[i][j];
}
}
}
int maxarea( int x1, int x2 ) {
int ans= 0;
for ( int i= x1, cnt; i<=x2; ++i ) {
cnt= 0;
for ( int j= 1; j<=m; ++j ) {
if ( i==x1 ) a[j]= 0;
if ( v[i][j]==0 ) ++a[j];
else a[j]= 0;
for ( ; cnt>=1 && a[j]<=a[st[cnt]]; --cnt ) ;
if ( cnt==0 ) x[j]= 1;
else x[j]= st[cnt]+1;
st[++cnt]= j;
}
cnt= 0;
for ( int j= m; j>=1; --j ) {
for ( ; cnt>=1 && a[j]<=a[st[cnt]]; --cnt ) ;
if ( cnt==0 ) y[j]= m;
else y[j]= st[cnt]-1;
st[++cnt]= j;
ans= max(ans, a[j]*(y[j]-x[j]+1));
}
}
return ans;
}
int solve( ) {
int aux= 0;
for ( int k= 2; k<=n; ++k ) {
int max1= maxarea(1, k-1), max2= maxarea(k, n);
if ( max1*max2!=0 && aux<max1+max2 ) {
aux= max1+max2;
}
}
return aux;
}
int main( ) {
assert( freopen( "bmatrix.in", "r", stdin) );
assert( freopen( "bmatrix.out", "w", stdout ) );
assert( scanf( "%d%d\n", &n, &m ) );
for ( int i= 1; i<=n; ++i ) {
char s;
for ( int j= 1; j<=m; ++j ) {
assert( scanf( "%c", &s ) );
v[i][j]= s-'0';
}
assert( scanf( "%c", &s ) );
}
int sol1= solve(), sol2, sol;
rotate();
sol2= solve();
sol= max(sol1, sol2);
printf( "%d\n", sol );
return 0;
}