# bzoj 2726 [SDOI2012]任务安排

5 1

1 3

3 2

4 3

2 3

1 4

153

### 题解

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 300009;
int N, S, V[maxn], q[maxn], stk[maxn], T[maxn], F[maxn];
ll dp[maxn];
bool chk(int a, int b, int c) {
int xl = T[b] - T[a], xr = T[c] - T[b];
ll yl = dp[b] - dp[a], yr = dp[c] - dp[b];
return ((xl < 0) ^ (xr < 0)) ? yl * xr <= yr * xl : yl * xr >= yr * xl;
}
bool Jud(int a, int b, int k) {
ll x = T[b] - T[a], y = dp[b] - dp[a];
return x < 0 ? y > x * k : y < x * k;
}
ll calc(int x, int y) {
return dp[y] + ll(F[x]) * (T[x] - T[y] + S);
}
void cdq(int l, int r) {
if(l + 1 == r) return;
int m = (l + r) >> 1;
int ql = l, qr = m;
for(int i = l; i < r; i++)
q[i] < m ? V[ql++] = q[i] : V[qr++] = q[i];
for(int i = l; i < r; i++) q[i] = V[i];
cdq(m, r);
int h = 0, t = -1;
for(int i = m; i < r; i++) {
while(t > 0 && chk(stk[t - 1], stk[t], q[i])) t--;
stk[++t] = q[i];
}
for(int i = l; i < m; i++) {
while(h < t && Jud(stk[h], stk[h + 1], F[q[i]])) h++;
dp[q[i]] = min(dp[q[i]], calc(q[i], stk[h]));
}
cdq(l, m);
ql = l, qr = m;
for(int i = l; i < r; i++) if(ql >= m) {
V[i] = q[qr++];
} else if(qr >= r) {
V[i] = q[ql++];
} else
V[i] = T[q[ql]] < T[q[qr]] ? q[ql++] : q[qr++];
for(int i = l; i < r; i++) q[i] = V[i];
}
main() {
scanf("%d%d", &N, &S);
for(int i = 0; i < N; i++) {
scanf("%d%d", T + i, F + i);
q[i] = N - i - 1;
}
T[N] = F[N] = 0;
for(int i = N; i--; )
T[i] += T[i + 1], F[i] += F[i + 1];
for(int i = 0; i < N; i++)
dp[i] = ll(F[i]) * (T[i] + S);
cdq(0, N);
printf("%lld\n", dp[0]);
}