代码

// 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 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; }
    nxt[0] = 0;
    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)
    struct Item { ll val; int type; int kind; ll assigned; };
    static Item it[MAXN * 2];
    int ni2 = 0;
    for (int i = 0; i < n; i++) {
        if (c[i] <= 0) continue;
        if (c[i] >= 1) it[ni2++] = Item{a[i] + s[i], i, 0, 0};
        if (c[i] >= 2) it[ni2++] = Item{a[i], i, 1, 0};
    }
    sort(it, it + ni2, [](const Item &u, const Item &v) { return u.val > v.val; });
    for (int idx = 0; idx < ni2; idx++) {
        int i = it[idx].type;
        ll limit = (it[idx].kind == 0) ? 1 : c[i] - 1;
        int dmax;
        if (it[idx].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 (it[idx].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;
        }
        it[idx].assigned = assigned;
        total += assigned * it[idx].val;
        sold += assigned;
    }
    // items for the undo: (value, count)
    static pair<ll, ll> items[MAXN * 2];
    int ni = 0;
    for (int idx = 0; idx < ni2; idx++) {
        if (it[idx].assigned > 0) items[ni++] = make_pair(it[idx].val, it[idx].assigned);
    }
    sort(items, items + ni);
    ll kept = sold, cur = total;
    int ptr = 0, rem = 0;   // rem units already removed from items[ptr]
    for (int pp = (int)P; pp >= 1; pp--) {
        ll target = min(sold, (ll)m * pp);
        while (kept > target && ptr < ni) {
            ll availCnt = items[ptr].second - rem;
            ll need = kept - target;
            ll take = min(availCnt, need);
            cur -= take * items[ptr].first;
            kept -= take;
            rem += (int)take;
            if (rem == items[ptr].second) { ptr++; rem = 0; }
        }
        ansArr[pp] = cur;
    }
    // output
    char *o = OUT;
    for (int i = 0; i < k; i++) {
        ll v = ansArr[(int)qp[i]];
        char tmp[24]; int kk = 0;
        do { tmp[kk++] = (char)('0' + v % 10); v /= 10; } while (v);
        while (kk) *o++ = tmp[--kk];
        *o++ = '\n';
    }
    OUTSZ = (u64)(o - OUT);
    return;
}

评测结果