This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub noshi91/Library
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3086" #include "algorithm/larsch.cpp" #include "data_structure/segment_tree.cpp" #include "other/int_alias.cpp" #include "other/less_equal_ordered_set.cpp" #include "other/min_semigroup.cpp" #include "other/opposite_ordered_set.cpp" #include "other/semigroup_to_monoid.cpp" #include <iostream> #include <limits> int main() { #include "other/fast_ios.cpp" static constexpr i64 inf = std::numeric_limits<i64>::max() / 2; usize n, l; std::cin >> n >> l; segment_tree<semigroup_to_monoid< min_semigroup<opposite_ordered_set<less_equal_ordered_set<i64>>>>> seg(n); for (usize i = 0; i != n; ++i) { i64 a; std::cin >> a; seg.update(i, a); } std::vector<i64> dp(n + 1); dp[0] = 0; const auto f = [&](const usize to_, const usize from) -> i64 { const usize to = to_ + 1; if (to - from < l) { return -inf; } else { return dp[from] + *seg.fold(from, to); } }; larsch<i64> larsch_(n, [&](int i, int j) { return -f(i, j); }); for (usize i = 0; i != n; i += 1) { dp[i + 1] = f(i, larsch_.get_argmin()); } std::cout << dp[n] << "\n"; return 0; }
#line 1 "test/larsch.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3086" #line 1 "algorithm/larsch.cpp" #include <functional> #include <memory> #include <vector> template <class T> class larsch { struct reduce_row; struct reduce_col; struct reduce_row { int n; std::function<T(int, int)> f; int cur_row; int state; std::unique_ptr<reduce_col> rec; reduce_row(int n_) : n(n_), f(), cur_row(0), state(0), rec() { const int m = n / 2; if (m != 0) { rec = std::make_unique<reduce_col>(m); } } void set_f(std::function<T(int, int)> f_) { f = f_; if (rec) { rec->set_f([&](int i, int j) -> T { return f(2 * i + 1, j); }); } } int get_argmin() { const int cur_row_ = cur_row; cur_row += 1; if (cur_row_ % 2 == 0) { const int prev_argmin = state; const int next_argmin = [&]() { if (cur_row_ + 1 == n) { return n - 1; } else { return rec->get_argmin(); } }(); state = next_argmin; int ret = prev_argmin; for (int j = prev_argmin + 1; j <= next_argmin; j += 1) { if (f(cur_row_, ret) > f(cur_row_, j)) { ret = j; } } return ret; } else { if (f(cur_row_, state) <= f(cur_row_, cur_row_)) { return state; } else { return cur_row_; } } } }; struct reduce_col { int n; std::function<T(int, int)> f; int cur_row; std::vector<int> cols; reduce_row rec; reduce_col(int n_) : n(n_), f(), cur_row(0), cols(), rec(n) {} void set_f(std::function<T(int, int)> f_) { f = f_; rec.set_f([&](int i, int j) -> T { return f(i, cols[j]); }); } int get_argmin() { const int cur_row_ = cur_row; cur_row += 1; const auto cs = [&]() -> std::vector<int> { if (cur_row_ == 0) { return {{0}}; } else { return {{2 * cur_row_ - 1, 2 * cur_row_}}; } }(); for (const int j : cs) { while ([&]() { const int size = cols.size(); return size != cur_row_ && f(size - 1, cols.back()) > f(size - 1, j); }()) { cols.pop_back(); } if (cols.size() != n) { cols.push_back(j); } } return cols[rec.get_argmin()]; } }; std::unique_ptr<reduce_row> base; public: larsch(int n, std::function<T(int, int)> f) : base(std::make_unique<reduce_row>(n)) { base->set_f(f); } int get_argmin() { return base->get_argmin(); } }; /** * @brief LARSCH Algorithm * @docs docs/larsch.md */ #line 2 "other/int_alias.cpp" #include <cstddef> #include <cstdint> using i32 = std::int32_t; using i64 = std::int64_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using isize = std::ptrdiff_t; using usize = std::size_t; #line 2 "data_structure/segment_tree.cpp" #include <cassert> #line 6 "data_structure/segment_tree.cpp" template <class M> class segment_tree { using T = typename M::value_type; public: using value_type = T; private: std::vector<T> tree; template <class F> usize search_subtree(usize index, const F f, T fold_l) const { while (index < size()) { const T temp = M::operation(fold_l, tree[index * 2]); if (!f(temp)) { index = index * 2; } else { fold_l = temp; index = index * 2 + 1; } } return index - size(); } public: segment_tree() = default; explicit segment_tree(const usize n) : tree(n * 2, M::identity) {} usize size() const noexcept { return tree.size() / 2; } T fold(usize first, usize last) const { assert(first <= last); assert(last <= size()); first += size(); last += size(); T fold_l = M::identity; T fold_r = M::identity; while (first != last) { if (first % 2 != 0) { fold_l = M::operation(fold_l, tree[first]); first += 1; } first /= 2; if (last % 2 != 0) { last -= 1; fold_r = M::operation(tree[last], fold_r); } last /= 2; } return M::operation(fold_l, fold_r); } template <class F> usize search(usize first, usize last, const F f) const { assert(first <= last); assert(last <= size()); first += size(); last += size(); const usize last_cp = last; usize shift = 0; T fold_l = M::identity; while (first != last) { if (first % 2 != 0) { const T temp = M::operation(fold_l, tree[first]); if (!f(temp)) return search_subtree(first, f, fold_l); fold_l = temp; first += 1; } first /= 2; last /= 2; shift += 1; } while (shift != 0) { shift -= 1; last = last_cp >> shift; if (last % 2 != 0) { last -= 1; const T temp = M::operation(fold_l, tree[last]); if (!f(temp)) return search_subtree(last, f, fold_l); fold_l = temp; } } return last_cp - size(); } void update(usize index, const T x) { assert(index < size()); index += size(); tree[index] = x; while (index != 1) { index /= 2; tree[index] = M::operation(tree[index * 2], tree[index * 2 + 1]); } } }; /** * @brief Segment Tree * @docs docs/segment_tree.md * @see https://scrapbox.io/data-structures/Segment_Tree */ #line 1 "other/less_equal_ordered_set.cpp" template <class T> class less_equal_ordered_set { public: using value_type = T; static constexpr bool compare(const T &x, const T &y) noexcept { return x <= y; } }; #line 1 "other/min_semigroup.cpp" template <class W> class min_semigroup { using T = typename W::value_type; public: using value_type = T; static constexpr T operation(const T &l, const T &r) noexcept { return W::compare(l, r) ? l : r; } }; #line 1 "other/opposite_ordered_set.cpp" template <class W> class opposite_ordered_set { using T = typename W::value_type; public: using value_type = T; static constexpr bool compare(const T &l, const T &r) noexcept { return W::compare(r, l); } }; #line 1 "other/semigroup_to_monoid.cpp" #include <optional> #include <utility> template <class S> class semigroup_to_monoid { using T = std::optional<typename S::value_type>; public: using value_type = T; static constexpr T operation(const T &l, const T &r) noexcept { if (!l) return r; if (!r) return l; return T(std::in_place, S::operation(*l, *r)); } static constexpr T identity{std::nullopt}; }; #line 10 "test/larsch.test.cpp" #include <iostream> #include <limits> int main() { #line 1 "other/fast_ios.cpp" std::ios::sync_with_stdio(false); std::cin.tie(nullptr); #line 16 "test/larsch.test.cpp" static constexpr i64 inf = std::numeric_limits<i64>::max() / 2; usize n, l; std::cin >> n >> l; segment_tree<semigroup_to_monoid< min_semigroup<opposite_ordered_set<less_equal_ordered_set<i64>>>>> seg(n); for (usize i = 0; i != n; ++i) { i64 a; std::cin >> a; seg.update(i, a); } std::vector<i64> dp(n + 1); dp[0] = 0; const auto f = [&](const usize to_, const usize from) -> i64 { const usize to = to_ + 1; if (to - from < l) { return -inf; } else { return dp[from] + *seg.fold(from, to); } }; larsch<i64> larsch_(n, [&](int i, int j) { return -f(i, j); }); for (usize i = 0; i != n; i += 1) { dp[i + 1] = f(i, larsch_.get_argmin()); } std::cout << dp[n] << "\n"; return 0; }