C++ Library for Competitive Programming
/*
* @title 動的計画法/convex full trick($x$ が単調増加する解答クエリ)
*
* verification-helper: IGNORE
* verification-helper: PROBLEM https://atcoder.jp/contests/dp/tasks/dp_z
*/
#include <iostream>
#include "emthrm/dynamic_programming/convex_hull_trick.hpp"
int main() {
int n;
long long c;
std::cin >> n >> c;
emthrm::ConvexHullTrick<long long> convex_hull_trick;
for (int i = 0; i < n; ++i) {
int h;
std::cin >> h;
if (i == 0) [[unlikely]] {
convex_hull_trick.add(-2 * h, static_cast<long long>(h) * h);
} else {
const long long dp = convex_hull_trick.monotonically_increasing_query(h)
+ static_cast<long long>(h) * h + c;
if (i + 1 == n) [[unlikely]] {
std::cout << dp << '\n';
} else {
convex_hull_trick.add(-2 * h, dp + static_cast<long long>(h) * h);
}
}
}
return 0;
}
#line 1 "test/dynamic_programming/convex_hull_trick.2.test.cpp"
/*
* @title 動的計画法/convex full trick($x$ が単調増加する解答クエリ)
*
* verification-helper: IGNORE
* verification-helper: PROBLEM https://atcoder.jp/contests/dp/tasks/dp_z
*/
#include <iostream>
#line 1 "include/emthrm/dynamic_programming/convex_hull_trick.hpp"
#include <cassert>
#include <deque>
#include <iterator>
#include <numeric>
#include <utility>
namespace emthrm {
template <typename T, bool IS_MINIMIZED = true>
struct ConvexHullTrick {
ConvexHullTrick() = default;
void add(T a, T b) {
if constexpr (!IS_MINIMIZED) {
a = -a;
b = -b;
}
const Line line(a, b);
if (deq.empty()) [[unlikely]] {
deq.emplace_back(line);
} else if (deq.back().first >= a) {
if (deq.back().first == a) {
if (b >= deq.back().second) return;
deq.pop_back();
}
for (int i = std::ssize(deq) - 2; i >= 0; --i) {
if (!must_pop(deq[i], deq[i + 1], line)) break;
deq.pop_back();
}
deq.emplace_back(line);
} else {
if (deq.front().first == a) {
if (b >= deq.front().second) return;
deq.pop_front();
}
while (deq.size() >= 2 && must_pop(line, deq.front(), deq[1])) {
deq.pop_front();
}
deq.emplace_front(line);
}
}
T query(const T x) const {
assert(!deq.empty());
int lb = -1, ub = deq.size() - 1;
while (ub - lb > 1) {
const int mid = std::midpoint(lb, ub);
(f(deq[mid], x) < f(deq[mid + 1], x) ? ub : lb) = mid;
}
return IS_MINIMIZED ? f(deq[ub], x) : -f(deq[ub], x);
}
T monotonically_increasing_query(const T x) {
while (deq.size() >= 2 && f(deq.front(), x) >= f(deq[1], x)) {
deq.pop_front();
}
return IS_MINIMIZED ? f(deq.front(), x) : -f(deq.front(), x);
}
T monotonically_decreasing_query(const T x) {
for (int i = std::ssize(deq) - 2; i >= 0; --i) {
if (f(deq[i], x) > f(deq[i + 1], x)) break;
deq.pop_back();
}
return IS_MINIMIZED ? f(deq.back(), x) : -f(deq.back(), x);
}
private:
using Line = std::pair<T, T>;
std::deque<Line> deq;
bool must_pop(const Line& l1, const Line& l2, const Line& l3) const {
#ifdef __SIZEOF_INT128__
const T lhs_num = l3.second - l2.second, lhs_den = l2.first - l3.first;
const T rhs_num = l2.second - l1.second, rhs_den = l1.first - l2.first;
return __int128{lhs_num} * rhs_den <= __int128{rhs_num} * lhs_den;
#else
const long double lhs =
static_cast<long double>(l3.second - l2.second) / (l2.first - l3.first);
const long double rhs =
static_cast<long double>(l2.second - l1.second) / (l1.first - l2.first);
return lhs <= rhs;
#endif // __SIZEOF_INT128__
}
T f(const Line& l, const T x) const { return l.first * x + l.second; }
};
} // namespace emthrm
#line 11 "test/dynamic_programming/convex_hull_trick.2.test.cpp"
int main() {
int n;
long long c;
std::cin >> n >> c;
emthrm::ConvexHullTrick<long long> convex_hull_trick;
for (int i = 0; i < n; ++i) {
int h;
std::cin >> h;
if (i == 0) [[unlikely]] {
convex_hull_trick.add(-2 * h, static_cast<long long>(h) * h);
} else {
const long long dp = convex_hull_trick.monotonically_increasing_query(h)
+ static_cast<long long>(h) * h + c;
if (i + 1 == n) [[unlikely]] {
std::cout << dp << '\n';
} else {
convex_hull_trick.add(-2 * h, dp + static_cast<long long>(h) * h);
}
}
}
return 0;
}