Cod sursa(job #1904031)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 5 martie 2017 13:28:00
Problema BMatrix Scor 24
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <cstdio>
#include <stack>

using namespace std;

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, int a[205][205]) {
    /// 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() {
    int a[205][205], b[205][205];

    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);
    }
    //(1,1) (1,2)
    //(2,1) (2,2)

    //(1,1) (2,1)
    //(1,2) (2,2)
    /// Matricea b este transpusa lui A
    for(int i = 1; i <= m; ++ i) {
       for(int j = 1; j <= n; ++ j) {
	     b[i][j] = a[j][i];
       }
    }

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

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

    return 0;
}