結果

問題 No.2741 Balanced Choice
ユーザー ThetaTheta
提出日時 2024-04-23 19:14:59
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,890 ms / 2,000 ms
コード長 1,504 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 81,960 KB
実行使用メモリ 80,256 KB
最終ジャッジ日時 2024-10-15 20:04:13
合計ジャッジ時間 16,026 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,504 ms
80,232 KB
testcase_01 AC 1,749 ms
79,916 KB
testcase_02 AC 1,786 ms
80,124 KB
testcase_03 AC 1,733 ms
80,252 KB
testcase_04 AC 1,890 ms
80,104 KB
testcase_05 AC 59 ms
67,080 KB
testcase_06 AC 62 ms
70,944 KB
testcase_07 AC 761 ms
79,804 KB
testcase_08 AC 1,201 ms
79,952 KB
testcase_09 AC 714 ms
79,776 KB
testcase_10 AC 937 ms
80,248 KB
testcase_11 AC 1,344 ms
80,256 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import accumulate, product
from math import inf
import sys

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


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

    max_value = 0
    for type_0_w, type_1_w in product(range(W + 1), repeat=2):
        if type_0_w + type_1_w > W:
            continue
        if abs(type_0_w - type_1_w) > D:
            continue
        max_value = max(
            max_value,
            type_0_dp_table[type_0_w] + type_1_dp_table[type_1_w]
        )
    print(max_value)


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