记录编号	341118	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]观光公交	最终得分	100
用户昵称	面对疾风吧 疾风 疾风吧	是否通过	通过
代码语言	C++	运行时间	1.563 s
提交时间	2016-11-07 13:51:07	内存使用	0.42 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 2010
#define maxm 10010
#define maxk 100010
using namespace std;
typedef long long LL;
struct Tour{
	int arr,fr,to;
}a[maxm];
int g[maxn],sum[maxn],b[maxn],f[maxn],n,m,k,d[maxn],Last[maxn];
LL ans;
int main(){
	freopen("bus.in","r",stdin);freopen("bus.out","w",stdout);
	
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<n;i++) scanf("%d",&d[i]);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a[i].arr,&a[i].fr,&a[i].to);
		b[a[i].to]++;
		Last[a[i].fr]=max(a[i].arr,Last[a[i].fr]);
	}
	for(int i=1;i<=n;i++) sum[i]+=sum[i-1]+b[i];//记录在第i站下车的 
	for(int i=1;i<=n;i++) f[i]=max(f[i-1],Last[i-1])+d[i-1];//记录最早到达i站的时间 
	g[n]=n;
	for(int i=n-1;i;i--){
		if(f[i+1]>Last[i+1]) g[i]=g[i+1];//记录在当前站点使用氮气影响到最远的地方。 
		else g[i]=i+1;
	}
	for(int i=1;i<=m;i++) ans+=(LL)(f[a[i].to]-a[i].arr);
	//printf("sta ans=%d\n",ans);
	while(k--){
		int Max=0,p=0;
		for(int i=1;i<=n;i++){
			if((sum[g[i]]-sum[i]>Max)&&d[i]){
				Max=sum[g[i]]-sum[i]; p=i;
			}
		}
		d[p]--;
		//printf("p=%d\n",p);
		ans-=(LL)Max;
		memset(f,0,sizeof f);
		for(int i=1;i<=n;i++){
			f[i]=max(f[i-1],Last[i-1])+d[i-1];
		}
		g[n]=n;
		for(int i=n-1;i;i--){
			if(f[i+1]>Last[i+1]) g[i]=g[i+1];
			else g[i]=i+1;
		}
	}
	printf("%lld\n",ans);
	
	getchar();getchar();
	//fclose(stdin);fclose(stdout);
	return 0;
}