Cod sursa(job #2345093)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 15 februarie 2019 21:36:09
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <bits/stdc++.h>

#define int_pair std::pair <int, int>

#define MAXN 205

int N, M;
int Height[MAXN], DP[4][MAXN];
bool BMatrix[MAXN][MAXN];

bool Rotator[MAXN][MAXN];
void Rotate90() {
    for (int i=1, j; i<=N; ++i)
        for (j=1; j<=M; ++j)
            Rotator[j][N-i+1] = BMatrix[i][j];

    std::swap(N, M);
    for (int i=1, j; i<=N; ++i)
        for (j=1; j<=M; ++j)
            BMatrix[i][j] = Rotator[i][j];
}

std::ifstream In ("bmatrix.in");
std::ofstream Out("bmatrix.out");

void Citire() {
    In >> N >> M;
    char ch;
    for (int i=1, j ; i<=N; ++i)
        for (j=1; j<=M; ++j)
            In >> ch, BMatrix[i][j] = ch - '0';
}

std::stack <int_pair> Stack;
void Rezolvare() {
    for (int step=0, i, j, count; step<4; ++step, Rotate90()) {
        for (j=1; j<=M; ++j)
            Height[j] = 0;

        for (i=1; i<=N; ++i) {
            DP[step][i] = DP[step][i-1];
            while (!Stack.empty()) Stack.pop();

            for (j=1; j<=M; ++j) {
                if (!BMatrix[i][j]) Height[j] ++;
                else Height[j] = 0;
                count = 0;

                while (!Stack.empty() && Height[j] <= Stack.top().first) {
                    count += Stack.top().second;
                    DP[step][i] = std::max(DP[step][i], count * Stack.top().first);
                    Stack.pop();
                }   Stack.push({Height[j], count+1});
            }

            count = 0;
            while (!Stack.empty()) {
                count += Stack.top().second;
                DP[step][i] = std::max(DP[step][i], count * Stack.top().first);
                Stack.pop();
            }
        }
    }

    int Ans = 0;
    for (int i=1; i<N; ++i)
        Ans = std::max(Ans, DP[0][i] + DP[2][N-i]);
    for (int i=1; i<M; ++i)
        Ans = std::max(Ans, DP[1][i] + DP[3][M-i]);
    Out << Ans << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}