Cod sursa(job #2139412)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 22 februarie 2018 15:34:13
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.47 kb
#include <cstdio>
#include <stack>
#include <cstring>

using namespace std;

const int nmax = 200;

int n, m;
int h[5 + nmax], st[5 + nmax], dr[5 + nmax];
stack <int> myStack;
int dp[5][5 + nmax];
char a[5 + nmax][5 + nmax];

int calulareDp(int lin, int init, int incr, int d) {
    memset(h, 0, sizeof(h));
    if(lin) {
        h[0] = h[m + 1] = -1;
        for(int i = init; 1 <= i && i <= n; i += incr) {
            dp[d][i] = dp[d][i - incr];

            for(int j = 1; j <= m; ++ j) {
                if(a[i][j] == '0') {
                    h[j] ++;
                } else {
                    h[j] = 0;
                }
            }

            myStack.push(0);
            for(int j = 1; j <= m; ++ j) {
                while(h[j] <= h[myStack.top()]) {
                    myStack.pop();
                }
                st[j] = myStack.top() + 1;
                myStack.push(j);
            }
            while(!myStack.empty())
                myStack.pop();

            myStack.push(m + 1);
            for(int j = m; j >= 1; -- j) {
                while(h[j] <= h[myStack.top()]) {
                    myStack.pop();
                }
                dr[j] = myStack.top() - 1;
                myStack.push(j);
            }
            while(!myStack.empty())
                myStack.pop();

            for(int j = 1; j <= m; ++ j) {
                int arie = h[j] * (dr[j] - st[j] + 1);
                if(arie > dp[d][i]) {
                    dp[d][i] = arie;
                }
            }
        }
    } else {
        h[0] = h[n + 1] = -1;
        for(int j = init; 1 <= j && j <= m; j += incr) {
            dp[d][j] = dp[d][j - incr];

            for(int i = 1; i <= n; ++ i) {
                if(a[i][j] == '0') {
                    h[i] ++;
                } else {
                    h[i] = 0;
                }
            }

            myStack.push(0);
            for(int i = 1; i <= n; ++ i) {
                while(h[i] <= h[myStack.top()]) {
                    myStack.pop();
                }
                st[i] = myStack.top() + 1;
                myStack.push(i);
            }
            while(!myStack.empty())
                myStack.pop();

            myStack.push(n + 1);
            for(int i = n; i >= 1; -- i) {
                while(h[i] <= h[myStack.top()]) {
                    myStack.pop();
                }
                dr[i] = myStack.top() - 1;
                myStack.push(i);
            }
            while(!myStack.empty())
                myStack.pop();

            for(int i = 1; i <= n; ++ i) {
                int arie = h[i] * (dr[i] - st[i] + 1);
                if(arie > dp[d][j]) {
                    dp[d][j] = arie;
                }
            }
        }
    }
}

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

    int maxim = 0;

    scanf("%d%d\n", &n, &m);
    for(int i = 1; i <= n; ++ i) {
        gets(a[i] + 1);
    }

    calulareDp(1, 1, 1, 1);
    calulareDp(1, n, -1, 2);

    for(int i = 1; i <= n; ++ i) {
        if(maxim < dp[1][i] + dp[2][i + 1]) {
            maxim = dp[1][i] + dp[2][i + 1];
        }
    }

    calulareDp(0, 1, 1, 1);
    calulareDp(0, m, -1, 2);

    for(int j = 1; j <= m; ++ j) {
        if(maxim < dp[1][j] + dp[2][j + 1]) {
            maxim = dp[1][j] + dp[2][j + 1];
        }
    }

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

    return 0;
}