Cod sursa(job #2002980)

Utilizator cristina_borzaCristina Borza cristina_borza Data 21 iulie 2017 13:06:39
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream f ("bmatrix.in");
ofstream g ("bmatrix.out");

char mat[500][500];

int aux[500][500], dp[500][500], st[500], dr[500];
int n, m, ans;

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

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int lg = aux[i][j];
            dp[i][j] = lg;

            for (int p = i - 1; p >= 1 && lg; --p) {
                lg = min(lg, aux[p][j]);
                dp[i][j] = max(dp[i][j], lg * (i - p + 1));
            }
        }
    }

    for (int j = m; j >= 1; --j) {
        for (int i = 1; i <= n; ++i) {
            st[j] = max(st[j], dp[i][j]);
        }

        st[j] = max(st[j], st[j + 1]);
    }
}

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

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int lg = aux[i][j];
            dp[i][j] = lg;

            for (int p = i - 1; p >= 1 && lg; --p) {
                lg = min(lg, aux[p][j]);
                dp[i][j] = max(dp[i][j], lg * (i - p + 1));
            }
        }
    }

    for (int j = 1; j <= m; ++j) {
        for (int i = 1; i <= n; ++i) {
            dr[j] = max(dr[j], dp[i][j]);
        }

        dr[j] = max(dr[j], dr[j - 1]);
    }
}

void rotate_90() {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            aux[j][n - i + 1] = mat[i][j];
        }
    }

    swap(n, m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            mat[i][j] = aux[i][j];
        }
    }
}

int main() {
    f >> n >> m;
    for (int i = 1; i <= n; ++i) {
        f >> (mat[i] + 1);
    }

    solve1();
    solve2();

    for (int i = 1; i <= m; ++i) {
        ans = max(ans, st[i] + dr[i - 1]);
    }


    memset (aux, 0, sizeof(aux));
    memset (st, 0, sizeof(st));
    memset (dr, 0, sizeof(dr));

    rotate_90();

    solve1();
    solve2();

    for (int i = 1; i <= m; ++i) {
        ans = max(ans, st[i] + dr[i - 1]);
    }

    g << ans;
    return 0;
}