#1181994 (PyPy3) No.3670 Fast Knapsack

• 問題: No.3670 Fast Knapsack
• ユーザー: harurun
• 提出日時: 2026-09-01 23:05:21
• 言語: PyPy3 (7.3.23)
• 結果: MLE
• 実行時間: -
• コード長: 18,041 bytes
• コンパイル時間: 225 ms
• コンパイル使用メモリ: 96,080 KB
• 実行使用メモリ: 1,343,280 KB
• 最終ジャッジ日時: 2026-09-04 23:05:18
• 合計ジャッジ時間: 12,815 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 11 MLE * 2 -- * 12

ソースコード

import sys
import os
import ctypes
import subprocess
import shutil
import hashlib


# ============================================================
# C++ implementation
# ============================================================

CPP_SOURCE = r'''
#include <cstdint>
#include <cstddef>
#include <cstring>
#include <algorithm>
#include <bit>


struct BitSet {
    std::size_t nbits;
    std::size_t nwords;
    std::uint64_t* a;

    explicit BitSet(std::size_t n)
        : nbits(n),
          nwords((n + 63) >> 6),
          a(new std::uint64_t[nwords]{}) {}

    BitSet(const BitSet& other)
        : nbits(other.nbits),
          nwords(other.nwords),
          a(new std::uint64_t[nwords]) {
        std::memcpy(
            a,
            other.a,
            nwords * sizeof(std::uint64_t)
        );
    }

    ~BitSet() {
        delete[] a;
    }

    inline void trim() {
        if (nwords && (nbits & 63)) {
            a[nwords - 1] &=
                (1ULL << (nbits & 63)) - 1;
        }
    }
};


extern "C" {


// ============================================================
// construction
// ============================================================

BitSet* bs_new(std::size_t n) {
    return new BitSet(n);
}

void bs_delete(BitSet* p) {
    delete p;
}

BitSet* bs_clone(const BitSet* p) {
    return new BitSet(*p);
}


// ============================================================
// basic
// ============================================================

void bs_clear(BitSet* p) {
    std::fill(
        p->a,
        p->a + p->nwords,
        0
    );
}

void bs_fill(BitSet* p) {
    std::fill(
        p->a,
        p->a + p->nwords,
        ~0ULL
    );

    p->trim();
}

void bs_set(BitSet* p, std::size_t i) {
    p->a[i >> 6] |=
        1ULL << (i & 63);
}

void bs_reset(BitSet* p, std::size_t i) {
    p->a[i >> 6] &=
        ~(1ULL << (i & 63));
}

void bs_flip(BitSet* p, std::size_t i) {
    p->a[i >> 6] ^=
        1ULL << (i & 63);
}

int bs_test(
    const BitSet* p,
    std::size_t i
) {
    return
        (p->a[i >> 6] >> (i & 63)) & 1;
}


// ============================================================
// queries
// ============================================================

std::size_t bs_count(const BitSet* p) {
    std::size_t res = 0;

    for (
        std::size_t i = 0;
        i < p->nwords;
        ++i
    ) {
        res += std::popcount(p->a[i]);
    }

    return res;
}

std::size_t bs_bit_length(const BitSet* p) {
    for (
        std::size_t i = p->nwords;
        i-- > 0;
    ) {
        const std::uint64_t x = p->a[i];

        if (x) {
            return
                (i << 6)
                + 64
                - std::countl_zero(x);
        }
    }

    return 0;
}

int bs_any(const BitSet* p) {
    for (
        std::size_t i = 0;
        i < p->nwords;
        ++i
    ) {
        if (p->a[i]) {
            return 1;
        }
    }

    return 0;
}

int bs_equal(
    const BitSet* x,
    const BitSet* y
) {
    if (x->nbits != y->nbits) {
        return 0;
    }

    for (
        std::size_t i = 0;
        i < x->nwords;
        ++i
    ) {
        if (x->a[i] != y->a[i]) {
            return 0;
        }
    }

    return 1;
}


// ============================================================
// bitwise
// ============================================================

void bs_iand(
    BitSet* x,
    const BitSet* y
) {
    for (
        std::size_t i = 0;
        i < x->nwords;
        ++i
    ) {
        x->a[i] &= y->a[i];
    }
}

void bs_ior(
    BitSet* x,
    const BitSet* y
) {
    for (
        std::size_t i = 0;
        i < x->nwords;
        ++i
    ) {
        x->a[i] |= y->a[i];
    }
}

void bs_ixor(
    BitSet* x,
    const BitSet* y
) {
    for (
        std::size_t i = 0;
        i < x->nwords;
        ++i
    ) {
        x->a[i] ^= y->a[i];
    }
}

void bs_inot(BitSet* x) {
    for (
        std::size_t i = 0;
        i < x->nwords;
        ++i
    ) {
        x->a[i] = ~x->a[i];
    }

    x->trim();
}


// ============================================================
// shift
// ============================================================

void bs_ishl(
    BitSet* p,
    std::size_t k
) {
    if (k >= p->nbits) {
        bs_clear(p);
        return;
    }

    const std::size_t q = k >> 6;
    const std::size_t r = k & 63;

    if (r) {
        for (
            std::size_t i = p->nwords;
            i-- > q + 1;
        ) {
            p->a[i] =
                (p->a[i - q] << r)
                |
                (p->a[i - q - 1] >> (64 - r));
        }

        p->a[q] =
            p->a[0] << r;
    }
    else {
        for (
            std::size_t i = p->nwords;
            i-- > q;
        ) {
            p->a[i] =
                p->a[i - q];
        }
    }

    std::fill(
        p->a,
        p->a + q,
        0
    );

    p->trim();
}

void bs_ishr(
    BitSet* p,
    std::size_t k
) {
    if (k >= p->nbits) {
        bs_clear(p);
        return;
    }

    const std::size_t q = k >> 6;
    const std::size_t r = k & 63;
    const std::size_t m = p->nwords - q;

    if (r) {
        for (
            std::size_t i = 0;
            i + 1 < m;
            ++i
        ) {
            p->a[i] =
                (p->a[i + q] >> r)
                |
                (p->a[i + q + 1] << (64 - r));
        }

        p->a[m - 1] =
            p->a[p->nwords - 1] >> r;
    }
    else {
        for (
            std::size_t i = 0;
            i < m;
            ++i
        ) {
            p->a[i] =
                p->a[i + q];
        }
    }

    std::fill(
        p->a + m,
        p->a + p->nwords,
        0
    );
}


// ============================================================
// fused shift OR
//
// p |= p << k
// p |= p >> k
//
// 一時 BitSet を生成しない。
// ============================================================

void bs_or_shift_left(
    BitSet* p,
    std::size_t k
) {
    if (k == 0 || k >= p->nbits) {
        return;
    }

    const std::size_t q = k >> 6;
    const std::size_t r = k & 63;

    if (r) {
        for (
            std::size_t i = p->nwords;
            i-- > q + 1;
        ) {
            p->a[i] |=
                (p->a[i - q] << r)
                |
                (p->a[i - q - 1] >> (64 - r));
        }

        p->a[q] |=
            p->a[0] << r;
    }
    else {
        for (
            std::size_t i = p->nwords;
            i-- > q;
        ) {
            p->a[i] |=
                p->a[i - q];
        }
    }

    p->trim();
}

void bs_or_shift_right(
    BitSet* p,
    std::size_t k
) {
    if (k == 0 || k >= p->nbits) {
        return;
    }

    const std::size_t q = k >> 6;
    const std::size_t r = k & 63;
    const std::size_t m = p->nwords - q;

    if (r) {
        for (
            std::size_t i = 0;
            i + 1 < m;
            ++i
        ) {
            p->a[i] |=
                (p->a[i + q] >> r)
                |
                (p->a[i + q + 1] << (64 - r));
        }

        p->a[m - 1] |=
            p->a[p->nwords - 1] >> r;
    }
    else {
        for (
            std::size_t i = 0;
            i < m;
            ++i
        ) {
            p->a[i] |=
                p->a[i + q];
        }
    }
}


// ============================================================
// find
// ============================================================

std::size_t bs_find_first(
    const BitSet* p
) {
    for (
        std::size_t i = 0;
        i < p->nwords;
        ++i
    ) {
        const std::uint64_t x = p->a[i];

        if (x) {
            return
                (i << 6)
                + std::countr_zero(x);
        }
    }

    return p->nbits;
}

std::size_t bs_find_next(
    const BitSet* p,
    std::size_t pos
) {
    ++pos;

    if (pos >= p->nbits) {
        return p->nbits;
    }

    std::size_t w = pos >> 6;

    std::uint64_t x =
        p->a[w]
        &
        (~0ULL << (pos & 63));

    if (x) {
        return
            (w << 6)
            + std::countr_zero(x);
    }

    for (
        ++w;
        w < p->nwords;
        ++w
    ) {
        x = p->a[w];

        if (x) {
            return
                (w << 6)
                + std::countr_zero(x);
        }
    }

    return p->nbits;
}


}
'''


# ============================================================
# yukicoder:
# PyPy の実行開始時に C++ を共有ライブラリへコンパイル
# ============================================================

BASE_DIR = os.path.dirname(
    os.path.abspath(__file__)
)

CACHE_DIR = os.path.join(
    BASE_DIR,
    "__pycache__"
)

os.makedirs(
    CACHE_DIR,
    exist_ok=True
)


# C++ソースが変わった場合だけ別ファイル名になる
SOURCE_HASH = hashlib.blake2b(
    CPP_SOURCE.encode(),
    digest_size=8
).hexdigest()

CPP_PATH = os.path.join(
    CACHE_DIR,
    "_fastbitset_" + SOURCE_HASH + ".cpp"
)

SO_PATH = os.path.join(
    CACHE_DIR,
    "_fastbitset_" + SOURCE_HASH + ".so"
)


def build_fastbitset():
    compiler = (
        shutil.which("g++-15")
        or shutil.which("g++-16")
        or shutil.which("g++")
    )

    if compiler is None:
        raise RuntimeError(
            "C++ compiler was not found"
        )

    with open(CPP_PATH, "w") as f:
        f.write(CPP_SOURCE)

    subprocess.run(
        [
            compiler,
            "-std=gnu++20",
            "-O3",
            "-march=native",
            "-shared",
            "-fPIC",
            CPP_PATH,
            "-o",
            SO_PATH,
        ],
        check=True,
    )


if not os.path.exists(SO_PATH):
    build_fastbitset()


# ============================================================
# ctypes
# ============================================================

lib = ctypes.CDLL(SO_PATH)

P = ctypes.c_void_p
Z = ctypes.c_size_t
I = ctypes.c_int


lib.bs_new.argtypes = [Z]
lib.bs_new.restype = P

lib.bs_delete.argtypes = [P]
lib.bs_delete.restype = None

lib.bs_clone.argtypes = [P]
lib.bs_clone.restype = P


lib.bs_clear.argtypes = [P]
lib.bs_clear.restype = None

lib.bs_fill.argtypes = [P]
lib.bs_fill.restype = None

lib.bs_set.argtypes = [P, Z]
lib.bs_set.restype = None

lib.bs_reset.argtypes = [P, Z]
lib.bs_reset.restype = None

lib.bs_flip.argtypes = [P, Z]
lib.bs_flip.restype = None

lib.bs_test.argtypes = [P, Z]
lib.bs_test.restype = I


lib.bs_count.argtypes = [P]
lib.bs_count.restype = Z

lib.bs_bit_length.argtypes = [P]
lib.bs_bit_length.restype = Z

lib.bs_any.argtypes = [P]
lib.bs_any.restype = I

lib.bs_equal.argtypes = [P, P]
lib.bs_equal.restype = I


lib.bs_iand.argtypes = [P, P]
lib.bs_iand.restype = None

lib.bs_ior.argtypes = [P, P]
lib.bs_ior.restype = None

lib.bs_ixor.argtypes = [P, P]
lib.bs_ixor.restype = None

lib.bs_inot.argtypes = [P]
lib.bs_inot.restype = None


lib.bs_ishl.argtypes = [P, Z]
lib.bs_ishl.restype = None

lib.bs_ishr.argtypes = [P, Z]
lib.bs_ishr.restype = None


lib.bs_or_shift_left.argtypes = [P, Z]
lib.bs_or_shift_left.restype = None

lib.bs_or_shift_right.argtypes = [P, Z]
lib.bs_or_shift_right.restype = None


lib.bs_find_first.argtypes = [P]
lib.bs_find_first.restype = Z

lib.bs_find_next.argtypes = [P, Z]
lib.bs_find_next.restype = Z


# ============================================================
# Python wrapper
# ============================================================

class Bitset:
    __slots__ = ("n", "_p")

    def __init__(self, n):
        if n < 0:
            raise ValueError(
                "Bitset size must be non-negative"
            )

        self.n = n
        self._p = lib.bs_new(n)

    @classmethod
    def _from_ptr(cls, n, p):
        obj = object.__new__(cls)
        obj.n = n
        obj._p = p
        return obj

    def __del__(self):
        p = getattr(
            self,
            "_p",
            None
        )

        if p:
            lib.bs_delete(p)
            self._p = None

    def copy(self):
        return Bitset._from_ptr(
            self.n,
            lib.bs_clone(self._p),
        )

    # --------------------------------------------------------
    # basic
    # --------------------------------------------------------

    def clear(self):
        lib.bs_clear(self._p)
        return self

    def fill(self):
        lib.bs_fill(self._p)
        return self

    def set(self, i):
        if not 0 <= i < self.n:
            raise IndexError(i)

        lib.bs_set(
            self._p,
            i
        )

        return self

    def reset(self, i):
        if not 0 <= i < self.n:
            raise IndexError(i)

        lib.bs_reset(
            self._p,
            i
        )

        return self

    def flip(self, i):
        if not 0 <= i < self.n:
            raise IndexError(i)

        lib.bs_flip(
            self._p,
            i
        )

        return self

    def __getitem__(self, i):
        if not 0 <= i < self.n:
            raise IndexError(i)

        return bool(
            lib.bs_test(
                self._p,
                i
            )
        )

    # --------------------------------------------------------
    # queries
    # --------------------------------------------------------

    def count(self):
        return lib.bs_count(
            self._p
        )

    def bit_length(self):
        return lib.bs_bit_length(
            self._p
        )

    def any(self):
        return bool(
            lib.bs_any(
                self._p
            )
        )

    def none(self):
        return not bool(
            lib.bs_any(
                self._p
            )
        )

    def __bool__(self):
        return bool(
            lib.bs_any(
                self._p
            )
        )

    def _check_size(self, other):
        if (
            not isinstance(other, Bitset)
            or self.n != other.n
        ):
            raise ValueError(
                "Bitset size mismatch"
            )

    # --------------------------------------------------------
    # inplace bitwise
    # --------------------------------------------------------

    def __iand__(self, other):
        self._check_size(other)

        lib.bs_iand(
            self._p,
            other._p
        )

        return self

    def __ior__(self, other):
        self._check_size(other)

        lib.bs_ior(
            self._p,
            other._p
        )

        return self

    def __ixor__(self, other):
        self._check_size(other)

        lib.bs_ixor(
            self._p,
            other._p
        )

        return self

    # --------------------------------------------------------
    # inplace shift
    # --------------------------------------------------------

    def __ilshift__(self, k):
        if k < 0:
            return self.__irshift__(-k)

        lib.bs_ishl(
            self._p,
            k
        )

        return self

    def __irshift__(self, k):
        if k < 0:
            return self.__ilshift__(-k)

        lib.bs_ishr(
            self._p,
            k
        )

        return self

    # --------------------------------------------------------
    # non-inplace
    # --------------------------------------------------------

    def __and__(self, other):
        res = self.copy()
        res &= other
        return res

    def __or__(self, other):
        res = self.copy()
        res |= other
        return res

    def __xor__(self, other):
        res = self.copy()
        res ^= other
        return res

    def __invert__(self):
        res = self.copy()

        lib.bs_inot(
            res._p
        )

        return res

    def __lshift__(self, k):
        res = self.copy()
        res <<= k
        return res

    def __rshift__(self, k):
        res = self.copy()
        res >>= k
        return res

    # --------------------------------------------------------
    # comparison
    # --------------------------------------------------------

    def __eq__(self, other):
        if not isinstance(other, Bitset):
            return NotImplemented

        if self.n != other.n:
            return False

        return bool(
            lib.bs_equal(
                self._p,
                other._p
            )
        )

    # --------------------------------------------------------
    # fused operations
    # --------------------------------------------------------

    def or_shift_left(self, k):
        # self |= self << k
        if k < 0:
            return self.or_shift_right(-k)

        lib.bs_or_shift_left(
            self._p,
            k
        )

        return self

    def or_shift_right(self, k):
        # self |= self >> k
        if k < 0:
            return self.or_shift_left(-k)

        lib.bs_or_shift_right(
            self._p,
            k
        )

        return self

    # --------------------------------------------------------
    # find
    # --------------------------------------------------------

    def first(self):
        x = lib.bs_find_first(
            self._p
        )

        if x == self.n:
            return -1

        return x

    def next(self, i):
        x = lib.bs_find_next(
            self._p,
            i
        )

        if x == self.n:
            return -1

        return x

    def __iter__(self):
        x = lib.bs_find_first(
            self._p
        )

        while x != self.n:
            yield x

            x = lib.bs_find_next(
                self._p,
                x
            )


BitSet = Bitset


# ============================================================
# solution
# ============================================================

input = sys.stdin.readline


def solve():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))

    C = Bitset(S + 1)

    C.set(0)

    for x in A:
        C.or_shift_left(x)

    print(C.bit_length() - 1)


def main():
    T = int(input())

    for _ in range(T):
        solve()


if __name__ == "__main__":
    main()