如果没有氮气加速器，则该题为一个模拟题。
但是本题存在氮气加速器，所以我们需要考虑贪心策略。
题目要求我们使所有人等待的时间最短，因此我们需要算出每段路径(路径即为车站之间的\(D\))对时间的贡献多少，取其中最多的减去就好了。首先我们需要求出每个车站最远向右影响到什么地方，然后算出这段地方的影响总人数。然后就能解出所有车站的的贡献了，每个车站的贡献在减去之后可能会变。所以要进行\(K\)次此操作，每次都找出最大的车站贡献，然后更新答案。
#include <bits/stdc++.h>
#include <queue>
#define int long long
using namespace std;
int n, m, k, ans;
int d[100050], resh[100050], _rea[100005];//resh表示i车站的出发时间, _rea表示i车站的到达时间, ha表示i向右最远能够影响到的车站。
int del[100050], sum[100005], ha[100050], temp[100005];
struct edg {
int t1, a, b;
} data[100050];
signed main()
{
scanf("%lld%lld%lld", &n, &m, &k);
for (register int i = 1; i < n; i++)
scanf("%lld", &d[i]);
for (register int i = 1; i <= m; i++)
scanf("%lld%lld%lld", &data[i].t1, &data[i].a, &data[i].b);
for (register int i = 1; i <= m; i++)
sum[data[i].b]++, resh[data[i].a] = max(resh[data[i].a], data[i].t1);//sum[i]表示0到i车站下车总人数，因为缩短路程只会影响下车的人的时间，
resh[n] = 0x3f3f3f3f;
for (register int i = 1; i < n; i++)
_rea[i + 1] = max(resh[i], _rea[i]) + d[i];
for (register int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + sum[i];
for (register int i = 1; i <= m; i++)
ans += _rea[data[i].b] - data[i].t1;//先加上ans
while (k--)//开始减去k的操作
{
int maxn = 0, maxk;
ha[n - 1] = n;
for (register int i = n - 2; i; i--)
{
if (_rea[i + 1] > resh[i + 1])//这里要加=，因为等于也算为不影响。
ha[i] = ha[i + 1];
else
ha[i] = i + 1;
}
for (register int i = 1; i < n; i++)
{
if (sum[ha[i]] - sum[i] > maxn && d[i])
{
maxn = sum[ha[i]] - sum[i];
maxk = i;
}
}
if (!maxn) break;
ans -= maxn;
d[maxk]--;//maxn是当前最多的车站所影响的人数。
_rea[1] = 0;
for (register int i = 1; i < n; i++)
_rea[i + 1] = max(resh[i], _rea[i]) + d[i];
}
printf("%lld", ans);
return 0;
}