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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
| #include<bits/stdc++.h>
using namespace std;
const int maxn = 210;
#define ll long long
int n;
int read()
{
char ch = getchar(); int x = 0, f = 1;
while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
struct Node
{
int cost;
ll num;
};
vector<ll>v;
struct node
{
ll cost;
ll num;
}tree[maxn<<2];
void PushUp(int rt)
{
tree[rt].cost=tree[rt<<1].cost+tree[rt<<1|1].cost;
tree[rt].num=tree[rt<<1].num+tree[rt<<1|1].num;
}
void update(int l,int r,int rt,int pos,ll k)
{
if(l==r)
{
tree[rt].cost+=1ll*k*pos;
tree[rt].num+=k;
return ;
}
int mid = (l+r)>>1;
if(pos>mid)update(mid+1,r,rt<<1|1,pos,k);
else update(l,mid,rt<<1,pos,k);
PushUp(rt);
}
ll query(int rt,int l,int r,ll k )
{
if(k<=0)return 0;
if(l==r)
{
return 1ll*l*k;
}
int mid = (l+r)>>1;
if(tree[rt<<1].num>=k)
{
return query(rt<<1,l,mid,k);
}
else
{
return tree[rt<<1].cost+query(rt<<1|1,mid+1,r,k-tree[rt<<1].num);
}
}
int main()
{
while(cin>>n)
{
map<ll,vector<Node> >mp;
for(int i=0;i<maxn*4;i++)
{
tree[i].cost=0;
tree[i].num=0;
}
v.clear();
for(int i=0;i<n;i++)
{
int h,c,p;
h=read();
c=read();
p=read();
mp[h].push_back(Node{c,p});
v.push_back(h);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
ll sum = 0;
for(auto i : v)
{
for(auto k:mp[i])
{
update(1,200,1,k.cost,k.num);
sum+=k.num;
}
}
ll ans = 1e18;
ll pre = 0;
for(int i=v.size()-1;i>=0;i--)
{
ll tempsum = 0;
ll tempcost = 0;
for(auto k:mp[v[i]])
{
tempsum+=k.num;
tempcost += 1ll*k.num*k.cost;
update(1,200,1,k.cost,-k.num);
}
sum -= tempsum;
ans = min(ans,pre+query(1,1,200,sum-tempsum+1));
pre+=tempcost;
}
cout<<ans<<endl;
}
return 0;
}
|