Want to try solving this problem? You can submit your code online if you log in or register.

The latest craze in personal transportation is jetstream riding, in which a rider flies through a tunnel of wind located just above the stratosphere in order to get from point A to B. As a casual employee of just over nine thousand small businesses around the globe, Lillian has taken to jetstream riding for its speed and convenience. It's even faster than taking the m9!

Lillian can ride on N different jetstreams, each D kilometres long, arranged
side-by-side, parallel to each other and all flowing in the same direction.
These jetstreams are labelled left-to-right with integers from 1 to N.
Jetstream i allows Lillian to travel a kilometre in v_{i} seconds. She begins
at the start of jetstream S and needs to reach the end of jetstream E.

While it is possible to jump between adjacent jetstreams instantaneously, there are C clouds of toxic ozone gas lingering between adjacent pairs of jetstreams. Due to strict government regulations (and the fact that Lillian wishes to survive her journey without contracting acute bronchitis), these ozone clouds cannot be crossed, even at their endpoints.

Your task is to determine the fastest possible time that Lillian can complete her journey in.

The first line of input will contain five integers: N, C, D, S and E, all separated by spaces.

The following N lines each contain a single integer v_{i}, representing the
number of seconds it takes to travel a kilometre in the ith jetstream.

The following C lines each contain three integers: l_{c}, b_{c} and f_{c},
representing the index of the jetstream immediately left of the cth
ozone cloud, the distance (in kilometres) of the starting point of the cloud from
the beginning of the jetstreams and the distance of the ending point of the cloud
from the beginning of the jetstreams respectively. It is guaranteed that these
ozone clouds will not intersect or touch at endpoints.

Output should consist of one line containing one integer: the fastest possible time it takes Lillian to complete her journey (in seconds). You are guaranteed that it is always possible to reach the end of jetstream E from the start of jetstream S.

3 2 3 1 3 100 10 1 1 0 1 2 1 2

111

3 2 3 3 1 1 10 100 1 0 1 2 1 2

12

4 6 7 1 1 10 5 2 1 2 5 7 1 2 4 3 4 7 2 0 1 1 6 7 2 2 3

25

For sample case 1, Lillian starts in jetstream 1 and has to end in jetstream 3 after covering 3km. She must ride jetstream 1 for 1km since there is a cloud blocking her way to jetstream 2. This takes 100 seconds. Instantly after the first kilometre Lillian can transfer to jetstream 2, this takes no extra time in jetstream 1 so she covers the second kilometre in 10 seconds. Similarly just after the end of kilometre two Lillian transfers into jetstream 3 where she rides out the final kilometre in 1 second. Thus the whole trip takes 111 seconds.

For sample case 2, Lillian can immediately transfer from jetstream 3 to jetstream 2 where she travels the first kilometre in 10 seconds. Once the ozone cloud blocking lane 1 is passed, Lillian transfers into jetstream 1. She stays there for the next 2km, which takes 2 seconds and so 12 seconds overall.

For sample case 3, Lillian immediately transfers from jetstream 1 to 2 and rides that for 1km, taking 5 seconds. Directly after the ozone cloud blocking her finishes Lillian jumps over to jetstream 4 and rides it for 3km, which takes her 3 seconds. Then she transfers to jetstream 3 just before the next ozone cloud would block her and stays there for 1km, taking 2 seconds. Similarly just before each of the next two ozone clouds start Lillian transfers past them. Thus she spends 5 seconds in jetstream 2, and then 10 in jetstream 1. Thus her journey is 25 seconds.

For all subtasks:
1 ≤ N ≤ 100,000,
0 ≤ C ≤ 100,000,
1 ≤ D ≤ 1,000,000,000,
1 ≤ v_{i} ≤ 100,000,
2 ≤ l_{c} < N,
0 ≤ b_{c} < f_{c} ≤ D.

- For Subtask 1 (11 points), Lillian ends her journey at the end of the
first jetstream (E = 1) and the time taken to travel a kilometre on a
jetstream is non-increasing as you go further to the right (v
_{i}≥ v_{i+1}for 1 ≤ i < N). - For Subtask 2 (9 points), All ozone clouds end at the end of Lillian's
journey (f
_{c}= D for all ozone clouds). - For Subtask 3 (14 points),
1 ≤ N ≤ 100,
1 ≤ D ≤ 1,000,
0 ≤ C ≤ 500.
- For Subtask 4 (23 points),
1 ≤ N, D ≤ 1,000,
0 ≤ C ≤ 1,000.
- For Subtask 5 (43 points), no further constraints apply.

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 26 October 2021, 12:36am AEDT