結果

問題 No.3670 Fast Knapsack
コンテスト
ユーザー harurun
提出日時 2026-09-01 22:35:32
言語 PyPy3
(7.3.23)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 2,287 ms / 2,500 ms
+ 474µs
コード長 1,807 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 247 ms
コンパイル使用メモリ 95,956 KB
実行使用メモリ 132,608 KB
最終ジャッジ日時 2026-09-04 23:03:52
合計ジャッジ時間 24,474 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge5_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
import pypyjit


# 短いテストケースが多数あっても、ループを早期に JIT コンパイルさせる。
pypyjit.set_param(
    "threshold=1,"
    "function_threshold=1,"
    "trace_eagerness=1,"
    "trace_limit=100000,"
    "inlining=1,"
    "decay=0"
)


def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))

    pos = 0
    t = data[pos]
    pos += 1

    answers = [""] * t
    case = 0

    while case < t:
        n = data[pos]
        s = data[pos + 1]
        pos += 2

        end = pos + n

        # bit i == 1 <=> 部分和 i が作れる
        reachable = 1

        # 現在到達可能な最大値
        hi = 0

        mask = (1 << (s + 1)) - 1

        while pos < end:
            a = data[pos]
            pos += 1

            # Ai > S は正整数なので絶対に使用できない
            if a > s:
                continue

            # 単独で S を作れる
            if a == s:
                hi = s
                pos = end
                break

            new_hi = hi + a

            if new_hi <= s:
                # この場合、S より上の bit は発生しないので
                # 高コストな & mask を省略できる
                reachable |= reachable << a
                hi = new_hi

                if hi == s:
                    pos = end
                    break
            else:
                reachable = (reachable | (reachable << a)) & mask
                hi = reachable.bit_length() - 1

                # S に到達した時点で答えは確定
                if hi == s:
                    pos = end
                    break

        answers[case] = str(hi)
        case += 1

    sys.stdout.write("\n".join(answers))


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