Cod sursa(job #1459786)

Utilizator SmarandaMaria Pandele Smaranda Data 10 iulie 2015 19:01:26
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <cstdio>
#include <cstring>
#include <stack>

using namespace std;

const int N = 202;

int a [N][N], dp [N][N], st [N], dr [N], b [N][N];
char ch [N];
int n, m, ans1 [N], ans2 [N], ans3 [N], ans4 [N];
stack <pair <int, int> > s;

void solve (int ans []) {
    int i, j;

    for (j = 1; j <= m; j ++)
        dp [1][j] = 1 - a [1][j];
    for (i = 1; i <= n; i ++)
        for (j = 1; j <= m; j ++)
            if (a [i][j] == 0)
                dp [i][j] = dp [i - 1][j] + 1;
            else dp [i][j] = 0;
    for (i = 1; i <= n; i ++) {
        ans [i] = 0;
        while (!s.empty ())
            s.pop ();
        for (j = 1; j <= m; j ++) {
            while (!s.empty () && s.top ().first >= dp [i][j])
                s.pop ();
            if (s.empty ())
                st [j] = 1;
            else
                st [j] = s.top ().second  + 1;
            s.push (make_pair (dp [i][j], j));
        }
        while (!s.empty ())
            s.pop ();
        for (j = m; j >= 1; j --) {
            while (!s.empty () && s.top ().first >= dp [i][j])
                s.pop ();
            if (s.empty ())
                dr [j] = m;
            else
                dr [j] = s.top ().second  - 1;
            s.push (make_pair (dp [i][j], j));
        }
        for (j = 1; j <= m; j ++)
            if (st [j] <= dr [j] && a [i][j] == 0)
                ans [i] = max (ans [i], dp [i][j] * (dr [j] - st [j] + 1));
        ans [i] = max (ans [i], ans [i - 1]);
    }
}

void rotatie () {
    int i, j, aux;

    for (i = 1; i <= m; i ++)
        for (j = 1; j <= n; j ++)
            b [i][j] = a [n - j + 1][i];
    aux = m;
    m = n;
    n = aux;
    memcpy (a, b, sizeof (a));
}

int main () {
    int i, j, sol = 0, aux;

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

    scanf ("%d%d\n", &n, &m);
    for (i = 1; i <= n; i ++) {
        scanf ("%s", ch);
        for (j = 0; j < m; j ++)
            a [i][j + 1] = ch [j] - '0';
    }
    solve (ans1);
    rotatie ();
    solve (ans3);
    rotatie ();
    solve (ans2);
    rotatie();
    solve (ans4);
    aux = n;
    n = m;
    m = aux;
    for (i = 1; i < n; i ++) {
        sol = max (sol, ans1 [i] + ans2 [n - i]);
    }
    for (i = 1; i < m; i ++) {
        sol = max (sol, ans3 [i] + ans4 [m - i]);
    }
    printf ("%d\n", sol);
    return 0;
}