레이팅 미적용공항 픽업이 길게 지연되긴 했지만, 풀 먹기에 관심 있는 소들을 위한 농부 존의 컨벤션은 지금까지 순조롭게 진행되고 있다. 전 세계에서 소들이 모여들었다.
하지만 컨퍼런스의 메인 이벤트가 농부 존에게 또 다른 일정 관리의 골칫거리를 안겨줄 것 같다. 그의 농장의 아주 작은 목초지에는 안목 있는 소들 사이에서 세계에서 가장 맛있다고 알려진 희귀한 풀이 자란다. 그 결과, 컨퍼런스에 참석한 \(N\)마리의 소 (\(1 \leq N \leq 10^5\)) 모두가 이 풀을 맛보고 싶어한다. 목초지가 너무 작아서 한 번에 한 마리의 소만 들어갈 수 있으므로, 긴 줄이 생길 가능성이 높다.
농부 존은 각 소 \(i\)가 특별한 목초지에 도착할 예정인 시각 \(a_i\)와, 자기 차례가 되었을 때 특별한 풀을 맛보며 보낼 시간 \(t_i\)를 알고 있다. 소 \(i\)는 풀을 먹기 시작하면 떠나기 전까지 \(t_i\)의 시간을 온전히 사용하며, 그동안 도착한 다른 소들은 기다려야 한다. 목초지가 다시 비었을 때 여러 마리의 소가 기다리고 있다면, 서열이 가장 높은 소가 다음으로 풀을 맛볼 수 있다. 이때, 다른 소가 끝나는 바로 그 순간에 도착한 소도 "기다리고 있는" 것으로 간주한다. 마찬가지로, 아무 소도 먹고 있지 않은 상태에서 여러 마리의 소가 정확히 같은 시각에 도착하면, 서열이 가장 높은 소가 다음으로 먹는다.
어떤 소든 줄에서 기다려야 할 수 있는 시간 (시각 \(a_i\)부터 그 소가 먹기 시작하는 시각까지)의 최댓값을 계산하도록 농부 존을 도와주자.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(N\)이 주어진다. 다음 \(N\)개의 줄에는 \(N\)마리의 소에 대한 정보가 서열 순서대로 (서열이 가장 높은 소가 먼저) 주어진다. 각 줄에는 소 한 마리의 \(a_i\)와 \(t_i\)가 주어진다. \(t_i\)는 각각 \(10^4\) 이하의 양의 정수이고, \(a_i\)는 \(10^9\) 이하의 양의 정수이다.
모든 소에 대해 가능한 가장 긴 대기 시간을 출력한다.
convention2.in · 출력을 쓸 파일 convention2.out5
25 3
105 30
20 50
10 17
100 1010In this example, we have 5 cows (numbered 1..5 according to their order in the
input). Cow 4 is the first to arrive (at time 10), and before she can finish
eating (at time 27) cows 1 and 3 both arrive. Since cow 1 has higher seniority,
she gets to eat next, having waited 2 units of time beyond her arrival time.
She finishes at time 30, and then cow 3 starts eating, having waited for 10
units of time beyond her starting time. After a gap where no cow eats, cow 5
arrives and then while she is eating cow 2 arrives, eating 5 units of time
later. The cow who is delayed the most relative to her arrival time is cow 3.
riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > December > Silver