代码

#include<bits/stdc++.h>
#define MAXN 100000
#define LL long long
using namespace std;
template<typename T>void Read(T &cn)
{
	char c;int sig = 1;
	while(!isdigit(c = getchar()))if(c == '-')sig = -1;cn = c-48;
	while(isdigit(c = getchar()))cn = cn*10+c-48;cn*=sig;
}
template<typename T>void Write(T cn)
{
	if(cn < 0) {putchar('-'); cn = 0-cn; }
	int wei = 0; T cm = 0; int cx = cn%10; cn/=10;
	while(cn)wei++,cm = cm*10+cn%10,cn/=10;
	while(wei--)putchar(cm%10+48),cm/=10;
	putchar(cx+48);
}
int n,m,k;
struct qwe{
	int a,s,x,c;
	int zui;
	inline friend bool operator <(qwe a,qwe b)
	{
		return a.zui > b.zui;
	}
	void getit() {Read(a); Read(s); Read(c); Read(x); zui = x ? (int)ceil((double)c/(double)x) : MAXN; zui = min(zui,MAXN); }
};
qwe a[MAXN+1];
int dui[MAXN+1];
int yong[MAXN+1];
int zhan[MAXN+1],zlen;
int Cmp1(int cn,int cm) {return a[cn].a + a[cn].s * (yong[cn] == 0) < a[cm].a + a[cm].s * (yong[cm] == 0); }
int Cmp2(int cn,int cm) {return a[cn].a + a[cn].s * (yong[cn] == 1) > a[cm].a + a[cm].s * (yong[cm] == 1); }
LL ans;
LL ans_p[MAXN+1];
int zong;
int sheng(int cn,int cm) {return a[cn].c - yong[cn] - 1ll*(cm-1) * (a[cn].x); }
signed main()
{
//	freopen("testdata_2.in","r",stdin);
//	freopen("testdata_2.ou","w",stdout);
	Read(n); Read(m); Read(k);
	for(int i = 1;i<=n;i++)a[i].getit();
	sort(a+1,a+n+1);
//	for(int i = 1;i<=n;i++)printf("a[%d].zui = %d a[%d].a = %d\n",i,a[i].zui,i,a[i].a);
	int dang = 0; ans = 0;
	int dlen = 0;
	memset(yong,0,sizeof(yong));
	for(int i = MAXN;i>=1;i--)
	{
		while(dang < n && a[dang+1].zui >= i)
		{
			dui[++dlen] = ++dang;
			push_heap(dui+1,dui+dlen+1,Cmp1);
		}
		int xian = 0;
		zlen = 0;
		while(xian < m && dlen)
		{
			int lin = dui[1];
//			if(i >= 200 && i<=260)printf("i = %d lin = %d %d %d\n",i,lin,Cmp1(2,4),sheng(lin,i));
			pop_heap(dui+1,dui+(dlen--)+1,Cmp1);
			if(!yong[lin]){
				yong[lin]++; xian++;
				ans = ans + a[lin].a + a[lin].s;
				dui[++dlen] = lin;
				push_heap(dui+1,dui+dlen+1,Cmp1);
			}
			else{
				zhan[++zlen] = lin;
				if(sheng(lin,i) <= 0)continue;
				int lin2 = min(sheng(lin,i),m-xian);
//				if(lin == 4)printf("lin2 = %d\n",lin2);
				ans = ans + 1ll*lin2 * a[lin].a;
				yong[lin] += lin2;
				xian += lin2;
			}
		}
		for(int j = 1;j<=zlen;j++) if(yong[zhan[j]] < a[zhan[j]].c) {dui[++dlen] = zhan[j]; push_heap(dui+1,dui+dlen+1,Cmp1);}
	}
	ans_p[MAXN] = ans;
	dlen = 0; zong = 0;
//	for(int i = 1;i<=n;i++)printf("yong[%d] = %d\n",i,yong[i]);
	for(int i = 1;i<=n;i++)zong += yong[i];
	for(int i = 1;i<=n;i++)if(yong[i])dui[++dlen] = i,push_heap(dui+1,dui+dlen+1,Cmp2);
	for(int i = MAXN-1;i>=1;i--)
	{
		while(zong > i*m)
		{
			int lin = dui[1]; pop_heap(dui+1,dui+(dlen--)+1,Cmp2);
			if(yong[lin] == 1){
				int lin2 = 1;
				int lin3 = a[lin].a + a[lin].s;
				ans = ans - 1ll*lin2 * lin3;
				yong[lin] -= lin2;
				zong -= lin2;
				continue;
			}
			int lin2 = min(yong[lin]-1,zong - i*m);
			int lin3 = a[lin].a;
			ans = ans - 1ll*lin2*lin3;
			yong[lin] -= lin2;
			zong -= lin2;
			dui[++dlen] = lin;
			push_heap(dui+1,dui+dlen+1,Cmp2);
		}
		ans_p[i] = ans;
	}
	for(int i = 1;i<=k;i++) {int bx; Read(bx); Write(ans_p[bx]); putchar('\n'); }
	return 0;
}

评测结果