Pagini recente » Cod sursa (job #2433955) | Cod sursa (job #301131) | Cod sursa (job #1050909) | Cod sursa (job #2269882) | Cod sursa (job #1367140)
#include <fstream>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int nmax= 200;
int n, m, sol;
int x[nmax+1], y[nmax+1], a[nmax+1];
int st[nmax+1];
char v[nmax+1][nmax+1], aux[nmax+1][nmax+1];
void rotate( ) {
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 j= 1; j<=m; ++j ) a[j]= 0;
for ( int i= x1, cnt; i<=x2; ++i ) {
cnt= 0; st[0]= 0;
for ( int j= 1; j<=m; ++j ) {
a[j]= (1-(v[i][j]-'0'))*(a[j]+1);
for ( ; cnt>=1 && a[j]<=a[st[cnt]]; --cnt ) ;
x[j]= st[cnt]+1;
st[++cnt]= j;
}
cnt= 0; st[0]= m+1;
for ( int j= m; j>=1; --j ) {
for ( ; cnt>=1 && a[j]<=a[st[cnt]]; --cnt ) ;
y[j]= st[cnt]-1;
st[++cnt]= j;
ans= max(ans, a[j]*(y[j]-x[j]+1));
}
}
return ans;
}
void 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;
}
}
sol= max(sol, aux);
}
int main( ) {
fin>>n>>m;
for ( int i= 1; i<=n; ++i ) {
fin>>v[i]+1;
}
solve();
rotate();
solve();
fout<<sol<<"\n";
return 0;
}