verify/aoj_dpl/aoj_dpl_3_c.test.cpp

• View this file on GitHub
• Last update: 2023-02-06 19:40:21+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_C

Depends on

• Histogram Largest Rectangle (ヒストグラムの最大長方形) (dp/histogram_largest_rectangle.hpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_C"

#include <bits/stdc++.h>

#include "dp/histogram_largest_rectangle.hpp"

int main() {
    int N;
    std::cin >> N;
    std::vector<long long> A(N);
    for (int i = 0; i < N; i++) std::cin >> A[i];
    std::cout << histogram_largest_rectangle(A) << '\n';
    return 0;
}

#line 1 "verify/aoj_dpl/aoj_dpl_3_c.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_C"

#include <bits/stdc++.h>

#line 2 "dp/histogram_largest_rectangle.hpp"

template <class T> T histogram_largest_rectangle(std::vector<T> &h) {
    int n = (int)h.size();
    std::vector<int> st(n), L(n), R(n);
    int t = 0;
    for (int i = 0; i < n; i++) {
        while (t > 0 and h[st[t - 1]] >= h[i]) t--;
        L[i] = (t == 0 ? 0 : st[t - 1] + 1);
        st[t++] = i;
    }
    t = 0;
    for (int i = n - 1; i >= 0; i--) {
        while (t > 0 and h[st[t - 1]] >= h[i]) t--;
        R[i] = (t == 0 ? n : st[t - 1]);
        st[t++] = i;
    }
    T res = 0;
    for (int i = 0; i < n; i++) res = std::max(res, h[i] * (R[i] - L[i]));
    return res;
}
#line 6 "verify/aoj_dpl/aoj_dpl_3_c.test.cpp"

int main() {
    int N;
    std::cin >> N;
    std::vector<long long> A(N);
    for (int i = 0; i < N; i++) std::cin >> A[i];
    std::cout << histogram_largest_rectangle(A) << '\n';
    return 0;
}

Back to top page