luogu_P1315 观光公交

#include<iostream>
#include<cstdio>

#define ri register int
#define u int

namespace opt {

    inline u in() {
        u x(0),f(1);
        char s(getchar());
        while(s<‘0‘||s>‘9‘) {
            if(s==‘-‘) f=-1;
            s=getchar();
        }
        while(s>=‘0‘&&s<=‘9‘) {
            x=(x<<1)+(x<<3)+s-‘0‘;
            s=getchar();
        }
        return x*f;
    }

}

using opt::in;

#include<algorithm>
#include<cstring>

#define NN 100005

namespace mainstay {

    u N,M,K,re,t[NN],st[NN],mx[NN],num[NN];

    struct node {
        u t,x,y;
    } a[NN];

    inline void solve() {
        N=in(),M=in(),K=in();
        for(ri i(1); i<N; ++i) t[i]=in(); //i到i+1时间（1~N-1）
        for(ri i(1); i<=M; ++i) a[i].t=in(),a[i].x=in(),a[i].y=in();
        //乘客i在t时间到x点要在y点下车
        for(ri i(1); i<=M; ++i) mx[a[i].x]=std::max(mx[a[i].x],a[i].t),++num[a[i].y];
        //每个点最晚到的乘客,num[x]在x站多少人下车
        for(ri i(1),pre(0); i<N; ++i) st[i]=std::max(mx[i],st[i-1]+t[i-1]);
        for(ri i(1); i<=M; ++i) re+=(st[a[i].y-1]+t[a[i].y-1]-a[i].t); //总时间
        //每个点不用k最早出发时间 ，车先到等人=mx[i]，车后到为st[i-1]+t[i-1]
        for(ri n(1); n<=K; ++n) { //k个加速器
            u et[2]= {0,0};
            for(ri i(1); i<N; ++i) { //每一段路 （1~N-1）
                u ans(0);
                if(!t[i]) continue;
                for(ri j(i); j<N; ++j) {
                    ans+=num[j+1];//从i段开始的价值
                    if(st[j+1]==mx[j+1]) break;//归零了。。。
                }
                if(ans>et[1]) et[1]=ans,et[0]=i;
            }
            //用这个在这段造成的修改（影响）
            re-=et[1],--t[et[0]];
            for(ri i(et[0]); i<N; ++i) {
                if(st[i+1]==mx[i+1]) break;
                --st[i+1];
            }
        }
        printf("%d",re);
    }

}

int main() {

    //freopen("x.txt","r",stdin);
    std::ios::sync_with_stdio(false);
    mainstay::solve();

}