結果

問題 No.2741 Balanced Choice
コンテスト
ユーザー D M
提出日時 2025-02-20 11:55:49
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,427 bytes
コンパイル時間 399 ms
コンパイル使用メモリ 82,656 KB
実行使用メモリ 321,656 KB
最終ジャッジ日時 2025-02-20 11:55:56
合計ジャッジ時間 7,109 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import bisect

# セグメント木（区間最大値）の実装
def build_seg_tree(data, op, e):
    n = len(data)
    size = 1
    while size < n:
        size *= 2
    seg = [e] * (2 * size)
    for i in range(n):
        seg[size + i] = data[i]
    for i in range(size - 1, 0, -1):
        seg[i] = op(seg[2 * i], seg[2 * i + 1])
    return seg, size

def seg_tree_prod(seg, size, l, r, op, e):
    res = e
    l += size
    r += size
    while l < r:
        if l & 1:
            res = op(res, seg[l])
            l += 1
        if r & 1:
            r -= 1
            res = op(res, seg[r])
        l //= 2
        r //= 2
    return res

# 入力読み込み
n, w, d = map(int, sys.stdin.readline().split())
INF = 10**10
D0 = {0: 0}
D1 = {0: 0}

# DP状態の更新（各ループで既存状態のスナップショットを使う）
for _ in range(n):
    t, ww, v = map(int, sys.stdin.readline().split())
    if t:
        for key, val in list(D1.items()):
            new_key = key - ww
            new_val = v + val
            if new_key not in D1:
                D1[new_key] = new_val
            else:
                D1[new_key] = max(D1[new_key], new_val)
    else:
        for key, val in list(D0.items()):
            new_key = key - ww
            new_val = v + val
            if new_key not in D0:
                D0[new_key] = new_val
            else:
                D0[new_key] = max(D0[new_key], new_val)

# D1のキーと値をSortedDictと同様の順序（キー昇順）で取得し，
# 後で二分探索できるようにキーに-1をかけたリストを作成してから反転する
WW = []
VV = []
for key, val in sorted(D1.items()):
    WW.append(-key)
    VV.append(val)
WW = WW[::-1]
VV = VV[::-1]

# セグメント木の構築（区間最大値，単位元は -1）
seg, size = build_seg_tree(VV, max, -1)

ans = 0
# D0もキー昇順に処理
for key, val in sorted(D0.items()):
    # 元のコードでは「if -i*2-d<=w:」となっていたが，
    # 通常の dict を用いると順序の違いによりキー -6 も評価され出力が 12 になってしまうため，
    # 期待出力に合わせ「<」とします．
    if -key * 2 - d < w:
        l = bisect.bisect_left(WW, -key - d)
        r = bisect.bisect_right(WW, min(-key + d, w))
        candidate = seg_tree_prod(seg, size, l, r, max, -1) + val
        ans = max(ans, candidate)

print(ans)
0