斜率优化,交叉相乘
#include<cstdio> #include<algorithm> using namespace std; int t[1000005],f[1000005]; long long F[1000005],G[1000005],Sum[1000005],C[1000005]; struct node{ long long k,b; }stack[1000005]; double check(node a,node b){ return ((double)a.b-b.b)/(b.k-a.k); } int main(){ int n,S; scanf("%d%d",&n,&S); for (int i=1; i<=n; i++){ scanf("%d%d",&t[i],&f[i]); Sum[i]=Sum[i-1]+t[i]; C[i]=C[i-1]+f[i]; } int top=0; for (int i=0; i<=n; i++){ int L=1,R=top; while (L<R){ int mid=(L+R)>>1; double l,r; if (mid==1) l=-1ll<<60; else l=check(stack[mid-1],stack[mid]); if (mid==top) r=1ll<<60; else r=check(stack[mid+1],stack[mid]); if (Sum[i]>=l && Sum[i]<=r){ L=mid; break; } else if (Sum[i]<l) R=mid-1; else L=mid+1; } F[i]=stack[L].k*Sum[i]+stack[L].b; F[i]+=Sum[i]*C[n]; G[i]=F[i]+(-Sum[i]+S)*(C[n]-C[i]); node line=(node){-C[i],G[i]}; while (top>=2 &&(stack[top].b-stack[top-1].b)*(line.k-stack[top].k)<= (line.b-stack[top].b)*(stack[top].k-stack[top-1].k))top--; stack[++top]=line; } printf("%lld ",F[n]); return 0; }