結果
問題 |
No.2686 商品券の使い道
|
ユーザー |
|
提出日時 | 2024-03-20 22:11:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 954 ms / 3,000 ms |
コード長 | 1,097 bytes |
コンパイル時間 | 216 ms |
コンパイル使用メモリ | 82,408 KB |
実行使用メモリ | 98,432 KB |
最終ジャッジ日時 | 2024-09-30 08:06:31 |
合計ジャッジ時間 | 28,383 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
import collections,sys,math,functools,operator,itertools,bisect,heapq,decimal,string,time,random #sys.setrecursionlimit(10**9) #sys.set_int_max_str_digits(0) n,m,q = map(int,input().split()) item = [list(map(int,input().split())) for i in range(n)] ans = 0 asu = [0 for i in range(1<<n)] for s in range(1<<n): a,b = 0,0 for j in range(n): if (s >> j) & 1 == 1: a += item[j][0] b += item[j][1] if a <= q: asu[s] = b #or convolution andにする場合は配列をreverseしてからゼータ変換して点積をとってメビウス変換してreverseする def subset_zeta_transform(s): for i in range(n): for j in range(1<<n): if (j >> i) & 1 == 0: s[j | (1 << i)] = max(s[j],s[j | (1 << i)]) return s asu = subset_zeta_transform(asu) for s in range(1<<n): a,b = 0,0 r = 0 for j in range(n): if (s >> j) & 1 == 1: a += item[j][0] b += item[j][1] else: r += (1 << j) if a <= m: ans = max(ans,b + asu[r]) print(ans)