結果

問題 No.2741 Balanced Choice
ユーザー wgrape
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

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