비행기 탑승

FJ의 소들은 휴가를 가기로 했고, 기꺼이 표를 팔아 줄 항공사도 찾아냈다. 비행기에 탑승하기 시작하면서 소들은 흥미로운 문제에 부딪힌다.

비행기에는 N개의 좌석이 있으며, 이를 수직선 위의 점 x=1부터 x=N으로 모델링한다. N마리의 소(1 <= N <= 200,000)가 모두 줄을 서서 자리로 가기를 기다리고 있다. 소 N은 위치 x=0에, 소 N-1은 위치 x=-1에 서 있으며, 이런 식으로 이어진다. 소 i는 좌석 S_i를 배정받았는데, S_1,...,S_N은 1,...,N의 순열이다.

매 시간 단계마다 각 소는 가능하면 오른쪽으로 한 칸 이동한다. 소 i가 자신의 좌석 S_i에 도착하면 멈춰 서서 짐을 머리 위 선반에 넣는데, 여기에 T_i초가 걸리고, 그 후 자리에 앉는다. 그 T_i 단계 동안 바로 뒤의 소(있다면)는 앞으로 나아가지 못하고 막힌다. 그 뒤에 소들이 줄지어 있다면 그 줄 전체도 사실상 막히게 된다.

모든 소가 자리에 앉기까지 얼마나 걸리는가? 모든 소의 T_i의 합은 1,000,000,000보다 작다.

첫째 줄: 정수 N 하나가 주어진다.

둘째 줄부터 N+1째 줄까지: 공백으로 구분된 두 정수 S_i와 T_i가 주어진다.

모든 소를 앉히는 데 걸리는 시간을 한 줄에 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2013-2014 > February > Gold