結果
問題 |
No.2686 商品券の使い道
|
ユーザー |
![]() |
提出日時 | 2023-12-11 11:10:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,357 ms / 3,000 ms |
コード長 | 1,269 bytes |
コンパイル時間 | 261 ms |
コンパイル使用メモリ | 82,664 KB |
実行使用メモリ | 92,888 KB |
最終ジャッジ日時 | 2024-09-30 05:07:15 |
合計ジャッジ時間 | 61,332 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
""" """ N,M,Q = map(int,input().split()) A = [] B = [] for i in range(N): a,b = map(int,input().split()) A.append(a) B.append(b) # dpM[s] = 集合sの部分集合において、M円で購入できる最高の価値 # を高速ゼータ変換で計算する dpM = [0] * (2**N) for bit in range(2**N): asum = 0 bsum = 0 for i in range(N): if 2**i & bit: asum += A[i] bsum += B[i] if asum <= M: dpM[bit] = bsum #高速ゼータ変換 for bit in range(2**N): for i in range(N): if 2**i | bit != bit: dpM[2**i | bit] = max(dpM[2**i | bit] , dpM[bit]) # 同様にdpQも計算する # dpQ[s] = 集合sの部分集合において、Q円で購入できる最高の価値 dpQ = [0] * (2**N) for bit in range(2**N): asum = 0 bsum = 0 for i in range(N): if 2**i & bit: asum += A[i] bsum += B[i] if asum <= Q: dpQ[bit] = bsum #高速ゼータ変換 for bit in range(2**N): for i in range(N): if 2**i | bit != bit: dpQ[2**i | bit] = max(dpQ[2**i | bit] , dpQ[bit]) # 答を計算 ans = 0 for bit in range(2**N): rembit = (2**N-1) ^ bit ans = max(ans , dpM[bit] + dpQ[rembit]) print (ans)