結果
問題 | No.50 おもちゃ箱 |
ユーザー |
|
提出日時 | 2022-10-23 22:30:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 260 ms / 5,000 ms |
コード長 | 1,911 bytes |
コンパイル時間 | 175 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 84,736 KB |
最終ジャッジ日時 | 2024-07-02 11:30:43 |
合計ジャッジ時間 | 5,138 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
ソースコード
# dp[S][T] = 今までに詰めたおもちゃの集合がS、おもちゃ箱の集合がTのとき、 # Tの最後の箱のスペースの大きさ import sys readline = sys.stdin.readline N = int(readline()) A = list(map(int,readline().split())) M = int(readline()) B = list(map(int,readline().split())) dp = [[-1] * (1 << M) for i in range(1 << N)] dp[0][0] = 0 for S in range(1 << N): for T in range(1 << M): if dp[S][T] == -1: continue for toy in range(N): # 次に詰めるおもちゃ if (S >> toy) & 1: continue next_S = S | (1 << toy) if dp[S][T] >= A[toy]: # 今のスペースに詰められる if dp[next_S][T] < dp[S][T] - A[toy]: dp[next_S][T] = dp[S][T] - A[toy] else: # 詰められないので新しいおもちゃ箱を選ぶ # print(bin(S)[2:].zfill(N), bin(T)[2:].zfill(M), "新しいおもちゃ箱選ぶ") for box in range(M): if (T >> box) & 1: # print(box,"は使用済み") continue if B[box] < A[toy]: # 詰められない # print(B[box],"に",A[toy],"は詰められない") continue next_T = T | (1 << box) if dp[next_S][next_T] < B[box] - A[toy]: dp[next_S][next_T] = B[box] - A[toy] # print("next_S",bin(next_S)[2:].zfill(N),"next_T",bin(next_T)[2:].zfill(M),"空きは",B[box] - A[toy]) #for d in dp: # print(d) def popcnt(x): res = 0 while x: if x & 1: res += 1 x >>= 1 return res ans = M + 1 # dp[-1][おもちゃ箱]の状態で、-1で無い物を探す。 # おもちゃ箱に立っているbitが最も少ないものが答え for T in range(1 << M): if dp[-1][T] != -1: # print(bin(T)[2:].zfill(M),"のとき空きは",dp[-1][T]) bits = popcnt(T) if ans > bits: ans = bits if ans == M + 1: print(-1) else: print(ans)