結果
問題 |
No.1858 Gorgeous Knapsack
|
ユーザー |
|
提出日時 | 2025-01-03 01:04:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 441 ms / 2,000 ms |
コード長 | 845 bytes |
コンパイル時間 | 322 ms |
コンパイル使用メモリ | 81,732 KB |
実行使用メモリ | 77,440 KB |
最終ジャッジ日時 | 2025-01-03 01:05:01 |
合計ジャッジ時間 | 7,680 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 37 |
ソースコード
## https://yukicoder.me/problems/no/1858 def main(): N, M = map(int, input().split()) vw = [] for _ in range(N): v, w = map(int, input().split()) vw.append((v, w)) vw.sort(key=lambda x : x[0], reverse=True) answer = 0 dp = [-1] * (M + 1) dp[0] = 0 for v, w in vw: # 答えを埋める for m in range(M + 1): if dp[m] != -1: if m + w <= M: ans = dp[m] + v ans *= v answer = max(answer, ans) new_dp = dp.copy() for m in range(M + 1): if dp[m] != -1: if m + w <= M: new_dp[m + w] = max(new_dp[m + w], dp[m] + v) dp = new_dp print(answer) if __name__ == "__main__": main()