提出 #41292474

---

ソースコード 拡げる

import sys

input = sys.stdin.readline


def solve(n, w, arr):
    dp1 = [0] * (w + 1)
    dp2 = [[] for _ in range(w + 1)]
    dp2[0] = arr
    ans = 0
    for i in range(w + 1):
        for wj, vj in dp2[i]:
            if i + wj <= w and dp1[i] + vj > dp1[i + wj]:
                dp1[i + wj] = dp1[i] + vj
                dp2[i + wj] = dp2[i][:]
                dp2[i + wj].remove((wj, vj))
        ans = max(ans, dp1[i])

    print(ans)


def main():
    n, w = list(map(int, input().split()))
    arr = [tuple(map(int, input().split())) for _ in range(n)]
    solve(n, w, arr)


main()

提出情報

ジャッジ結果