結果
| 問題 | No.3670 Fast Knapsack |
| コンテスト | |
| ユーザー |
 harurun
|
| 提出日時 | 2026-09-01 23:24:44 |
| 言語 | PyPy3 (7.3.23) |
| 結果 |
AC
|
| 実行時間 | 1,793 ms / 2,500 ms |
| + 288µs | |
| コード長 | 17,480 bytes |
| 記録 | |
| コンパイル時間 | 264 ms |
| コンパイル使用メモリ | 96,080 KB |
| 実行使用メモリ | 101,056 KB |
| 最終ジャッジ日時 | 2026-09-04 23:06:48 |
| 合計ジャッジ時間 | 28,651 ms |
|
ジャッジサーバーID （参考情報） |
judge5_0 / judge4_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 25 |
ソースコード
WORD_BITS = 63
WORD_MASK = (1 << WORD_BITS) - 1
_LOW_KEEP = [0] * WORD_BITS
_LOW_BITS = [0] * WORD_BITS
_r = 1
while _r < WORD_BITS:
_LOW_KEEP[_r] = (1 << (WORD_BITS - _r)) - 1
_LOW_BITS[_r] = (1 << _r) - 1
_r += 1
class BitSet:
__slots__ = ("nbits", "nwords", "_last_mask", "_words")
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
# +1 は左シフト時の carry 用 sentinel
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
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 copy(self):
obj = object.__new__(BitSet)
obj.nbits = self.nbits
obj.nwords = self.nwords
obj._last_mask = self._last_mask
obj._words = self._words[:]
return obj
def clear(self):
words = self._words
i = self.nwords
while i >= 0:
words[i] = 0
i -= 1
return self
def set_all(self):
words = self._words
nwords = self.nwords
i = 0
while i < nwords - 1:
words[i] = WORD_MASK
i += 1
words[nwords - 1] = self._last_mask
words[nwords] = 0
return self
def flip_all(self):
words = self._words
nwords = self.nwords
i = 0
while i < nwords - 1:
words[i] = WORD_MASK ^ words[i]
i += 1
last = nwords - 1
mask = self._last_mask
words[last] = mask ^ (words[last] & mask)
words[nwords] = 0
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
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
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
else:
self._words[q] &= WORD_MASK ^ bit
def count(self):
words = self._words
last = self.nwords - 1
res = 0
i = 0
while i < last:
res += words[i].bit_count()
i += 1
return res + (words[last] & self._last_mask).bit_count()
def any(self):
words = self._words
last = self.nwords - 1
i = 0
while i < last:
if words[i]:
return True
i += 1
return (words[last] & self._last_mask) != 0
def none(self):
return not self.any()
def all(self):
words = self._words
last = self.nwords - 1
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):
words = self._words
last = self.nwords - 1
i = 0
while i < last:
x = words[i]
if x:
return i * WORD_BITS + (x & -x).bit_length() - 1
i += 1
x = words[last] & self._last_mask
if x:
return last * WORD_BITS + (x & -x).bit_length() - 1
return -1
def find_next(self, i):
p = i + 1
if p < 0:
p = 0
if p >= self.nbits:
return -1
q = p // WORD_BITS
r = p - q * WORD_BITS
words = self._words
last = self.nwords - 1
x = words[q] >> r
if q == last:
x &= (1 << (self.nbits - p)) - 1
if x:
return p + (x & -x).bit_length() - 1
q += 1
while q < last:
x = words[q]
if x:
return q * WORD_BITS + (x & -x).bit_length() - 1
q += 1
if q == last:
x = words[q] & self._last_mask
if x:
return q * WORD_BITS + (x & -x).bit_length() - 1
return -1
def find_last(self):
words = self._words
i = self.nwords - 1
x = words[i] & self._last_mask
if x:
return i * WORD_BITS + x.bit_length() - 1
i -= 1
while i >= 0:
x = words[i]
if x:
return i * WORD_BITS + x.bit_length() - 1
i -= 1
return -1
def __iter__(self):
words = self._words
last = self.nwords - 1
wi = 0
while wi <= last:
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
# self |= self << shift
def ior_lshift(self, shift):
if shift < 0:
raise ValueError("negative shift count")
if shift == 0 or shift >= self.nbits:
return self
words = self._words
q = shift // WORD_BITS
r = shift - q * WORD_BITS
src = (self.nbits - 1 - shift) // WORD_BITS
if r == 0:
while src >= 0:
words[src + q] |= words[src]
src -= 1
else:
low_keep = _LOW_KEEP[r]
rr = WORD_BITS - r
while src >= 0:
x = words[src]
dst = src + q
words[dst] |= (x & low_keep) << r
words[dst + 1] |= x >> rr
src -= 1
return self
or_shift_left = ior_lshift
# self |= self >> shift
def ior_rshift(self, shift):
if shift < 0:
raise ValueError("negative shift count")
if shift == 0 or shift >= self.nbits:
return self
self._clean_for_right_shift()
words = self._words
nwords = self.nwords
q = shift // WORD_BITS
r = shift - q * WORD_BITS
dst = 0
limit = nwords - q
if r == 0:
while dst < limit:
words[dst] |= words[dst + q]
dst += 1
else:
low_bits = _LOW_BITS[r]
rr = WORD_BITS - r
last = nwords - 1
while dst < limit:
src = dst + q
x = words[src] >> r
if src < last:
x |= (words[src + 1] & low_bits) << rr
words[dst] |= x
dst += 1
return self
or_shift_right = ior_rshift
# self ^= self << shift
def ixor_lshift(self, shift):
if shift < 0:
raise ValueError("negative shift count")
if shift == 0:
return self.clear()
if shift >= self.nbits:
return self
words = self._words
q = shift // WORD_BITS
r = shift - q * WORD_BITS
src = (self.nbits - 1 - shift) // WORD_BITS
if r == 0:
while src >= 0:
words[src + q] ^= words[src]
src -= 1
else:
low_keep = _LOW_KEEP[r]
rr = WORD_BITS - r
while src >= 0:
x = words[src]
dst = src + q
words[dst] ^= (x & low_keep) << r
words[dst + 1] ^= x >> rr
src -= 1
return self
xor_shift_left = ixor_lshift
# self ^= self >> shift
def ixor_rshift(self, shift):
if shift < 0:
raise ValueError("negative shift count")
if shift == 0:
return self.clear()
if shift >= self.nbits:
return self
self._clean_for_right_shift()
words = self._words
nwords = self.nwords
q = shift // WORD_BITS
r = shift - q * WORD_BITS
dst = 0
limit = nwords - q
if r == 0:
while dst < limit:
words[dst] ^= words[dst + q]
dst += 1
else:
low_bits = _LOW_BITS[r]
rr = WORD_BITS - r
last = nwords - 1
while dst < limit:
src = dst + q
x = words[src] >> r
if src < last:
x |= (words[src + 1] & low_bits) << rr
words[dst] ^= x
dst += 1
return self
xor_shift_right = ixor_rshift
# self &= self << shift
def iand_lshift(self, shift):
if shift < 0:
raise ValueError("negative shift count")
if shift == 0:
return self
if shift >= self.nbits:
return self.clear()
words = self._words
nwords = self.nwords
q = shift // WORD_BITS
r = shift - q * WORD_BITS
dst = nwords - 1
if r == 0:
while dst >= q:
words[dst] &= words[dst - q]
dst -= 1
else:
low_keep = _LOW_KEEP[r]
rr = WORD_BITS - r
while dst >= q:
src = dst - q
x = (words[src] & low_keep) << r
if src:
x |= words[src - 1] >> rr
words[dst] &= x
dst -= 1
while dst >= 0:
words[dst] = 0
dst -= 1
words[nwords] = 0
return self
and_shift_left = iand_lshift
# self &= self >> shift
def iand_rshift(self, shift):
if shift < 0:
raise ValueError("negative shift count")
if shift == 0:
return self
if shift >= self.nbits:
return self.clear()
self._clean_for_right_shift()
words = self._words
nwords = self.nwords
q = shift // WORD_BITS
r = shift - q * WORD_BITS
dst = 0
limit = nwords - q
if r == 0:
while dst < limit:
words[dst] &= words[dst + q]
dst += 1
else:
low_bits = _LOW_BITS[r]
rr = WORD_BITS - r
last = nwords - 1
while dst < limit:
src = dst + q
x = words[src] >> r
if src < last:
x |= (words[src + 1] & low_bits) << rr
words[dst] &= x
dst += 1
while dst < nwords:
words[dst] = 0
dst += 1
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:
return self.clear()
words = self._words
nwords = self.nwords
q = shift // WORD_BITS
r = shift - q * WORD_BITS
dst = nwords - 1
if r == 0:
while dst >= q:
words[dst] = words[dst - q]
dst -= 1
else:
low_keep = _LOW_KEEP[r]
rr = WORD_BITS - r
while dst >= q:
src = dst - q
x = (words[src] & low_keep) << r
if src:
x |= words[src - 1] >> rr
words[dst] = x
dst -= 1
while dst >= 0:
words[dst] = 0
dst -= 1
return self
def __irshift__(self, shift):
if shift < 0:
raise ValueError("negative shift count")
if shift == 0:
return self
if shift >= self.nbits:
return self.clear()
self._clean_for_right_shift()
words = self._words
nwords = self.nwords
q = shift // WORD_BITS
r = shift - q * WORD_BITS
dst = 0
limit = nwords - q
if r == 0:
while dst < limit:
words[dst] = words[dst + q]
dst += 1
else:
low_bits = _LOW_BITS[r]
rr = WORD_BITS - r
last = nwords - 1
while dst < limit:
src = dst + q
x = words[src] >> r
if src < last:
x |= (words[src + 1] & low_bits) << rr
words[dst] = x
dst += 1
while dst < nwords:
words[dst] = 0
dst += 1
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)
a = self._words
b = other._words
n = self.nwords
i = 0
while i < n:
a[i] |= b[i]
i += 1
return self
def __iand__(self, other):
self._check_compatible(other)
a = self._words
b = other._words
n = self.nwords
i = 0
while i < n:
a[i] &= b[i]
i += 1
return self
def __ixor__(self, other):
self._check_compatible(other)
a = self._words
b = other._words
n = self.nwords
i = 0
while i < n:
a[i] ^= b[i]
i += 1
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()
words = res._words
last = res.nwords - 1
i = 0
while i < last:
words[i] = WORD_MASK ^ words[i]
i += 1
mask = res._last_mask
words[last] = mask ^ (words[last] & mask)
words[res.nwords] = 0
return res
def intersects(self, other):
self._check_compatible(other)
a = self._words
b = other._words
last = self.nwords - 1
i = 0
while i < last:
if a[i] & b[i]:
return True
i += 1
return ((a[last] & b[last]) & self._last_mask) != 0
def is_subset_of(self, other):
self._check_compatible(other)
a = self._words
b = other._words
last = self.nwords - 1
i = 0
while i < last:
if a[i] & (WORD_MASK ^ b[i]):
return False
i += 1
mask = self._last_mask
aa = a[last] & mask
bb = b[last] & mask
return (aa & (mask ^ bb)) == 0
def to_int(self):
words = self._words
i = self.nwords - 1
value = words[i] & 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):
return False
if self.nbits != other.nbits:
return False
a = self._words
b = other._words
last = self.nwords - 1
i = 0
while i < last:
if a[i] != b[i]:
return False
i += 1
mask = self._last_mask
return (a[last] & mask) == (b[last] & mask)
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()