题目正着做不好做。
然而考虑逆向思维。
把时间轴反转，则问题变成了每次会运来一些菜，询问最大的价值。
先考虑如何回答一个询问。
从(p)开始倒推。
我们当前的最高价值的菜一定会卖掉。这是因为如果拖到后面会占用更多的空间，后面很可能会有更高价值的菜运过来。
于是可以维护一个大根堆(x)。首先把所有当前的菜的(a_i+s_i)插入堆，然后每次删除最大价值的。
维护一个回收堆(y)，表示当前还有什么菜。
在删除(x)的元素后，若这个元素的菜没被卖光，则把这个菜的(a)值插入(y)中。
然而后面的点数据范围为(10^5)，上述算法无能为力。
由于(q)的范围为(10^5)，且卖出天数如果相同，则答案也相同。
所以考虑求出卖出(1 o 10^5)天的答案。
由于前面的时间的菜的集合一定包含后面的时间的菜的集合，所以发现(p-1)可以选择的菜包含(p)可以选择的。
(p-1)天比(p)天要少卖掉的只有(m)个菜。
并且卖掉任意的菜都可以。
显然我们只需要不卖价值最小的(m)个菜即可。
在实现上，要先考虑不卖没有额外价值，再不卖有额外价值的部分。
最终时间复杂度(O(pmlog_2n+q))
细节看代码。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100010
int n,m,k,ans[N],a[N],s[N],c[N],x[N],vi[N],sl[N],ct;
vector<int>v[N];
struct n1{
int x,y;
};
int operator <(n1 x,n1 y){
return x.y<y.y;
}
struct n2{
int x,y;
};
int operator <(n2 x,n2 y){
return x.y>y.y;
}
priority_queue<n1>q1;
priority_queue<n2>q2;
queue<int>q;
signed main(){
int p=1e5;
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld%lld",&a[i],&s[i],&c[i],&x[i]);
if(!x[i])
v[p].push_back(i);
else
v[min(p,(c[i]+x[i]-1)/x[i])].push_back(i);
}
for(int i=p;i;i--){
for(int j=0;j<v[i].size();j++){
int x=v[i][j];
q1.push((n1){x,a[x]+s[x]});
}
int f=m;
while(!q1.empty()&&f){
n1 y=q1.top();
q1.pop();
if(!vi[y.x]){
vi[y.x]=1;
ans[p]+=y.y;
f--;
sl[y.x]++;
ct++;
if(c[y.x]!=1)
q1.push((n1){y.x,a[y.x]});
}
else{
int t=c[y.x]-(i-1)*x[y.x]-sl[y.x];
t=min(t,f);
ans[p]+=y.y*t;
f-=t;
sl[y.x]+=t;
ct+=t;
if(sl[y.x]!=c[y.x])
q.push(y.x);
}
}
while(!q.empty()){
int x=q.front();
q.pop();
q1.push((n1){x,a[x]});
}
}
for(int i=1;i<=n;i++){
if(sl[i]==1)
q2.push((n2){i,a[i]+s[i]});
else if(sl[i])
q2.push((n2){i,a[i]});
}
for(int i=p-1;i;i--){
ans[i]=ans[i+1];
if(ct<=i*m)
continue;
int f=ct-i*m;
while(!q2.empty()&&f){
n2 y=q2.top();
q2.pop();
if(sl[y.x]==1){
sl[y.x]=0;
f--;
ans[i]-=y.y;
}
else{
int t=min(f,sl[y.x]-1);
f-=t;
sl[y.x]-=t;
ans[i]-=t*y.y;
if(sl[y.x]==1)
q2.push((n2){y.x,s[y.x]+a[y.x]});
else
q2.push((n2){y.x,a[y.x]});
}
}
ct=i*m;
}
for(int i=1;i<=k;i++){
int p;
scanf("%lld",&p);
printf("%lld
",ans[p]);
}
}