WA on #2,代码如下:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4+10;
int n, stk[N], top, q[N], h = 1, t = 1;
long long f[N];
struct node{
int w, l;
} p[N];
bool cmp(node x, node y) {
if (x.w == y.w) return x.l < y.l;
return x.w < y.w;
}
double K(int a, int b) {
return 1.0 * (f[b] - f[a]) / (p[stk[a+1]].l - p[stk[b+1]].l);
}
signed main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i ++)
scanf("%lld%lld", &p[i].w, &p[i].l);
sort(p+1, p+n+1, cmp);
for (int i = 1; i <= n; i ++) {
while (top && p[i].l > p[stk[top]].l) top --;
stk[++ top] = i;
}
for (int i = 1; i <= top; i ++) {
while (h < t && K(q[h], q[h+1]) <= p[stk[i]].w) h ++;
f[i] = f[q[h]] + p[stk[i]].w * p[stk[q[h]+1]].l;
while (h < t && K(q[t-1], q[t]) >= K(q[t], i)) t --;
q[++ t] = i;
}
printf("%lld", f[top]);
}