結果

問題 No.1858 Gorgeous Knapsack
ユーザー lam6er
提出日時 2025-03-20 20:54:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 438 ms / 2,000 ms
コード長 998 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 82,752 KB
実行使用メモリ 272,732 KB
最終ジャッジ日時 2025-03-20 20:55:00
合計ジャッジ時間 5,859 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

N, M = map(int, input().split())
gems = []
for _ in range(N):
    v, w = map(int, input().split())
    gems.append((v, w))

# Sort gems in descending order of value; if values are equal, order by weight (order doesn't matter)
gems.sort(key=lambda x: (-x[0], x[1]))

# Preprocess the dp list where dp[i] represents the DP array for the first i-1 gems (0-based)
dp_prev = [0] * (M + 1)
dp_list = [dp_prev.copy()]

for i in range(N):
    v, w = gems[i]
    new_dp = dp_prev.copy()
    for j in range(M, w - 1, -1):
        if new_dp[j - w] + v > new_dp[j]:
            new_dp[j] = new_dp[j - w] + v
    dp_list.append(new_dp)
    dp_prev = new_dp

max_g = 0
for i in range(N):
    v_i, w_i = gems[i]
    if w_i > M:
        continue
    remaining = M - w_i
    if remaining < 0:
        continue
    sum_rest = dp_list[i][remaining]  # dp_list[i] uses the first i-1 gems (0-based)
    total = v_i + sum_rest
    current_g = v_i * total
    if current_g > max_g:
        max_g = current_g

print(max_g)
0