레이팅 미적용농부 존은 농장에 쓸 물품을 사러 시장에 나왔다. 그의 주머니에는 K개의 동전이 있으며 (1 <= K <= 16), 각 동전의 가치는 1..100,000,000 범위이다. FJ는 N번의 구매를 순서대로 하려고 한다 (1 <= N <= 100,000). i번째 구매의 가격은 c(i)이다 (1 <= c(i) <= 10,000). 이 구매들을 순서대로 진행하면서, 그는 때때로 멈추어 마지막 지불 이후의 모든 구매 금액을 동전 하나로 지불할 수 있다 (사용하는 동전 하나는 그동안의 구매 금액 전부를 감당할 수 있을 만큼 커야 한다). 안타깝게도 상인들에게는 거스름돈이 전혀 없어서, FJ가 지불해야 할 금액보다 큰 동전을 사용하면 거스름돈을 전혀 돌려받지 못한다!
FJ가 N번의 구매를 순서대로 모두 마친 후 남길 수 있는 돈의 최댓값을 구하시오. FJ가 모든 구매를 마치는 것이 불가능하다면 -1을 출력한다.
첫째 줄에 두 정수 K와 N이 주어진다.
둘째 줄부터 1+K번째 줄까지, 각 줄에 FJ의 동전 하나의 금액이 주어진다.
2+K번째 줄부터 1+N+K번째 줄까지, 이 N개의 줄에 FJ가 구매하려는 물품들의 가격이 주어진다.
FJ가 남길 수 있는 돈의 최댓값을 출력한다. FJ가 모든 구매를 마칠 수 없다면 -1을 출력한다.
nochange.in · 출력을 쓸 파일 nochange.out3 6
12
15
10
6
3
3
2
3
712Output details: FJ spends his 10-unit coin on the first two purchases, then the 15-unit coin on the rest, leaving the 12-unit coin.
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > November > Gold