A3453 | $观光公交（Day 2）$

来源NOIP提高组 / 2011

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

风景迷人的小城Y市，拥有n个美丽的景点。由于慕名而来的游客越来越多，Y市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。观光公交车在第0分钟出现在1号景点，随后依次前往2、3、4...n号景点。从第i号景点开到第i+1号景点需要Di分钟。任意时刻，公交车只能往前开，或在景点处等待。 设共有m个游客，每位游客需要乘车1次从一个景点到达另一个景点，第i位游客在Ti分钟来到景点Ai，希望乘车前往景点Bi（Ai <Bi ）。为了使所有乘客都能顺利到达目的地，公交车在每站都必须等待需要从该景点出发的所有

每组输入数据的第1行是3个整数n, m, k，每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。 第2行是n-1个整数，每两个整数之间用一个空格隔开，第i个数表示从第i个景点开往第i+1个景点所需要的时间，即Di。 第3行至m+2行每行3个整数Ti, Ai, Bi，每两个整数之间用一个空格隔开。第i+2行表示第i位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。 数据规模： 对于10%的数据，k=0； 对于20%的数据，k=1； 对于40%

每组输出共一行，包含一个整数，表示最小的总旅行时间。 下面是对样例数据的解释： 对D2使用2个加速器，从2号景点到3号景点时间变为2分钟。 公交车在第1分钟从1号景点出发，第2分钟到达2号景点，第5分钟从2号景点出发，第7分钟到达3号景点。 第1个旅客旅行时间7-0=7分钟。 第2个旅客旅行时间2-1=1分钟。 第3个旅客旅行时间7-5=2分钟。 总时间7+1+2=10分钟。

输入 #1

输出 #1

C++ 编辑器

输入

输出