레이팅 미적용설명
농부 존에게는 착유가 필요한 소 N마리가 있으며 (1 <= N <= 10,000), 각 소의 착유에는 정확히 한 단위 시간이 걸린다.
성질이 급한 동물이라, 농부 존이 너무 오래 기다리게 하면 착유를 거부하는 소도 있다. 더 구체적으로, 소 i는 g_i갤런의 우유를 생산하지만 (1 <= g_i <= 1000), 시각 d_i의 마감 시간 전에 착유될 때에만 그렇다 (1 <= d_i <= 10,000). 시간은 t=0에서 시작하므로, 시각 t=x의 마감 시간 전에는 최대 x마리의 소를 착유할 수 있다.
농부 존이 소들을 최적으로 착유할 때 얻을 수 있는 우유의 최대량을 구하는 것을 도와주시오.
제약
입력 형식
첫째 줄에 N의 값이 주어진다.
둘째 줄부터 1+N번째 줄까지, i+1번째 줄에 정수 g_i와 d_i가 주어진다.
출력 형식
농부 존이 얻을 수 있는 우유의 최대 갤런 수를 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
msched.in · 출력을 쓸 파일 msched.out예제 1
입력
4
10 3
7 5
8 1
2 1출력
25설명
Output details: FJ milks cow 3 first (giving up cow 4), then cows 1 and 2.
문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > December > Silver
태그