代码

#include <sys/auxv.h>
#include <stdint.h>
#include <algorithm>
using namespace std;

struct DuckInfo {
  uint64_t abi_version;
  const char *stdin_ptr; uint64_t stdin_size;
  char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size;
  char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size;
  const char *IB_ptr; uint64_t IB_limit;
  char *OB_ptr; uint64_t OB_limit;
  uint64_t tsc_frequency;
} __attribute__((packed));

#define AT_DUCK 0x6b637564UL

typedef long long ll;
typedef unsigned __int128 u128;

struct Group { ll v, c, s, d; };

static Group g[200005];
static int fa[100005];
static int daycnt[100005];
static ll qry[100005];

// breakpoints: batch i starts at sold count bcnt[i] with profit bval[i],
// sells units each worth bw[i].
static ll bcnt[600005];
static u128 bval[600005];
static ll bw[600005];
static int nbp;

static int P, M;

static inline ll rd(const char*& p){
  ll x = 0;
  while (*p < '0' || *p > '9') ++p;
  while (*p >= '0' && *p <= '9') { x = x*10 + (*p - '0'); ++p; }
  return x;
}

static inline int findf(int x){
  while (fa[x] != x) { fa[x] = fa[fa[x]]; x = fa[x]; }
  return x;
}

static inline void exitasm(){
  __asm__ __volatile__("mov $60, %%rax; xor %%rdi, %%rdi; syscall" ::: "rax","rdi","rcx","r11","memory");
}

static inline void pr_u128(char*& o, u128 v){
  char tmp[40]; int nn = 0;
  if (v == 0) { *o++ = '0'; return; }
  while (v) { tmp[nn++] = (char)('0' + (unsigned)(v % 10)); v /= 10; }
  while (nn) *o++ = tmp[--nn];
}

#ifdef DUCK_RENAME_MAIN
extern "C" int duck_solve()
#else
int main()
#endif
{
  struct DuckInfo *di = (struct DuckInfo *)getauxval(AT_DUCK);
  const char *p = di->stdin_ptr;
  int n = (int)rd(p);
  M = (int)rd(p);
  int k = (int)rd(p);

  int ng = 0;
  for (int i = 0; i < n; i++) {
    ll a = rd(p), s = rd(p), c = rd(p), x = rd(p);
    ll d1 = (x == 0) ? 1000000000000LL : ((c - 1) / x + 1);
    g[ng].v = a + s; g[ng].c = 1; g[ng].s = 0; g[ng].d = d1; ng++;
    if (c - 1 > 0) {
      ll d2 = (x == 0) ? 1000000000000LL : ((c - 2) / x + 1);
      g[ng].v = a; g[ng].c = c - 1; g[ng].s = x; g[ng].d = d2; ng++;
    }
  }

  P = 0;
  for (int i = 0; i < k; i++) { qry[i] = rd(p); if (qry[i] > P) P = (int)qry[i]; }

  sort(g, g + ng, [](const Group& A, const Group& B){ return A.v > B.v; });

  for (int i = 0; i <= P; i++) { fa[i] = i; daycnt[i] = 0; }

  u128 total = 0;
  ll sold = 0;
  nbp = 0;

  for (int gi = 0; gi < ng; gi++) {
    ll w = g[gi].v, cnt = g[gi].c, sub = g[gi].s, dl = g[gi].d;
    if (dl > P) dl = P;
    if (dl <= 0) continue;
    int idx = findf((int)dl);
    ll ssum = sub ? (ll)(idx - 1) * sub : 0;
    ll r = cnt - ssum;
    while (idx && r > 0) {
      int cap = M - daycnt[idx];
      ll mn = cap < r ? (ll)cap : r;
      bcnt[nbp] = sold; bval[nbp] = total; bw[nbp] = w; nbp++;
      daycnt[idx] += (int)mn;
      sold += mn;
      total += (u128)mn * (u128)w;
      r -= mn;
      if (daycnt[idx] == M) { fa[idx] = findf(idx - 1); }
      int pidx = idx;
      idx = findf(idx - 1);
      int skipped = pidx - idx;
      if (sub && ssum > 0) {
        r += (ll)skipped * sub;
        ssum -= (ll)skipped * sub;
      }
    }
  }

  char *o = di->stdout_ptr;
  for (int i = 0; i < k; i++) {
    ll need = qry[i] * (ll)M;
    if (need > sold) need = sold;
    if (need <= 0) { *o++ = '0'; *o++ = '\n'; continue; }
    int lo = 0, hi = nbp - 1;
    while (lo < hi) {
      int mid = (lo + hi + 1) >> 1;
      if (bcnt[mid] < need) lo = mid; else hi = mid - 1;
    }
    u128 ans = bval[lo] + (u128)(need - bcnt[lo]) * (u128)bw[lo];
    pr_u128(o, ans);
    *o++ = '\n';
  }
  di->stdout_size = (uint64_t)(o - di->stdout_ptr);
  exitasm();
  return 0;
}

评测结果