test/aoj/DPL_3_C.test.cpp

• View this file on GitHub
• Last update: 2024-01-08 01:52:54+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_C

Depends on

• Largest Rectangle (dp/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/largest_rectangle.hpp"
using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;
    vector<ll> h(N);
    for (auto& x : h) cin >> x;
    cout << largest_rectangle(h) << endl;
}

#line 1 "test/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 6 "dp/largest_rectangle.hpp"

/**
 * @brief Largest Rectangle
 */
template <typename T>
T largest_rectangle(const std::vector<T>& h) {
    int n = h.size();
    std::vector<int> left(n), right(n);
    std::stack<std::pair<T, int>> st;
    st.emplace(-1, -1);
    for (int i = 0; i < n; ++i) {
        while (st.top().first >= h[i]) st.pop();
        left[i] = st.top().second + 1;
        st.emplace(h[i], i);
    }
    while (!st.empty()) st.pop();
    st.emplace(-1, n);
    for (int i = n - 1; i >= 0; --i) {
        while (st.top().first >= h[i]) st.pop();
        right[i] = st.top().second;
        st.emplace(h[i], i);
    }
    T ret = 0;
    for (int i = 0; i < n; ++i)
        ret = std::max(ret, h[i] * (right[i] - left[i]));
    return ret;
}
#line 7 "test/aoj/DPL_3_C.test.cpp"
using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;
    vector<ll> h(N);
    for (auto& x : h) cin >> x;
    cout << largest_rectangle(h) << endl;
}

Back to top page