반응형
https://www.acmicpc.net/problem/1202
1202번: 보석 도둑
첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci
www.acmicpc.net
import sys
import heapq
N, K = map(int, sys.stdin.readline().split())
MV = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
bags = [int(sys.stdin.readline()) for _ in range(K)]
bags.sort()
jewels = []
for mv in MV:
heapq.heappush(jewels, mv)
ans = 0
values = []
for bag in bags:
while jewels and bag >= jewels[0][0]:
heapq.heappush(values, -heapq.heappop(jewels)[1])
if values:
ans -= heapq.heappop(values)
elif not jewels:
break
print(ans)
반응형