This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://atcoder.jp/contests/dp/tasks/dp_z" #include <iostream> #include <vector> #include "library/datastructure/convex_hull_trick.hpp" using suisen::ConvexHullTrick; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; long long c; std::cin >> n >> c; std::vector<long long> h(n); for (int i = 0; i < n; ++i) { std::cin >> h[i]; } std::vector<long long> dp(n, 0); ConvexHullTrick<long long> cht; for (int i = 1; i < n; ++i) { cht.add_line(-2 * h[i - 1], dp[i - 1] + h[i - 1] * h[i - 1]); dp[i] = cht.query(h[i]) + h[i] * h[i] + c; } std::cout << dp[n - 1] << std::endl; return 0; }
#line 1 "test/src/datastructure/convex_hull_trick/EDPC_Z.test.cpp" #define PROBLEM "https://atcoder.jp/contests/dp/tasks/dp_z" #include <iostream> #include <vector> #line 1 "library/datastructure/convex_hull_trick.hpp" #include <cassert> #include <limits> #include <set> #line 1 "library/type_traits/type_traits.hpp" #line 6 "library/type_traits/type_traits.hpp" #include <type_traits> namespace suisen { template <typename ...Constraints> using constraints_t = std::enable_if_t<std::conjunction_v<Constraints...>, std::nullptr_t>; template <typename T, typename = std::nullptr_t> struct bitnum { static constexpr int value = 0; }; template <typename T> struct bitnum<T, constraints_t<std::is_integral<T>>> { static constexpr int value = std::numeric_limits<std::make_unsigned_t<T>>::digits; }; template <typename T> static constexpr int bitnum_v = bitnum<T>::value; template <typename T, size_t n> struct is_nbit { static constexpr bool value = bitnum_v<T> == n; }; template <typename T, size_t n> static constexpr bool is_nbit_v = is_nbit<T, n>::value; template <typename T, typename = std::nullptr_t> struct safely_multipliable { using type = T; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 32>>> { using type = long long; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 64>>> { using type = __int128_t; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 32>>> { using type = unsigned long long; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 64>>> { using type = __uint128_t; }; template <typename T> using safely_multipliable_t = typename safely_multipliable<T>::type; template <typename T, typename = void> struct rec_value_type { using type = T; }; template <typename T> struct rec_value_type<T, std::void_t<typename T::value_type>> { using type = typename rec_value_type<typename T::value_type>::type; }; template <typename T> using rec_value_type_t = typename rec_value_type<T>::type; template <typename T> class is_iterable { template <typename T_> static auto test(T_ e) -> decltype(e.begin(), e.end(), std::true_type{}); static std::false_type test(...); public: static constexpr bool value = decltype(test(std::declval<T>()))::value; }; template <typename T> static constexpr bool is_iterable_v = is_iterable<T>::value; template <typename T> class is_writable { template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::ostream&>() << e, std::true_type{}); static std::false_type test(...); public: static constexpr bool value = decltype(test(std::declval<T>()))::value; }; template <typename T> static constexpr bool is_writable_v = is_writable<T>::value; template <typename T> class is_readable { template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::istream&>() >> e, std::true_type{}); static std::false_type test(...); public: static constexpr bool value = decltype(test(std::declval<T>()))::value; }; template <typename T> static constexpr bool is_readable_v = is_readable<T>::value; } // namespace suisen #line 9 "library/datastructure/convex_hull_trick.hpp" namespace suisen { namespace internal::convex_hull_trick { template <typename T> struct Line { // f(x)=ax+b,m=max{x|f=argmin_{f' in S}{f'(x)}} mutable T a, b, m; Line(const T& a, const T& b, const T& m) : a(a), b(b), m(m) {} bool operator<(const Line<T>& rhs) const { return a < rhs.a; } bool operator<(const T& x) const { return not (m < x); } }; template <typename T, std::enable_if_t<std::is_integral<T>::value, std::nullptr_t> = nullptr> inline T div(const T& num, const T& den) { return num / den - ((num ^ den) < 0 and num % den); } template <typename T, std::enable_if_t<std::negation<std::is_integral<T>>::value, std::nullptr_t> = nullptr> inline T div(const T& num, const T& den) { return num / den; } } template <typename T, bool is_min_query = true> class ConvexHullTrick : std::multiset<internal::convex_hull_trick::Line<T>, std::less<>> { using iterator = typename std::multiset<internal::convex_hull_trick::Line<T>>::iterator; using MultT = safely_multipliable_t<T>; using Line = internal::convex_hull_trick::Line<T>; static constexpr T inf = std::numeric_limits<T>::max(); public: bool has_line() const { return not this->empty(); } void add_line(T slope, T intercept) { if constexpr (not is_min_query) slope = -slope, intercept = -intercept; auto it = this->emplace(slope, intercept, inf); auto itl = it; for (; itl != this->begin();) { if (update_intersec_right(--itl, it)) { ++itl; break; } } auto itm = this->erase(itl, it), itr = std::next(itm); if (not update_intersec_right(itm, itr)) { update_intersec_right(--itm, itr); } for (it = itm; itr != this->end();) { itm = itr++; if (itr != this->end() and itm->m <= itr->m) { update_intersec_right(it, itr); } else { break; } } if (it != itm) this->erase(std::next(it), itm); } MultT query(T x) { assert(not this->empty()); const iterator l = --(this-> template lower_bound<T>(x)); auto res = (MultT) l->a * x + l->b; if constexpr (is_min_query) { return res; } else { return -res; } } private: // updates r->m and returns whether l is necessary or not. bool update_intersec_right(iterator l, iterator r) { if (r == this->end()) return true; if (l->a == r->a) { r->m = r->b <= l->b ? inf : -inf; } else { r->m = internal::convex_hull_trick::div(r->b - l->b, l->a - r->a); } return l->m > r->m; } }; template <typename T> using MinCHT = ConvexHullTrick<T, /* is_min_query = */ true>; template <typename T> using MaxCHT = ConvexHullTrick<T, /* is_min_query = */ false>; } // namespace suisen #line 7 "test/src/datastructure/convex_hull_trick/EDPC_Z.test.cpp" using suisen::ConvexHullTrick; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; long long c; std::cin >> n >> c; std::vector<long long> h(n); for (int i = 0; i < n; ++i) { std::cin >> h[i]; } std::vector<long long> dp(n, 0); ConvexHullTrick<long long> cht; for (int i = 1; i < n; ++i) { cht.add_line(-2 * h[i - 1], dp[i - 1] + h[i - 1] * h[i - 1]); dp[i] = cht.query(h[i]) + h[i] * h[i] + c; } std::cout << dp[n - 1] << std::endl; return 0; }