레이팅 미적용농부 존은 우유 생산으로 얻는 수입이 농장을 키우기에는 부족하다는 것을 깨닫고, 추가 수입을 벌기 위해 소 대여 서비스를 시작했다. 그는 이 서비스를 "USACOW" ("유즈-어-카우"라고 읽는다)라고 부른다.
농부 존에게는 \(N\)마리의 소 (\(1 \leq N \leq 100,000\))가 있으며, 각 소는 매일 일정량의 우유를 생산할 수 있다. 농장 근처의 \(M\)개의 상점 (\(1 \leq M \leq 100,000\))은 각각 일정량의 우유를 일정 가격에 사겠다고 제안한다. 또한 농부 존의 이웃 농부 \(R\)명 (\(1 \leq R \leq 100,000\))은 각각 일정 가격에 소 한 마리를 빌리고 싶어한다.
농부 존은 각 소마다 우유를 짤지, 이웃 농부에게 빌려줄지 선택해야 한다. 그가 하루에 벌 수 있는 최대 금액을 구하는 것을 도와주자.
Problem credits: Jay Leeds
Problem credits: Jay Leeds
입력의 첫째 줄에 \(N\), \(M\), \(R\)가 주어진다. 다음 \(N\)개의 줄에 각각 정수 \(c_i\) (\(1 \leq c_i \leq 1,000,000\))가 주어지며, 농부 존의 \(i\)번째 소가 매일 \(c_i\)갤런의 우유를 생산할 수 있음을 의미한다. 다음 \(M\)개의 줄에 각각 두 정수 \(q_i\)와 \(p_i\) (\(1 \leq q_i, p_i \leq 1,000,000\))가 주어지며, \(i\)번째 상점이 우유를 갤런당 \(p_i\)센트에 최대 \(q_i\)갤런까지 사겠다는 의미이다. 농부 존은 한 상점에 0갤런 이상 \(q_i\)갤런 이하의 어떤 양이든 팔 수 있다는 점에 유의한다. 다음 \(R\)개의 줄에 각각 정수 \(r_i\) (\(1 \leq r_i \leq 1,000,000\))가 주어지며, 농부 존의 이웃 중 한 명이 하루에 \(r_i\)센트를 내고 소 한 마리를 빌리고 싶어한다는 의미이다.
각 소의 우유를 짜거나 빌려주어 농부 존이 하루에 벌 수 있는 최대 수익을 한 줄에 출력한다. 출력이 표준 32비트 정수에 담기에는 너무 클 수 있으므로, C/C++의 "long long"과 같은 더 큰 정수 타입을 사용해야 할 수도 있다는 점에 유의한다.
rental.in · 출력을 쓸 파일 rental.out5 3 4
6
2
4
7
1
10 25
2 10
15 15
250
80
100
40725Farmer John should milk cows #1 and #4, to produce 13 gallons of milk. He
should completely fill the order for 10 gallons, earning 250 cents, and sell the
remaining three gallons at 15 cents each, for a total of 295 cents of milk
profits.
Then, he should rent out the other three cows for 250, 80, and 100 cents, to
earn 430 more cents. (He should leave the request for a 40-cent rental
unfilled.) This is a total of 725 cents of daily profit.
riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > January > Silver