Code:
#include<bits/stdc++.h> #define setIO(s) freopen(s".in","r",stdin) #define maxn 1000004 #define x(i) (a[i]) #define y(i) (f[i]+b[i]) #define ll long long using namespace std; ll dis[maxn],p[maxn],cost[maxn],a[maxn],b[maxn],f[maxn]; int q[maxn], tail, head; double slope(int i,int j) { return (double)(1.0*y(i)-y(j))/(double)(1.0*x(i)-x(j)); } int main() { // setIO("input"); int n,i,j; scanf("%d",&n); for(i=1;i<=n;++i) { scanf("%lld%lld%lld",&dis[i],&p[i],&cost[i]); a[i]=a[i-1]+p[i]; b[i]=b[i-1]+p[i]*dis[i]; } head=tail=0; for(i=1;i<=n;++i) { while(head<tail && slope(q[head], q[head+1]) < dis[i]) ++head; f[i]=f[q[head]] + dis[i]*(a[i]-a[q[head]]) - (b[i]-b[q[head]]) + cost[i]; while(head<tail && slope(q[tail], i) < slope(q[tail-1], i)) --tail; q[++tail]=i; } printf("%lld\n",f[n]); return 0; }