Pagini recente » Cod sursa (job #812708) | Cod sursa (job #2448228) | Cod sursa (job #2774968) | Cod sursa (job #816351) | Cod sursa (job #2712839)
#include <fstream>
#include <algorithm>
#include <stack>
using namespace std;
ifstream fin( "bmatrix.in" );
ofstream fout( "bmatrix.out" );
const int Lim = 202;
int M[Lim][Lim];
int d[Lim][Lim];
int l[Lim], r[Lim];
stack<int> s;
int n, m, line;
inline void getLR() {
for ( int i = 1; i <= m; ++i ) {
l[i] = 0;
r[i] = 0;
}
for ( int i = 1; i <= m; ++i ) {
while ( s.size() && d[line][s.top()] > d[line][i] ) {
r[s.top()] = i;
s.pop();
}
s.push( i );
}
while ( s.size() ) s.pop();
for ( int i = m; i >= 1; --i ) {
while ( s.size() && d[line][s.top()] > d[line][i] ) {
l[s.top()] = i;
s.pop();
}
s.push( i );
}
while ( s.size() ) s.pop();
for ( int i = 1; i <= m; ++i ) {
if ( !r[i] ) {
r[i] = m + 1;
}
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
inline void MaxAreas( int mx[] ) {
for ( int i = 1; i <= n; ++i ) {
for (int j = 1; j <= m; ++j ) {
d[i][j] = 0;
}
}
for ( int i = 1; i <= n; ++i ) {
for ( int j = 1; j <= m; ++j ) {
if ( M[i][j] == 0 ) {
if ( i != 1 ) {
d[i][j] = d[i - 1][j] + 1;
} else {
d[i][j] = 1;
}
}
}
}
for ( int i = 1; i <= n; ++i ) {
mx[i] = 0;
}
for ( int i = 1; i <= n; ++i ) {
line = i;
getLR();
mx[i] = mx[i - 1];
for ( int j = 1; j <= m; ++j ) {
mx[i] = max( mx[i], (r[j] - l[j] - 1) * d[i][j] );
}
}
}
char str[Lim];
int aux[Lim][Lim];
inline void rotateRight() {
for ( int i = 1; i <= n; ++i ) {
for ( int j = 1; j <= m; ++j ) {
aux[j][n - i + 1] = M[i][j];
}
}
swap( m, n );
for ( int i = 1; i <= n; ++i ) {
for ( int j = 1; j <= m; ++j ) {
M[i][j] = aux[i][j];
}
}
}
int line_best_left[Lim];
int line_best_right[Lim];
int col_best_left[Lim];
int col_best_right[Lim];
int main() {
int mx;
fin >> n >> m;
for ( int i = 1; i <= n; ++i ) {
fin >> str;
for ( int j = 1; j <= m; ++j ) {
M[i][j] = str[j - 1] - '0';
}
}
mx = 0;
MaxAreas( line_best_left );
rotateRight(), rotateRight();
MaxAreas( line_best_right );
rotateRight();
MaxAreas( col_best_left );
rotateRight(), rotateRight();
MaxAreas( col_best_right );
rotateRight(), rotateRight(), rotateRight();
for ( int i = 1; i < n; ++i ) {
if ( mx < line_best_left[i] + line_best_right[n - i] ) {
mx = line_best_left[i] + line_best_right[n - i];
}
}
for ( int i = 1; i < m; ++i ) {
if ( mx < col_best_left[i] + col_best_right[m - i] ) {
mx = col_best_left[i] + col_best_right[m - i];
}
}
fout << mx;
fin.close();
fout.close();
return 0;
}