记录编号	600981	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	2774.[NOI 2017]蔬菜	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	0.861 s
提交时间	2025-05-22 20:18:09	内存使用	8.15 MiB

#include<bits/stdc++.h>
#define maxn 100005
#define int long long
int n,m,k,ans[maxn*10],a[maxn],s[maxn],c[maxn],x[maxn],sld[maxn],cnt,qry[maxn],mx;
bool vis[maxn];
std::vector<int>ap[maxn];
struct node
{
	int v,id;
	bool operator<(const node&x)
		const{return v<x.v;}
};std::priority_queue<node>q;
std::queue<int>qq;
inline bool cmp(int&x,int&y){return x>y;}
inline int read()
{
	int x = 0,f = 1;char ch = getchar();
	while(ch<'0'||ch>'9')f = ch == '-'?-f:f,ch = getchar();
	while(ch>='0'&&ch<='9')x = (x<<3)+(x<<1)+(ch^'0'),ch = getchar();
	return x*f;
}
inline void write(int x)
{
	if(x<0)putchar('-'),x = -x;
	static char sta[35];int top = 0;
	do{sta[top++] = x%10^'0',x/=10;}while(x);
	while(top)putchar(sta[--top]);
	putchar('\n');
}
signed main()
{
	 freopen("vegetables.in","r",stdin);
	 freopen("vegetables.out","w",stdout);
	n = read(),m = read(),k = read(),mx;
	for(int i = 1;i<=n;++i)
		a[i] = read(),s[i] = read(),c[i] = read()-1,x[i] = read();
	for(int i = 1;i<=k;++i)mx = std::max(mx,qry[i] = read());
	for(int i = 1;i<=n;++i)
		if(!x[i])ap[mx].push_back(i);
		else ap[std::min(mx,c[i]/x[i]+1)].push_back(i);
	node u;
	for(int i = mx,lft,num,v,id;lft = m,i;--i)
	{
		for(int v:ap[i])q.push({a[v]+s[v],v});
		while(!q.empty()&&lft)
		{
			v = q.top().v,id = q.top().id,q.pop();
			if(vis[id])
			{
				num = std::min(lft,c[id]-(i-1)*x[id]-sld[id]);
				if(x[id]||sld[id]!=c[id])qq.push(id);
				lft-=num,sld[id]+=num;
				for(int j = 1;j<=num;++j)ans[++cnt] = v;
			}
			else if(c[id]-(i-1)*x[id])
				vis[id] = true,--lft,ans[++cnt] = v,q.push({a[id],id});
			else vis[id] = true,--lft,ans[++cnt] = v,qq.push(id);
		}
		while(!qq.empty())q.push({a[qq.front()],qq.front()}),qq.pop();
	}
	std::sort(ans+1,ans+cnt+1,cmp);
	for(int i = 1;i<=cnt;++i)ans[i]+=ans[i-1];
	for(int i = 1;i<=k;++i)write(ans[std::min(cnt,qry[i]*m)]);
	return 0;
}