結果
問題 | No.2686 商品券の使い道 |
ユーザー |
![]() |
提出日時 | 2024-03-20 22:37:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 943 ms / 3,000 ms |
コード長 | 567 bytes |
コンパイル時間 | 238 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 84,096 KB |
最終ジャッジ日時 | 2024-09-30 08:42:34 |
合計ジャッジ時間 | 27,113 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
n,m,q=map(int,input().split()) ab=[] for i in range(n): a,b=map(int,input().split()) ab.append([a,b]) dp=[0]*(1<<n) for bit in range(1<<n): cost=0 val=0 for i in range(n): if (bit>>i)&1: cost+=ab[i][0] val+=ab[i][1] if cost<=m: dp[bit]=val for i in range(n): if (bit>>i)&1==0: dp[bit|(1<<i)]=max(dp[bit|(1<<i)],dp[bit]) mask=(1<<n)-1 ans=0 for bit in range(1<<n): cost=0 val=0 for i in range(n): if (bit>>i)&1: cost+=ab[i][0] val+=ab[i][1] if cost<=q: ans=max(ans,val+dp[bit^mask]) print(ans)