斜率优化

# include <stdio.h>

# include <stdlib.h>

# include <iostream>

# include <string.h>

# include <algorithm>

# define IL inline

# define RG register

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

IL ll Read(){

    RG char c = getchar(); RG ll x = 0, z = 1;

    for(; c > '9' || c < '0'; c = getchar()) z = c == '-' ? -1 : 1;;

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';

    return x * z;

}

const int MAXN(20010), INF(2e9);

int n, Q[MAXN], tail, head, w[MAXN], d[MAXN];

int dis[MAXN], s[MAXN], ans, f[MAXN], c[MAXN], g[MAXN];

IL double Calc(RG int i, RG int j){

    return 1.0 * (c[i] - c[j]) / (w[i] - w[j]);

}

int main(){

    n = Read();

    for(RG int i = 1; i <= n; i++)

        w[i] = w[i - 1] + Read(), d[i] = Read();

    for(RG int i = 1; i <= n + 1; i++){

        dis[i] = dis[i - 1] + d[i - 1];

        s[i] = s[i - 1] + w[i - 1] * d[i - 1];

        c[i] = w[i] * dis[i];

    }

    for(RG int i = 1; i <= n; i++)

        g[i] = s[n + 1] + c[i] - w[i] * dis[n + 1];

    ans = INF;

    Q[0] = 1;

    for(RG int i = 2; i <= n; i++){

        while(head < tail && Calc(Q[head], Q[head + 1]) <= dis[i]) head++;

        RG int j = Q[head];

        ans = min(ans, g[i] + c[j] - w[j] * dis[i]);

        while(head < tail && Calc(Q[tail - 1], Q[tail]) >= Calc(Q[tail], i)) tail--;

        Q[++tail] = i;

    }

    printf("%d\n", ans);

    return 0;

}