Cod sursa(job #1532895)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 21 noiembrie 2015 19:12:35
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 200;

char a[kMaxN][kMaxN + 1];
char aux[kMaxN][kMaxN];

int st[kMaxN], ss;
int h[kMaxN + 1];
int lineDown[kMaxN], lineUp[kMaxN];
int columnDown[kMaxN], columnUp[kMaxN];

void histogramSolver(int n, int m, int d[]) {
    int q;
    for (int i = 0; i < n; i++) {
        q = 0;
        ss = 0;
        for (int j = 0; j <= m; j++) {
            if (j != m) {
                h[j] = (h[j] + 1) & -(a[i][j] == '0');
            } else {
                h[j] = 0;
            }
            while ((ss > 0) && (h[st[ss - 1]] > h[j])) {
                ss--;
                q = max(q, h[st[ss]] * (ss ? j - st[ss - 1] - 1 : j));
            }
            st[ss++] = j;
        }
        d[i] = (i == 0) ? q : max(d[i - 1], q);
    }
    for (int i = 0; i < m; i++) {
        h[i] = 0;
    }
}

void rotate90Degrees(int &n, int &m) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            aux[i][j] = a[n - j - 1][i];
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            a[i][j] = aux[i][j];
        }
    }
    swap(n, m);
}

int main(void) {
    ifstream in("bmatrix.in");
    ofstream out("bmatrix.out");
    int n, m, q;

    in >> n >> m;
    for (int i = 0; i < n; i++) {
        in >> a[i];
    }
    in.close();

    histogramSolver(n, m, lineUp);

    rotate90Degrees(n, m);
    histogramSolver(n, m, columnUp);

    rotate90Degrees(n, m);
    histogramSolver(n, m, lineDown);
    reverse(lineDown, lineDown + n);

    rotate90Degrees(n, m);
    histogramSolver(n, m, columnDown);
    reverse(columnDown, columnDown + n);

    q = 0;
    for (int i = 1; i < m; i++) {
        q = max(lineUp[i - 1] + lineDown[i], q);
    }
    for (int i = 1; i < n; i++) {
        q = max(columnUp[i - 1] + columnDown[i], q);
    }

    out << q << '\n';
    out.close();
    return 0;
}