#1181995 (PyPy3) No.3670 Fast Knapsack

• 問題: No.3670 Fast Knapsack
• ユーザー: harurun
• 提出日時: 2026-09-01 23:06:51
• 言語: PyPy3 (7.3.23)
• 結果: AC
• 実行時間: 1,220 ms / 2,500 ms
• コード長: 3,052 bytes
• コンパイル時間: 230 ms
• コンパイル使用メモリ: 96,080 KB
• 実行使用メモリ: 133,328 KB
• 最終ジャッジ日時: 2026-09-04 23:05:25
• 合計ジャッジ時間: 16,024 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 25

ソースコード

import sys
import pypyjit


pypyjit.set_param(
    "threshold=1,"
    "function_threshold=1,"
    "trace_eagerness=1,"
    "decay=0"
)


W = 63
FULL_MASK = (1 << W) - 1

LOW_MASK = [0] * W
for r in range(1, W):
    LOW_MASK[r] = (1 << (W - r)) - 1


class Bitset:
    __slots__ = (
        "nbits",
        "_words",
        "_last_word",
        "_last_mask",
    )

    def __init__(self, nbits: int) -> None:
        if nbits <= 0:
            raise ValueError("nbits must be positive")

        self.nbits = nbits

        last_word = (nbits - 1) // W
        self._last_word = last_word

        self._words = [0] * (last_word + 2)

        rem = nbits - last_word * W
        self._last_mask = (1 << rem) - 1

    def clear(self) -> None:
        words = self._words

        i = len(words) - 1
        while i >= 0:
            words[i] = 0
            i -= 1

    def set(self, i: int) -> None:
        if i < 0 or i >= self.nbits:
            raise IndexError(i)

        q = i // W
        r = i - q * W

        self._words[q] |= 1 << r

    def reset(self, i: int) -> None:
        if i < 0 or i >= self.nbits:
            raise IndexError(i)

        q = i // W
        r = i - q * W

        self._words[q] &= FULL_MASK ^ (1 << r)

    def test(self, i: int) -> bool:
        if i < 0 or i >= self.nbits:
            raise IndexError(i)

        q = i // W
        r = i - q * W

        return ((self._words[q] >> r) & 1) != 0

    def ior_lshift(self, shift: int):
        if shift < 0:
            raise ValueError("negative shift count")

        if shift == 0 or shift >= self.nbits:
            return self

        words = self._words

        q = shift // W
        r = shift - q * W

        src = (self.nbits - 1 - shift) // W

        if r == 0:
            while src >= 0:
                words[src + q] |= words[src]
                src -= 1

        else:
            low_mask = LOW_MASK[r]
            rr = W - r

            while src >= 0:
                x = words[src]
                dst = src + q

                words[dst] |= (x & low_mask) << r
                words[dst + 1] |= x >> rr

                src -= 1

        return self

    def max_set_bit(self) -> int:
        words = self._words

        wi = self._last_word
        x = words[wi] & self._last_mask

        while x == 0:
            wi -= 1

            if wi < 0:
                return -1

            x = words[wi]

        return wi * W + x.bit_length() - 1


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

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

    ans = [""] * T

    tc = 0
    while tc < T:
        N = data[pos]
        S = data[pos + 1]
        pos += 2

        bits = Bitset(S + 1)
        bits.set(0)

        end = pos + N

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

            if a <= S:
                bits.ior_lshift(a)

        ans[tc] = str(bits.max_set_bit())
        tc += 1

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


if __name__ == "__main__":
    solve()