Cod sursa(job #3368247)

Utilizator Cris21234123Cristian Cris21234123 Data 13 octombrie 2026 20:22:57
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.22 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];
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;
}