結果
問題 | No.50 おもちゃ箱 |
ユーザー |
![]() |
提出日時 | 2021-10-01 00:47:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 85 ms / 5,000 ms |
コード長 | 655 bytes |
コンパイル時間 | 216 ms |
コンパイル使用メモリ | 82,408 KB |
実行使用メモリ | 68,288 KB |
最終ジャッジ日時 | 2024-07-18 05:35:48 |
合計ジャッジ時間 | 3,506 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
ソースコード
n = int(input()) A = list(map(int, input().split())) m = int(input()) B = list(map(int, input().split())) B.reverse() C = [[] for j in range(m)] for mask in range(1<<n): x = 0 for i in range(n): if (mask>>i)&1: x += A[i] for j in range(m): if x <= B[j]: C[j].append(mask) INF =10**18 dp = [INF]*(1<<n) dp[0] = 0 for j in range(m): nx = [INF]*(1<<n) for mask1 in range(1<<n): nx[mask1] = dp[mask1] for mask1 in range(1<<n): for mask2 in C[j]: nx[mask1|mask2] = min(nx[mask1|mask2], dp[mask1]+1) dp = nx if dp[-1] != INF: print(dp[-1]) else: print(-1)