結果
問題 | No.2364 Knapsack Problem |
ユーザー |
👑 ![]() |
提出日時 | 2023-06-30 21:28:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 66 ms / 3,000 ms |
コード長 | 722 bytes |
コンパイル時間 | 139 ms |
コンパイル使用メモリ | 82,100 KB |
実行使用メモリ | 69,404 KB |
最終ジャッジ日時 | 2024-07-07 09:00:31 |
合計ジャッジ時間 | 2,022 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
""""""N,M,W = map(int,input().split())A = list(map(int,input().split()))B = list(map(int,input().split()))C = list(map(int,input().split()))D = list(map(int,input().split()))for i in range(M):A.append(-C[i])B.append(-D[i])dpok = [False] * (2**(N+M))dpok[0] = Truew = [0] * (2**(N+M))v = [0] * (2**(N+M))for i in range(2**(N+M)):for j in range(N+M):if 2**j & i:w[i] += A[j]v[i] += B[j]#print (w,v)ans = 0for i in range(2**(N+M)):if not dpok[i]:continuefor j in range(N+M):if dpok[2**j | i] == False and 0 <= w[2**j | i] <= W:dpok[2**j | i] = Trueans = max(ans , v[2**j | i])print (ans)