记录编号	599373	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2017]蔬菜	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	2.005 s
提交时间	2025-03-08 21:51:32	内存使用	7.96 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pir pair<ll,ll>
#define ls first
#define rs second
#define mp make_pair
#define mod
#define MAXN 100010
#define V 100000
#define qmod(x) (x>mod?x-mod:x)
// By flyfreemrn
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
ll s[MAXN],a[MAXN],c[MAXN],x[MAXN];
ll n,m,qs;
ll cnt[MAXN],ans[MAXN],used;
vector<ll> vec[MAXN],sp;
//bool used[MAXN];
priority_queue<pir,vector<pir>,greater<pir> > q2;
priority_queue<pir> q1;
int main(){
	freopen("vegetables.in","r",stdin);
	freopen("vegetables.out","w",stdout);
	n=read(),m=read(),qs=read();
	for(int i=1;i<=n;i++){
		a[i]=read(),s[i]=read(),c[i]=read(),x[i]=read();
		if(x[i]==0)vec[V].push_back(i);
		else{
			ll lim=(c[i]-1)/x[i]+1;
			vec[lim].push_back(i);
//			cout<<lim<<endl;
		}
	}
	for(int i=V;i;i--){
		for(int j=0;j<vec[i].size();j++){
			ll now=vec[i][j];
			if(!cnt[now])q1.push(mp(a[now]+s[now],now));
			else q1.push(mp(a[now],now));
		}
		for(int j=1;j<=m;j++){
			if(q1.empty())break;
			pir now=q1.top();
			q1.pop();
			used++,cnt[now.rs]++,ans[V]+=now.ls;
			if(cnt[now.rs]<c[now.rs]-x[now.rs]*(i-1))q1.push(mp(a[now.rs],now.rs));
			else sp.push_back(now.rs);
		}
		for(int j=0;j<sp.size();j++)if(cnt[sp[j]]<c[sp[j]])vec[i-1].push_back(sp[j]);
		sp.clear();
	}
//	for(int i=1;i<=3;i++)cout<<sum[i]<<endl;
	for(int i=1;i<=n;i++){
		if(cnt[i]>1)q2.push(mp(a[i],i));
		else if(cnt[i]==1)q2.push(mp(a[i]+s[i],i));
	}
//	cout<<ans[V]<<" "<<cnt[1]<<" "<<cnt[2]<<endl;
	for(int i=V-1;i;i--){
		ans[i]=ans[i+1];
		while(used>i*m){
			pir now=q2.top();
			q2.pop();
			used--,ans[i]-=now.ls,cnt[now.rs]--;
			if(cnt[now.rs]>1)q2.push(mp(a[now.rs],now.rs));
			else if(cnt[now.rs]==1)q2.push(mp(a[now.rs]+s[now.rs],now.rs));
		}
	}
	for(int i=1;i<=qs;i++){
		ll pos=read();
		cout<<ans[pos]<<endl;
	}
	return 0;
}