题解

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;const int N=1e5+10;typedef long long ll;
int n;int m;int k;ll a[N];ll s[N];ll x[N];ll c[N];ll ans[N];
struct data
{
	ll v;int pos;
	friend bool operator <(data a,data b){return a.v<b.v;}
};priority_queue <data> pq;
struct nod
{
	ll v;int pos;
	friend bool operator <(nod a,nod b){return a.v>b.v;}
};priority_queue <nod> hp;
queue <int> us;int p=1e5;ll tot;
vector <int> app[N];bool used[N];ll sd[N];
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++){scanf("%d%d%d%d",&a[i],&s[i],&c[i],&x[i]);}
	for(int i=1;i<=n;i++)//处理每天出现的菜 
	{
		if(x[i]==0){app[p].push_back(i);}
		else {app[min((ll)p,(c[i]+x[i]-1)/x[i])].push_back(i);}
	}
	for(int i=p;i>=1;i--)
	{
		for(int j=0;j<app[i].size();j++)pq.push((data){a[app[i][j]]+s[app[i][j]],app[i][j]});
		if(pq.empty()){continue;}//先插入所有可能的菜 
		for(ll lim=m;lim&&!pq.empty();pq.pop())
		{
			data now=pq.top();//取出堆头 
			if(used[now.pos]==false)//获得si 
			{
				used[now.pos]=true;ans[p]+=now.v;sd[now.pos]++;lim--;
				if(c[now.pos]!=1){pq.push((data){a[now.pos],now.pos});}//重新插回去 
			}
			else //贪心的多取 
			{
				ll rem=c[now.pos]-sd[now.pos]-(i-1)*x[now.pos];//剩余的 
				ll del=min(rem,lim);ans[p]+=del*now.v;sd[now.pos]+=del;lim-=del;
				if(sd[now.pos]!=c[now.pos]){us.push(now.pos);}//放到回收的队列里 
			}
		}
		for(;!us.empty();us.pop()){int nw=us.front();pq.push((data){a[nw],nw});}//重新插回去 
	}
	for(int i=1;i<=n;i++)//递推ans 
	{
		if(sd[i]==1){hp.push((nod){s[i]+a[i],i});}//特判si 
		else if(sd[i]!=0){hp.push((nod){a[i],i});}tot+=sd[i];//统计下现在卖了多少菜 
	}
	for(int i=p-1;i>=1;i--)
	{
		ans[i]=ans[i+1];if(tot<=m*i){continue;}//如果还是可以卖一样的菜就不扔菜 
		for(ll lim=tot-m*i;lim&&!hp.empty();)//否则扔代价和最小的菜 
		{
			nod now=hp.top();hp.pop();//取出堆头 
			if(sd[now.pos]!=1)//扔掉非si部分 
			{
				ll del=min(sd[now.pos]-1,lim);
				sd[now.pos]-=del;lim-=del;ans[i]-=del*now.v;
				if(sd[now.pos]==1){hp.push((nod){a[now.pos]+s[now.pos],now.pos});}
				else {hp.push((nod){a[now.pos],now.pos});}//判一下是不是需要插回去 
			}
			else {lim--;sd[now.pos]--;ans[i]-=now.v;}//扔掉si部分 
		}tot=m*i;//更改tot 
	}
	for(int i=1,t;i<=k;i++){scanf("%d",&t);printf("%lld\n",ans[t]);}//查表出答案 
	return 0;//拜拜程序~ 
}