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/abc218/tasks/abc218_h" #include "library/optimization/alien_dp.hpp" #include <algorithm> #include <iostream> #include <vector> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, r; std::cin >> n >> r; std::vector<long long> a(n - 1); for (auto &e : a) { std::cin >> e; } // sup f(x)-px auto g = [&](long long p) { std::vector<std::pair<long long, int>> dp0(n, { -(1LL << 60), -n-1 }), dp1(n, { -(1LL << 60), -n-1 }); dp0[0] = { 0, 0 }; dp1[0] = { -p, 1 }; for (int i = 0; i < n - 1; ++i) { dp0[i + 1] = std::max<std::pair<long long, int>>(dp0[i], { dp1[i].first + a[i], dp1[i].second }); dp1[i + 1] = std::max<std::pair<long long, int>>({ dp1[i].first - p, dp1[i].second + 1 }, { dp0[i].first - p + a[i], dp0[i].second + 1 }); } return std::max(dp0[n - 1], dp1[n - 1]); }; std::cout << suisen::alien_concave<long long>(r, -2'000'000'000LL, +2'000'000'000LL, g) << std::endl; }
#line 1 "test/src/optimization/alien_dp/abc218_h_1.test.cpp" #define PROBLEM "https://atcoder.jp/contests/abc218/tasks/abc218_h" #line 1 "library/optimization/alien_dp.hpp" #include <type_traits> #include <utility> namespace suisen { /** * @brief evaluates f(x) (f: convex) * @param g p -> inf(f(x)-px) */ template <typename Cost, typename DP, std::enable_if_t<std::is_invocable_r_v<Cost, DP, Cost>, std::nullptr_t> = nullptr> Cost alien_convex(int x, Cost min_slope, Cost max_slope, DP g) { // x <= max (argmin (f(x)-rx)) Cost lp = min_slope - 1, rp = max_slope + 1; while (rp - lp > 1) { Cost p = (lp + rp) / 2; // xp: max (argmin f(x)-px) (= min (argmin f(x)-(p+1)x)) int xp = g(p) - g(p + 1); (x <= xp ? rp : lp) = p; } return g(rp) + Cost(rp) * x; } /** * @brief evaluates f(x) (f: convex) * @param g p -> { inf(f(x)-px), min argmin(f(x)-px) } */ template <typename Cost, typename DP, std::enable_if_t<std::is_invocable_r_v<std::pair<Cost, int>, DP, Cost>, std::nullptr_t> = nullptr> Cost alien_convex(int x, Cost min_slope, Cost max_slope, DP g) { Cost lp = min_slope - 1, rp = max_slope + 1; while (rp - lp > 1) { Cost p = (lp + rp) / 2; // g(p).second: min (argmin f(x)-px) (g(p).second <= x ? lp : rp) = p; } return g(lp).first + Cost(lp) * x; } /** * @brief evaluates f(x) (f: concave) * @param g p -> sup(f(x)-px) */ template <typename Cost, typename DP, std::enable_if_t<std::is_invocable_r_v<Cost, DP, Cost>, std::nullptr_t> = nullptr> Cost alien_concave(int x, Cost min_slope, Cost max_slope, DP g) { // min (argmax f(x)-rx) <= x Cost lp = min_slope - 1, rp = max_slope + 1; while (rp - lp > 1) { Cost p = (lp + rp) / 2; // xp: min (argmax f(x)-px) (= max (argmax f(x)-(p+1)x)) int xp = g(p) - g(p + 1); (xp <= x ? rp : lp) = p; } return g(rp) + Cost(rp) * x; } /** * @brief evaluates f(x) (f: concave) * @param g p -> { sup(f(x)-px), max argmax(f(x)-px) } */ template <typename Cost, typename DP, std::enable_if_t<std::is_invocable_r_v<std::pair<Cost, int>, DP, Cost>, std::nullptr_t> = nullptr> Cost alien_concave(int x, Cost min_slope, Cost max_slope, DP g) { // x <= max (argmax f(x)-lx) Cost lp = min_slope - 1, rp = max_slope + 1; while (rp - lp > 1) { Cost p = (lp + rp) / 2; // g(p).second: max (argmax f(x)-px) (x <= g(p).second ? lp : rp) = p; } return g(lp).first + Cost(lp) * x; } } // namespace suisen #line 4 "test/src/optimization/alien_dp/abc218_h_1.test.cpp" #include <algorithm> #include <iostream> #include <vector> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, r; std::cin >> n >> r; std::vector<long long> a(n - 1); for (auto &e : a) { std::cin >> e; } // sup f(x)-px auto g = [&](long long p) { std::vector<std::pair<long long, int>> dp0(n, { -(1LL << 60), -n-1 }), dp1(n, { -(1LL << 60), -n-1 }); dp0[0] = { 0, 0 }; dp1[0] = { -p, 1 }; for (int i = 0; i < n - 1; ++i) { dp0[i + 1] = std::max<std::pair<long long, int>>(dp0[i], { dp1[i].first + a[i], dp1[i].second }); dp1[i + 1] = std::max<std::pair<long long, int>>({ dp1[i].first - p, dp1[i].second + 1 }, { dp0[i].first - p + a[i], dp0[i].second + 1 }); } return std::max(dp0[n - 1], dp1[n - 1]); }; std::cout << suisen::alien_concave<long long>(r, -2'000'000'000LL, +2'000'000'000LL, g) << std::endl; }