sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#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; }