結果

問題 No.3076 Goodstuff Deck Builder
コンテスト
ユーザー Koi
提出日時 2025-03-29 00:03:19
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 871 bytes
コンパイル時間 404 ms
コンパイル使用メモリ 82,780 KB
実行使用メモリ 849,944 KB
最終ジャッジ日時 2025-03-29 00:03:33
合計ジャッジ時間 3,833 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 MLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

N, M = map(int, input().split())
CD = [list(map(int, input().split())) for _ in range(N)]
dp = [[[0] * 11 for _ in range(M + 1)] for _ in range(N + 1)]
CD.sort(reverse=True)
Pot = [2 ** i for i in range(11)]
add = 0
# print(CD)
last = 0
for i in range(N):
    if(CD[i][0] == 0):
        add += CD[i][1]
    else:
        last = i + 1
        for j in range(M + 1):
            for k in range(11):
                dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k])
                if(j + CD[i][0] * Pot[k] <= M):
                    dp[i + 1][j + CD[i][0] * Pot[k]][k + 1] = max(dp[i + 1][j + CD[i][0] * Pot[k]][k + 1], dp[i][j][k] + CD[i][1])

ans = 0
# for i in range(N + 1):
#     print(i)
#     for j in range(M + 1):
#         print(dp[i][j])
for i in range(M + 1):
    for j in range(11):
        ans = max(ans, dp[last][i][j])
print(ans + add)
0