Submission #53788285

---

Source Code Expand

#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);

    auto f = [&](int i, int j) { return dist[i] + cost(i, j); };

    // (f(i, *), intersection with the previous function)
    std::deque<std::pair<int, int>> dq;
    auto intersection = [&](int i1, int i2) {
        if (f(i1, i2) >= f(i2, i2)) return -1;
        int lb = i2, ub = N;
        while (ub - lb > 1) {
            int m = (lb + ub) / 2;
            if (f(i1, m) <= f(i2, m)) {
                lb = m;
            } else {
                ub = m;
            }
        }
        return lb;
    };
    auto add = [&](int i) {
        int x = -1;
        while (dq.size() >= 2 &&
               dq.back().second >= (x = intersection(dq.back().first, i))) {
            dq.pop_back();
        }
        if (dq.size() == 1) x = intersection(dq.back().first, i);
        dq.push_back({i, x});
    };
    auto get = [&](int i) {
        while (dq.size() >= 2 && f(dq.front().first, i) > f(dq[1].first, i)) {
            dq.pop_front();
        }
        dq.front().second = -1;
        return f(dq.front().first, i);
    };

    dist[0] = 0;
    add(0);
    for (int i = 1; i < N; ++i) {
        dist[i] = get(i);
        add(i);
    }
    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;
}

Submission Info

Judge Result