結果

問題 No.2741 Balanced Choice
コンテスト
ユーザー D M
提出日時 2025-02-20 12:13:00
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 291 ms / 2,000 ms
コード長 2,229 bytes
コンパイル時間 1,494 ms
コンパイル使用メモリ 82,112 KB
実行使用メモリ 77,344 KB
最終ジャッジ日時 2025-02-20 12:13:06
合計ジャッジ時間 5,073 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve():
    import sys
    input = sys.stdin.readline
    INF_NEG = -10**9  # 不可能状態の値

    # 入力の取得
    N, W, D = map(int, input().split())
    stones0 = []
    stones1 = []
    for _ in range(N):
        t, w, v = map(int, input().split())
        if t == 0:
            stones0.append((w, v))
        else:
            stones1.append((w, v))
    
    # ナップザックDP (各グループ別)
    def knap(stones):
        dp = [INF_NEG] * (W+1)
        dp[0] = 0
        for w_stone, v_stone in stones:
            # 重さの大きい方から更新
            for weight in range(W, w_stone-1, -1):
                if dp[weight - w_stone] != INF_NEG:
                    dp[weight] = max(dp[weight], dp[weight - w_stone] + v_stone)
        return dp

    dp0 = knap(stones0)
    dp1 = knap(stones1)
    
    # セグメントツリーの構築（dp1 用）
    # セグメントツリーは，インデックス i (0<=i<=W) の dp1[i] を保持し，
    # 区間最大値クエリを O(log W) で答えられるようにする
    nsize = W + 1
    size = 1
    while size < nsize:
        size *= 2
    seg = [INF_NEG] * (2 * size)
    # 葉にdp1の値をセット
    for i in range(nsize):
        seg[size + i] = dp1[i]
    for i in range(size - 1, 0, -1):
        seg[i] = max(seg[2*i], seg[2*i+1])
    
    def seg_query(l, r):
        # [l, r) の区間最大値を返す
        res = INF_NEG
        l += size
        r += size
        while l < r:
            if l & 1:
                res = max(res, seg[l])
                l += 1
            if r & 1:
                r -= 1
                res = max(res, seg[r])
            l //= 2
            r //= 2
        return res

    ans = 0
    # dp0 の各重量 x について，対応する dp1 の重さ y の区間
    for x in range(W+1):
        if dp0[x] == INF_NEG:
            continue
        # y の条件： y in [L, R] となるように
        L = max(0, x - D)
        R = min(W - x, x + D)
        if L > R:
            continue
        best_dp1 = seg_query(L, R+1)
        if best_dp1 == INF_NEG:
            continue
        ans = max(ans, dp0[x] + best_dp1)
    print(ans)

if __name__ == '__main__':
    solve()
0