DP+斜率优化。
DP方程为dp[i]:=max(dp[j]+(p[k]*(x[i]-x[k]))+c[i]) (j<k<i)
化简为dp[i]:=max(dp[j]+x[i]*(sum[i]-sum[j])+sum2[i]-sum2[j]+c[i]) (j<i)，其中sum[i]表示p[1]到p[i]的总和，sum2[i]表示p[1]*x[1]到p[i]*x[i]的总和。
接着进行斜率优化，我就不再多说。。。
-
var
-
n,i,s,t,a:longint;
-
d,p,c,dp,sp,sxp,x,y,dd:array[0..1000001] of int64;
-
begin
-
read(n);
-
inc(n);
-
d[1]:=0;p[1]:=0;c[1]:=0;
-
for i:=2 to n do read(d[i],p[i],c[i]);
-
for i:=1 to n do sp[i]:=sp[i-1]+p[i];
-
for i:=1 to n do sxp[i]:=sxp[i-1]+d[i]*p[i];
-
for i:=1 to n do x[i]:=sp[i];
-
dp[1]:=c[1]+d[1]*sp[1]-sxp[1];
-
dd[1]:=1;
-
t:=1;
-
s:=1;
-
y[1]:=dp[1]+sxp[1];
-
for i:=2 to n do
-
begin
-
while s<t do
-
if (y[dd[s+1]]-y[dd[s]])/(x[dd[s+1]]-x[dd[s]])<d[i]
-
then begin
-
dd[s]:=0;
-
inc(s);
-
end
-
else break;
-
a:=dd[s];
-
dp[i]:=dp[a]+c[i]+d[i]*(sp[i]-sp[a])-(sxp[i]-sxp[a]);
-
y[i]:=dp[i]+sxp[i];
-
while t>s do
-
if (y[i]-y[dd[t]])/(x[i]-x[dd[t]])<(y[dd[t]]-y[dd[t-1]])/(x[dd[t]]-x[dd[t-1]])
-
then begin
-
dd[t]:=0;
-
dec(t);
-
end
-
else break;
-
inc(t);
-
dd[t]:=i;
-
end;
-
write(dp[n]);
-
end.