Cod sursa(job #1840357)

Utilizator dariusdariusMarian Darius dariusdarius Data 4 ianuarie 2017 12:36:52
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <algorithm>
#include <fstream>
#include <iostream>
using namespace std;

int a[255][255];
int aux[255][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 up[255], down[255];
int c[255][255];
int l[255], r[255];
int st[255];

int soldiers_row(int a[255], int n) {
    ///get_left
    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;
    }
    ///get_right
    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 cin("bmatrix.in");
    ofstream cout("bmatrix.out");
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) {
        cin >> s;
        for (int j = 1; j <= m; ++ j) {
            a[i][j] = s[j - 1] - '0';
        }
    }
    int answer = solve(n, m);
    rotate_matrix(n, m);
    ///dump(a, n, m);
    answer = max(answer, solve(n, m));
    cout << answer << "\n";
    return 0;
}