提出 #53788299

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i)
#define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i)
#define all(x) begin(x), end(x)
template <typename T>
bool chmax(T& a, const T& b) {
    return a < b ? (a = b, 1) : 0;
}
template <typename T>
bool chmin(T& a, const T& b) {
    return a > b ? (a = b, 1) : 0;
}

template <typename F>
long long golden_section_search(F f, long long lb, long long ub) {
    // t-s, s, t are consecutive fibonacci numbers
    long long s = 1, t = 2;
    while (t < ub - lb + 2) std::swap(s += t, t);
    long long l = lb - 1, m1 = l + t - s, m2 = l + s;
    auto v1 = f(m1), v2 = f(m2);
    while (m1 != m2) {
        std::swap(s, t -= s);
        if (ub < m2 || v1 <= v2) {
            m2 = m1;
            v2 = v1;
            m1 = l + t - s;
            v1 = f(m1);
        } else {
            l = m1;
            m1 = m2;
            v1 = v2;
            m2 = l + s;
            v2 = m2 <= ub ? f(m2) : v1;
        }
    }
    return m1;
}

template <typename T, typename F>
std::vector<T> monge_shortest_path(int N, const F& cost) {
    const T INF = std::numeric_limits<T>::max() / 2;
    std::vector<T> dist(N, INF);
    dist[0] = 0;
    std::vector<int> amin(N);

    auto update = [&](int i, int k) {
        if (i <= k) return;
        auto nd = dist[k] + cost(k, i);
        if (nd < dist[i]) {
            dist[i] = nd;
            amin[i] = k;
        }
    };

    auto dfs = [&](auto& dfs, int l, int r) -> void {
        if (r - l == 1) return;
        int m = (l + r) / 2;
        for (int k = amin[l]; k <= amin[r]; ++k) update(m, k);
        dfs(dfs, l, m);
        for (int k = l + 1; k <= m; ++k) update(r, k);
        dfs(dfs, m, r);
    };

    dfs(dfs, 0, N - 1);
    return dist;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int N, K;
    cin >> N >> K;
    vector<ll> P(N + 1);
    rep(i, 1, N + 1) cin >> P[i];

    vector<ll> P0(N + 2), P1(N + 2);
    rep(i, 0, N + 1) {
        P0[i + 1] = P0[i] + P[i];
        P1[i + 1] = P1[i] + P[i] * i;
    }

    auto cost = [&](int i, int j) {
        if (i == 0 && j == N + 1) return (ll)1e18;
        if (i == 0) {
            return j * P0[j] - P1[j];
        }
        if (j == N + 1) {
            return (P1[N + 1] - P1[i]) - i * (P0[N + 1] - P0[i]);
        }
        int m = (i + j) / 2 + 1;
        return (P1[m] - P1[i]) - i * (P0[m] - P0[i]) + j * (P0[j] - P0[m]) -
               (P1[j] - P1[m]);
    };

    auto calc = [&](ll lambda) {
        auto dist = monge_shortest_path<ll>(
            N + 2, [&](int i, int j) { return cost(i, j) + lambda; });
        return dist[N + 1] - lambda * (K + 1);
    };

    ll lambda = golden_section_search([&](ll lambda) { return -calc(lambda); },
                                      0, 3e10);
    cout << calc(lambda) << endl;
}

提出情報

ジャッジ結果