Cod sursa(job #1912476)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 8 martie 2017 09:13:05
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <cstdio>
#include <stack>

using namespace std;

int lin[205][205], col[205][205];
int v[205], st[205], dr[205];
char s[205];
stack <int> mystack;

void golesc_stiva() {
    while(!mystack.empty()) {
        mystack.pop();
    }
}

int drept_maxim(int i1, int i2, int n, int care) {
    int h = i2 - i1;
    if(care == 1) {
        for(int i = 1; i <= n; ++ i) {
            if(col[i2][i] > h) {
                v[i] = h;
            } else {
                v[i] = col[i2][i];
            }
        }
    } else {
        for(int i = 1; i <= n; ++ i) {
            if(lin[i][i2] > h) {
                v[i] = h;
            } else {
                v[i] = lin[i][i2];
            }
        }
    }

    v[0] = v[n + 1] = -1;

    golesc_stiva();
    mystack.push(0);
    for(int i = 1; i <= n; ++ i) {
        while(v[i] <= v[mystack.top()]) {
            mystack.pop();
        }
        st[i] = mystack.top();
        mystack.push(i);
    }

    golesc_stiva();
    mystack.push(n + 1);
    for(int i = n; i >= 1; -- i) {
        while(v[i] <= v[mystack.top()]) {
            mystack.pop();
        }
        dr[i] = mystack.top();
        mystack.push(i);
    }

    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);

    for(int i = 1; i <= n; ++ i) {
        gets(s + 1);
        for(int j = 1; j <= m; ++ j) {
            if(s[j] == '0') {
                lin[i][j] = lin[i][j - 1] + 1;
                col[i][j] = col[i - 1][j] + 1;
            }
        }
    }

    int rasp = 0;
    for(int i1 = 1; i1 < n; ++ i1) {
        for(int i2 = i1; i2 <= n; ++ i2) {
            int suma;
            suma = drept_maxim(0, i1, m, 1) + drept_maxim(i1, i2, m, 1);
            if(suma > rasp) {
                rasp = suma;
            }
        }
    }

    for(int j1 = 1; j1 < m; ++ j1) {
        for(int j2 = j1; j2 <= m; ++ j2) {
            int suma;
            suma = drept_maxim(0, j1, n, 0) + drept_maxim(j1, j2, n, 0);
            if(suma > rasp) {
                rasp = suma;
            }
        }
    }

    printf("%d", rasp);

    return 0;
}