結果
問題 | No.50 おもちゃ箱 |
ユーザー |
![]() |
提出日時 | 2020-03-07 03:59:25 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 141 ms / 5,000 ms |
コード長 | 794 bytes |
コンパイル時間 | 128 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 10,880 KB |
最終ジャッジ日時 | 2024-10-14 11:09:07 |
合計ジャッジ時間 | 4,114 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
ソースコード
#!/usr/bin/env python3 # %% import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines # %% N = int(readline()) *A, = map(int, readline().split()) M = int(readline()) *B, = map(int, readline().split()) # %% B.sort(reverse=True) # %% sum_size = [0] for x in A: sum_size += [x + y for y in sum_size] # %% dp = [0] * (1 << N) dp[0] = 1 answer = -1 for n, box_size in enumerate(B): newdp = [0] * (1 << N) for i in range(1 << N): j = i while True: if sum_size[j] <= box_size and dp[i ^ j]: newdp[i] = 1 break if not j: break j = (j - 1) & i dp = newdp if dp[-1]: answer = n + 1 break print(answer)