#1181996 (PyPy3) No.3670 Fast Knapsack

• 問題: No.3670 Fast Knapsack
• ユーザー: harurun
• 提出日時: 2026-09-01 23:09:48
• 言語: PyPy3 (7.3.23)
• 結果: AC
• 実行時間: 1,265 ms / 2,500 ms
• コード長: 5,330 bytes
• コンパイル時間: 847 ms
• コンパイル使用メモリ: 95,816 KB
• 実行使用メモリ: 114,028 KB
• 最終ジャッジ日時: 2026-09-04 23:05:47
• 合計ジャッジ時間: 20,077 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

import sys
import os

# ============================================================
# Native bitset
#
# yukicoder:
#   PyPyのcompile phaseではMain.pyを実行できないため、
#   最初の実行時に小さなCライブラリだけコンパイルする。
#
# C++ではなくCにすることでコンパイラのメモリ消費を抑える。
# ============================================================

C_SOURCE = r'''
#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>

typedef struct {
    size_t nbits;
    size_t nwords;
    uint64_t *a;
} BitSet;


BitSet* bs_new(size_t n) {
    BitSet *p = (BitSet*)malloc(sizeof(BitSet));

    if (!p) {
        return NULL;
    }

    p->nbits = n;
    p->nwords = (n + 63) >> 6;

    p->a = (uint64_t*)calloc(
        p->nwords ? p->nwords : 1,
        sizeof(uint64_t)
    );

    if (!p->a) {
        free(p);
        return NULL;
    }

    return p;
}


void bs_delete(BitSet *p) {
    if (p) {
        free(p->a);
        free(p);
    }
}


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


/*
    p |= p << k

    後ろから更新するので一時bitset不要。
*/
void bs_or_shift_left(BitSet *p, size_t k) {
    if (k == 0 || k >= p->nbits) {
        return;
    }

    const size_t q = k >> 6;
    const unsigned r = (unsigned)(k & 63);
    const size_t n = p->nwords;

    if (r) {
        for (size_t i = n; 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 (size_t i = n; i-- > q;) {
            p->a[i] |= p->a[i - q];
        }
    }

    /*
        最終wordのnbits以降を0にする。
    */
    const unsigned rem =
        (unsigned)(p->nbits & 63);

    if (rem) {
        p->a[n - 1] &=
            (UINT64_C(1) << rem) - 1;
    }
}


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

        if (x) {
            return
                (i << 6)
                + 64
                - (unsigned)__builtin_clzll(x);
        }
    }

    return 0;
}
'''


# ============================================================
# Compile
#
# ctypesをimportする前にコンパイルする。
# コンパイル中のPyPy側メモリをなるべく小さくする。
# ============================================================

_pid = os.getpid()

_c_path = "/tmp/fastbitset_%d.c" % _pid
_so_path = "/tmp/fastbitset_%d.so" % _pid

with open(_c_path, "w") as f:
    f.write(C_SOURCE)

ret = os.spawnlp(
    os.P_WAIT,
    "gcc-15",
    "gcc-15",
    "-O2",
    "-march=native",
    "-shared",
    "-fPIC",
    _c_path,
    "-o",
    _so_path,
)

if ret != 0:
    raise RuntimeError(
        "failed to compile fastbitset"
    )


# コンパイル終了後にctypesをimport
import ctypes


lib = ctypes.CDLL(_so_path)

P = ctypes.c_void_p
Z = ctypes.c_size_t


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

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

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

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

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


# dlopen済みなのでLinuxでは削除してよい
try:
    os.unlink(_c_path)
except OSError:
    pass

try:
    os.unlink(_so_path)
except OSError:
    pass


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

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

    def __init__(self, n):
        self.n = n
        self._p = lib.bs_new(n)

        if not self._p:
            raise MemoryError

    def set(self, i):
        lib.bs_set(
            self._p,
            i
        )

    def or_shift_left(self, k):
        lib.bs_or_shift_left(
            self._p,
            k
        )

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

    def close(self):
        """
        PyPyでは必ず明示的に呼ぶ。

        C側のmalloc領域はPyPy GCから見えないため、
        __del__だけに任せるとMLEの原因になる。
        """
        p = self._p

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

    def __del__(self):
        # closeし忘れた場合の保険
        p = getattr(
            self,
            "_p",
            None
        )

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


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

input = sys.stdin.buffer.readline


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

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

    # A = list(...) としない。
    # PyPyではintのlistがかなり大きい。
    for x in map(int, input().split()):
        C.or_shift_left(x)

    ans = C.bit_length() - 1

    # 重要:
    # 次のテストケースに行く前にC側メモリを即座にfreeする。
    C.close()

    print(ans)


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

    for _ in range(T):
        solve()


if __name__ == "__main__":
    main()