Cod sursa(job #828219)

Utilizator savimSerban Andrei Stan savim Data 3 decembrie 2012 14:01:18
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.94 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX_N = 210;

int N, M, ans;

int up[MAX_N][MAX_N];

int c[MAX_N], d[MAX_N], stack[MAX_N], st[MAX_N], dr[MAX_N];

char A[MAX_N][MAX_N], B[MAX_N][MAX_N];

void rotate_line(int i) {
    for (int j = 1; j <= M / 2; j++) {
        swap(A[i][j], A[i][M + 1 - j]);
        swap(up[i][j], up[i][M + 1 - j]);
    }
}

void rotate() {
    memset(B, 0, sizeof(B));

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            B[j][N - i + 1] = A[i][j];
    swap(N, M);

    memset(A, 0, sizeof(A));
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            A[i][j] = B[i][j];
}

void get_ans() {
    for (int i = 1; i < N; i++)
        ans = max(ans, c[i] + d[i + 1]);
}

void get_values(int i, int V[]) {
    memset(V, 0, sizeof(int) * MAX_N);
    memset(stack, 0, sizeof(stack));

    for (int j = 1; j <= M; j++) {
        stack[++stack[0]] = j;

        //printf("*****%d\n", j);
        //printf("%d %d   %d %d\n", stack[stack[0]], up[i][stack[stack[0]]], stack[stack[0] - 1], up[i][stack[stack[0] - 1]]);

        V[j] = j;
        while (stack[0] > 1 && up[i][stack[stack[0] - 1]] >= up[i][stack[stack[0]]]) {
            V[j] = min(V[j], V[stack[stack[0] - 1]]);
            stack[stack[0] - 1] = stack[stack[0]];
            stack[0]--;
        }
    }
}

void compute(int V[]) {
    memset(V, 0, sizeof(int) * MAX_N);
    memset(up, 0, sizeof(up));

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            if (A[i][j] == '0')
                up[i][j] = 1 + up[i - 1][j];

    for (int i = 1; i <= N; i++) {
        get_values(i, st);
        rotate_line(i);

        get_values(i, dr);
        for (int j = 1; j <= M; j++)
            dr[j] = M - dr[j] + 1;
        for (int j = 1; j <= M / 2; j++)
            swap(dr[j], dr[M - j + 1]);
        rotate_line(i);


        /*printf("**** %d\n", i);
        for (int j = 1; j <= M; j++)
            printf("%d ", st[j]);
        printf("\n");
        for (int j = 1; j <= M; j++)
            printf("%d ", dr[j]);
        printf("\n\n");*/

        V[i] = V[i - 1];
        for (int j = 1; j <= M; j++)
            if (A[i][j] == '0')
                V[i] = max(V[i], up[i][j] * (dr[j] - st[j] + 1));
    }
}

int main() {

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

    scanf("%d %d\n", &N, &M);
    for (int i = 1; i <= N; i++) {
        scanf("%s", A[i] + 1);
        A[i][0] = ' ';
    }

    compute(c);
    rotate(); rotate();
    compute(d);
    for (int i = 1; i <= N / 2; i++)
        swap(d[i], d[N + 1 - i]);
    get_ans();

    rotate();
    compute(c);
    rotate(); rotate();
    compute(d);
    for (int i = 1; i <= N / 2; i++)
        swap(d[i], d[N + 1 - i]);
    get_ans();

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

    return 0;
}