代码

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i)
#define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i)
#define For(i,a,b) for(i=(a),i<=(b);++i)
#define Forward(i,a,b) for(i=(a),i>=(b);--i)
#define Chkmin(a,b) a=a<b?a:b
#define Chkmax(a,b) a=a>b?a:b
#define pb push_back
inline void read(int &x)
{
    static const int BUFSIZE = 1048576;
    static char buf[BUFSIZE];
    static char *bufnow = buf;
    static char *bufmax = buf;
    if (bufnow == bufmax) {
        bufmax = buf + fread(buf, 1, BUFSIZE, stdin);
        bufnow = buf;
    }
    static int c;
    c = *bufnow++;
    for (;!isdigit(c);c = *bufnow++) {
            if (bufnow == bufmax) {
            bufmax = buf + fread(buf, 1, BUFSIZE, stdin);
            bufnow = buf;
        }
    }
    x = 0;
    for (;isdigit(c);c = *bufnow++) {
        x = (x << 1) + (x << 3) + c - 48;
        if (bufnow == bufmax) {
            bufmax = buf + fread(buf, 1, BUFSIZE, stdin);
            bufnow = buf;
        }
    }
}

inline void write(int a,char ed='\n')
{
    static short s[13],tp;
    if(!a){putchar('0'),putchar(ed);return;}
    for(tp=0;a;a/=10)s[++tp]=a%10;
    for(;tp;putchar(s[tp--]^48));
    putchar(ed);
}
using namespace std;
void file()
{
#ifndef ONLINE_JUDGE
    freopen("water.in","r",stdin);
    freopen("water.out","w",stdout);
#endif
}

const int MAXN=1e5+7;

static int n,m,k;

static int a[MAXN],s[MAXN],c[MAXN],x[MAXN];

typedef long long ll;

static int que[MAXN],P;

static vector<int>App[MAXN];

inline void init()
{
    read(n);read(m);read(k);
    Rep(i,1,n)read(a[i]),read(s[i]),read(c[i]),read(x[i]);
    Rep(i,1,k)read(que[i]),Chkmax(P,que[i]);
    Rep(i,1,n)
    {
        if(x[i])App[min(P,(c[i]+x[i]-1)/x[i])].push_back(i);
        else App[P].push_back(i);
    }
}

typedef pair<int,int>Pr;

static priority_queue<Pr>G;

static priority_queue<Pr,vector<Pr>,greater<Pr> >K;

static bool us[MAXN];

static ll ans[MAXN],sold;

static int got[MAXN];

static queue<int>shown;

inline void solve()
{
    static int poi,t;
    static ll an=0ll;
    static int u,v;
    Repe(i,P,1)
    {
        for(int j:App[i])G.push(Pr(a[j]+s[j],j));
        if(G.empty())continue;
        for(poi=m;poi&&!G.empty();G.pop())
        {
            u=G.top().first,v=G.top().second;
            if(!us[v])
            {
                us[v]=true;++got[v];an+=u;--poi;
                if(c[v]>1)G.push(Pr(a[v],v));
            }
            else
            {
                t=min(poi,c[v]-got[v]-(i-1)*x[v]);
                poi-=t;got[v]+=t;an+=(ll)u*t;
                if(got[v]<c[v])shown.push(v);
            }
        }
        for(;!shown.empty();shown.pop())
        {
            u=shown.front();
            G.push(Pr(a[u],u));
        }
    }
    ans[P]=an;
    static long long num=0ll;
    Rep(i,1,n)
    {
        if(got[i]==1)K.push(Pr(a[i]+s[i],i));
        else if(got[i])K.push(Pr(a[i],i));
        sold+=got[i];if(got[i])num+=got[i]*a[i]+s[i];
    }
    Repe(i,P-1,1)
    {
        ans[i]=ans[i+1];
        if(sold<=i*m)continue;
        poi=sold-i*m;
        while(poi)
        {
            u=K.top().first;v=K.top().second;K.pop();
            if(got[v]>1)
            {
                t=min(poi,got[v]-1);
                got[v]-=t;poi-=t;ans[i]-=(ll)t*u;
                if(got[v]==1)K.push(Pr(a[v]+s[v],v));
                else K.push(Pr(u,v));
            }
            else{--poi;--got[v];ans[i]-=u;}
        }sold=m*i;
    }
    Rep(i,1,k)printf("%lld\n",ans[que[i]]);
}

int main()
{
    init();
    solve();
    return 0;
}

评测结果