提出詳細

ソースコード

A = int(input())
ans_list = []
for a in range(A):
    N = int(input())
    B = int(input())
    item_list = [list(map(int, input().split())) for i in range(N)]

    dp_list = [[[0, 0] for i in range(B + 1)] for j in range(N + 1)]
    dp_list[0][B] = [0, 0]

    for i in range(N):
        for j in range(B + 1):
            if j >= item_list[i][0]:
                if dp_list[i][j - item_list[i][0]][0] + item_list[i][1] > dp_list[i][j][0]:
                    dp_list[i + 1][j] = [dp_list[i][j - item_list[i][0]][0] +
                                         item_list[i][1], dp_list[i][j - item_list[i][0]][1] + item_list[i][0]]
                elif dp_list[i][j - item_list[i][0]][0] + item_list[i][1] == dp_list[i][j][0]:
                    if abs(dp_list[i][j - item_list[i][0]][1] + item_list[i][0] - B) < abs(dp_list[i][j][1] - B):
                        dp_list[i + 1][j] = [dp_list[i][j - item_list[i][0]][0] +
                                             item_list[i][1], dp_list[i][j - item_list[i][0]][1] + item_list[i][0]]
                    else:
                        dp_list[i + 1][j] = [dp_list[i][j][0], dp_list[i][j][1]]
                else:
                    dp_list[i + 1][j] = [dp_list[i][j][0], dp_list[i][j][1]]

            else:
                dp_list[i + 1][j] = [dp_list[i][j][0], dp_list[i][j][1]]

    ans_list.append(dp_list[N][B])


for i, j in enumerate(ans_list):
    print("Case #" + str(i + 1) + ":")
    print(j[1], j[0])

提出情報

提出時間 2020-04-29 16:04:06
問題 J - 質より量 (large)
ユーザ名 NekoZ
状態 形式違反
正解率 N/A
提出出力結果

テストケース情報

# 状態 詳細情報
正解か誤答の場合のみ表示されます．