题解：
做这题的时候为了敢速度- - 直接orz了神小黑的题解
其实我还是有想一个拙计的方法的- -
dp：f[i][j] 表示到i点使用j个加速器 在i前上车的人的时间和
轻松愉悦转移之 - - 但是有很严重的两个问题
1.空间复杂度O(nk)爆掉
2.时间复杂度O(nk^2)更呵呵- -
于是弃疗
正解：
贪心！
time[i]表示到i点的时间
last[i]表示从i出发的人的最晚到达的时间
sum[i]表示在i或i前下车的人数
f[i]表示在i后time[j]<=last[j]的最小j
贪心每个加速器在哪使用
选出使sum[f[i]]-sum[i]最大的i
证明：
显然每次使用加速器都要在能让最多人加速的地方使用
而如果在i点使用加速器 我能使在i+1到f[i]下车的人都加速
超过f[i]下车的由于要在f[i]车站等人 所以相当于没加速
sum[f[i]]-sum[i] 即为在i+1到f[i]下车的人
优化：
orz神ak想出的优化
我们在选出i的同时 显然可以同时使用好几个加速器 只要使用后i+1到f[i]-1没有 time[j]<last[j]
于是我们可以统计i+1到f[i]-1中last[j]-time[j]的最小值 直接使用这么多
注意 如果这个最小值大于剩余的加速器 或大于i到i+1所需的时间 那么取他们的最小值
原来的时间复杂度为O(nk) 而这样做复杂度为O(n^2)
因为对于任意一对(i,f[i])如果他们被加速过 那么之后就不可能再加速了
代码：
#include <cstdio>
const int N=;
struct info{
int x,y,t;
info(const int a=,const int b=,const int c=):
x(a),y(b),t(c){}
}im[];
int n,m,k,out[N],ti[N],last[N],sum[N],lon[N],ans;
int max(int x,int y){ return x>y ? x : y; }
void work(){
while (k){
int x=,y,z;
for (int i=n,la=n,min=;i>=;i--){
if (sum[la]-sum[i]>x && lon[i+]){
x=sum[la]-sum[i];
y=i;
z=min;
if (lon[i+]<z) z=lon[i+];
}
if (i<n)
if (min>ti[i]-last[i]) min=ti[i]-last[i];
if (ti[i]<=last[i]){
la=i;
min=;
}
}
if (z>k) z=k;
k-=z;
ans-=x*z;
lon[y+]-=z;
for (int i=y+;i<=n && ti[i]>last[i];i++) ti[i]-=z;
}
}
void maketi(){
for (int i=;i<=n;i++){
sum[i]=sum[i-]+out[i];
ti[i]=max(ti[i-],last[i-])+lon[i];
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
int x,y,z;
for (int i=;i<=n;i++) scanf("%d",&lon[i]);
for (int i=;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
im[i]=info(y,z,x);
last[y]=max(last[y],x);
++out[z];
}
maketi();
for (int i=;i<=m;i++) ans+=ti[im[i].y]-im[i].t;
work();
printf("%d",ans);
}