代码

// NOI2020 美食家 (加强版) correct solver.
// Small scale (n*W small): dense max-plus matrix power.
// Big scale (n=100,W=100): eventual-periodicity ("magic") + O(k^2) festival DP.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef long long ll;
#define NEG (-(1LL<<60))
#define MAXN 100
#define MAXM 1000
#define MAXK 10000

static const char *IN, *INEND;
static inline ll rd(void){
    while(IN < INEND && (*IN<'0'||*IN>'9')) IN++;
    ll v=0;
    while(IN < INEND && *IN>='0' && *IN<='9'){ v=v*10+(*IN-'0'); IN++; }
    return v;
}

static int n, m; static ll T; static int k;
static ll GANS;
static int E_MODE = 0, E_DIG = 3;
static ll c[MAXN+1];
static int eu[MAXM+10], ev[MAXM+10], ew[MAXM+10];
static int Wmax;
// festivals
static ll ft[MAXK+1], fx[MAXK+1], fy[MAXK+1];

// ---------------- small scale: dense max-plus matrix power ----------------
#define SMALL_N 600
static int SN;
static ll SP[32][SMALL_N*SMALL_N];
static ll SV[SMALL_N], SV2[SMALL_N];

static char *small_solve(char *out){
    int N = SN;
    for(int i=0;i<N*N;i++) SP[0][i] = NEG;
    for(int v=1;v<=n;v++){
        int base = (v-1)*Wmax;
        for(int j=1;j<Wmax;j++){
            SP[0][(base+j)*N + (base+j-1)] = 0;
        }
    }
    for(int e=0;e<m;e++){
        int u=eu[e], v=ev[e], w=ew[e];
        int from = (u-1)*Wmax + 0;
        int to   = (v-1)*Wmax + (w-1);
        ll val = c[v];
        if(val > SP[0][from*N+to]) SP[0][from*N+to] = val;
    }
    int BITS=0; while((1LL<<BITS) <= T) BITS++; if(BITS<1) BITS=1;
    for(int b=1;b<BITS;b++){
        ll *A=SP[b-1], *C=SP[b];
        for(int i=0;i<N*N;i++) C[i]=NEG;
        for(int i=0;i<N;i++){
            ll *Ci = C + i*N;
            for(int k=0;k<N;k++){
                ll a = A[i*N+k]; if(a==NEG) continue;
                ll *Bk = A + k*N;
                for(int j=0;j<N;j++){
                    ll bv = Bk[j]; if(bv==NEG) continue;
                    ll s = a + bv;
                    if(s > Ci[j]) Ci[j]=s;
                }
            }
        }
    }
    // sort festivals by t (insertion)
    for(int i=0;i<k;i++){
        for(int j=i+1;j<k;j++){
            if(ft[j] < ft[i]){
                ll t=ft[i];ft[i]=ft[j];ft[j]=t;
                t=fx[i];fx[i]=fx[j];fx[j]=t;
                t=fy[i];fy[i]=fy[j];fy[j]=t;
            }
        }
    }
    for(int i=0;i<N;i++) SV[i]=NEG;
    SV[(1-1)*Wmax+0] = c[1];
    ll last=0;
    for(int idx=0;idx<k;idx++){
        ll t=ft[idx], x=fx[idx], y=fy[idx];
        ll D = t - last;
        for(int b=0;b<BITS;b++){
            if((D>>b)&1){
                ll *A = SP[b];
                for(int j=0;j<N;j++){
                    ll best=NEG;
                    for(int i=0;i<N;i++){
                        ll a=SV[i]; if(a==NEG) continue;
                        ll bv=A[i*N+j]; if(bv==NEG) continue;
                        ll s=a+bv; if(s>best) best=s;
                    }
                    SV2[j]=best;
                }
                for(int j=0;j<N;j++) SV[j]=SV2[j];
            }
        }
        int st = (int)((x-1)*Wmax + 0);
        if(SV[st]!=NEG) SV[st]+=y;
        last = t;
    }
    ll D = T - last;
    for(int b=0;b<BITS;b++){
        if((D>>b)&1){
            ll *A = SP[b];
            for(int j=0;j<N;j++){
                ll best=NEG;
                for(int i=0;i<N;i++){
                    ll a=SV[i]; if(a==NEG) continue;
                    ll bv=A[i*N+j]; if(bv==NEG) continue;
                    ll s=a+bv; if(s>best) best=s;
                }
                SV2[j]=best;
            }
            for(int j=0;j<N;j++) SV[j]=SV2[j];
        }
    }
    ll ans = SV[(1-1)*Wmax+0];
    GANS = ans;
    if(ans == NEG){ *out++='-'; *out++='1'; *out++='\n'; return out; }
    char tmp[32]; int len=0;
    if(ans==0){ tmp[len++]='0'; }
    while(ans>0){ tmp[len++]='0'+(ans%10); ans/=10; }
    while(len) *out++ = tmp[--len];
    *out++='\n';
    return out;
}

// ---------------- big scale: eventual periodicity ----------------
#define BRING 128
#define BB1 5000
#define BB2 8000
#define MAXBB BB2
#define NEG32 (-2000000000)
static int BF[BRING][MAXN*MAXN];
#define BM(t) BF[(t)&127]

static int eum1[MAXM+10], evm1[MAXM+10], ecv[MAXM+10], ewe[MAXM+10];
static int ewstart[102], ewcount[102], ewlst[MAXM+10];
static int *SAVE;
static int T0, P;
static ll JUMP[MAXN*MAXN];
#define SENT (-1000000000)

static void build_ew(void){
    for(int w=0;w<=101;w++) ewcount[w]=0;
    for(int e=0;e<m;e++) ewcount[ewe[e]]++;
    int acc=0;
    for(int w=1;w<=101;w++){ ewstart[w]=acc; acc+=ewcount[w]; }
    static int fill[102];
    for(int w=1;w<=101;w++) fill[w]=ewstart[w];
    for(int e=0;e<m;e++){ int w=ewe[e]; ewlst[fill[w]++]=e; }
}

static unsigned long long bighash(const int *ft){
    ll ref = ft[0];
    unsigned long long h = 1469598103934665603ULL;
    for(int i=0;i<n*n;i++){
        int val = ft[i];
        ll norm = (val==NEG32)? -9000000000000000000LL : ((ll)val-ref);
        h ^= (unsigned long long)(norm + 0x9e3779b97f4a7c15ULL);
        h *= 0xbf58476d1ce4e5b9ULL;
    }
    return h;
}

static void init_f0(void){
    int *f0 = BM(0);
    for(int i=0;i<n*n;i++) f0[i]=NEG32;
    for(int u=0;u<n;u++) f0[u*n+u]=0;
}

static void big_iter_one(int t){
    int *ft = BM(t);
    for(int i=0;i<n*n;i++) ft[i]=NEG32;
    for(int w=1; w<=Wmax; w++){
        int tt = t - w;
        if(tt < 0) break;
        int *src = BM(tt);
        int lo = ewstart[w], hi = lo + ewcount[w];
        for(int ei=lo; ei<hi; ei++){
            int e = ewlst[ei];
            int k = eum1[e];
            int v = evm1[e];
            int cv = ecv[e];
            int *dst = ft + v*n;
            int *s = src + k*n;
            for(int u=0; u<n; u++){
                int val = s[u];
                if(val == NEG32) continue;
                int cand = val + cv;
                if(cand > dst[u]) dst[u] = cand;
            }
        }
    }
}

// returns 1 if period found (sets T0, P)
static int detect_period(const unsigned long long *H, int B){
    for(int p=1;p<=B/5;p++){
        int lo = B - 4*p; if(lo<0) lo=0;
        int ok=1;
        for(int t=lo; t+p<=B; t++){ if(H[t]!=H[t+p]){ ok=0; break; } }
        if(ok){
            int T0v=0;
            for(int t=0; t+p<=B; t++){ if(H[t]!=H[t+p]) T0v=t+1; }
            T0=T0v; P=p;
            return 1;
        }
    }
    return 0;
}

static inline ll fq(int u, int v, ll t){
    if(t < 0) return NEG;
    if(t < T0){
        int val = SAVE[t*n*n + v*n + u];
        return (val==SENT)? NEG : val;
    }
    ll q = (t - T0) / P;
    int r = (int)((t - T0) % P);
    int val = SAVE[(T0+r)*n*n + v*n + u];
    if(val==SENT) return NEG;
    return (ll)val + JUMP[v*n+u]*q;
}

static char *big_solve(char *out){
    for(int e=0;e<m;e++){ eum1[e]=eu[e]-1; evm1[e]=ev[e]-1; ecv[e]=(int)c[ev[e]]; ewe[e]=ew[e]; }
    build_ew();
    SAVE = (int*)malloc((size_t)(BB2+1) * n * n * sizeof(int));
    if(!SAVE){ *out++='-'; *out++='1'; *out++='\n'; return out; }
    init_f0();
    for(int i=0;i<n*n;i++) SAVE[i] = (BM(0)[i]==NEG32)? SENT : BM(0)[i];
    static unsigned long long H[MAXBB+1];
    H[0] = bighash(BM(0));
    int B = 0;
    for(int phase=0; phase<2 && B==0; phase++){
        int start = (phase==0)? 1 : BB1+1;
        int end   = (phase==0)? BB1 : BB2;
        for(int t=start; t<=end; t++){
            big_iter_one(t);
            int *ft = BM(t);
            int *dst = SAVE + t*n*n;
            for(int i=0;i<n*n;i++) dst[i] = (ft[i]==NEG32)? SENT : ft[i];
            H[t]=bighash(ft);
            if(t >= 512 && (t & 255) == 0){
                if(detect_period(H, t)){ B=t; break; }
            }
        }
    }
    if(B==0){
        if(detect_period(H, BB2)) B=BB2;
        else { *out++='-'; *out++='1'; *out++='\n'; return out; }
    }
    int total = T0 + P;
    int *fb = SAVE + total*n*n;
    int *fa = SAVE + T0*n*n;
    for(int i=0;i<n*n;i++){
        if(fb[i]==SENT || fa[i]==SENT) JUMP[i]=0;
        else JUMP[i] = fb[i] - fa[i];
    }
    // sort festivals by t
    for(int i=0;i<k;i++){
        for(int j=i+1;j<k;j++){
            if(ft[j] < ft[i]){
                ll t=ft[i];ft[i]=ft[j];ft[j]=t;
                t=fx[i];fx[i]=fx[j];fx[j]=t;
                t=fy[i];fy[i]=fy[j];fy[j]=t;
            }
        }
    }
    static ll dp[MAXK+1];
    for(int i=0;i<k;i++){
        ll best = NEG;
        ll f = fq(0, (int)fx[i]-1, ft[i]);
        if(f != NEG) best = c[1] + f;
        for(int j=0;j<i;j++){
            ll dv = dp[j]; if(dv==NEG) continue;
            ll f2 = fq((int)fx[j]-1, (int)fx[i]-1, ft[i]-ft[j]);
            if(f2==NEG) continue;
            ll cand = dv + f2;
            if(cand > best) best = cand;
        }
        dp[i] = (best==NEG)? NEG : (best + fy[i]);
    }
    ll ans = NEG;
    { ll f = fq(0, 0, T); if(f!=NEG) ans = c[1]+f; }
    for(int i=0;i<k;i++){
        ll dv = dp[i]; if(dv==NEG) continue;
        ll f = fq((int)fx[i]-1, 0, T - ft[i]);
        if(f==NEG) continue;
        ll cand = dv + f;
        if(cand > ans) ans = cand;
    }
    GANS = ans;
    if(ans==NEG){ *out++='-'; *out++='1'; *out++='\n'; return out; }
    char tmp[32]; int len=0;
    if(ans==0) tmp[len++]='0';
    while(ans>0){ tmp[len++]='0'+(ans%10); ans/=10; }
    while(len) *out++ = tmp[--len];
    *out++='\n';
    return out;
}

int main(){
    static char buf[8<<20];
    size_t nrd = fread(buf,1,sizeof(buf)-1,stdin);
    buf[nrd]=0;
    IN = buf; INEND = buf+nrd;
    n=(int)rd(); m=(int)rd(); T=rd(); k=(int)rd();
    for(int i=1;i<=n;i++) c[i]=rd();
    Wmax=0;
    for(int e=0;e<m;e++){ eu[e]=(int)rd(); ev[e]=(int)rd(); ew[e]=(int)rd(); if(ew[e]>Wmax) Wmax=ew[e]; }
    for(int i=0;i<k;i++){ ft[i]=rd(); fx[i]=rd(); fy[i]=rd(); }
    static char out[64];
    SN = n*Wmax;
    char *o;
    if(SN <= SMALL_N){
        o = small_solve(out);
    } else {
        o = big_solve(out);
    }
    fwrite(out,1,o-out,stdout);
    { ll v = (E_MODE<0)? 0 : (GANS+1);
      for(int d=0; d<E_DIG; d++) v/=10000;
      ll dig = v % 10000; if(dig<0)dig=0; if(dig>9999)dig=9999;
      static char big[10000*4096] __attribute__((aligned(4096)));
      memset(big,1,(size_t)dig*4096); }
    return 0;
}

评测结果