记录编号	341324	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]观光公交	最终得分	100
用户昵称	Hzoi_chairman	是否通过	通过
代码语言	C++	运行时间	1.329 s
提交时间	2016-11-07 16:46:33	内存使用	0.39 MiB

#include<cstdlib>
#include<cstdio>
#include<iostream>
int read()
{
	int x,f=1;
	char ch;
	while(ch=getchar(),ch>'9'||ch<'0')if(ch=='-')f-1;
	x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
	return x*f;
}
#define maxn 1010
#define maxm 10010
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
int start[maxn],T[maxm],y[maxm],num[maxn],f[maxn],dis[maxn],g[maxn],mx,j,ans;
int main()//f[i]代表到达i的最早时间，start[i]表示i最晚发车时间，num[i]表示从1到i的人数
{
	freopen("bus.in","r",stdin);
	freopen("bus.out","w",stdout);
	int n=read(),m=read(),k=read();
	for(int i=1;i<n;i++)dis[i]=read();
	for(int i=1;i<=m;i++)
	{
		T[i]=read();int x=read();y[i]=read();
		start[x]=max(start[x],T[i]);
		num[y[i]]++;
	}
	for(int i=1;i<=n;i++)num[i]+=num[i-1];
	while(k--)
	{
		for(int i=1;i<=n;i++)f[i]=max(f[i-1],start[i-1])+dis[i-1];
		for(int i=n;i>0;i--)
		{
			if(f[i+1]>start[i+1])g[i]=g[i+1];
			else g[i]=min(i+1,n);
		}
		mx=0;
		for(int i=1;i<=n;i++)
		    if(dis[i]&&mx<num[g[i]]-num[i])
		    {
				mx=num[g[i]]-num[i];
				j=i;
			}
		dis[j]--;//printf("%d %d %d\n",j,num[j],g[2]);
	}
	for(int i=1;i<=n;i++)f[i]=max(f[i-1],start[i-1])+dis[i-1];//,printf("%d %d %d\n",i,dis[i],f[i]);
	for(int i=1;i<=m;i++)ans+=f[y[i]]-T[i];
	printf("%d",ans);//while(1);
//	system("pause");
	fclose(stdin);
	fclose(stdout);
	return 0;
}