結果

問題 No.1861 Required Number
ユーザー 👑 rin204rin204
提出日時 2023-07-05 23:38:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 199 ms / 2,500 ms
コード長 8,011 bytes
コンパイル時間 242 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 338,988 KB
最終ジャッジ日時 2024-07-19 18:07:58
合計ジャッジ時間 21,377 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
61,184 KB
testcase_01 AC 45 ms
239,092 KB
testcase_02 AC 44 ms
60,544 KB
testcase_03 AC 165 ms
338,988 KB
testcase_04 AC 178 ms
85,256 KB
testcase_05 AC 46 ms
323,444 KB
testcase_06 AC 44 ms
60,928 KB
testcase_07 AC 48 ms
55,680 KB
testcase_08 AC 66 ms
66,048 KB
testcase_09 AC 45 ms
55,424 KB
testcase_10 AC 48 ms
56,576 KB
testcase_11 AC 46 ms
56,320 KB
testcase_12 AC 44 ms
55,680 KB
testcase_13 AC 53 ms
63,360 KB
testcase_14 AC 46 ms
55,936 KB
testcase_15 AC 50 ms
56,704 KB
testcase_16 AC 45 ms
55,680 KB
testcase_17 AC 47 ms
56,064 KB
testcase_18 AC 51 ms
56,832 KB
testcase_19 AC 68 ms
68,736 KB
testcase_20 AC 59 ms
64,768 KB
testcase_21 AC 48 ms
56,832 KB
testcase_22 AC 58 ms
65,152 KB
testcase_23 AC 46 ms
56,192 KB
testcase_24 AC 169 ms
78,916 KB
testcase_25 AC 193 ms
78,676 KB
testcase_26 AC 166 ms
78,676 KB
testcase_27 AC 168 ms
78,720 KB
testcase_28 AC 173 ms
78,592 KB
testcase_29 AC 175 ms
78,776 KB
testcase_30 AC 125 ms
78,208 KB
testcase_31 AC 181 ms
79,380 KB
testcase_32 AC 163 ms
78,208 KB
testcase_33 AC 175 ms
78,592 KB
testcase_34 AC 181 ms
78,976 KB
testcase_35 AC 180 ms
79,196 KB
testcase_36 AC 171 ms
78,592 KB
testcase_37 AC 170 ms
78,824 KB
testcase_38 AC 182 ms
79,256 KB
testcase_39 AC 180 ms
78,336 KB
testcase_40 AC 178 ms
78,736 KB
testcase_41 AC 183 ms
79,048 KB
testcase_42 AC 199 ms
79,804 KB
testcase_43 AC 194 ms
78,732 KB
testcase_44 AC 49 ms
55,424 KB
04_evil_1.txt TLE -
04_evil_2.txt TLE -
04_evil_3.txt TLE -
04_evil_4.txt TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def popcount32(x):
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0F0F0F0F
    x += x >> 8
    x += x >> 16
    return x & 0x0000003F


def popcount64(x):
    x = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x & 0x0F0F0F0F0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F0F0F0F0F)
    x = (x & 0x00FF00FF00FF00FF) + ((x >> 8) & 0x00FF00FF00FF00FF)
    x = (x & 0x0000FFFF0000FFFF) + ((x >> 16) & 0x0000FFFF0000FFFF)
    x = (x & 0x00000000FFFFFFFF) + ((x >> 32) & 0x00000000FFFFFFFF)
    return x


class Bitset:
    def __init__(self, n: int) -> None:
        self.n = n
        self.m = (n + 62) // 63
        self.A = [0] * self.m

    def __len__(self) -> int:
        return self.n

    @property
    def size(self) -> int:
        return self.n

    def __str__(self) -> str:
        S = []
        for a in self.A:
            S.append(bin(a)[2:].zfill(63)[::-1])
        S = "".join(S)
        return S[: self.n][::-1]

    def __getitem__(self, ind: int) -> int:
        i = ind // 63
        j = ind - i * 63
        return self.A[i] >> j & 1

    def __setitem__(self, ind: int, k: int) -> None:
        i = ind // 63
        j = ind - i * 63
        if (self.A[i] >> j & 1) != k:
            self.A[i] ^= 1 << j
        else:
            pass

    def rev(self, ind: int) -> None:
        i = ind // 63
        j = ind - i * 63
        self.A[i] ^= 1 << j

    def count(self) -> int:
        ret = 0
        for a in self.A:
            ret += popcount64(a)
        return ret

    def __sum__(self) -> int:
        return self.count()

    def resize(self, n: int) -> None:
        m = (n + 62) // 63
        if m > self.m:
            self.A += [0] * (m - self.m)
        else:
            self.A = self.A[:m]
            j = n % 63
            if j != 0:
                self.A[-1] &= (1 << j) - 1
            else:
                pass
        self.n = n
        self.m = m

    def __and__(self, other: "Bitset") -> "Bitset":
        if self.n < other.n:
            n = self.n
        else:
            n = other.n

        ret = Bitset(n)
        for i, (a, b) in enumerate(zip(self.A, other.A)):
            ret.A[i] = a & b

        return ret

    def __iand__(self, other: "Bitset") -> "Bitset":
        if self.m < other.m:
            m = self.m
        else:
            m = other.m
        for i in range(m):
            self.A[i] &= other.A[i]
        for i in range(m, self.m):
            self.A[i] = 0
        return self

    def __or__(self, other: "Bitset") -> "Bitset":
        if self.n > other.n:
            n = self.n
        else:
            n = other.n

        ret = Bitset(n)
        for i in range(ret.m):
            if i < self.m and i < other.m:
                ret.A[i] = self.A[i] | other.A[i]
            elif i < self.m:
                ret.A[i] = self.A[i]
            else:
                ret.A[i] = other.A[i]

        return ret

    def __ior__(self, other: "Bitset") -> "Bitset":
        if self.m < other.m:
            m = self.m
        else:
            m = other.m
        for i in range(m):
            self.A[i] |= other.A[i]
        if self.n < other.n:
            x = self.n % 63
            if x != 0:
                mask = (1 << x) - 1
                self.A[-1] &= mask
        else:
            pass
        return self

    def __xor__(self, other: "Bitset") -> "Bitset":
        if self.n > other.n:
            n = self.n
        else:
            n = other.n

        ret = Bitset(n)
        for i in range(ret.m):
            if i < self.m and i < other.m:
                ret.A[i] = self.A[i] ^ other.A[i]
            elif i < self.m:
                ret.A[i] = self.A[i]
            else:
                ret.A[i] = other.A[i]

        return ret

    def __ixor__(self, other: "Bitset") -> "Bitset":
        if self.m < other.m:
            m = self.m
        else:
            m = other.m
        for i in range(m):
            self.A[i] ^= other.A[i]
        if self.n < other.n:
            x = self.n % 63
            if x != 0:
                mask = (1 << x) - 1
                self.A[-1] &= mask
        else:
            pass
        return self

    def and_count(self, other: "Bitset") -> int:
        ret = 0
        for a, b in zip(self.A, other.A):
            ret += popcount64(a & b)
        return ret

    def or_count(self, other: "Bitset") -> int:
        ret = 0
        if self.m < other.m:
            m = self.m
        else:
            m = other.m
        for a, b in zip(self.A[:m], other.A[:m]):
            ret += popcount64(a | b)

        for a in self.A[m:]:
            ret += popcount64(a)

        for a in other.A[m:]:
            ret += popcount64(a)

        return ret

    def xor_count(self, other: "Bitset") -> int:
        ret = 0
        if self.m < other.m:
            m = self.m
        else:
            m = other.m
        for a, b in zip(self.A[:m], other.A[:m]):
            ret += popcount64(a ^ b)

        for a in self.A[m:]:
            ret += popcount64(a)

        for a in other.A[m:]:
            ret += popcount64(a)

        return ret

    def __rshift__(self, k: int) -> "Bitset":
        ret = Bitset(self.n)
        x = k // 63
        for i in range(x, self.m):
            ret.A[i - x] = self.A[i]
        k -= x * 63
        if k != 0:
            mask = (1 << k) - 1
            rk = 63 - k
            for i, a in enumerate(ret.A):
                if i != 0:
                    ret.A[i - 1] |= (a & mask) << (rk)
                ret.A[i] = a >> k
        else:
            pass
        return ret

    def __irshift__(self, k: int) -> "Bitset":
        x = k // 63
        for i in range(x, self.m):
            self.A[i - x] = self.A[i]
        for i in range(self.m - x, self.m):
            self.A[i] = 0
        k -= x * 63
        if k != 0:
            mask = (1 << k) - 1
            rk = 63 - k
            for i, a in enumerate(self.A):
                if i != 0:
                    self.A[i - 1] |= (a & mask) << (rk)
                self.A[i] = a >> k
        else:
            pass
        return self

    def __lshift__(self, k: int) -> "Bitset":
        ret = Bitset(self.n)
        x = k // 63
        for i in range(x, self.m):
            ret.A[i] = self.A[i - x]
        k -= x * 63
        if k != 0:
            rk = 63 - k
            mask = (1 << rk) - 1
            for i in range(self.m - 1, -1, -1):
                ret.A[i] &= mask
                ret.A[i] <<= k
                if i != 0:
                    ret.A[i] |= ret.A[i - 1] >> rk
        else:
            pass
        return ret

    def __ilshift__(self, k: int) -> "Bitset":
        x = k // 63
        for i in range(self.m - 1, x - 1, -1):
            self.A[i] = self.A[i - x]
        for i in range(x - 1, -1, -1):
            self.A[i] = 0
        k -= x * 63
        if k != 0:
            rk = 63 - k
            mask = (1 << rk) - 1
            for i in range(self.m - 1, -1, -1):
                self.A[i] &= mask
                self.A[i] <<= k
                if i != 0:
                    self.A[i] |= self.A[i - 1] >> rk
        else:
            pass
        return self


from copy import deepcopy

n, k = map(int, input().split())
A = list(map(int, input().split()))
B = int(n**0.5)
bs = Bitset(k + 1)
bs[0] = 1
dp = [deepcopy(bs)]
for i, a in enumerate(A, 1):
    bs |= bs << a
    if i % B == 0:
        dp.append(deepcopy(bs))

if not bs[k]:
    print(-1)
    exit()

bit = Bitset(k + 1)
bit[k] = 1
ans = 0

p = (n - 1) // B
dp2 = [dp[p]]
for i in range(B * p, n - 1):
    dp2.append(dp2[-1] | (dp2[-1] << A[i]))

for i in range(n - 1, -1, -1):
    if bit.and_count(dp2[i % B]) == 0:
        ans += 1
    if i % B == 0:
        p = (i - 1) // B
        dp2 = [dp[p]]
        for j in range(B * p, B * (p + 1) - 1):
            dp2.append(dp2[-1] | (dp2[-1] << A[j]))
    bit |= bit >> A[i]

print(ans)
0