Pagini recente » Cod sursa (job #2171135) | Cod sursa (job #1630615) | Cod sursa (job #2840626) | Cod sursa (job #3187183) | Cod sursa (job #1813921)
# include <iostream>
# include <fstream>
# include <vector>
# include <algorithm>
# include <stack>
# include <cassert>
using namespace std;
# define MAX_N 200
int l1_1[1 + MAX_N + 1][1 + MAX_N + 1];
int l1_2[1 + MAX_N + 1][1 + MAX_N + 1];
int l2_1[1 + MAX_N + 1][1 + MAX_N + 1];
int l2_2[1 + MAX_N + 1][1 + MAX_N + 1];
char mat[1 + MAX_N + 1][1 + MAX_N + 1];
int s[1 + MAX_N + 1][1 + MAX_N + 1];
int dr_up[1 + MAX_N + 1];
int dr_dn[1 + MAX_N + 1];
int dr_lf[1 + MAX_N + 1];
int dr_rg[1 + MAX_N + 1];
int r[1 + MAX_N + 1];
int l[1 + MAX_N + 1];
int skyline( int n, int * h, int m )
{
static int r[1 + MAX_N + 1];
static int l[1 + MAX_N + 1];
int v[1 + MAX_N + 1];
v[0] = v[n + 1] = -1;
for ( int i = 1; i <= n; i ++ )
v[i] = min( m, h[i] );
static vector<int> s;
s.clear();
s.push_back( 0 );
for ( int i = 1; i <= n; i ++ ) {
while ( v[s.back()] >= v[i] )
s.pop_back();
l[i] = i - s.back();
s.push_back( i );
}
s.clear();
s.push_back( n + 1 );
for ( int i = n; i > 0; i -- ) {
while ( v[s.back()] >= v[i] )
s.pop_back();
r[i] = s.back() - i;
s.push_back( i );
}
int mx = 0;
for ( int i = 1; i <= n; i ++ )
mx = max( mx, min( m, v[i] ) * ( r[i] + l[i] - 1 ) );
return mx;
}
int main()
{
ifstream fin( "bmatrix.in" );
ofstream fout( "bmatrix.out" );
int n, m, k, i, j, mx;
char ch;
fin >> n >> m;
for ( i = 1; i <= n; i ++ ) {
for ( j = 1; j <= m; j ++ ) {
fin >> mat[i][j];
l1_1[i][j] = ( mat[i][j] == '0' ) * ( l1_1[i - 1][j] + 1 );
l2_1[j][i] = ( mat[i][j] == '0' ) * ( l2_1[j - 1][i] + 1 );
}
}
for ( i = n; i > 0; i -- ) {
for ( j = m; j > 0; j -- ) {
fin >> mat[i][j];
l1_2[i][j] = ( mat[i][j] == '0' ) * ( l1_2[i + 1][j] + 1 );
l2_2[j][i] = ( mat[i][j] == '0' ) * ( l2_2[j + 1][i] + 1 );
}
}
for ( i = 1; i <= n; i ++ )
dr_up[i] = max( dr_up[i - 1], skyline( m, l1_1[i], i ) );
for ( i = 1; i <= m; i ++ )
dr_lf[i] = max( dr_lf[i - 1], skyline( n, l2_1[i], i ) );
for ( i = n; i > 0; i -- )
dr_dn[i] = max( dr_dn[i + 1], skyline( m, l1_2[i], i ) );
for ( i = m; i > 0; i -- )
dr_rg[i] = max( dr_rg[i + 1], skyline( n, l2_2[i], i ) );
mx = 0;
for ( i = 1; i <= n; i ++ )
mx = max( mx, dr_up[i] + dr_dn[i + 1] );
for ( i = 1; i <= m; i ++ )
mx = max( mx, dr_lf[i] + dr_rg[i + 1] );
fout << mx;
fin.close();
fout.close();
return 0;
}