골드 III민준이는 신약 개발 연구소에서 N번의 실험을 순서대로 진행하려 한다.
i번째 실험을 수행하는 순간, 실험 장비의 온도는 반드시 구간 [Lᵢ, Rᵢ] 안에 있어야 한다. 장비의 초기 온도는 0이며, 온도를 x에서 y로 바꾸는 데는 |x - y| 만큼의 비용(시간)이 든다. 온도는 실수 값을 가질 수 있지만, 모든 Lᵢ, Rᵢ가 정수이므로 항상 정수 온도만 사용해도 최적해를 놓치지 않는다.
실험은 반드시 1번부터 N번까지 순서대로 진행해야 하며, 실험과 실험 사이에는 온도를 자유롭게(원하는 만큼) 바꿀 수 있다. 단, 어떤 순간에도 온도를 바꾸지 않고 그대로 둘 수도 있다. 즉 이전 실험이 끝난 온도가 다음 실험 구간에 이미 포함되어 있다면 비용 없이 그대로 진행 가능하다.
모든 실험을 순서대로 마치기 위한 최소 총 비용을 구하여라.
첫 줄에 실험 개수 N (1 ≤ N ≤ 200,000)
다음 N개 줄에 걸쳐 각 줄마다 Lᵢ, Rᵢ (-1,000,000,000 ≤ Lᵢ ≤ Rᵢ ≤ 1,000,000,000)가 주어진다.
모든 실험을 순서대로 마치기 위한 최소 총 비용을 한 줄에 출력한다. (값이 매우 클 수 있으므로 64비트 정수 범위를 사용할 것)
3
5 10
1 3
7 20110 → 5로 이동 (비용 5), 첫 실험 수행 ([5,10] 안)
5 → 3으로 이동 (비용 2), 두 번째 실험 수행 ([1,3] 안)
3 → 7로 이동 (비용 4), 세 번째 실험 수행 ([7,20] 안)
총 비용 = 5 + 2 + 4 = 11
(3 → 1로 갔다가 다시 7로 가는 등 다른 경로는 모두 11보다 크거나 같음을 확인할 수 있다.)
4
2 8
4 6
10 10
-5 -2223
0 10
8 9
0 115anthony0506 작성
출처 지정되지 않음