这题面写得有毒……应该理解为对于第$i$种蔬菜，有$x _i$个单位只能在第一天卖，有$x _i$个单位只能在第二天结束前卖，以此类推. 也就是说，说你把当天结束本来要变质的蔬菜卖了，那天就不会有蔬菜变质了.
那么我们就有一个朴素的贪心策略：每种蔬菜尽量等到它快要变质了才卖，也就是时间上从后往前贪心. 如果有两种蔬菜要抢夺某一天出售的机会，那肯定是从贵的开始贪心.
这个算法看上去很正确，但是它没有办法处理$s _i$. 方法是把每种蔬菜拆成两部分：$(a _i,c _i-1)$和$(a _i+s _i,1)$，后者的过期时间即为该种蔬菜最晚的销售时间，然后把所有这些东西按价格排序，每种价格从后往前贪心就可以了. 每种蔬菜在某一天可以销售的量等于贪心到那个时候还剩下的量减去那天之前变质的量. 要用并查集或者set来查询上一个还可以销售的时间.
但是这样只能处理一个询问. 用反证法容易证明$k$天的答案一定是$k+1$天的答案的子集，而在较后时间出售的蔬菜在较前的时间显然也可以出售，那么只需要对$\max p _i$算出答案，然后每天去掉最廉价的若干单位蔬菜就可以了. 每天需要去掉的量其实就是，把蔬菜的销售尽量往前放之后，当天销售的量.
代码：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
using namespace std;
const ele INF=1e18;
struct st{
ele a,c,d,x;
inline bool operator<(st b)const{
return a!=b.a?a<b.a:d<b.d;
}
}b[maxn];
ele n,m,K,mx,p[maxn],a[maxn],s[maxn],c[maxn],x[maxn],u[maxn],prv[maxn],r[maxn],res[maxn],f[10000010];
priority_queue<st> Q;
ele getf(ele *u,ele x){
return u[x]<0?x:(u[x]=getf(u,u[x]));
}
inline void uni(ele x,ele y){
ele a=getf(u,x),b=getf(u,y);
if (a!=b) u[a]=b;
}
int main(){
scanf("%lld%lld%lld",&n,&m,&K);
for (int i=0; i<n; ++i) scanf("%lld%lld%lld%lld",a+i,s+i,c+i,x+i);
mx=0;
for (int i=0; i<K; ++i) scanf("%lld",p+i),mx=max(mx,p[i]);
for (int i=0; i<n; ++i)
if (x[i]){
ele d=(c[i]-1)/x[i]+1;
b[i<<1]=(st){a[i]+s[i],1,d-1,0};
b[i<<1|1]=(st){a[i],c[i]-1,d-1,x[i]};
}
else{
b[i<<1]=(st){a[i]+s[i],1,mx-1,0};
b[i<<1|1]=(st){a[i],c[i]-1,mx-1,0};
}
for (int i=0; i<n*2; ++i)
if (b[i].d>=0 && b[i].c) Q.push(b[i]);
memset(u,-1,sizeof(u));
for (int i=0; i<mx; ++i) prv[i]=i-1,r[i]=m;
prv[0]=mx; u[mx]=-1;
ele ans=0,cnt=0;
while (Q.size() && getf(u,mx-1)!=mx){
st k=Q.top(); Q.pop();
ele d=getf(u,min(k.d,mx-1));
while (d<mx && k.c){
ele tmp=min(k.c-k.x*d,r[d]);
k.c-=tmp; r[d]-=tmp;
ans+=k.a*tmp;
for (int j=0; j<tmp; ++j) f[cnt++]=-k.a;
if (!r[d]) uni(d,prv[d]);
d=getf(u,prv[d]);
}
}
sort(f,f+cnt);
res[mx]=ans;
ele tot=0;
for (int i=0; i<mx; ++i) tot+=m-r[i];
memset(r,0,sizeof(r));
for (int i=0; i<mx; ++i) r[i]=min(m,tot),tot-=r[i];
for (int i=mx-1; ~i; --i){
res[i]=res[i+1];
for (int j=0; j<r[i]; ++j) res[i]-=-f[--cnt];
}
for (int i=0; i<K; ++i) printf("%lld\n",res[p[i]]);
return 0;
}