C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title 動的計画法/スライド最小値 * * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D */ #include <iostream> #include <vector> #include "emthrm/dynamic_programming/slide_min.hpp" int main() { int n, l; std::cin >> n >> l; std::vector<int> a(n); for (int i = 0; i < n; ++i) { std::cin >> a[i]; } const std::vector<int> ans = emthrm::slide_min(a, l); for (int i = 0; i + l <= n; ++i) { std::cout << ans[i] << " \n"[i + l == n]; } return 0; }
#line 1 "test/dynamic_programming/slide_min.test.cpp" /* * @title 動的計画法/スライド最小値 * * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D */ #include <iostream> #include <vector> #line 1 "include/emthrm/dynamic_programming/slide_min.hpp" #include <deque> #line 6 "include/emthrm/dynamic_programming/slide_min.hpp" namespace emthrm { template <bool IS_MINIMIZED = true, typename T> std::vector<T> slide_min(const std::vector<T>& a, const int len) { const int n = a.size(); std::vector<T> res(n - len + 1); std::deque<T> deq; for (int i = 0; i < n; ++i) { while (!deq.empty() && !(IS_MINIMIZED ? a[deq.back()] < a[i] : a[deq.back()] > a[i])) { deq.pop_back(); } deq.emplace_back(i); if (i + 1 >= len) { const int left = i + 1 - len; res[left] = a[deq.front()]; if (deq.front() == left) deq.pop_front(); } } return res; } } // namespace emthrm #line 11 "test/dynamic_programming/slide_min.test.cpp" int main() { int n, l; std::cin >> n >> l; std::vector<int> a(n); for (int i = 0; i < n; ++i) { std::cin >> a[i]; } const std::vector<int> ans = emthrm::slide_min(a, l); for (int i = 0; i + l <= n; ++i) { std::cout << ans[i] << " \n"[i + l == n]; } return 0; }