test/src/optimization/alien_dp/abc218_h_2.test.cpp

View this file on GitHub
Last update: 2024-01-31 02:46:42+09:00
Problem: https://atcoder.jp/contests/abc218/tasks/abc218_h

Depends on

Alien Dp (library/optimization/alien_dp.hpp)

Code

#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]).first;
    };

    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_2.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_2.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]).first;
    };

    std::cout << suisen::alien_concave<long long>(r, -2'000'000'000LL, +2'000'000'000LL, g) << std::endl;
}