Cod sursa(job #1961433)

Utilizator DanielRusuDaniel Rusu DanielRusu Data 11 aprilie 2017 09:27:05
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.03 kb
#include <iostream>
#include <cstdio>
#include <stack>

using namespace std;

#define DIM 204

char mat[DIM][DIM];
int fromUpToDown[DIM][DIM], fromDownToUp[DIM][DIM], fromLeftToRight[DIM][DIM], fromRightToLeft[DIM][DIM];
int ansUpDown[DIM], ansDownUp[DIM], ansRightLeft[DIM], ansLeftRight[DIM];
int N, M, row[DIM], pos;

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 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));
    }

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

            row[pos++] = fromUpToDown[i][j];
        }

        result = max(result, maxHist(row, M));
        ansUpDown[i] = result;
    }

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

            row[pos++] = fromDownToUp[i][j];
        }

        result = max(result, maxHist(row, M));
        ansDownUp[i] = result;
        ans = max(ans, ansUpDown[i] + ansDownUp[i + 1]);
    }

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

            row[pos++] = fromLeftToRight[i][j];
        }

        result = max(result, maxHist(row, N));
        ansLeftRight[j] = result;
    }

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

            row[pos++] = fromRightToLeft[i][j];
        }

        result = max(result, maxHist(row, N));
        ansRightLeft[j] = result;
        ans = max(ans, ansLeftRight[j] + ansRightLeft[j + 1]);
    }

    cout << ans << '\n';

    return 0;
}