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
| #include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, m, k, tot, fa[100005], g[100005], cnt, usd[200005], usa[200005];
ll ans[200005];
struct Node{
int a, b, c, d;
}nd[200005];
bool cmp(Node x, Node y){
return x.a>y.a;
}
int myfind(int x){
return fa[x]==x?x:fa[x]=myfind(fa[x]);
}
int main(){
cin>>n>>m>>k;
for(int i=1; i<=n; i++){
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
nd[++tot] = (Node){a+b, 1, 0, d?(c-1)/d+1:100000};
if(c>1) nd[++tot] = (Node){a, c-1, d, d?(c-2)/d+1:100000};
}
for(int i=1; i<=100000; i++) fa[i] = i;
sort(nd+1, nd+1+tot, cmp);
for(int i=1; i<=tot; i++){
cnt++;
int p=myfind(nd[i].d);
ll now=nd[i].b-(ll)(p-1)*nd[i].c;
while(p && now>0){
ll tmp=min((ll)m-g[p], now);
g[p] += tmp; usa[cnt] += tmp; usd[cnt] = nd[i].a; now -= tmp;
ans[100000] += (ll)tmp * nd[i].a;
if(g[p]==m) fa[p] = myfind(p-1);
now += (ll)(p-1)*nd[i].c;
p = myfind(p-1);
now -= (ll)(p-1)*nd[i].c;
}
if(!myfind(100000)) break;
}
tot = 0;
for(int i=1; i<=100000; i++) tot += g[i];
for(int i=99999; i; i--){
ans[i] = ans[i+1];
if(tot<=i*m) continue;
ll lim=tot-i*m;
while(lim){
ll mn=min(lim, (ll)usa[cnt]);
ans[i] -= mn * usd[cnt];
lim -= mn; usa[cnt] -= mn;
if(!usa[cnt]) cnt--;
}
tot = i * m;
}
for(int i=1; i<=k; i++){
scanf("%d", &tot);
printf("%lld\n", ans[tot]);
}
return 0;
}
|