记录编号	341313	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]观光公交	最终得分	100
用户昵称	Hzoi_Go灬Fire	是否通过	通过
代码语言	C++	运行时间	1.449 s
提交时间	2016-11-07 16:38:37	内存使用	4.49 MiB

#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<iostream>
using namespace std;
#define LL long long
#define Begin freopen("bus.in","r",stdin);freopen("bus.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
const int maxn=200010;
struct Node{
	int from,t,to;
}a[maxn];
int n,m,K,ans;
int lastest[maxn],Time[maxn],g[maxn],dis[maxn],num[maxn];
void Init();

int main(){
    Begin;
    Init();
    getchar();getchar();
    End;
    return 0;
}
void Init(){
	scanf("%d%d%d",&n,&m,&K);
	for(int i=1;i<n;i++)scanf("%d",&dis[i]);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a[i].t,&a[i].from,&a[i].to);
		lastest[a[i].from]=max(lastest[a[i].from],a[i].t);//最晚到达的人的时间 
		num[a[i].to]++;//在此车站下车的人数 
	}
	for(int i=2;i<=n;i++)num[i]+=num[i-1];
	Time[1]=0;
	for(int i=2;i<=n;i++)Time[i]=max(Time[i-1],lastest[i-1])+dis[i-1];//没有加速器正常到达 
	for(int i=1;i<=m;i++)ans+=Time[a[i].to]-a[i].t;//没有加速器的答案 
	while(K){
		g[n]=n;g[n-1]=n;//最远可以影响到的车站 
		for(int i=n-2;i;i--){
			if(Time[i+1]<=lastest[i+1])g[i]=i+1;//可以影响到的条件是没有等待时间 
			else g[i]=g[i+1];
		}
		int Max=0,j;
		for(int i=1;i<=n;i++){//从影响的最远的地方开始找人数最多的 
			if(num[g[i]]-num[i]>Max && dis[i]>0)Max=num[g[i]]-num[i],j=i;
		}
		if(!Max)break;
		ans-=Max;
		dis[j]--;K--;
		for(int i=2;i<=n;i++)Time[i]=max(Time[i-1],lastest[i-1])+dis[i-1];
	}
	printf("%d\n",ans);
}