记录编号	309966	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]观光公交	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.650 s
提交时间	2016-09-20 21:53:44	内存使用	0.64 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=10010;
int n,m,k,ans,d[N],mint[N],maxt[N],arrive[N];
//mint表示最早离站时间,maxt表示最晚到站时间,arrive[i]表示此时到达i的时刻 
struct person{int t,x,y;}p[N];
int num[N],sum[N];
//num[i]表示到达i+1的人数,sum[i]表示到i+1时间变短影响的人数 
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",&p[i].t,&p[i].x,&p[i].y);
		mint[p[i].x]=max(mint[p[i].x],p[i].t);
		num[p[i].y-1]++;
	}
	for (int i=1;i<n;i++) mint[i+1]=max(mint[i+1],mint[i]);
	for (int i=1;i<n;i++) arrive[i+1]=max(arrive[i],mint[i])+d[i];
	for (int i=1;i<=m;i++) ans+=arrive[p[i].y]-p[i].t;
	for (int i=1;i<=k;i++){
		for (int i=n-1;i;i--) sum[i]=num[i];
		for (int i=n-1;i;i--)
			if (arrive[i+1]>mint[i+1]) sum[i]+=sum[i+1];
		int p=0;
		for (int i=1;i<n;i++)
			if (d[i]&&sum[i]>sum[p]) p=i;
		if (!p) break;
		ans-=sum[p];d[p]--;
		for (int i=p;i<n;i++) arrive[i+1]=max(arrive[i],mint[i])+d[i];
	}
	printf("%d\n",ans);
	return 0;
}