Cod sursa(job #3148110)

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

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

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

void DeterminareArie (int pivot , int indice , int linii , int coloane , bool vertical)
{
    int optiuni[201] , stanga[201]; optiuni[0] = 0;
    for (int indice = 1 ; indice <= (vertical ? linii : coloane) ; indice++)
    {
        adancime[indice] = ((vertical ? matrice[indice][pivot] : matrice[pivot][indice]) == '0' ? adancime[indice] + 1 : 0);

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

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

    optiuni[0] = 0;

    for (int coloana = (vertical ? linii : 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][pivot] = max(maxim[indice][pivot] , (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 , linii , coloane , false); }

    for (int indice = 1 ; indice <= coloane ; indice++)
        adancime[indice] = 0;

    for (int linie = linii ; linie ; linie--)
        DeterminareArie(linie , 1 , linii , coloane , false);

    for (int indice = 1 ; indice <= coloane ; indice++)
        adancime[indice] = 0;

    for (int coloana = 1 ; coloana <= coloane ; coloana++)
        DeterminareArie(coloana , 2 , linii , coloane , true);

    for (int indice = 1 ; indice <= linii ; indice++)
        adancime[indice] = 0;

    for (int coloana = coloane ; coloana ; coloana--)
        DeterminareArie(coloana , 3 , linii , coloane , true);
    
    int arie_maxima = 0;
    for (int indice = 0 ; indice <= linii ; indice++)
        arie_maxima = max(arie_maxima , max(maxim[0][indice] + maxim[1][indice + 1] , maxim[2][indice] + maxim[3][indice + 1]));

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