結果
| 問題 | No.3670 Fast Knapsack |
| コンテスト | |
| ユーザー |
 harurun
|
| 提出日時 | 2026-09-01 23:35:46 |
| 言語 | PyPy3 (7.3.23) |
| 結果 |
AC
|
| 実行時間 | 2,215 ms / 2,500 ms |
| + 625µs | |
| コード長 | 23,943 bytes |
| 記録 | |
| コンパイル時間 | 242 ms |
| コンパイル使用メモリ | 96,592 KB |
| 実行使用メモリ | 107,872 KB |
| 最終ジャッジ日時 | 2026-09-04 23:07:14 |
| 合計ジャッジ時間 | 25,234 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge5_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 25 |
ソースコード
import pypyjit
pypyjit.set_param(
"threshold=1,"
"function_threshold=1,"
"trace_eagerness=1,"
"decay=0"
)
WORD_BITS = 63
WORD_MASK = (1 << WORD_BITS) - 1
_LOW_KEEP = [0] * WORD_BITS
_LOW_BITS = [0] * WORD_BITS
for _r in range(1, WORD_BITS):
_LOW_KEEP[_r] = (1 << (WORD_BITS - _r)) - 1
_LOW_BITS[_r] = (1 << _r) - 1
class BitSet:
__slots__ = ("nbits", "nwords", "_last_mask", "_words", "_lo", "_hi")
def __init__(self, nbits, value=0):
if nbits <= 0:
raise ValueError("nbits must be positive")
if value < 0:
raise ValueError("value must be non-negative")
self.nbits = nbits
nwords = (nbits + WORD_BITS - 1) // WORD_BITS
self.nwords = nwords
rem = nbits - (nwords - 1) * WORD_BITS
self._last_mask = WORD_MASK if rem == WORD_BITS else (1 << rem) - 1
words = [0] * (nwords + 1)
i = 0
while i < nwords and value:
words[i] = value & WORD_MASK
value >>= WORD_BITS
i += 1
words[nwords - 1] &= self._last_mask
self._words = words
hi = min(i - 1, nwords - 1)
while hi >= 0 and words[hi] == 0:
hi -= 1
if hi < 0:
self._lo = nwords
self._hi = -1
else:
lo = 0
while words[lo] == 0:
lo += 1
self._lo = lo
self._hi = hi
def _clean_for_right_shift(self):
words = self._words
words[self.nwords - 1] &= self._last_mask
words[self.nwords] = 0
def _check_compatible(self, other):
if not isinstance(other, BitSet):
raise TypeError("operand must be BitSet")
if self.nbits != other.nbits:
raise ValueError("bitset sizes differ")
def _trim(self):
lo = self._lo
hi = self._hi
if hi < lo:
self._lo = self.nwords
self._hi = -1
return
words = self._words
last = self.nwords - 1
if hi > last:
hi = last
if hi == last:
words[last] &= self._last_mask
while lo <= hi and words[lo] == 0:
lo += 1
while hi >= lo and words[hi] == 0:
hi -= 1
if lo > hi:
self._lo = self.nwords
self._hi = -1
else:
self._lo = lo
self._hi = hi
def copy(self):
obj = object.__new__(BitSet)
obj.nbits = self.nbits
obj.nwords = self.nwords
obj._last_mask = self._last_mask
obj._words = self._words[:]
obj._lo = self._lo
obj._hi = self._hi
return obj
def clear(self):
self._words = [0] * (self.nwords + 1)
self._lo = self.nwords
self._hi = -1
return self
def set_all(self):
n = self.nwords
words = [WORD_MASK] * (n + 1)
words[n - 1] = self._last_mask
words[n] = 0
self._words = words
self._lo = 0
self._hi = n - 1
return self
def flip_all(self):
words = self._words
n = self.nwords
i = 0
while i < n - 1:
words[i] = WORD_MASK ^ words[i]
i += 1
last = n - 1
words[last] = self._last_mask ^ (words[last] & self._last_mask)
words[n] = 0
self._lo = 0
self._hi = last
self._trim()
return self
def set(self, i):
if i < 0 or i >= self.nbits:
raise IndexError(i)
q = i // WORD_BITS
r = i - q * WORD_BITS
self._words[q] |= 1 << r
if q < self._lo:
self._lo = q
if q > self._hi:
self._hi = q
return self
def reset(self, i):
if i < 0 or i >= self.nbits:
raise IndexError(i)
q = i // WORD_BITS
r = i - q * WORD_BITS
self._words[q] &= WORD_MASK ^ (1 << r)
return self
def flip(self, i):
if i < 0 or i >= self.nbits:
raise IndexError(i)
q = i // WORD_BITS
r = i - q * WORD_BITS
self._words[q] ^= 1 << r
if self._words[q]:
if q < self._lo:
self._lo = q
if q > self._hi:
self._hi = q
return self
def test(self, i):
if i < 0 or i >= self.nbits:
raise IndexError(i)
q = i // WORD_BITS
r = i - q * WORD_BITS
return ((self._words[q] >> r) & 1) != 0
def __getitem__(self, i):
return self.test(i)
def __setitem__(self, i, value):
if i < 0 or i >= self.nbits:
raise IndexError(i)
q = i // WORD_BITS
r = i - q * WORD_BITS
bit = 1 << r
if value:
self._words[q] |= bit
if q < self._lo:
self._lo = q
if q > self._hi:
self._hi = q
else:
self._words[q] &= WORD_MASK ^ bit
def count(self):
if self._hi < self._lo:
return 0
words = self._words
lo = self._lo
hi = self._hi
last = self.nwords - 1
res = 0
i = lo
while i <= hi:
x = words[i]
if i == last:
x &= self._last_mask
res += x.bit_count()
i += 1
return res
def any(self):
if self._hi < self._lo:
return False
words = self._words
i = self._lo
hi = self._hi
last = self.nwords - 1
while i <= hi:
x = words[i]
if i == last:
x &= self._last_mask
if x:
if i > self._lo:
self._lo = i
return True
i += 1
self._lo = self.nwords
self._hi = -1
return False
def none(self):
return not self.any()
def all(self):
last = self.nwords - 1
if self._lo > 0 or self._hi < last:
return False
words = self._words
i = 0
while i < last:
if words[i] != WORD_MASK:
return False
i += 1
return (words[last] & self._last_mask) == self._last_mask
def find_first(self):
if self._hi < self._lo:
return -1
words = self._words
i = self._lo
hi = self._hi
last = self.nwords - 1
while i <= hi:
x = words[i]
if i == last:
x &= self._last_mask
if x:
self._lo = i
return i * WORD_BITS + (x & -x).bit_length() - 1
i += 1
self._lo = self.nwords
self._hi = -1
return -1
def find_next(self, i):
p = i + 1
if p < 0:
p = 0
if p >= self.nbits or self._hi < self._lo:
return -1
q = p // WORD_BITS
r = p - q * WORD_BITS
if q < self._lo:
q = self._lo
r = 0
hi = self._hi
if q > hi:
return -1
words = self._words
last = self.nwords - 1
x = words[q]
if q == last:
x &= self._last_mask
x >>= r
if x:
return q * WORD_BITS + r + (x & -x).bit_length() - 1
q += 1
while q <= hi:
x = words[q]
if q == last:
x &= self._last_mask
if x:
return q * WORD_BITS + (x & -x).bit_length() - 1
q += 1
return -1
def find_last(self):
if self._hi < self._lo:
return -1
words = self._words
i = self._hi
lo = self._lo
last = self.nwords - 1
while i >= lo:
x = words[i]
if i == last:
x &= self._last_mask
if x:
self._hi = i
return i * WORD_BITS + x.bit_length() - 1
i -= 1
self._lo = self.nwords
self._hi = -1
return -1
def __iter__(self):
if self._hi < self._lo:
return
words = self._words
wi = self._lo
hi = self._hi
last = self.nwords - 1
while wi <= hi:
x = words[wi]
if wi == last:
x &= self._last_mask
base = wi * WORD_BITS
while x:
lsb = x & -x
yield base + lsb.bit_length() - 1
x ^= lsb
wi += 1
def ior_lshift(self, shift):
"""self |= self << shift"""
if shift < 0:
raise ValueError("negative shift count")
if shift == 0 or shift >= self.nbits or self._hi < self._lo:
return self
words = self._words
lo = self._lo
hi = self._hi
q = shift // WORD_BITS
r = shift - q * WORD_BITS
src = (self.nbits - 1 - shift) // WORD_BITS
if src > hi:
src = hi
if src < lo:
return self
if r == 0:
s = src
while s >= lo:
words[s + q] |= words[s]
s -= 1
dh = src + q
else:
low_keep = _LOW_KEEP[r]
rr = WORD_BITS - r
s = src
while s >= lo:
x = words[s]
dst = s + q
words[dst] |= (x & low_keep) << r
words[dst + 1] |= x >> rr
s -= 1
dh = src + q + 1
if dh >= self.nwords:
dh = self.nwords - 1
if dh > self._hi:
self._hi = dh
return self
or_shift_left = ior_lshift
def ior_rshift(self, shift):
"""self |= self >> shift"""
if shift < 0:
raise ValueError("negative shift count")
if shift == 0 or shift >= self.nbits or self._hi < self._lo:
return self
self._clean_for_right_shift()
words = self._words
lo = self._lo
hi = self._hi
q = shift // WORD_BITS
r = shift - q * WORD_BITS
dhi = hi - q
if dhi < 0:
return self
dlo = lo - q - (1 if r else 0)
if dlo < 0:
dlo = 0
limit = self.nwords - q - 1
if dhi > limit:
dhi = limit
if dlo > dhi:
return self
if r == 0:
dst = dlo
while dst <= dhi:
words[dst] |= words[dst + q]
dst += 1
else:
low_bits = _LOW_BITS[r]
rr = WORD_BITS - r
last = self.nwords - 1
dst = dlo
while dst <= dhi:
src = dst + q
x = words[src] >> r
if src < last:
x |= (words[src + 1] & low_bits) << rr
words[dst] |= x
dst += 1
if dlo < self._lo:
self._lo = dlo
return self
or_shift_right = ior_rshift
def ixor_lshift(self, shift):
"""self ^= self << shift"""
if shift < 0:
raise ValueError("negative shift count")
if shift == 0:
return self.clear()
if shift >= self.nbits or self._hi < self._lo:
return self
words = self._words
lo = self._lo
hi = self._hi
q = shift // WORD_BITS
r = shift - q * WORD_BITS
src = (self.nbits - 1 - shift) // WORD_BITS
if src > hi:
src = hi
if src < lo:
return self
if r == 0:
s = src
while s >= lo:
words[s + q] ^= words[s]
s -= 1
dl = lo + q
dh = src + q
else:
low_keep = _LOW_KEEP[r]
rr = WORD_BITS - r
s = src
while s >= lo:
x = words[s]
dst = s + q
words[dst] ^= (x & low_keep) << r
words[dst + 1] ^= x >> rr
s -= 1
dl = lo + q
dh = src + q + 1
if dh >= self.nwords:
dh = self.nwords - 1
if dl < self._lo:
self._lo = dl
if dh > self._hi:
self._hi = dh
return self
xor_shift_left = ixor_lshift
def ixor_rshift(self, shift):
"""self ^= self >> shift"""
if shift < 0:
raise ValueError("negative shift count")
if shift == 0:
return self.clear()
if shift >= self.nbits or self._hi < self._lo:
return self
self._clean_for_right_shift()
words = self._words
lo = self._lo
hi = self._hi
q = shift // WORD_BITS
r = shift - q * WORD_BITS
dhi = hi - q
if dhi < 0:
return self
dlo = lo - q - (1 if r else 0)
if dlo < 0:
dlo = 0
limit = self.nwords - q - 1
if dhi > limit:
dhi = limit
if dlo > dhi:
return self
if r == 0:
dst = dlo
while dst <= dhi:
words[dst] ^= words[dst + q]
dst += 1
else:
low_bits = _LOW_BITS[r]
rr = WORD_BITS - r
last = self.nwords - 1
dst = dlo
while dst <= dhi:
src = dst + q
x = words[src] >> r
if src < last:
x |= (words[src + 1] & low_bits) << rr
words[dst] ^= x
dst += 1
if dlo < self._lo:
self._lo = dlo
return self
xor_shift_right = ixor_rshift
def iand_lshift(self, shift):
"""self &= self << shift"""
if shift < 0:
raise ValueError("negative shift count")
if shift == 0:
return self
if shift >= self.nbits or self._hi < self._lo:
return self.clear()
words = self._words
lo = self._lo
hi = self._hi
q = shift // WORD_BITS
r = shift - q * WORD_BITS
dlo = lo + q
if dlo > hi:
return self.clear()
dst = hi
if r == 0:
while dst >= dlo:
words[dst] &= words[dst - q]
dst -= 1
else:
low_keep = _LOW_KEEP[r]
rr = WORD_BITS - r
while dst >= dlo:
src = dst - q
x = (words[src] & low_keep) << r
if src > 0:
x |= words[src - 1] >> rr
words[dst] &= x
dst -= 1
dst = lo
while dst < dlo:
words[dst] = 0
dst += 1
self._lo = dlo
self._hi = hi
self._trim()
return self
and_shift_left = iand_lshift
def iand_rshift(self, shift):
"""self &= self >> shift"""
if shift < 0:
raise ValueError("negative shift count")
if shift == 0:
return self
if shift >= self.nbits or self._hi < self._lo:
return self.clear()
self._clean_for_right_shift()
words = self._words
lo = self._lo
hi = self._hi
q = shift // WORD_BITS
r = shift - q * WORD_BITS
dhi = hi - q
if dhi < lo:
return self.clear()
dst = lo
if r == 0:
while dst <= dhi:
words[dst] &= words[dst + q]
dst += 1
else:
low_bits = _LOW_BITS[r]
rr = WORD_BITS - r
last = self.nwords - 1
while dst <= dhi:
src = dst + q
x = words[src] >> r
if src < last:
x |= (words[src + 1] & low_bits) << rr
words[dst] &= x
dst += 1
dst = dhi + 1
while dst <= hi:
words[dst] = 0
dst += 1
self._lo = lo
self._hi = dhi
self._trim()
return self
and_shift_right = iand_rshift
def __ilshift__(self, shift):
if shift < 0:
raise ValueError("negative shift count")
if shift == 0:
return self
if shift >= self.nbits or self._hi < self._lo:
return self.clear()
words = self._words
lo = self._lo
hi = self._hi
q = shift // WORD_BITS
r = shift - q * WORD_BITS
dlo = lo + q
if dlo >= self.nwords:
return self.clear()
dhi = hi + q + (1 if r else 0)
if dhi >= self.nwords:
dhi = self.nwords - 1
dst = dhi
if r == 0:
while dst >= dlo:
src = dst - q
words[dst] = words[src] if src <= hi else 0
dst -= 1
else:
low_keep = _LOW_KEEP[r]
rr = WORD_BITS - r
while dst >= dlo:
src = dst - q
x = 0
if src <= hi:
x = (words[src] & low_keep) << r
if src > lo:
x |= words[src - 1] >> rr
words[dst] = x
dst -= 1
dst = lo
while dst < dlo:
words[dst] = 0
dst += 1
words[self.nwords] = 0
self._lo = dlo
self._hi = dhi
self._trim()
return self
def __irshift__(self, shift):
if shift < 0:
raise ValueError("negative shift count")
if shift == 0:
return self
if shift >= self.nbits or self._hi < self._lo:
return self.clear()
self._clean_for_right_shift()
words = self._words
lo = self._lo
hi = self._hi
q = shift // WORD_BITS
r = shift - q * WORD_BITS
dhi = hi - q
if dhi < 0:
return self.clear()
dlo = lo - q - (1 if r else 0)
if dlo < 0:
dlo = 0
dst = dlo
if r == 0:
while dst <= dhi:
src = dst + q
words[dst] = words[src] if src >= lo else 0
dst += 1
else:
low_bits = _LOW_BITS[r]
rr = WORD_BITS - r
while dst <= dhi:
src = dst + q
x = 0
if src >= lo:
x = words[src] >> r
if src < hi:
x |= (words[src + 1] & low_bits) << rr
words[dst] = x
dst += 1
dst = dhi + 1
while dst <= hi:
words[dst] = 0
dst += 1
words[self.nwords] = 0
self._lo = dlo
self._hi = dhi
self._trim()
return self
def __lshift__(self, shift):
res = self.copy()
res <<= shift
return res
def __rshift__(self, shift):
res = self.copy()
res >>= shift
return res
def __ior__(self, other):
self._check_compatible(other)
if other._hi < other._lo:
return self
a = self._words
b = other._words
lo = other._lo
hi = other._hi
i = lo
while i <= hi:
a[i] |= b[i]
i += 1
if lo < self._lo:
self._lo = lo
if hi > self._hi:
self._hi = hi
return self
def __iand__(self, other):
self._check_compatible(other)
if self is other:
return self
if self._hi < self._lo or other._hi < other._lo:
return self.clear()
old_lo = self._lo
old_hi = self._hi
lo = max(old_lo, other._lo)
hi = min(old_hi, other._hi)
if lo > hi:
return self.clear()
a = self._words
b = other._words
i = old_lo
while i < lo:
a[i] = 0
i += 1
i = lo
while i <= hi:
a[i] &= b[i]
i += 1
i = hi + 1
while i <= old_hi:
a[i] = 0
i += 1
self._lo = lo
self._hi = hi
self._trim()
return self
def __ixor__(self, other):
self._check_compatible(other)
if self is other:
return self.clear()
if other._hi < other._lo:
return self
old_lo = self._lo
old_hi = self._hi
lo = other._lo
hi = other._hi
overlap = not (old_hi < lo or hi < old_lo)
a = self._words
b = other._words
i = lo
while i <= hi:
a[i] ^= b[i]
i += 1
if lo < self._lo:
self._lo = lo
if hi > self._hi:
self._hi = hi
if overlap:
self._trim()
return self
def __or__(self, other):
if not isinstance(other, BitSet):
return NotImplemented
res = self.copy()
res |= other
return res
def __and__(self, other):
if not isinstance(other, BitSet):
return NotImplemented
res = self.copy()
res &= other
return res
def __xor__(self, other):
if not isinstance(other, BitSet):
return NotImplemented
res = self.copy()
res ^= other
return res
def __invert__(self):
res = self.copy()
res.flip_all()
return res
def intersects(self, other):
self._check_compatible(other)
lo = max(self._lo, other._lo)
hi = min(self._hi, other._hi)
if lo > hi:
return False
a = self._words
b = other._words
last = self.nwords - 1
i = lo
while i <= hi:
x = a[i] & b[i]
if i == last:
x &= self._last_mask
if x:
return True
i += 1
return False
def is_subset_of(self, other):
self._check_compatible(other)
if self._hi < self._lo:
return True
a = self._words
b = other._words
i = self._lo
hi = self._hi
last = self.nwords - 1
while i <= hi:
x = a[i]
y = b[i] if other._lo <= i <= other._hi else 0
if i == last:
x &= self._last_mask
y &= self._last_mask
if x & (WORD_MASK ^ y):
return False
i += 1
return True
def to_int(self):
words = self._words
i = self._hi
if i < self._lo:
return 0
value = words[i]
if i == self.nwords - 1:
value &= self._last_mask
i -= 1
while i >= 0:
value = (value << WORD_BITS) | words[i]
i -= 1
return value
def __len__(self):
return self.nbits
def __bool__(self):
return self.any()
def __eq__(self, other):
if not isinstance(other, BitSet) or self.nbits != other.nbits:
return False
lo = min(self._lo, other._lo)
hi = max(self._hi, other._hi)
if hi < lo:
return True
a = self._words
b = other._words
last = self.nwords - 1
i = lo
while i <= hi:
x = a[i]
y = b[i]
if i == last:
mask = self._last_mask
x &= mask
y &= mask
if x != y:
return False
i += 1
return True
import sys
def solve():
N, S = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
C = BitSet(S + 1)
C.set(0)
for i in A:
C|=C<<i
print(C.find_last())
def main():
T = int(sys.stdin.readline())
for _ in range(T):
solve()
if __name__ == "__main__":
main()