RT，P2120仓库建设求条

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1000005;
ll n,sumx[MAXN],p[MAXN],sump[MAXN],c[MAXN],sumxp[MAXN];
ll f[MAXN],q[MAXN],g[MAXN],h,t;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>sumx[i]>>p[i]>>c[i];
		sump[i]=sump[i-1]+p[i];
		sumxp[i]=sumxp[i-1]+sumx[i]*p[i];
	}
	for(long long i=0;i<=n;i++){
		while(h<t&&(g[q[h+1]]-g[q[h]])<=sumx[i]*(sump[q[h+1]]-sump[q[h]])) h++;
		f[i]=f[q[h]]-sumx[i]*sump[q[h]]+sumxp[q[h]]+c[i]+sumx[i]*sump[i]-sumxp[i];
		g[i]=f[i]+sumxp[i];
		while(h<t&&(g[q[t]]-g[q[t-1]])*(sump[i]-sump[q[t]])>=(g[i]-g[q[t]])*(sump[q[t]]-sump[q[t-1]])) t--;
		q[++t]=i;
	}
	for(int i=n;i>=0;i--){
		if(p[i]>0){
			cout<<f[i];
			return 0;
		}
	}
	return 0; 
}