Pagini recente » Cod sursa (job #2120420) | Cod sursa (job #61186) | Cod sursa (job #644561) | Cod sursa (job #1168661) | Cod sursa (job #1813899)
# include <iostream>
# include <fstream>
# include <vector>
# include <algorithm>
# include <stack>
# include <cassert>
using namespace std;
# define MAX_N 200
int l1[1 + MAX_N + 1][1 + MAX_N + 1];
int l2[1 + MAX_N + 1][1 + MAX_N + 1];
int mat[1 + MAX_N + 1][1 + MAX_N + 1];
int s[1 + MAX_N + 1][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 drept( int (*v)[1 + MAX_N + 1], int n, int m )
{
int i, j, mx;
mx = 0;
for ( i = 1; i <= n; i ++ ) {
mx = max( mx, skyline( m, v[i], i ) );
}
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 >> ch;
l1[i][j] = ( ch == '0' ) * ( l1[i - 1][j] + 1 );
l2[j][i] = ( ch == '0' ) * ( l2[j - 1][i] + 1 );
}
}
mx = 0;
for ( k = 1; k < n; k ++ )
mx = max( mx, drept( l1, k, m ) + drept( &l1[k], n - k, m ) );
for ( k = 1; k < m; k ++ )
mx = max( mx, drept( l2, k, n ) + drept( &l2[k], m - k, n ) );
fout << mx;
fin.close();
fout.close();
return 0;
}