시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 65 | 27 | 25 | 40.984% |
Anna is working in an amusement park and she is in charge of building the railroad for a new roller coaster. She has already designed n special sections (conveniently numbered from 0 to n - 1) that affect the speed of a roller coaster train. She now has to put them together and propose a final design of the roller coaster. For the purpose of this problem you may assume that the length of the train is zero.
For each i between 0 and n - 1, inclusive, the special section i has two properties:
The finished roller coaster is a single railroad line that contains the n special sections in some order. Each of the n sections should be used exactly once. Consecutive sections are connected with tracks. Anna should choose the order of the n sections and then decide the lengths of the tracks. The length of a track is measured in meters and may be equal to any non-negative integer (possibly zero).
Each meter of the track between two special sections slows the train down by 1 km/h. At the beginning of the ride, the train enters the first special section in the order selected by Anna, going at 1 km/h.
The final design must satisfy the following requirements:
In all subtasks except subtask 3, your task is to find the minimum possible total length of tracks between sections. In subtask 3 you only need to check whether there exists a valid roller coaster design, such that each track has zero length.
You should implement the following function (method):
int64 plan_roller_coaster(int[] s, int[] t).
s
: array of length n, maximum allowed entry speeds.t
: array of length n, exit speeds.plan_roller_coaster([1, 4, 5, 6], [7, 3, 8, 6])
In this example there are four special sections. The best solution is to build them in the order 0, 3, 1, 2, and to connect them by tracks of lengths 1, 2, 0 respectively. This is how a train travels along this railroad track:
The function should return the total length of tracks between the special sections: 1 + 2 + 0 = 3.
In all subtasks 1 ≤ si ≤ 109 and 1 ≤ ti ≤ 109.
번호 | 배점 | 제한 |
---|---|---|
1 | 11 | 2 ≤ n ≤ 8 |
2 | 23 | 2 ≤ n ≤ 16 |
3 | 30 | 2 ≤ n ≤ 200,000. In this subtask your program only needs to check whether the answer is zero or not. If the answer is not zero, any positive integer answer is considered correct. |
4 | 36 | 2 ≤ n ≤ 200,000 |
The sample grader reads the input in the following format:
Olympiad > International Olympiad in Informatics > IOI 2016 > Day 1 2번
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)