定义 $dp_i$ 是把前 i 个工厂料理完，在 i 处建了一个仓库的最小花费。然后我推出了这样一个柿子：

$dp_i=\min_{j<i}\{ dp_j+c_i+(sump_{i}-sump_{j})\times x_i-(sumpx_i-sumpx_j)\}$

其中 $sump_i$ 表示 $p_i$ 的前缀和，$sumpx_i$ 表示 $p_i\times x_i$ 的前缀和。

然后我们有点的坐标 $(sump_i,dp_i-sumpx_i)$ 斜率：$x_i$。排序后能够保证斜率是递增的。然后写挂了，WA11分，不知道为什么，求助。

#include<bits/stdc++.h>
using namespace std;
struct node{
    long long xt,pt,ct;
    friend bool operator<(node a,node b){
        return a.xt<b.xt;
    }
}cts[1000005];
long long n,x[1000005],p[1000005],c[1000005],sp[1000005];
long long spx[1000005],dp[1000005],deq[1000005],s=1,t=1;
long double slope(int u,int v){
    if(sp[u]==sp[v])
        return 1e18;
    return ((long double)dp[u]-spx[u]-dp[v]+spx[v])/((long double)sp[u]-sp[v]);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>cts[i].xt>>cts[i].pt>>cts[i].ct;
    sort(cts+1,cts+n+1);
    for(int i=1;i<=n;i++){
        x[i]=cts[i].xt;
        p[i]=cts[i].pt;
        c[i]=cts[i].ct;
        sp[i]=sp[i-1]+p[i];
        spx[i]=spx[i-1]+p[i]*x[i];
    }
    for(int i=1;i<=n;i++){
        while(s<t&&slope(deq[s],deq[s+1])<x[i])
            s++;
        dp[i]=dp[deq[s]]+c[i]+(sp[i]-sp[deq[s]])*x[i]-(spx[i]-spx[deq[s]]);
        while(s<t&&slope(deq[t-1],deq[t])>slope(deq[t],i))
            t--;
        deq[++t]=i;
    }
    cout<<dp[n];
}