Informatica Online Judge

  롤러 코스터 철길 2 [1764 / 06E4]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 0   Total Tried : 3


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[IOI 2016 - Kazan, Russia]

Background

안나는 놀이 공원에서 일하고 있는데, 새로운 롤러 코스터가 다닐 수 있는 철로를 설계하는 일을 맡고 있다. 롤러 코스터 열차의 속도에 영향을 미치는 n곳의 특별 구역을 이미 설계해 놓았는데, 각 구역은 0부터 n − 1로 번호가 매겨져 있다. 이제 이 구역들을 모아서 롤러 코스터의 최종 설계를 제안하려고 한다.

문제를 푸는 과정에서, 열차의 길이는 0이라고 가정하자.

0부터 n − 1까지 각 i에 대해서, 특별 구역 i는 다음 두 성질을 띠고 있다.
* 이 특별 구역에 진입할 때, 속도 제한이 있다. 열차의 진입 속도는 시속 si km/h 보다 작거나 같아야 한다.
* 이 특별 구역을 빠져나갈 때, 열차의 속도는 정확히 ti km/h이다. 이 값은 열차가 구역에 진입했을 때 속도와는 상관이 없다.

롤러 코스터의 최종 설계는 n개의 특별 구역을 어떤 순서로 방문하는 단일한 철로 노선이고, 각 n개의 특별 구역을 정확히 한번 지나야 한다. 연속하는 두 특별 구역은 철로로 이어진다. 안나는 n개의 구역을 방문하는 순서를 정하고, 각각의 철로의 길이를 결정해야 한다. 철로의 길이의 단위는 미터이고, 길이는 음이 아닌 정수이다. (0일 수 있다.)

열차가 두 특별 구역을 잇는 철로를 지날 때, 1m를 지날 때마다 속도가 1km/h 감소한다. 열차가 처음 출발할 때, 열차는 안나가 지정한 순서에서 처음에 오는 특별 구역을 1 km/h의 속도로 진입한다.

최종 설계는 다음 요구 사항을 반영해야 한다.
* 열차가 각 특별 구역을 진입할 때, 이 구역의 진입 속도 제한을 어기지 않는다.
* 열차의 속도는 항상 양수이다.

당신은 연속한 특별 구역을 잇는 철로들의 길이의 총합의 최소값을 구해야 한다.

Input

line 1: 정수 n. ($2 <= n <= 200000$)
line 2 + i, i는 0 부터 n − 1까지: 두 정수 $s_i$와 $t_i$. ($1 <= s_i, t_i <= 10^9$)

이 때,

s: 길이 n인 배열이며, 열차 진입 속도의 최대값이다.
t: 길이 n인 배열이며, 구역을 빠져나가는 속도이다.

[Sub-Task Info]
1. (11 points): 2 ≤ n ≤ 8
2. (23 points): 2 ≤ n ≤ 16
3. (66 points): 2 ≤ n ≤ 200 000

대회 당시 30점 상당의 특수한 서브태스크가 존재했으며 이는 롤러 코스터 철길 1 문제로 분리되었다.

Output

연속한 특별 구역을 잇는 철로들의 길이의 총합의 최소값을 구하여라.

IO Example

입력
4
1 7
4 3
5 8
6 6

출력
3

설명
이 예제에서는 4곳의 특별 구역이 있다. 최적해는 0, 3, 1, 2의 순서로 특별 구역을 나열하고, 각각을 잇는
철로의 길이는 차례로 1, 2, 0이다. 이렇게 했을 때 열차가 철로를 지나는 과정은 다음과 같다:
* 처음 열차의 속도는 1 km/h이다.
* 열차의 운행은 특별 구역 0에 진입하는 것으로 시작한다.
* 열차는 특별구역 0을 7 km/h의 속도로 빠져나간다.
* 열차는 길이 1 m의 철로를 지난다. 철로의 끝에서 열차의 속도는 시속 6 km/h이다.
* 열차는 특별 구역 3을 6 km/h의 속도로 진입하고 같은 속도로 빠져나간다.
* 특별 구역 3을 빠져나간 다음, 열차는 2m 길이의 철로를 지난다. 열차의 속도는 시속 4km/h로 감소한다.
* 열차는 특별 구역 1을 시속 4 km/h로 진입하고, 시속 3 km/h로 빠져나간다.
* 특별 구역 1을 빠져나가자마자 열차는 특별 구역 2에 진입한다.
* 열차는 특별 구역 2를 빠져나간다. 열차의 최종 속도는 8 km/h이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]