Cod sursa(job #798088)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 15 octombrie 2012 18:46:36
Problema BMatrix Scor 24
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.83 kb
#include <cassert>
#include <cstdio>
#include <cstring>

#include <algorithm>

using namespace std;

struct bmatrix {
    int x, y;

    bmatrix() {
        x = y = 0;
    }

    bmatrix(int x, int y) {
        this->x = x;
        this->y = y;
    }
};

const int N = 205;

int n, m, head;
int a[N][N];
int up[N], left[N], up2[N], left2[N];
bmatrix stack[N];
char mat[N][N], mat2[N][N];

void read() {
    assert(freopen("bmatrix.in", "r", stdin) != NULL);
    assert(freopen("bmatrix.out", "w", stdout) != NULL);

    assert(scanf("%d %d", &n, &m) == 2);
    for (int i = 1; i <= n; ++i)
        assert(scanf("%s", mat[i] + 1) == 1);
}

void zero() {
    memset(a, 0, sizeof(a));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (mat[i - 1][j] == '0')
                a[i][j] = a[i - 1][j] + 1;
            else
                a[i][j] = 0;
        }
}

int dr(int x) {
    int maxSol = 0, left;
    stack[head = 1] = bmatrix(a[x][1], 1);
    for (int i = 2; i <= m; ++i) {
        left = i;
        while (head > 0 && stack[head].x >= a[x][i]) {
            left = stack[head].y;
            maxSol = max(maxSol, (i - stack[head].y) * stack[head].x);
            --head;
        }
        stack[++head] = bmatrix(a[x][i], left);
    }

    while (head > 0) {
        maxSol = max(maxSol, (m + 1 - stack[head].y) * stack[head].x);
        --head;
    }

    return maxSol;
}

void preproc(int v[]) {
    memset(v, 0, sizeof(v));
    for (int i = 1; i <= n + 1; ++i)
        v[i] = max(v[i - 1], dr(i));
}

void rotate() {
    memset(mat2, 0, sizeof(mat2));
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            mat2[i][j] = mat[n - j + 1][i];
    //memcpy(mat, mat2, sizeof(mat2));
    memset(mat, 0, sizeof(mat));
    swap(n, m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            mat[i][j] = mat2[i][j];
    /*for (int i = 1; i <= n; ++i, printf("\n"))
        for (int j = 1; j <= m; ++j)
            printf("%c", mat[i][j]);*/
}

int main() {
    read();
    zero();
    preproc(up);
    /*for (int i = 1; i <= n + 1; ++i)
        printf("%d ", up[i]);
    printf("\n");*/
    rotate();
    zero();
    preproc(left);
    /*for (int i = 1; i <= n + 1; ++i)
        printf("%d ", left[i]);
    printf("\n");*/
    rotate();
    zero();
    preproc(up2);
    /*for (int i = 1; i <= n + 1; ++i)
        printf("%d ", up2[i]);
    printf("\n");*/
    rotate();
    zero();
    preproc(left2);
    /*for (int i = 1; i <= n + 1; ++i)
        printf("%d ", left2[i]);*/
    int sol = 0;
    for (int i = 1; i <= n + 1; ++i)
        if (up[i] > 0 && up2[n - i + 1] > 0)
            sol = max(sol, up[i] + up2[n - i + 1]);
    //printf("%d\n", sol);
    for (int i = 1; i <= n + 1; ++i)
        if (left[i] > 0 && left2[i] > 0)
        sol = max(sol, left[i] + left2[n - i + 1]);
    printf("%d\n", sol);
}