提出詳細

ソースコード

t = int(input())
ans_w = []
ans_v = []
for loop in range(t):
    max_num = int(input())
    max_weight = int(input())
    weight, value = [], []
    for i in range(max_num):
        a, b = map(int, input().split())
        weight.append(a), value.append(b)
    
    dp = [[[0, 0] for j in range(max_weight + 1)]for i in range(max_num + 1)] # [何個目][重み（値段）][価値（重さ）、その価値の時の最大の重み（値段）]

    for num in range(max_num):
        for wei in range(max_weight + 1):
            if wei >= weight[num]:
                if dp[num][wei - weight[num]][0] + value[num] == dp[num][wei][0]:
                    if dp[num][wei - weight[num]][1] + weight[num] >= dp[num][wei][1]:
                        dp[num + 1][wei][0] = dp[num][wei - weight[num]][0] + value[num]
                        dp[num + 1][wei][1] = dp[num][wei - weight[num]][1] + weight[num]
                    else:
                        dp[num + 1][wei] = dp[num][wei]
                elif dp[num][wei - weight[num]][0] + value[num] > dp[num][wei][0]:
                    dp[num + 1][wei][0] = dp[num][wei - weight[num]][0] + value[num]
                    dp[num + 1][wei][1] = dp[num][wei - weight[num]][1] + weight[num]
                else:
                    dp[num + 1][wei] = dp[num][wei]
            else:
                dp[num + 1][wei] = dp[num][wei]

    ans_v.append(dp[max_num][max_weight][0])
    ans_w.append(dp[max_num][max_weight][1])

for loop in range(t):
    print("Case #{}:".format(loop + 1))
    print(ans_w[loop], ans_v[loop])

提出情報

提出時間 2020-03-12 01:15:14
問題 J - 質より量 (large)
ユーザ名 konchan
状態 正解
正解率 50/50
提出出力結果

テストケース情報

# 状態 詳細情報
テストケース 1 正解 詳細を見る
テストケース 2 正解 詳細を見る
テストケース 3 正解 詳細を見る
テストケース 4 正解 詳細を見る
テストケース 5 正解 詳細を見る
テストケース 6 正解 詳細を見る
テストケース 7 正解 詳細を見る
テストケース 8 正解 詳細を見る
テストケース 9 正解 詳細を見る
テストケース 10 正解 詳細を見る
テストケース 11 正解 詳細を見る
テストケース 12 正解 詳細を見る
テストケース 13 正解 詳細を見る
テストケース 14 正解 詳細を見る
テストケース 15 正解 詳細を見る
テストケース 16 正解 詳細を見る
テストケース 17 正解 詳細を見る
テストケース 18 正解 詳細を見る
テストケース 19 正解 詳細を見る
テストケース 20 正解 詳細を見る
テストケース 21 正解 詳細を見る
テストケース 22 正解 詳細を見る
テストケース 23 正解 詳細を見る
テストケース 24 正解 詳細を見る
テストケース 25 正解 詳細を見る
テストケース 26 正解 詳細を見る
テストケース 27 正解 詳細を見る
テストケース 28 正解 詳細を見る
テストケース 29 正解 詳細を見る
テストケース 30 正解 詳細を見る
テストケース 31 正解 詳細を見る
テストケース 32 正解 詳細を見る
テストケース 33 正解 詳細を見る
テストケース 34 正解 詳細を見る
テストケース 35 正解 詳細を見る
テストケース 36 正解 詳細を見る
テストケース 37 正解 詳細を見る
テストケース 38 正解 詳細を見る
テストケース 39 正解 詳細を見る
テストケース 40 正解 詳細を見る
テストケース 41 正解 詳細を見る
テストケース 42 正解 詳細を見る
テストケース 43 正解 詳細を見る
テストケース 44 正解 詳細を見る
テストケース 45 正解 詳細を見る
テストケース 46 正解 詳細を見る
テストケース 47 正解 詳細を見る
テストケース 48 正解 詳細を見る
テストケース 49 正解 詳細を見る
テストケース 50 正解 詳細を見る