레이팅 미적용농부 존(Farmer John)은 소들이 격렬한 운동을 하면 더 질 좋은 우유를 생산한다는 것을 발견했다. 그래서 존은 N마리 (1 <= N <= 25,000)의 소들을 근처 산에 올라갔다가 다시 내려오게 하기로 했다!
소 i는 산을 오르는 데 U(i)의 시간이 걸리고, 내려오는 데 D(i)의 시간이 걸린다. 길들여진 소들인지라 각 소는 오르막과 내리막 각각에서 농부의 도움이 필요한데, 불경기 탓에 농부는 농부 존과 그의 사촌 농부 돈(Farmer Don) 둘뿐이다. FJ는 오르막에서 소들을 인도하고, FD는 내리막에서 소들을 인도할 계획이다. 모든 소에게 인도자가 필요하고 여정의 각 구간마다 농부가 한 명뿐이므로, 어느 시점에든 오르막을 오르는 소는 최대 한 마리(FJ의 도움을 받아)이고, 내리막을 내려가는 소도 최대 한 마리(FD의 도움을 받아)이다. 산을 오른 뒤 FD의 도움을 기다려야 하는 소들이 산꼭대기에 일시적으로 모여 있을 수 있다. 소들이 내려가는 순서는 올라간 순서와 다를 수 있다.
N마리의 소 전부가 전체 여정을 마치는 데 걸리는 최소 시간을 구하시오.
첫째 줄: 소의 수 N.
둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 공백으로 구분된 두 정수 U(i)와 D(i)가 주어진다. (1 <= U(i), D(i) <= 50,000).
모든 소가 산을 넘는 데 걸리는 최소 시간을 나타내는 정수 하나.
climb.in · 출력을 쓸 파일 climb.out3
6 4
8 1
2 317Output details: If cow 3 goes first, then cow 1, and then cow 2 (and this same order is used for both the ascent and descent), this gives a total time of 17.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > January > Silver