Pagini recente » Cod sursa (job #596328) | Cod sursa (job #1187504) | Cod sursa (job #1795912) | Cod sursa (job #1811098) | Cod sursa (job #1806870)
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int n, m, a[205][205], d[205][205], sol, b[205][205];
int st[2][205];
char s[205];
int maximal_area( int i1, int i2, int j1, int j2 ){
int r = 0;
for( int i = i1; i <= i2; i++ ){
int maxim = 0;
int k = 0;
for( int j = j1; j <= j2; j++ ){
if( d[i][j] > st[0][k] ){
k++;
st[0][k] = d[i][j];
st[1][k] = j;
}else{
int pos = 0;
while( d[i][j] <= st[0][k] && k > 0 ){
if( maxim < st[0][k] * (j - st[1][k]) ){
maxim = st[0][k] * (j - st[1][k]);
}
pos = st[1][k];
k--;
}
if( d[i][j] != 0 ){
k++;
st[0][k] = d[i][j];
st[1][k] = pos;
}
}
}
while( k > 0 ){
if( maxim < st[0][k] * (j2 + 1 - st[1][k]) ){
maxim = st[0][k] * (j2 + 1 - st[1][k]);
}
k--;
}
r = max( r, maxim );
}
return r;
}
void rotesc_90(){
for( int i = 1; i <= n; i++ ){
for( int j = 1; j <= m; j++ ){
b[j][n - i + 1] = a[i][j];
}
}
memset( a, 0, sizeof(a) );
memcpy( a, b, sizeof(b) );
}
int main(){
fin >> n >> m;
for( int i = 1; i <= n; i++ ){
fin >> s;
for( int j = 1; j <= m; j++ ){
a[i][j] = (s[j - 1] - '0');
}
}
for( int i = 1; i <= n; i++ ){
for( int j = 1; j <= m; j++ ){
if( a[i][j] == 0 ){
d[i][j] = d[i - 1][j] + 1;
}
}
}
for( int j = 1; j < m; j++ ){
int aria = maximal_area( 1, n, 1, j ) + maximal_area( 1, n, j + 1, m );
sol = max( sol, aria );
}
rotesc_90();
memset( d, 0, sizeof(d) );
swap( n, m );
for( int i = 1; i <= n; i++ ){
for( int j = 1; j <= m; j++ ){
if( a[i][j] == 0 ){
d[i][j] = d[i - 1][j] + 1;
}
}
}
for( int j = 1; j < m; j++ ){
int aria = maximal_area( 1, n, 1, j ) + maximal_area( 1, n, j + 1, m );
sol = max( sol, aria );
}
fout << sol << "\n";
return 0;
}