P1315 [NOIP 2011 提高组] 观光公交 completed!

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,k,d[N];
struct people{
	int time,t;
}p[N];
int down[N],arrive[N],late[N];
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<n;i++) cin>>d[i];
	int t;
	for(int i=1;i<=m;i++){
		cin>>p[i].time>>t>>p[i].t;
		down[p[i].t]++;
		late[t]=max(late[t],p[i].time);
	}
	int time=0;
	for(int i=1;i<=n;i++){
		arrive[i]=time;
		time=max(time,late[i]);
		time+=d[i];	
	}
	int max_time,aim,js;
	while(k--){
		max_time=0;
		for(int i=2;i<=n;i++){
			if(!d[i-1]) continue;
			js=0;
			for(int j=i;j<=n;j++){
				js+=down[j];
				if(arrive[j]<=late[j]) break;
			}
			if(js>max_time){
				max_time=js;
				aim=i;
			}
		}
		d[aim-1]--;
		for(int i=aim;i<=n;i++){
			arrive[i]--;
			if(arrive[i]<late[i]) break;		//此处是已经加速后的，如果加速后相等的话那离开时间也是比一开始早了一秒 
//			if(arrive[i]<=late[i]){
//				arrive[i]--;
//				break;
//			}
//			arrive[i]--;
		}
	}
	int ans=0;
	for(int i=1;i<=m;i++){
		ans+=arrive[p[i].t]-p[i].time;
	}
	cout<<ans<<endl;
	
	return 0;
}