Mining

#include <bits/stdc++.h>

using namespace std;


typedef long long ll;

const ll INF = (ll) 1e18;

const ll N = 5005;

ll x[N];
ll w[N];
ll P[N];
ll S[N];
int n;

vector<ll> newH;
vector<ll> newF;

struct Line {
    ll K;
    ll B;

    Line(ll K = 0, ll B = 0): K(K), B(B) {}
};

Line q[N];

double getInter(Line a, Line b) {
    return (a.B - b.B) * 1.0 / (b.K - a.K);
}

const double eps = 1e-9;

bool throwAway(const Line& a, const Line& b, const Line& c) {
    double x_last = getInter(c, b);
    double x_pred = getInter(a, b);
    return x_pred - eps > x_last;
}

ll calc(Line l, ll x) {
    return l.K * x + l.B;
}

struct LineDeque {
    int head;
    int tail;

    LineDeque(): head(0), tail(0) {}

    void add(Line newLine) {
        while (head <= tail - 2 && throwAway(q[tail - 2], q[tail - 1], newLine))
            tail--;
        q[tail] = newLine;
        tail++;
    }

    ll getBest(ll x) {
        while (head + 1 < tail && calc(q[head], x) >= calc(q[head + 1], x))
            head++;
        return calc(q[head], x);
    }
};

void calcLayer(vector<ll>& oldF, vector<ll>& oldH) {
    fill(newH.begin(), newH.end(), INF);
    newH[0] = 0;
    fill(newF.begin(), newF.end(), INF);
    LineDeque lf;
    for (int i = 1; i <= n; i++) {
        lf.add(Line(-S[i - 1], oldH[i - 1] + P[i - 1]));
        newF[i] = lf.getBest(x[i]) + x[i] * S[i] - P[i];
    }
    LineDeque lh;
    for (int i = 1; i <= n; i++) {
        lh.add(Line(-x[i], newF[i] - P[i - 1] + x[i] * S[i - 1]));
        newH[i] = lh.getBest(S[i]) + P[i];
    }
    copy(newF.begin(), newF.end(), oldF.begin());
    copy(newH.begin(), newH.end(), oldH.begin());
}

int main() {
    ios_base::sync_with_stdio(0);
    int k;
    cin >> n >> k;
    newH.resize(n + 1);
    newF.resize(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> w[i];
    for (int i = 1; i <= n; i++) {
        P[i] = P[i - 1] + w[i] * x[i];
        S[i] = S[i - 1] + w[i];
    }
    vector<ll> f(n + 1, INF);
    for (int r = 1; r <= n; r++)
        f[r] = P[0] - x[r] * S[0] + x[r] * S[r] - P[r];
    vector<ll> h(n + 1, INF);
    h[0] = 0;
    for (int r = 1; r <= n; r++)
        for (int l = 1; l <= r; l++)
            h[r] = min(h[r], f[l] - P[l - 1] + x[l] * S[l - 1] - x[l] * S[r] + P[r]);
    for (int i = 2; i <= k; i++)
        calcLayer(f, h);
    cout << h[n] << endl;
    return 0;
}