시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 39 | 15 | 11 | 37.931% |
Nora the kitesurfer is taking part in a race across the Frisian islands, a very long and thin archipelago in the north of the Netherlands. The race takes place on the water and follows a straight line from start to finish. Any islands on the route must be jumped over – it is not allowed to surf around them.
The length of the race is s metres and the archipelago consists of a number of non-intersecting intervals between start and finish line. During the race, Nora can move in two different ways:
While it is not possible to land on or surf across the islands, it is still allowed to visit the end points of any island.
Figure K.1: Illustration of the two sample cases.
Your task is to find the shortest possible time Nora can complete the race in. You may assume that no island is more than d metres long. In other words it is always possible to finish the race.
The input consists of:
The islands do not touch and are given from left to right, that is ri < ℓi+1 for each valid i.
Output one number, the shortest possible time in seconds needed to complete the race. It can be shown that this number is always an integer.
9 3 4 2 2 4 7 8
11
12 5 3 3 1 3 5 7 8 11
9
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2019 K번