Cod sursa(job #3148100)

Utilizator SSKMFSS KMF SSKMF Data 29 august 2023 13:32:09
Problema BMatrix Scor 8
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <fstream>
using namespace std;

ifstream cin ("bmatrix.in");
ofstream cout ("bmatrix.out");

int maxim[2][202] , adancime[201];
char matrice[201][201];

void DeterminareArie (int linie , int indice , int coloane)
{
    int optiuni[201] , stanga[201]; optiuni[0] = 0;
    for (int coloana = 1 ; coloana <= coloane ; coloana++)
    {
        adancime[coloana] = (matrice[linie][coloana - 1] == '0' ? adancime[coloana] + 1 : 0);

        while (optiuni[0] && adancime[coloana] <= adancime[optiuni[optiuni[0]]])
            optiuni[0]--;

        stanga[coloana] = optiuni[optiuni[0]] + 1;
        optiuni[++optiuni[0]] = coloana;
    }

    optiuni[0] = 0;

    for (int coloana = coloane ; coloana ; coloana--)
    {
        while (optiuni[0] && adancime[coloana] <= adancime[optiuni[optiuni[0]]])
            optiuni[0]--;

        const int dreapta = (optiuni[0] ? optiuni[optiuni[0]] - 1 : coloane);
        maxim[indice][linie] = max(maxim[indice][linie] , (dreapta - stanga[coloana] + 1) * adancime[coloana]);
        optiuni[++optiuni[0]] = coloana;
    }
}

int main ()
{
    int linii , coloane;
    cin >> linii >> coloane;

    for (int linie = 1 ; linie <= linii ; linie++)
        { cin >> matrice[linie]; DeterminareArie(linie , 0 , coloane); }

    for (int linie = linii ; linie ; linie--)
        DeterminareArie(linie , 1 , coloane);
    
    int arie_maxima = 0;
    for (int linie = 0 ; linie <= linii ; linie++)
        arie_maxima = max(arie_maxima , maxim[0][linie] + maxim[1][linie + 1]);

    cout << arie_maxima;
    cout.close(); cin.close();
    return 0;
}