Cod sursa(job #3368243)

Utilizator Cris21234123Cristian Cris21234123 Data 13 octombrie 2026 18:30:17
Problema BMatrix Scor 28
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.86 kb
#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];
stack<int> stiva;
bool mat[202][202];
char ch;
void resetareH() {
    for ( int i = 1; i <= max(n, m); i++ )
        H[i] = 0;
}
int limita(int& i) {
    int l = 1;
    while ( !stiva.empty() && H[stiva.top()] >= H[i] )
        stiva.pop();
    if ( !stiva.empty() )
        l = stiva.top();
    stiva.push(i);
    return ( i - l ) * H[i];
}
int main() {
    fin >> m >> n;
    for ( i = 1; i <= m; i++ ) {
        max_sus[i] = max_sus[i-1];
        for ( j = 1; j <= n; j++ ) {
            fin >> ch;
            mat[i][j] = ch - '0';
            H[j]++;
            if ( mat[i][j] )
                H[j] = 0;
            max_sus[i] = max(max_sus[i], limita(j));
        }
    }
    resetareH();
    for ( i = m; i > 0; i-- ) {
        max_jos[i] = max_jos[i+1];
        for ( j = 1; j <= n; j++ ) {
            H[j]++;
            if ( mat[i][j] )
                H[j] = 0;
            max_jos[i] = max(max_jos[i], limita(j));
        }
    }
    resetareH();
    for ( j = 1; j <= n; j++) {
        max_stanga[j] = max_stanga[j-1];
        for ( i = 1; i <= m; i++ ) {
            H[i]++;
            if ( mat[i][j] )
                H[i] = 0;
            max_stanga[j] = max(max_stanga[j], limita(i));
        }
    }
    resetareH();
    for ( j = n; j > 0; j-- ) {
        max_dreapta[j] = max_dreapta[j+1];
        for ( i = 1; i <= m; i++ ) {
            H[i]++;
            if ( mat[i][j] )
                H[i] = 0;
            max_dreapta[j] = max(max_dreapta[j], limita(i));
        }
    }
    for ( i = 1; i <= m; i++ )
        for ( j = 1; j <= n; j++ )
            Max = max(Max, max(max_sus[i] + max_jos[i+1], max_stanga[j] + max_dreapta[j+1]));
    fout << Max;
    return 0;
}