【正经题解】观光公交

对于每一段，如果用加速器，那么受影响的有从这一段到达的站到后面的某个站（设为 $rang$ [ $i$ ]（避免 $range$ 重名尴尬）），那么从 $i$ 到 $rang$ [ $i$ ]，每一段都是人在等车（ $last$ [ $i$ ] $<time$ [ $i$ ]）,到这些站的时间可以都减一，所以在这个区间下车的人用的时间都会减一，每次找最优的地方用 $1$ 个加速器，然后更新 $time$ [ $i$ ]，复杂度,,大概 $O$ ( $kn$ ).

#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
#define ll long long 
#define	re register
#define MAXN 10005
#define mod 10007
#define inf 0x3f3f3f3f
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define inl inline
//#pragma GCC optimize (2)
//#pragma G++ optimize (2)
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//不要在意那么多头文件
using namespace std;
inline ll read() {
    re ll x = 0; re int f = 1;
    char ch = getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f = -1; ch = getchar(); }
    while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x * f;
}
inline void write(ll x){
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}
inline void writeln(ll x){
    write(x); puts("");
}//读优+输出优化
ll last[MAXN],In[MAXN],Out[MAXN];
struct Node{
    ll t,b,e;
}e[MAXN];
ll ssw[MAXN],d[MAXN],sum[MAXN];
ll tim[MAXN],rang[MAXN],n,m,k;
int main(){
    n=read(),m=read(),k=read();
    re ll ans=0;
    for(re ll i=1;i<n;i++) {
        d[i]=read();
    }
    for(re ll i=1;i<=m;i++) {
        e[i].t=read(),e[i].b=read(),e[i].e=read();
        last[e[i].b]=max(e[i].t,last[e[i].b]);
        In[e[i].b]+=1;//可以忽略
        Out[e[i].e]+=1;//划重点，下车的人数
    }
    last[n]=inf;
    for(re ll i=1;i<n;i++){
        tim[i+1]=max(tim[i],last[i])+d[i];
        ssw[i]=ssw[i-1]+In[i]-Out[i];//完全没用，打着玩的，，
    }
    for(re ll i=1;i<=n;i++) sum[i]=sum[i-1]+Out[i];//划重点，前缀和
    for(re ll i=1;i<=m;i++){ans+=tim[e[i].e]-e[i].t;}
    while(k--){//每次用一个，美滋滋
    	ll maxn=0,flag;rang[n-1]=n;
        for(re ll i=n-2;i;i--){
            if(tim[i+1]>last[i+1]) rang[i]=rang[i+1];
            else rang[i]=i+1;
        }//求rang[i](如果在i站等人，那么只影响下一站下的，反之会影响到rang[i+1](反正到rang[i+1]都是人等车)
        for (re ll i=1;i<n;i++){
            if (sum[rang[i]]-sum[i]>maxn&&d[i]){
            	maxn=sum[rang[i]]-sum[i],flag=i;
            }//找最优的一段
        }
        if(!maxn) break;
        ans-=maxn;
        d[flag]-=1;//更新d
        tim[1]=0;
        for(re ll i=1;i<n;i++){tim[i+1]=max(tim[i],last[i])+d[i];}//更新tim[i]
    }
    writeln(ans);//输出
    return 0;
}