思路是贪心，当车上人最多时加速：

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define maxx(a,b) a>b?a:b
#define minn(a,b) a<b?a:b
const int MAXN=2e5+16;
ll n,m,k;
ll d[MAXN],t[MAXN],a[MAXN],b[MAXN];
//d:所需时间 t:乘客到达时间 a:乘客出发点 b:乘客目的地 
ll last[MAXN],sum[MAXN],f[MAXN],g[MAXN];
//last:每个地点最晚出发时间 sum:从i--i+1车上的乘客 f:每个站点累计所需时间  
ll ans;
int main(){
//	freopen("P1315_3.in","r",stdin);
//	freopen("bus.out","w",stdout);
	cin>>n>>m>>k;
	//cout<<n<<" "<<m<<" "<<k<<endl;
	for(int i=1;i<n;i++)cin>>d[i];
	for(int i=1;i<=m;i++){//存储信息 
		cin>>t[i]>>a[i]>>b[i];
		last[a[i]]=maxx(last[a[i]],t[i]);
		sum[b[i]]++;
	}
	for(int i=1;i<=n;i++)sum[i]+=sum[i-1];
	f[1]=last[1];
	for(int i=2;i<=n;i++)f[i]=maxx(f[i-1],last[i-1])+d[i-1];
	for(int i=1;i<=m;i++)ans+=(f[b[i]]-t[i]);
	int ssy=ans;
	while(k--){
		g[n-1]=n;
		for(int i=n-2;i>=1;i--){
			if(last[i+1]>=f[i+1]) g[i]=i+1;
			else g[i]=g[i+1];
		}
		int maxs=0,k=0;
		for(int i=1;i<=n;i++){
			int t=sum[g[i]]-sum[i];
			if(t>maxs&&d[i]){
				maxs=t;
				k=i;
			}
		}
		ans-=maxs;
		d[k]--;
		for(int i=2;i<=n;i++) f[i]=maxx(f[i-1],last[i-1])+d[i-1];
	}
/*	cout<<1111<<endl;
	cout<<"after use:"<<ans<<endl;
	cout<<"not use:"<<ssy<<endl;
	cout<<"compare:"<<(ssy-ans);*/
	cout<<ans;
	return 0;
//	fclose(stdin);
//	fclose(stdout);
}

只有10tps QAQ