Cod sursa(job #1961042)

Utilizator DanielRusuDaniel Rusu DanielRusu Data 10 aprilie 2017 20:57:39
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <iostream>
#include <cstdio>
#include <stack>

using namespace std;

char mat[204][204];
int dp[204][204];
int N, M;

int maxHist(int row[], int C) {
    stack <int> result;
    int top_val;
    int max_area = 0;
    int area = 0;
    int i = 0;
    while(i < C) {
        if(result.empty() || row[result.top()] <= row[i]) {
            result.push(i++);
        }
        else {
            top_val = row[result.top()];
            result.pop();
            area = top_val * i;
            if(!result.empty()) {
                area = top_val * (i - result.top() - 1);
            }
            max_area = max(max_area, area);
        }
    }

    while(!result.empty()) {
        top_val = row[result.top()];
        result.pop();
        area = top_val * i;
        if(!result.empty()) {
            area = top_val * (i - result.top() - 1);
        }
        max_area = max(max_area, area);
    }

    return max_area;
}

int calculate(int a, int b, int c, int d) {
    int line[204];
    int result = 0;
    for(int i = a; i <= c; ++i) {
        int pos = 0;
        for(int j = b; j <= d; ++j) {
            line[pos++] = min(i - a + 1, dp[i][j]);
        }

        line[pos] = 0;
        result = max(result, maxHist(line, d - b + 1));
    }

    return result;
}

int main() {
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);

    scanf("%d %d\n", &N, &M);

    for(int i = 1; i <= N; ++i) {
        scanf("%s", (mat[i] + 1));
    }

    for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= M; ++j) {
            if(mat[i][j] == '0') {
                dp[i][j] = dp[i - 1][j] + 1;
            }
        }
    }

    int ans = calculate(1, 1, N, M);
    for(int colbetween = 1; colbetween < M; ++colbetween) {
        ans = max(ans, calculate(1, 1, N, colbetween) + calculate(1, colbetween + 1, N, M));
    }

    for(int linebetween = 1; linebetween < N; ++linebetween) {
        ans = max(ans, calculate(1, 1, linebetween, M) + calculate(linebetween + 1, 1, N, M));
    }

    cout << ans << '\n';

    return 0;
}