Cod sursa(job #1401374)

Utilizator andreey_047Andrei Maxim andreey_047 Data 25 martie 2015 20:22:52
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <cstring>
#include <fstream>
#include <stack>
using namespace std;

const int MAX_N = 202;

int N, M, sol;
int H[MAX_N][MAX_N], D[MAX_N][MAX_N], dp[MAX_N][MAX_N];
char s[MAX_N];
bool A[MAX_N][MAX_N];
void read() {
    ifstream f("bmatrix.in");

    f >> N >> M;
    for(int i = 1; i <= N; ++i) {
        f >> s;
        for(int j = 0; j < M; ++j)
            if(s[j] == '0')
                A[i][j + 1] = 1;
    }

    f.close();
}

void solveLine(int line, int v[], int n) {
    stack < pair < int, int > > st;

    for(int i = 1; i <= n; ++i) {
        if(st.empty() || v[i] > st.top().first)
            st.push(make_pair(v[i], 1));
        else if(st.top().first == v[i])
            ++st.top().second;
        else {
            int cnt = 0;
            while(!st.empty() && v[i] < st.top().first) {
                cnt += st.top().second;
                int top = st.top().first;
                st.pop();
                H[line][top] = max(H[line][top], cnt);
            }
            st.push(make_pair(v[i], cnt + 1));
        }
    }

    int cnt = 0;
    while(!st.empty()) {
        cnt += st.top().second;
        int top = st.top().first;
        st.pop();
        H[line][top] = max(H[line][top], cnt);
    }
}

void compute() {
    memset(H, 0, sizeof(H));
    memset(D, 0, sizeof(D));
    for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= M; ++j)
            if(A[i][j])
                D[i][j] = D[i - 1][j] + 1;
        solveLine(i, D[i], M);
    }

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

   for(int h = 1; h < N; ++h)
        for(int i = 1; i + h <= N; ++i) {
            int j = i + h;
            dp[i][j] = max(H[j][j - i + 1] * (j - i + 1), max(dp[i + 1][j], dp[i][j - 1]));
        }

    for(int i = 1; i < N; ++i)
        sol = max(sol, dp[1][i] + dp[i + 1][N]);
}

void transpose() {
    int T[MAX_N][MAX_N];
    memset(T, 0, sizeof(T));
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            T[j][i] = A[i][j];
    swap(N, M);
    memset(A, 0, sizeof(A));
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            A[i][j] = T[i][j];
}

void solve() {
    compute();
    transpose();
    compute();
}

void write() {
    ofstream g("bmatrix.out");

    g << sol << "\n";

    g.close();
}

int main() {
    read();
    solve();
    write();

    return 0;
}