Cod sursa(job #1946646)

Utilizator xraven78Eduard Mihes xraven78 Data 30 martie 2017 12:10:11
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <algorithm>
#include <fstream>
#include <iostream>
using namespace std;

int a[255][255],aux[255][255],up[255],down[255],c[255][255],l[255],r[255],st[255];

char s[255];

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

void dump(int matrix[255][255], int n, int m) {
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            cout << matrix[i][j] << " ";
        }
        cout << "\n";
    }
}

int soldiers_row(int a[255], int n) {
    int k = 0; st[0] = 0;
    for (int i = 1; i <= n; ++ i) {
        while (k > 0 && a[st[k]] >= a[i]) {
            -- k;
        }
        l[i] = st[k];
        st[++ k] = i;
    }

    k = 0; st[0] = n + 1;
    for (int i = n; i >= 1; -- i) {
        while (k > 0 && a[st[k]] >= a[i]) {
            -- k;
        }
        r[i] = st[k];
        st[++ k] = i;
    }

    int answer = 0;
    for (int i = 1; i <= n; ++ i) {
        answer = max(answer, a[i] * (r[i] - l[i] - 1));
    }
    return answer;
}

void get_up_array(int n, int m, int up[255]) {
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            if (a[i][j] == 0) {
                c[i][j] = c[i - 1][j] + 1;
            } else {
                c[i][j] = 0;
            }
        }
    }
    for (int i = 1; i <= n; ++ i) {
        up[i] = max(up[i - 1], soldiers_row(c[i], m));
    }
}

int solve(int n, int m) {
    get_up_array(n, m, up);
    rotate_matrix(n, m);
    rotate_matrix(n, m);
    get_up_array(n, m, down);
    reverse(down + 1, down + n + 1);
    int answer = 0;
    for (int i = 1; i < n; ++ i) {
        answer = max(answer, up[i] + down[i + 1]);
    }
    return answer;
}

int main() {
    ifstream f("bmatrix.in");
    ofstream g("bmatrix.out");
    int n, m;
    f>>n>>m;
    for (int i = 1; i <= n; ++ i) {
        f>>s;
        for (int j = 1; j <= m; ++ j) {
            a[i][j] = s[j - 1] - '0';
        }
    }
    int answer = solve(n, m);
    rotate_matrix(n, m);
    answer = max(answer, solve(n, m));
    g << answer << "\n";
    return 0;
}