結果

問題 No.2741 Balanced Choice
ユーザー wgrapewgrape
提出日時 2024-11-01 14:17:20
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 685 ms / 2,000 ms
コード長 947 bytes
コンパイル時間 394 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 78,100 KB
最終ジャッジ日時 2024-11-01 14:17:28
合計ジャッジ時間 7,244 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 571 ms
77,288 KB
testcase_01 AC 624 ms
77,408 KB
testcase_02 AC 674 ms
77,488 KB
testcase_03 AC 665 ms
77,412 KB
testcase_04 AC 685 ms
78,100 KB
testcase_05 AC 38 ms
53,948 KB
testcase_06 AC 39 ms
53,876 KB
testcase_07 AC 314 ms
77,256 KB
testcase_08 AC 459 ms
77,364 KB
testcase_09 AC 298 ms
77,368 KB
testcase_10 AC 355 ms
77,332 KB
testcase_11 AC 465 ms
77,212 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# タイプ0,1の石それぞれで組めるパターン（重量に対する最大価値）を求める
# できたものをW未満になるように全探索

N,W,D = map(int,input().split())
stones = [list(map(int,input().split())) for i in range(N)]

def f(N,W,stones, typ):
#    print("typ",typ)
    INF = 1 << 60
    # dp[w] = wのときの最大価値
    dp = [-INF] * (W + 1)
    dp[0] = 0
    for t,w,v in stones:
        if t != typ:
            continue
#        print(w,v)
        for i in range(W, -1, -1):
            if dp[i] == -INF:
                continue
            if i + w > W:
                continue
            dp[i + w] = max(dp[i + w], dp[i] + v)
#    print(dp)
    return dp
    
type0 = f(N,W,stones,0)
type1 = f(N,W,stones,1)

ans = 0
for i in range(W + 1):
    for j in range(max(0, i - D), min(W + 1, i + D)):
        if i + j > W:
            continue
        ans = max(ans, type1[i] + type0[j])

print(ans)
0