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/arc168/tasks/arc168_e" #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, k; long long s; std::cin >> n >> k >> s; std::vector<long long> a(n); for (auto& e : a) { std::cin >> e; } std::vector<long long> sa(n + 1); for (int i = 0; i < n; ++i) { sa[i + 1] = sa[i] + a[i]; } std::vector<int> max_l(n + 1); for (int r = 0; r <= n; ++r) { max_l[r] = int(std::upper_bound(sa.begin(), sa.end(), sa[r] - s) - sa.begin()) - 1; } constexpr long long inf = 1LL << 60; auto solve = [&](int p) { std::vector<std::pair<long long, int>> dp(n + 1, { inf, n + 1 }); dp[0] = { 0LL, 0 }; for (int i = 1; i <= n; ++i) { dp[i] = dp[i - 1]; if (int j = max_l[i]; j >= 0) { dp[i] = std::min(dp[i], std::pair{ dp[j].first + (i - j - 1) - p, dp[j].second + 1 }); } } return dp[n]; }; int ok = 0, ng = k + 1; while (ng - ok > 1) { int x = (ok + ng) / 2; (suisen::alien_convex<long long>(x, 0, n, solve) <= n - k ? ok : ng) = x; } std::cout << ok << std::endl; }
#line 1 "test/src/optimization/alien_dp/arc168_e_1.test.cpp" #define PROBLEM "https://atcoder.jp/contests/arc168/tasks/arc168_e" #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/arc168_e_1.test.cpp" #include <algorithm> #include <iostream> #include <vector> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, k; long long s; std::cin >> n >> k >> s; std::vector<long long> a(n); for (auto& e : a) { std::cin >> e; } std::vector<long long> sa(n + 1); for (int i = 0; i < n; ++i) { sa[i + 1] = sa[i] + a[i]; } std::vector<int> max_l(n + 1); for (int r = 0; r <= n; ++r) { max_l[r] = int(std::upper_bound(sa.begin(), sa.end(), sa[r] - s) - sa.begin()) - 1; } constexpr long long inf = 1LL << 60; auto solve = [&](int p) { std::vector<std::pair<long long, int>> dp(n + 1, { inf, n + 1 }); dp[0] = { 0LL, 0 }; for (int i = 1; i <= n; ++i) { dp[i] = dp[i - 1]; if (int j = max_l[i]; j >= 0) { dp[i] = std::min(dp[i], std::pair{ dp[j].first + (i - j - 1) - p, dp[j].second + 1 }); } } return dp[n]; }; int ok = 0, ng = k + 1; while (ng - ok > 1) { int x = (ok + ng) / 2; (suisen::alien_convex<long long>(x, 0, n, solve) <= n - k ? ok : ng) = x; } std::cout << ok << std::endl; }