結果

問題 No.3076 Goodstuff Deck Builder
ユーザー D M
提出日時 2025-04-03 12:16:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,357 bytes
コンパイル時間 428 ms
コンパイル使用メモリ 82,452 KB
実行使用メモリ 150,392 KB
最終ジャッジ日時 2025-04-03 12:16:17
合計ジャッジ時間 5,565 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, m = map(int, input().split())
cards = [tuple(map(int, input().split())) for _ in range(n)]
cards.sort(reverse=True)  # c, dの両面で大きい順

# dp[k] は、カードを k 枚選んだときの (cost, score) 状態のリスト（コスト昇順）
dp = [[] for _ in range(n+1)]
dp[0].append((0, 0))  # 初期状態

for c, d in cards:
    # k の降順に更新：同じカードからの複数更新を防ぐため
    for k in range(n-1, -1, -1):
        new_states = []
        for cost, score in dp[k]:
            new_cost = cost + c * (1 << k)  # 2^k を掛ける
            if new_cost <= m:
                new_states.append((new_cost, score + d))
        if new_states:
            # dp[k+1] に既存の状態と新状態を併合
            combined = dp[k+1] + new_states
            combined.sort(key=lambda x: x[0])  # コストでソート
            # ドミネーション除去：コストは低いほどよく、scoreが上回る状態だけを残す
            filtered = []
            best = -1
            for cost_val, score_val in combined:
                if score_val > best:
                    filtered.append((cost_val, score_val))
                    best = score_val
            dp[k+1] = filtered

ans = 0
for states in dp:
    if states:
        ans = max(ans, max(score for cost, score in states))
print(ans)
0