代码

// noi17e 【NOI2017】蔬菜
// Greedy: process types by decreasing a_i, assigning units to the latest free
// slots <= their deadlines (DSU over days, bulk per day).  Queries p<P are
// answered by dropping the cheapest sold units as the capacity m*p shrinks.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

static const int MAXN = 100005;
static int n, m, k;
static ll a[MAXN], s[MAXN], c[MAXN], x[MAXN];
static ll qp[MAXN];
static ll cap[MAXN + 2];      // free slots per day
static int nxt[MAXN + 2];     // DSU: greatest free day <= d
static ll t_i[MAXN];          // units sold per type
static ll ansArr[MAXN + 2];
static ll itVal[MAXN * 2], itAsg[MAXN * 2];

static int find(int d) {
    int r = d;
    while (nxt[r] != r) r = nxt[r];
    while (nxt[d] != r) { int nx = nxt[d]; nxt[d] = r; d = nx; }
    return r;
}

typedef unsigned long long u64;
struct DI { u64 abi; const char*in; u64 insz; char*out; u64 outlim; u64 outsz; char*err;
            u64 errlim; u64 errsz; const char*IB; u64 IBlim; char*OB; u64 OBlim; u64 tscfreq; }
            __attribute__((packed));

static const char *IN; static u64 INSZ; static char *OUT; static u64 OUTSZ = 0; static u64 OUTLIM;

#ifndef TEST_IO
static void run();
extern "C" int __libc_start_main(int (*mm)(int, char**, char**), int argc, char **argv,
                                 void (*i)(void), void (*f)(void), void (*l)(void), void *se) {
    (void)mm; (void)argc; (void)argv; (void)i; (void)f; (void)l; (void)se;
    DI *di = (DI *)0x243FFF90ULL;
    IN = di->in; INSZ = di->insz; OUT = di->out; OUTLIM = di->outlim;
    run();
    di->outsz = OUTSZ;
    register long rax __asm__("rax") = 60;
    register long rdi __asm__("rdi") = 0;
    __asm__ volatile("syscall" :: "a"(rax), "D"(rdi) : "rcx", "r11", "memory");
    __builtin_unreachable();
}
#endif
static void run();
#ifdef TEST_IO
static char tbuf[1 << 26];
static char tobuf[1 << 24];
int main() {
    size_t got = fread(tbuf, 1, sizeof(tbuf), stdin);
    IN = tbuf; INSZ = got; OUT = tobuf; OUTLIM = sizeof(tobuf);
    run();
    fwrite(tobuf, 1, OUTSZ, stdout);
    return 0;
}
#else
int main() { return 0; }
#endif

static void run() {
    const char *p = IN, *pend = IN + INSZ;
    static const unsigned int P10[9] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
    auto rd = [&]() -> ll {
        while (p < pend && (*p < '0' || *p > '9')) p++;
        ll v = 0;
        while (p + 8 <= pend) {
            unsigned long long xx;
            __builtin_memcpy(&xx, p, 8);
            unsigned long long bad = ((xx ^ 0x3030303030303030ULL) + 0x7676767676767676ULL)
                                     & 0x8080808080808080ULL;
            if (bad) break;                       // fewer than 8 digits in this window
            unsigned long long d = xx - 0x3030303030303030ULL;
            unsigned long long t = (d * 10 + (d >> 8)) & 0x00FF00FF00FF00FFULL;
            t = (t * 100 + (t >> 16)) & 0x0000FFFF0000FFFFULL;
            t = (t * 10000 + (t >> 32)) & 0xFFFFFFFFULL;
            v = v * 100000000LL + (ll)(unsigned)t;
            p += 8;
        }
        while (p < pend && *p >= '0' && *p <= '9') v = v * 10 + (*p++ - '0');
        return v;
    };
    n = (int)rd(); m = (int)rd(); k = (int)rd();
    for (int i = 0; i < n; i++) { a[i] = rd(); s[i] = rd(); c[i] = rd(); x[i] = rd(); }
    ll P = 0;
    for (int i = 0; i < k; i++) { qp[i] = rd(); if (qp[i] > P) P = qp[i]; }
    if (P <= 0) { for (int i = 0; i < k; i++) { *OUT = '0'; OUT[1] = '\n'; } OUTSZ = 2ULL * k; return; }

    for (int d = 0; d <= (int)P + 1; d++) { cap[d] = (d >= 1 && d <= (int)P) ? m : 0; nxt[d] = d; }
    if (m == 0) { for (int i = 0; i < k; i++) { *OUT = '0'; OUT[1] = '\n'; } OUTSZ = 2ULL * k; return; }

    ll total = 0, sold = 0;
    // items: bonus (value a+s, 1 unit, deadline Dmax) and regular (value a, c-1 units)
    static u64 rec[MAXN * 2], rec2[MAXN * 2];
    int ni2 = 0;
    for (int i = 0; i < n; i++) {
        if (c[i] <= 0) continue;
        if (c[i] >= 1) rec[ni2++] = ((u64)(unsigned)(0xFFFFFFFFu - (unsigned)(a[i] + s[i])) << 32) | ((u64)(unsigned)i << 1) | 0u;
        if (c[i] >= 2) rec[ni2++] = ((u64)(unsigned)(0xFFFFFFFFu - (unsigned)a[i]) << 32) | ((u64)(unsigned)i << 1) | 1u;
    }
    {
        static unsigned cntR[256];
        u64 *s1 = rec, *s2 = rec2, *tmp;
        for (int shift = 32; shift < 64; shift += 8) {
            memset(cntR, 0, sizeof(cntR));
            for (int i = 0; i < ni2; i++) cntR[(s1[i] >> shift) & 255u]++;
            unsigned sum = 0;
            for (int b = 0; b < 256; b++) { unsigned cc = cntR[b]; cntR[b] = sum; sum += cc; }
            for (int i = 0; i < ni2; i++) { unsigned b = (unsigned)((s1[i] >> shift) & 255u); s2[cntR[b]++] = s1[i]; }
            tmp = s1; s1 = s2; s2 = tmp;
        }
        if (s1 != rec) memcpy(rec, s1, sizeof(u64) * (size_t)ni2);
    }
    for (int idx = 0; idx < ni2; idx++) {
        int i = (int)((rec[idx] >> 1) & 0x1FFFFFu);
        int kind = (int)(rec[idx] & 1u);
        ll val = (ll)(unsigned)(0xFFFFFFFFu - (unsigned)(rec[idx] >> 32));
        itVal[idx] = val;
        ll limit = (kind == 0) ? 1 : c[i] - 1;
        int dmax;
        if (kind == 0) {
            if (x[i] == 0) dmax = (int)P;
            else dmax = (int)min<ll>((c[i] + x[i] - 1) / x[i], P);
        } else {
            if (x[i] == 0) dmax = (int)P;
            else dmax = (int)min<ll>((c[i] - 1 + x[i] - 1) / x[i], P);
        }
        ll assigned = 0;
        int d = dmax;
        while (d >= 1 && assigned < limit) {
            int day = find(d);
            if (day == 0) break;
            ll avail;
            if (kind == 0) avail = 1;
            else if (x[i] == 0) avail = c[i] - 1;
            else {
                ll expired = min<ll>(c[i] - 1, (ll)(day - 1) * x[i]);
                avail = (c[i] - 1) - expired;
            }
            ll canTake = min(cap[day], avail - assigned);
            if (canTake > 0) {
                ll take = min(limit - assigned, canTake);
                cap[day] -= take;
                assigned += take;
                if (cap[day] == 0) nxt[day] = day - 1;
                if (assigned >= limit) break;
            }
            d = day - 1;
        }
        itAsg[idx] = assigned;
        total += assigned * val;
        sold += assigned;
    }
    // undo: drop the cheapest sold units as the capacity m*p shrinks.
    // `it` is sorted by decreasing value, so walk it backwards.
    ll kept = sold, cur = total;
    int idx2 = ni2 - 1;
    ll rem = 0;
    for (int pp = (int)P; pp >= 1; pp--) {
        ll target = min(sold, (ll)m * pp);
        while (kept > target && idx2 >= 0) {
            ll availCnt = itAsg[idx2] - rem;
            ll need = kept - target;
            ll take = min(availCnt, need);
            cur -= take * itVal[idx2];
            kept -= take;
            rem += take;
            if (rem >= itAsg[idx2]) { idx2--; rem = 0; }
        }
        ansArr[pp] = cur;
    }
    // output
    static const char DIG2[201] =
      "00010203040506070809101112131415161718192021222324252627282930313233343536373839"
      "40414243444546474849505152535455565758596061626364656667686970717273747576777879"
      "8081828384858687888990919293949596979899";
    char *o = OUT;
    for (int i = 0; i < k; i++) {
        ll v = ansArr[(int)qp[i]];
        if (v < 0) v = 0;
        char tmp[24]; int kk = 0;
        while (v >= 100) { ll r = v % 100; v /= 100; tmp[kk++] = DIG2[2*r+1]; tmp[kk++] = DIG2[2*r]; }
        if (v >= 10) { tmp[kk++] = DIG2[2*v+1]; tmp[kk++] = DIG2[2*v]; }
        else tmp[kk++] = (char)('0' + (int)v);
        while (kk) *o++ = tmp[--kk];
        *o++ = '\n';
    }
    OUTSZ = (u64)(o - OUT);
    return;
}

评测结果