题目描述
小 N 是蔬菜仓库的管理员，负责设计蔬菜的销售方案。
在蔬菜仓库中，共存放有nn 种蔬菜，小NN 需要根据不同蔬菜的特性，综合考虑各方面因素，设计合理的销售方案，以获得最多的收益。
在计算销售蔬菜的收益时，每销售一个单位第ii 种蔬菜，就可以获得a_iai 的收益。
特别地，由于政策鼓励商家进行多样化销售，第一次销售第 i 种蔬菜时，还会额外得到s_isi 的额外收益。
在经营开始时，第ii 种蔬菜的库存为c_ici 个单位。
然而，蔬菜的保鲜时间非常有限，一旦变质就不能进行销售，不过聪明的小 N 已经计算出了每个单位蔬菜变质的时间：对于第ii 种蔬菜，存在保鲜值x_ixi ，每天结束时会有x_ixi 个单位的蔬菜变质，直到所有蔬菜都变质。（注意：每一单位蔬菜的变质时间是固定的，不随销售发生变化）
形式化地：对于所有的满足条件d \times x_i \leqslant cid×xi⩽ci 的正整数dd ，有x_ixi 个单位的蔬菜将在第dd 天结束时变质。
特别地，若(d - 1) \times x_i \leqslant c_i \leqslant d \times x_i(d−1)×xi⩽ci⩽d×xi ，则有c_i - (d - 1) \times x_ici−(d−1)×xi 单位的蔬菜将在第dd 天结束时变质。
注意，当x_i = 0xi=0 时，意味着这种蔬菜不会变质。
同时，每天销售的蔬菜总量也是有限的，最多不能超过mm 个单位。
现在，小 N 有kk 个问题，想请你帮忙算一算。每个问题的形式都是：对于已知的p_jpj ，如果需要销售p_jpj 天，最多能获得多少收益？
输入输出格式
输入格式：
第一行包含三个正整数n, m, kn,m,k ，分别表示蔬菜的种类数目、每天能售出蔬菜总量上限、小 N 提出的问题的个数。
接下来nn 行，每行输入四个非负整数，描述一种蔬菜的特点，依次为a_i, s_i, c_i, x_iai,si,ci,xi ，意义如上文所述。
接下来kk 行，每行输入一个非负整数p_jpj ，意义如上文所述。
输出格式：
输出kk 行，每行包含一个整数，第ii 行的数表示第ii 个问题的答案。
题意：
定义了一种蔬菜为：ai,si,ci,xi;
意思是蔬菜的价格为ai，第一份卖出时价格为ai+si,一共有ci份，每天会有xi份过期；每天最多卖出m份蔬菜，多组输入天数依次最大化收入；
题解：
①一个很神的贪心：我们尽量晚点卖过期晚的，早点卖贵的；
②现在想象有一个天数的序列，我们狡猾而又贪心地往里面填蔬菜。为了处理第一次卖出，我们把一种蔬菜分成两种，(1,ai+si)和(ci-1,ai)，第一份蔬菜最后过期。把所有蔬菜里最贵的先拿出来，找到当前蔬菜最后过期的那一天，尽量把那一天放满，满了之后再往前面找，后面过期的在前一天一定可以放，动态加上比较早过期的一直放直到放不下或放完。
③本来能放的最后一天(可以(ci-1)/xi+1)o(1)算，并查集维护一下往前没满的第一个位置可以保证复杂度。注意特判一下 xi==0永不过期；
⑤要求多组询问，考虑d天内卖掉的蔬菜为S，我们d-1天一定是丢掉比较便宜的蔬菜，丢掉的个数即为d天选的蔬菜减前面空着的总份数，求出最后一天的状态往前减即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N = ;
int n,m,k,f[N],d[N],ga[N],g[N],cnt,tot,Q[N],maxd,upd[N];
ll ans[N],sum,L[N],R;
struct node {int c,a,x,d;}A[N];
char gc(){
static char *p1,*p2,s[];
if(p1==p2) p2=(p1=s)+fread(s,,,stdin);
return (p1==p2)?EOF:*p1++;
}
int rd(){
int x = ; char c = gc();
while(c<''||c>'') c = gc();
while(c>=''&&c<='') x = x * + c - '',c = gc();
return x;
}
bool cmp(const node &x,const node &y){return x.a > y.a;}
int find(int x){return(f[x]==x)?x:f[x]=find(f[x]);}
void Union(int x,int y){int fx = find(x),fy = find(y);if(fx==fy)return;f[fy] = fx;}
void calc(int idx,int c,int a){
sum += 1ll * c * a;
g[cnt] += c,ga[cnt] = a;
d[idx] += c;
if(d[idx]==m) Union(idx-,idx);
}
int main()
{ //freopen("mzoj1115.in","r",stdin);
//freopen("mzoj1115.out","w",stdout);
freopen("testdata.in","r",stdin);
freopen("testdata.out","w",stdout);
n = rd(); m = rd(); k = rd();
for(int i = ,a,s,c,x;i <= n;i++){
a=rd(),s=rd(),c=rd(),x=rd();
A[++tot] = (node){,a+s,,x?(c-)/x+:N};
if(--c) A[++tot] = (node){c,a,x,x?(c-)/x+:N};
}
for(int i = ,x;i <= k;i++) {
maxd = max(maxd,Q[i] = rd());
}
sort(A+,A+tot+,cmp);
for(int i = ;i <= maxd;i++) f[i] = i;
for(int i = ;i <= tot;i++) {
cnt++;
int idx=find(min(A[i].d,maxd));
int res = (idx-)*A[i].x,now = A[i].c - res;
while(idx&&now){
int tmp = m - d[idx];
int mn = min(tmp,now);
calc(idx,mn,A[i].a);
now -= mn;
int p = idx; idx = find(idx - ); p-=idx;
if(res) now += p*A[i].x,res -= p*A[i].x;
}
if(!find(maxd)) break;
}
//for(int i = 1;i <= cnt/2;i++) swap(g[i],g[cnt-i+1]),swap(ga[i],ga[cnt-i+1]);
for(int i = ;i <= maxd;i++) L[i] = m - d[i] + L[i - ];
for(int i = maxd;i >= ;i--)
upd[i] = max(R - L[i],0ll),R+=d[i];
for(int i = maxd;i>=;i--){
ans[i] = sum;
int tmp = upd[i-] - upd[i];
while(tmp){
int mn = min(tmp,g[cnt]);
sum -= 1ll * ga[cnt] * mn;
tmp -= mn; g[cnt] -= mn; if(!g[cnt]) cnt--;
}
}
for(int i = ;i <= k;i++) printf("%lld\n",ans[Q[i]]);
return ;
}//by tkys_Austin;