結果

問題 No.3076 Goodstuff Deck Builder
コンテスト
ユーザー D M
提出日時 2025-04-03 13:08:31
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,070 bytes
コンパイル時間 553 ms
コンパイル使用メモリ 81,928 KB
実行使用メモリ 87,924 KB
最終ジャッジ日時 2025-04-03 13:08:39
合計ジャッジ時間 7,799 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    # 入力読み込み
    N, M = map(int, input().split())
    free_damage = 0
    nonfree = []
    for _ in range(N):
        c, d = map(int, input().split())
        if c == 0:
            free_damage += d
        else:
            nonfree.append((c, d))
    
    # 非無料カードをコストの降順にソート
    nonfree.sort(key=lambda x: x[0], reverse=True)
    
    # DPテーブル dp[r]: {消費エネルギー: 獲得ダメージ}
    # r は非無料カード使用枚数 (r枚使った場合，新たに使うカードのコストは 2^(r) 倍)
    max_r = len(nonfree)  # 使える枚数の上限だが，エネルギー M が小さいため実際は小さい枚数に制限される
    # ※ M <= 10^3 かつカードのコストは最低 1 ならば，2^(r)-1 <= M となる r は概ね 10 程度
    # ここでは十分大きめに確保
    dp = [defaultdict(lambda: -1) for _ in range(max_r+2)]
    dp[0][0] = 0
    
    # 各カードを 0-1 ナップサック的に処理
    for cost, dmg in nonfree:
        # r の大きいほうから更新 (同じカードを複数回使わないように)
        # r_max は M 以内に使える枚数の上限は実際の dp のサイズにより自動に制限される
        for r in range(max_r, -1, -1):
            # dp[r] の各状態について，新たにカードを採用した場合の状態を更新
            for energy_used, curr_damage in list(dp[r].items()):
                # 新たなカードを使うときの追加エネルギー: 2^r * cost
                new_energy = energy_used + (1 << r) * cost
                if new_energy <= M:
                    new_damage = curr_damage + dmg
                    if new_damage > dp[r+1].get(new_energy, -1):
                        dp[r+1][new_energy] = new_damage
    
    best = 0
    for d in dp:
        if d:
            best = max(best, max(d.values()))
    
    print(best + free_damage)

if __name__ == '__main__':
    main()
0