結果

問題 No.2741 Balanced Choice
ユーザー ThetaTheta
提出日時 2024-04-23 18:43:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,398 bytes
コンパイル時間 437 ms
コンパイル使用メモリ 82,160 KB
実行使用メモリ 713,104 KB
最終ジャッジ日時 2024-10-15 19:31:26
合計ジャッジ時間 23,327 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 TLE -
testcase_02 TLE -
testcase_03 TLE -
testcase_04 TLE -
testcase_05 AC 74 ms
67,932 KB
testcase_06 AC 60 ms
68,792 KB
testcase_07 MLE -
testcase_08 MLE -
testcase_09 AC 1,332 ms
493,224 KB
testcase_10 MLE -
testcase_11 MLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import accumulate
from math import inf
import sys

from math import inf
from typing import Callable, Generic, Sequence, TypeVar

ElmType = TypeVar("ElmType")


class SegmentTree(Generic[ElmType]):
    def __init__(self, seq: Sequence[ElmType], op: Callable[[
                 ElmType, ElmType], ElmType], init: ElmType) -> None:
        self._size = 1 << ((len(seq) - 1).bit_length())
        self.data = [init] * (2 * self._size)
        self.data[self._size:self._size + len(seq)] = seq
        self._op = op
        self._init = init

        for i in reversed(range(1, self._size)):
            self._update(i)

    def _update(self, k: int):
        self.data[k] = self._op(self.data[k * 2], self.data[k * 2 + 1])

    def set(self, idx: int, x: int):
        idx += self._size
        self.data[idx] = x

        idx //= 2
        while idx > 0:
            self._update(idx)
            idx //= 2

    def prod(self, l_idx: int, r_idx: int) -> ElmType:
        l_idx += self._size
        r_idx += self._size

        left_result = self._init
        right_result = self._init
        while l_idx < r_idx:
            if l_idx % 2:
                left_result = self._op(left_result, self.data[l_idx])
                l_idx += 1
            if r_idx % 2:
                r_idx -= 1
                right_result = self._op(self.data[r_idx], right_result)

            l_idx //= 2
            r_idx //= 2
        return self._op(left_result, right_result)

    def all_prod(self) -> ElmType:
        return self.data[1]

    def get(self, idx: int) -> ElmType:
        return self.data[idx + self._size]


def printe(*args, end="\n", **kwargs):
    print(*args, end=end, file=sys.stderr, **kwargs)


def main():
    N, W, D = map(int, input().split())
    stones = [list(map(int, input().split())) for _ in range(N)]

    type_0_dp_table = [[-inf for _ in range(W + 1)] for _ in range(N + 1)]
    type_1_dp_table = [[-inf for _ in range(W + 1)] for _ in range(N + 1)]
    type_0_dp_table[0][0] = 0
    type_1_dp_table[0][0] = 0
    for idx in range(N):
        for c_w in range(W + 1):
            type_0_dp_table[idx + 1][c_w] = max(
                type_0_dp_table[idx + 1][c_w],
                type_0_dp_table[idx][c_w]
            )
            type_1_dp_table[idx + 1][c_w] = max(
                type_1_dp_table[idx + 1][c_w],
                type_1_dp_table[idx][c_w]
            )
            if c_w + stones[idx][1] <= W:
                if stones[idx][0] == 0:
                    type_0_dp_table[idx + 1][c_w + stones[idx][1]] = max(
                        type_0_dp_table[idx + 1][c_w + stones[idx][1]],
                        type_0_dp_table[idx][c_w] + stones[idx][2]
                    )
                else:
                    type_1_dp_table[idx + 1][c_w + stones[idx][1]] = max(
                        type_1_dp_table[idx + 1][c_w + stones[idx][1]],
                        type_1_dp_table[idx][c_w] + stones[idx][2]
                    )

    last_type_0 = type_0_dp_table[-1]
    last_type_1 = type_1_dp_table[-1]
    last_type_1_accum_max = SegmentTree(last_type_1, max, -inf)

    max_value = 0
    for type_0_w in range(W + 1):
        max_value = max(max_value, last_type_0[type_0_w] + last_type_1_accum_max.prod(
            max(type_0_w - D, 0), min(type_0_w + D, W - type_0_w) + 1))
    print(max_value)


if __name__ == "__main__":
    main()
0