結果
問題 | No.1015 おつりは要らないです |
ユーザー | FromBooska |
提出日時 | 2023-02-24 15:10:54 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 271 ms / 2,000 ms |
コード長 | 2,282 bytes |
コンパイル時間 | 238 ms |
コンパイル使用メモリ | 87,284 KB |
実行使用メモリ | 92,852 KB |
最終ジャッジ日時 | 2023-10-10 00:15:02 |
合計ジャッジ時間 | 9,902 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 72 ms
71,328 KB |
testcase_01 | AC | 65 ms
71,452 KB |
testcase_02 | AC | 68 ms
71,288 KB |
testcase_03 | AC | 66 ms
71,440 KB |
testcase_04 | AC | 67 ms
71,668 KB |
testcase_05 | AC | 65 ms
71,168 KB |
testcase_06 | AC | 67 ms
71,532 KB |
testcase_07 | AC | 67 ms
71,512 KB |
testcase_08 | AC | 66 ms
71,368 KB |
testcase_09 | AC | 67 ms
71,424 KB |
testcase_10 | AC | 264 ms
92,748 KB |
testcase_11 | AC | 271 ms
92,780 KB |
testcase_12 | AC | 253 ms
92,416 KB |
testcase_13 | AC | 263 ms
92,612 KB |
testcase_14 | AC | 267 ms
92,852 KB |
testcase_15 | AC | 259 ms
92,820 KB |
testcase_16 | AC | 261 ms
92,688 KB |
testcase_17 | AC | 267 ms
92,716 KB |
testcase_18 | AC | 268 ms
92,804 KB |
testcase_19 | AC | 263 ms
92,500 KB |
testcase_20 | AC | 253 ms
92,480 KB |
testcase_21 | AC | 250 ms
92,392 KB |
testcase_22 | AC | 247 ms
92,064 KB |
testcase_23 | AC | 246 ms
91,996 KB |
testcase_24 | AC | 252 ms
92,496 KB |
testcase_25 | AC | 248 ms
92,212 KB |
testcase_26 | AC | 252 ms
92,112 KB |
testcase_27 | AC | 250 ms
92,116 KB |
testcase_28 | AC | 243 ms
92,232 KB |
testcase_29 | AC | 247 ms
92,176 KB |
testcase_30 | AC | 64 ms
71,616 KB |
testcase_31 | AC | 125 ms
90,108 KB |
testcase_32 | AC | 128 ms
90,408 KB |
testcase_33 | AC | 129 ms
92,540 KB |
testcase_34 | AC | 66 ms
71,188 KB |
testcase_35 | AC | 67 ms
71,188 KB |
testcase_36 | AC | 63 ms
71,184 KB |
ソースコード
# dpも考えたがどのように構築するのかわからず # dpでなく貪欲法、10000円札の使い方を貪欲で決める、次に5000円札の使い方を貪欲で決める # 10000円札があるとき、1万円以上の商品には1万円札を使ってよい、千・5千を組み合わせて使ってbetterなことはない # 10000円札があるとき、最大価格の店で使ってよい、それ未満の店で使うメリットなし N, X, Y, Z = map(int, input().split()) A = list(map(int, input().split())) A_heap = [-(a+1) for a in A] from heapq import * heapify(A_heap) #print(A_heap) X_remainder = X Y_remainder = Y Z_remainder = Z # 1万円札貪欲 while len(A_heap)>0 and Z_remainder > 0: mx = - heappop(A_heap) Z_use = min(Z_remainder, mx//10000) if Z_use > 0: Z_remainder -= Z_use if mx - Z_use*10000 > 0: heappush(A_heap, -(mx - Z_use*10000)) elif Z_use == 0: Z_use = 1 Z_remainder -= Z_use if mx - Z_use*10000 > 0: heappush(A_heap, -(mx - Z_use*10000)) if Z_remainder == 0: break #print(A_heap, [X_remainder, Y_remainder, Z_remainder]) # 5千円札貪欲 while len(A_heap)>0 and Y_remainder > 0: mx = - heappop(A_heap) Y_use = min(Y_remainder, mx//5000) if Y_use > 0: Y_remainder -= Y_use if mx - Y_use*5000 > 0: heappush(A_heap, -(mx - Y_use*5000)) elif Y_use == 0: Y_use = 1 Y_remainder -= Y_use if mx - Y_use*5000 > 0: heappush(A_heap, -(mx - Y_use*5000)) if Y_remainder == 0: break #print(A_heap, [X_remainder, Y_remainder, Z_remainder]) # 1千円札貪欲 while len(A_heap)>0 and X_remainder > 0: mx = - heappop(A_heap) X_use = min(X_remainder, mx//1000) if X_use > 0: X_remainder -= X_use if mx - X_use*1000 > 0: heappush(A_heap, -(mx - X_use*1000)) elif X_use == 0: X_use = 1 X_remainder -= X_use if mx - X_use*1000 > 0: heappush(A_heap, -(mx - X_use*1000)) if X_remainder == 0: break #print(A_heap, [X_remainder, Y_remainder, Z_remainder]) if len(A_heap) == 0: print('Yes') else: print('No')