結果

問題 No.3076 Goodstuff Deck Builder
コンテスト
ユーザー 👑 binap
提出日時 2025-02-10 21:09:01
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,893 ms / 3,000 ms
コード長 1,107 bytes
コンパイル時間 186 ms
コンパイル使用メモリ 82,040 KB
実行使用メモリ 87,416 KB
最終ジャッジ日時 2025-03-28 20:50:44
合計ジャッジ時間 24,948 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

# convert the following C++ code into pypy3 code
# https://yukicoder.me/submissions/1041740

import sys
from functools import lru_cache

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    index = 2
    
    hand = []
    ans1 = 0
    
    for _ in range(N):
        C, D = int(data[index]), int(data[index + 1])
        index += 2
        if C == 0:
            ans1 += D
        else:
            hand.append((C, D))
    
    hand.sort(reverse=True, key=lambda x: x[0])
    
    K = 10
    dp = [[0] * (M + 1) for _ in range(K + 1)]
    
    for _C, D in hand:
        dp_old = [row[:] for row in dp]  # Deep copy
        
        for i in range(K + 1):
            for j in range(M + 1):
                dp[i][j] = max(dp[i][j], dp_old[i][j])
        
        for i in range(K - 1, -1, -1):
            C = _C << i
            for j in range(M - C, -1, -1):
                dp[i + 1][j + C] = max(dp[i + 1][j + C], dp_old[i][j] + D)
    
    ans2 = max(max(row) for row in dp)
    print(ans1 + ans2)

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