Luogu

LOJ

分析

考虑求出卖了 $i$ 个蔬菜时的最大收益 $ans_i$。

容易想到，我们要先卖贵的菜，且要尽量靠后卖。

用一个堆维护所有还有存货的蔬菜，然后每次选一个收益最大的放在能放的最后的一天。

通过并查集维护每一天往前到哪一天才有没有用掉卖的额度即可求出这一天。

假设最多能卖 $cnt$ 个蔬菜，则前 $i$ 天的答案为 $ans_{\min\left\{cnt,m\times i\right\}}$，因为在后面卖掉的菜放到前面来也是一定能卖掉的。

这么讲相当抽象，不过看一下代码应该就懂了。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,L=100000;

int n,m,k,a[N],s[N],c[N],x[N];
priority_queue<pair<int,int> > Q;
int f[N],r[N];
int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }
ll ans[N*10];

int main() {
    n=read(),m=read(),k=read();
    for (int i=1;i<=n;++i) a[i]=read(),s[i]=read(),c[i]=read(),x[i]=read();
    for (int i=1;i<=n;++i) Q.push(make_pair(a[i]+s[i],i));
    for (int i=1;i<=L;++i) f[i]=i,r[i]=m;
    int cnt=0;
    while (!Q.empty()) {
        int w=Q.top().first,p=Q.top().second; Q.pop();
        int t=find(x[p]?min(L,int(ceil(1.*c[p]/x[p])+0.5)):L);
        if (!t) continue;
        --c[p],--r[t],++cnt,ans[cnt]=ans[cnt-1]+w;
        if (!r[t]) f[t]=find(t-1);
        if (c[p]) Q.push(make_pair(a[p],p));
    }
    while (k--) printf("%lld\n",ans[min(cnt,m*read())]);
    return 0;
}