Pagini recente » Cod sursa (job #3368243) | Cod sursa (job #3367894) | Cod sursa (job #3367893) | Cod sursa (job #3367353) | Cod sursa (job #3368247)
#include <fstream>
#include <stack>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int m, n, i, j, H[202], Max, max_sus[202], max_jos[202], max_stanga[202], max_dreapta[202];
bool mat[202][202];
char ch;
void resetareH() {
for ( int i = 1; i <= max(n, m); i++ )
H[i] = 0;
}
void actualizare_arie_max(stack<int>& stiva, int& j1, int& max_actual) {
int Top = stiva.top(), latime = j1 - 1;
stiva.pop();
if ( !stiva.empty() )
latime -= stiva.top();
max_actual = max(max_actual, H[Top] * latime);
}
int arie_max(int& n1) {
int max_actual = 0, j1 = 1;
stack<int> stiva;
while ( j1 <= n1 )
if ( stiva.empty() || H[stiva.top()] <= H[j1] )
stiva.push(j1++);
else
actualizare_arie_max(stiva, j1, max_actual);
while ( !stiva.empty() )
actualizare_arie_max(stiva, j1, max_actual);
return max_actual;
}
int main() {
fin >> m >> n;
for ( i = 1; i <= m; i++ )
for ( j = 1; j <= n; j++ ) {
fin >> ch;
mat[i][j] = ch - '0';
}
resetareH();
for ( i = 1; i <= m; i++ ) {
for ( j = 1; j <= n; j++ )
if ( !mat[i][j] )
H[j]++;
else
H[j] = 0;
max_sus[i] = max(max_sus[i-1], arie_max(n));
}
resetareH();
for ( i = m; i > 0; i-- ) {
for ( j = 1; j <= n; j++ )
if ( !mat[i][j] )
H[j]++;
else
H[j] = 0;
max_jos[i] = max(max_jos[i+1], arie_max(n));
}
resetareH();
for ( j = 1; j <= n; j++ ) {
for ( i = 1; i <= m; i++ )
if ( !mat[i][j] )
H[i]++;
else
H[i] = 0;
max_stanga[j] = max(max_stanga[j-1], arie_max(m));
}
resetareH();
for ( j = n; j > 0; j-- ) {
for ( i = 1; i <= m; i++ )
if ( !mat[i][j] )
H[i]++;
else
H[i] = 0;
max_dreapta[j] = max(max_dreapta[j+1], arie_max(m));
}
for ( i = 1; i < m; i++ )
Max = max(Max, max_sus[i] + max_jos[i+1]);
for ( j = 1; j < n; j++ )
Max = max(Max, max_stanga[j] + max_dreapta[j+1]);
fout << Max;
return 0;
}