代码

#include <sys/auxv.h>
#include <stdint.h>
#include <string.h>
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 long long ull;
static ll varr[200005], cnta[200005], suba[200005], dla[200005];
static ull key[200005], keytmp[200005];
static int cnt16[65536];
static int fa[100005], daycnt[100005];
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 void radix64(ull* a,int n){ ull* src=a; ull* dst=keytmp; for(int shift=0;shift<64;shift+=16){ memset(cnt16,0,sizeof(cnt16)); for(int i=0;i<n;i++) cnt16[(src[i]>>shift)&0xFFFF]++; int sum=0; for(int i=0;i<65536;i++){int c=cnt16[i];cnt16[i]=sum;sum+=c;} for(int i=0;i<n;i++){ull x=src[i]; dst[cnt16[(x>>shift)&0xFFFF]++]=x;} ull* t=src;src=dst;dst=t; } if(src!=a) memcpy(a,src,(size_t)n*8); }
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"); }
int main(){
  struct DuckInfo *di=(struct DuckInfo*)getauxval(AT_DUCK);
  const char* p=di->stdin_ptr;
  int n=(int)rd(p), M=(int)rd(p), 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); varr[ng]=a+s;cnta[ng]=1;suba[ng]=0;dla[ng]=d1;ng++; if(c-1>0){ll d2=(x==0)?1000000000000LL:((c-2)/x+1);varr[ng]=a;cnta[ng]=c-1;suba[ng]=x;dla[ng]=d2;ng++;} }
  int P=0; for(int i=0;i<k;i++){ ll q=rd(p); if(q>P)P=(int)q; }
  for(int i=0;i<ng;i++) key[i]=((ull)varr[i]<<20)|(ull)i;
  radix64(key,ng);
  for(int i=0;i<=P;i++){fa[i]=i;daycnt[i]=0;}
  ll total=0,sold=0;
  for(int gi=ng-1;gi>=0;gi--){ int ii=(int)(key[gi]&0xFFFFF); ll w=varr[ii],cnt=cnta[ii],sub=suba[ii],dl=dla[ii]; 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; daycnt[idx]+=(int)mn; sold+=mn; total+=mn*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;} } }
  di->stdout_ptr[0]='0'; di->stdout_ptr[1]='\n'; di->stdout_size=2;
  exitasm();
}

评测结果