1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| const int N = 1000005,INF = (1ull<<63)-1;
int x[N],p[N],c[N],f[N];
int n;
class lctree{
private:
struct{int l,r;pair<int,int> f;} tr[N];
int val(pair<int,int> f,int x){return f.first*x+f.second;};
int idx;
public:
int root;
void insert(int &u,int l,int r,pair<int,int> f){
if(!u)
tr[u=++idx].f = f;
else{
int mid = (l+r)>>1;
if(val(f,mid)<val(tr[u].f,mid))
swap(f,tr[u].f);
if(f.first>tr[u].f.first)
insert(tr[u].l,l,mid,f);
else
insert(tr[u].r,mid+1,r,f);
}
}
int query(int u,int l,int r,int p){
if(!u)
return INF;
int mid = (l+r)>>1;
return min(val(tr[u].f,p),p<=mid?query(tr[u].l,l,mid,p):query(tr[u].r,mid+1,r,p));
}
}tr;
signed main(){
n = in;
int V = 0;
for(int k=1;k<=n;k++){
x[k] = in,p[k] = in,c[k] = in;
V = max(V,x[k]);
}
tr.insert(tr.root,0,V,{0,0});
int sp = 0,sxp = 0;
for(int k=1;k<=n;k++){
sp += p[k];
sxp += x[k]*p[k];
f[k] = tr.query(tr.root,0,V,x[k])+x[k]*sp-sxp+c[k];
tr.insert(tr.root,0,V,{-sp,f[k]+sxp});
}
int ans = f[n];
for(int k=n;k&&!p[k];k--)
ans = min(ans,f[k-1]);
out(ans);
return 0;
}
|