結果

問題 No.1015 おつりは要らないです
ユーザー norioc
提出日時 2025-02-18 05:14:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 301 ms / 2,000 ms
コード長 768 bytes
コンパイル時間 437 ms
コンパイル使用メモリ 82,152 KB
実行使用メモリ 91,772 KB
最終ジャッジ日時 2025-02-18 05:14:21
合計ジャッジ時間 9,208 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappush, heappop, heapify


def f(m, unit, cnt):
    if m >= unit and cnt > 0:
        d = min(cnt, m // unit)
        return m - (unit * d), cnt - d

    # 支払えない
    return m, cnt


N, X, Y, Z = map(int, input().split())
A = list(map(int, input().split()))

x, y, z = X, Y, Z
q = [-a for a in A]
heapify(q)

freq = { 1_000: X, 5_000: Y, 10_000: Z }
while q:
    m = -heappop(q)
    assert m > 0

    for u in [10_000, 5_000, 1_000]:
        if m >= u and freq[u] > 0:
            m2, cnt = f(m, u, freq[u])
            freq[u] = cnt
            if m2 > 0:
                heappush(q, -m2)
                break

        if freq[u] > 0:
            freq[u] -= 1
            break
    else:
        print('No')
        exit()

print('Yes')
0