Cod sursa(job #2240339)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 13 septembrie 2018 09:38:17
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <fstream>
#include <cstring>
#include <stack>

using namespace std;

ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");

int N, M, answer, heights[205];
int upDP[205]; ///cel mai mare dreptunghi care sta pe sau peste linia i
int downDP[205]; ///cel mai mare dreptunghi care sta sub linia i
int leftDP[205]; ///cel mai mare dreptunghi care sta pe sau inaintea coloanei j
int rightDP[205]; ///cel mai mare dreptunghi care sta dupa linia j
char s[205][205];

int Solve(int dim)
{
    stack <int> st;
    int maxAreaRect = 0;

    st.push(0);
    for(int i = 1; i <= dim + 1; i++)
    {
        while(st.size() > 1 && heights[i] <= heights[st.top()])
        {
            int currentHeight = heights[st.top()];
            st.pop();
            maxAreaRect = max(maxAreaRect, currentHeight * (i - st.top() - 1));
        }

        st.push(i);
    }

    return maxAreaRect;
}

int main()
{
    fin >> N >> M;
    fin.get();

    for(int i = 1; i <= N; i++)
        fin.getline(s[i], sizeof(s[i]));

    ///upDP
    for(int i = 1; i <= N; i++)
    {
        for(int j = 0; j < M; j++)
            heights[j + 1] = (s[i][j] == '1') ? 0 : heights[j + 1] + 1;
        upDP[i] = max(Solve(M), upDP[i - 1]);
    }

    ///downDP
    memset(heights, 0, sizeof(heights));
    for(int i = N - 1; i >= 1; i--)
    {
        for(int j = 0; j < M; j++)
            heights[j + 1] = (s[i + 1][j] == '1') ? 0 : heights[j + 1] + 1;
        downDP[i] = max(Solve(M), downDP[i + 1]);
    }

    ///leftDP
    memset(heights, 0, sizeof(heights));
    for(int j = 0; j < M; j++)
    {
        for(int i = 1; i <= N; i++)
            heights[i] = (s[i][j] == '1') ? 0 : heights[i] + 1;
        leftDP[j + 1] = max(Solve(N), leftDP[j]);
    }

    ///rightDP
    memset(heights, 0, sizeof(heights));
    for(int j = M - 2; j >= 0; j--)
    {
        for(int i = 1; i <= N; i++)
            heights[i] = (s[i][j + 1] == '1') ? 0 : heights[i] + 1;
        rightDP[j + 1] = max(Solve(N), rightDP[j + 2]);
    }

    for(int i = 1; i <= N; i++)
        answer = max(answer, upDP[i] + downDP[i]);

    for(int i = 1; i <= M; i++)
        answer = max(answer, leftDP[i] + rightDP[i]);

    fout << answer << '\n';

    return 0;
}