复习斜率优化。

#include
     
      #include
      
       #include
       
        using namespace std;typedef long long LL;int list[1010000];LL f[1010000],d[1010000],sp[1010000];LL s[1010000],p[1010000],c[1010000];double X(int j){    return double(f[j]+d[j]);}double Y(int j){    return double(sp[j]);}double slope(int j1,int j2){    return (X(j1)-X(j2))/(Y(j1)-Y(j2));}int main(){    int n;    scanf("%d",&n);    for(int i=1;i<=n;i++)scanf("%lld%lld%lld",&s[i],&p[i],&c[i]);    d[0]=0;sp[0]=0;    for(int i=1;i<=n;i++)    {        sp[i]=sp[i-1]+p[i];        d[i]=d[i-1]+p[i]*s[i];    }    int head=1,tail=1;    list[1]=0;    for(int i=1;i<=n;i++)    {        while(head
        
         
          slope(list[tail],i))tail--;        list[++tail]=i;    }    printf("%lld\n",f[n]);    return 0;}