Cod sursa(job #1903897)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 5 martie 2017 13:08:31
Problema BMatrix Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <cstdio>
#include <stack>

using namespace std;

int a[205][205];
int st[205], dr[205], v[205];

stack <int> stiva;

void golesc_Stiva() {
    while(!stiva.empty()) {
        stiva.pop();
    }
}

int dreptunghi_Maxim(int i1, int i2, int n) {
    /// O(n)
    /// [i1 - 1, i2]

    /// Vector de inaltimi
    v[0] = v[n + 1] = -1;
    int h;
    h = i2 - i1;
    for(int j = 1; j <= n; ++ j) {
        if(a[i2][j] > h)
            v[j] = h;
        else
            v[j] = a[i2][j];
    }

    /// Stanga
    golesc_Stiva();
    stiva.push(0);
    for(int i = 1; i <= n; ++ i) {
        while(v[stiva.top()] >= v[i]) {
            stiva.pop();
        }
        st[i] = stiva.top();
        stiva.push(i);
    }

    /// Dreapta
    golesc_Stiva();
    stiva.push(n + 1);
    for(int i = n; i >= 1; -- i) {
        while(v[stiva.top()] >= v[i]) {
            stiva.pop();
        }
        dr[i] = stiva.top();
        stiva.push(i);
    }

    /// Raspuns
    int rasp = 0;
    for(int i = 1; i <= n; ++ i) {
        int arie;
        arie = v[i] * ((dr[i] - 1) - (st[i] + 1) + 1);
        if(arie > rasp) {
            rasp = arie;
        }
    }

    return rasp;
}

int main() {
    freopen("bmatrix.in", "r", stdin);
    freopen("bmatrix.out", "w", stdout);

    int n, m;
    scanf("%d%d\n", &n, &m);

    ///Citire matrice + Suma de 0 pe coloana
    char c;
    for(int i = 1; i <= n; ++ i) {
        for(int j = 1; j <= m; ++ j) {
            c = getc(stdin);
            a[i][j] = 1 - (c - '0');

            if(a[i][j] == 1)
                a[i][j] += a[i - 1][j];
        }
        c = getc(stdin);
    }

    /*/// Debug-Open

    printf("%d", dreptunghi_Maxim(0, 2, m) + dreptunghi_Maxim(2, 5, m));
    return 0;
    /// Debug-Close */

    ///Fixez linia i1 si i2
    int rasp = 0;
    for(int i1 = 1; i1 < n; ++ i1) {
        for(int i2 = i1 + 1; i2 <= n; ++ i2) {
            int suma;
            suma = dreptunghi_Maxim(0, i1, m) + dreptunghi_Maxim(i1, i2, m);
            if(suma > rasp) {
                rasp = suma;
            }
        }
    }

    printf("%d\n", rasp);

    return 0;
}