test/aoj/DPL_3_C/main.test.cpp
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_C"
#include <iostream>
#include <vector>
#include "Mylib/IO/input_vector.cpp"
#include "Mylib/Typical/max_rectangle_in_histogram.cpp"
namespace hl = haar_lib;
int main() {
int N;
std::cin >> N;
auto h = hl::input_vector<int64_t>(N);
auto ans = hl::max_rectangle_in_histogram(h);
std::cout << ans << std::endl;
return 0;
}
#line 1 "test/aoj/DPL_3_C/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_C"
#include <iostream>
#include <vector>
#line 4 "Mylib/IO/input_vector.cpp"
namespace haar_lib {
template <typename T>
std::vector<T> input_vector(int N) {
std::vector<T> ret(N);
for (int i = 0; i < N; ++i) std::cin >> ret[i];
return ret;
}
template <typename T>
std::vector<std::vector<T>> input_vector(int N, int M) {
std::vector<std::vector<T>> ret(N);
for (int i = 0; i < N; ++i) ret[i] = input_vector<T>(M);
return ret;
}
} // namespace haar_lib
#line 2 "Mylib/Typical/max_rectangle_in_histogram.cpp"
#include <stack>
#include <utility>
#line 5 "Mylib/Typical/max_rectangle_in_histogram.cpp"
namespace haar_lib {
template <typename T>
T max_rectangle_in_histogram(const std::vector<T> &h) {
std::stack<std::pair<T, int>> st;
T ret = 0;
for (size_t i = 0; i < h.size(); ++i) {
if (st.empty()) {
st.emplace(h[i], i);
} else if (st.top().first < h[i]) {
st.emplace(h[i], i);
} else if (st.top().first > h[i]) {
int j = i;
while (not st.empty() and st.top().first > h[i]) {
ret = std::max(ret, st.top().first * ((T) i - st.top().second));
j = st.top().second;
st.pop();
}
st.emplace(h[i], j);
}
}
while (not st.empty()) {
ret = std::max(ret, st.top().first * ((T) h.size() - st.top().second));
st.pop();
}
return ret;
}
} // namespace haar_lib
#line 7 "test/aoj/DPL_3_C/main.test.cpp"
namespace hl = haar_lib;
int main() {
int N;
std::cin >> N;
auto h = hl::input_vector<int64_t>(N);
auto ans = hl::max_rectangle_in_histogram(h);
std::cout << ans << std::endl;
return 0;
}
Back to top page
Input vector
(Mylib/IO/input_vector.cpp)