ABC308F - Vouchers

考え方

使ったクーポンの$D_{i}$の総和を最大化する．

クーポン$i$は「(定価)$\geq L_{i}$」を満たす商品に適用できる．同じクーポンならなるべく定価が小さいものに使ったほうが有利．

1. 商品の定価を小さい順に見ていき
2. 定価$p$の商品に対して$S_{p} = \{D_{i}\,|\, p\geq L_{i},i=1,\ldots, M\}$のなかから最大の$D_{i}$となるクーポンを使う

とすれば，「各商品に対して，使えるクーポンのうち割引価格が最大のものが使われる（ただし，定価の低い商品を優先する）」ことになる．

定価を小さい順に見ていくとき，集合列$\{S_{p}\}$は単調増加になる．よって，$S_{p}$は優先度付きキューで管理できる．

回答例

from collections import deque
from heapq import heapify, heappop, heappush

N, M = map(int, input().split())
P = list(map(int, input().split()))
L = list(map(int, input().split()))
D = list(map(int, input().split()))

P.sort()

Li = [(l, i) for i, l in enumerate(L)]
Li.sort()
Li = deque(Li)

ans = 0
q = []
for p in P:
    ans += p
    while Li and p >= Li[0][0]:
        l, i = Li.popleft()
        heappush(q, -D[i])
    if q:
        ans += heappop(q)

print(ans)

【参考】Submission #43125307 - AtCoder Beginner Contest 308