Problem:


Score : 600 points

Problem Statement

AtCoDeer the deer has N cards with positive integers written on them. The number on the i-th card (1≤i≤N) is a_i.
Because he loves big numbers, he calls a subset of the cards good when the sum of the numbers written on the cards in the subset, is K or greater.

Then, for each card i, he judges whether it is unnecessary or not, as follows:

If, for any good subset of the cards containing card i, the set that can be obtained by eliminating card i from the subset is also good, card i is unnecessary.

Otherwise, card i is NOT unnecessary.

Find the number of the unnecessary cards. Here, he judges each card independently, and he does not throw away cards that turn out to be unnecessary.

Constraints

All input values are integers.

1≤N≤5000

1≤K≤5000

1≤a_i≤10^9 (1≤i≤N)

Partial Score

300 points will be awarded for passing the test set satisfying N,K≤400.

Input

The input is given from Standard Input in the following format:

N K
a_1 a_2 ... a_N

Output

Print the number of the unnecessary cards.

Sample Input 1

3 6
1 4 3

Sample Output 1

1

There are two good sets: {2,3} and {1,2,3}.

Card 1 is only contained in {1,2,3}, and this set without card 1, {2,3}, is also good. Thus, card 1 is unnecessary.

For card 2, a good set {2,3} without card 2, {3}, is not good. Thus, card 2 is NOT unnecessary.

Neither is card 3 for a similar reason, hence the answer is 1.

Sample Input 2

5 400
3 1 4 1 5

Sample Output 2

5

In this case, there is no good set. Therefore, all the cards are unnecessary.

Sample Input 3

6 20
10 4 3 10 25 2

Sample Output 3

3



Sample input:
3 6
1 4 3


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split() if int(x) < K]
N = len(A)
dp_init = lambda x:True if x == 0 else False
#Aの左からと右から加えていく場合のdpテーブルを作成
ldp = [[dp_init(i) for i in range(K)] for _ in range(N+1)]
rdp = [[dp_init(i) for i in range(K)] for _ in range(N+1)]
for i in range(N):
    for j in range(K):
        ldp[i+1][j] = (lambda:ldp[i][j] if j < A[i] else ldp[i][j] | ldp[i][j-A[i]])()
        rdp[i+1][j] = (lambda:rdp[i][j] if j < A[N-1-i] else rdp[i][j] | rdp[i][j-A[N-1-i]])()

def Need(n):
    ndp = [any(ldp[n][j] & rdp[N-n-1][i-j] for j in range(i+1)) for i in range(K-A[n],K)]
    return any(ndp)

NoNeed = 0
for i in range(N):
    if not Need(i):
        NoNeed += 1
print(NoNeed)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split() if int(x) < K]

dp = [set() for _ in range(2*K)]
dp[0].add(0)
for a in A:
    for i in reversed(range(a,2*K)):
        if len(dp[i-a]) != 0:
            dp[i].update(dp[i-a])
            dp[i].add(a)
#dpテーブルK以上の集合に対して累積ユニオンを取る
#dp_cumunion[i] == set.union(*dp[K:K+i])
dp_cumunion, temp = [set()], dp[K]
for d in dp[K:]:
    dp_cumunion.append(temp.union(d))
    temp.update(d)

NoNeed = 0
for a in A:
    if a  in dp_cumunion[a]: #aを取り除いたら要素和がK未満になる部分集合が存在する
        continue
    NoNeed += 1
print(NoNeed)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split() if int(x) < K]

dp = [set() for _ in range(2*K)]
dp[0].add(0)
for a in A:
    for i in reversed(range(a,2*K)):
        if len(dp[i-a]) != 0:
            dp[i].update(dp[i-a])
            dp[i].add(a)

NoNeed = 0
for a in A:
    if a  in set().union(*dp[K:K+a]):
        continue
    NoNeed += 1
print(NoNeed)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split() if int(x) < K]
l = len(A)

def DP(x):
    dp = [True] + [False] * (K-1)
    for a in A:
        for i in reversed(range(a,K)):
            if dp[i-a]:
                dp[i] = True
    return dp

NoNeed = 0
for _ in range(l):
    a = A.pop(0)
    if not any(DP(a)[K-a:]):
        NoNeed += 1
    A.append(a)
print(NoNeed)

Submission status: Time Limit Exceeded

Solution code:
import sys

def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,K = MI()
A = [0] + LI()


dp1 = [[0]*K for _ in range(N+1)]  # dp1[i][j] = A1~Aiを用いてjを作れるか
dp1[0][0] = 1
for i in range(1,N+1):
    a = A[i]
    for j in range(K):
        if j >= a:
            dp1[i][j] = dp1[i-1][j] | dp1[i-1][j-a]
        else:
            dp1[i][j] = dp1[i-1][j]

dp2 = [[0]*K for _ in range(N+2)]  # dp2[i][j] = Ai~ANを用いてjが作れるか
dp2[N+1][0] = 1
for i in range(N,0,-1):
    a = A[i]
    for j in range(K):
        if j >= a:
            dp2[i][j] = dp2[i+1][j] | dp2[i+1][j-a]
        else:
            dp2[i][j] = dp2[i+1][j]

from itertools import accumulate

ans = 0
for i in range(1,N+1):
    B = list(accumulate(dp2[i+1]))
    for j in range(0,K):
        if j < K-A[i]:
            if dp1[i-1][j] & (B[K-1-j]-B[K-A[i]-j-1] > 0):
                ans += 1
                break
        else:
            if dp1[i-1][j]:
                ans += 1
                break

print(N-ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,K = MI()
A = LI()
A.sort()


def f(n):  # Anが必要か否か
    B = [0] + [A[i] for i in range(N) if i != n]
    dp = [[0]*K for _ in range(2)]  # dp[i][j] = B1~Biを用いてjを作れるか(メモリ節約のため工夫してる)
    dp[0][0] = 1
    for i in range(1,N):
        b = B[i]
        if i % 2 == 1:
            for j in range(K):
                dp[1][j] = dp[0][j]
                if dp[1][j] == 0 and j >= b:
                    dp[1][j] = dp[0][j-b]
        else:
            for j in range(K):
                dp[0][j] = dp[1][j]
                if dp[0][j] == 0 and j >= b:
                    dp[0][j] = dp[1][j-b]
    if sum(dp[(N-1) % 2 == 1][j] for j in range(max(K-A[n],0),K)) != 0:
        return True
    else:
        return False


left = -1  # 不必要
right = N  # 必要
while left + 1 < right:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Time Limit Exceeded

Solution code:

def main():
    import sys

    def MI():
        return map(int, sys.stdin.readline().rstrip().split())

    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり

    N, K = MI()
    A = LI()
    A.sort()

    def f(n):  # Anが必要か否か
        B = [0] + [A[i] for i in range(N) if i != n]
        dp = [[0] * K for _ in range(2)]  # dp[i][j] = B1~Biを用いてjを作れるか(メモリ節約のため工夫してる)
        dp[0][0] = 1
        for i in range(1, N):
            b = B[i]
            if i % 2 == 1:
                for j in range(K):
                    if j >= b:
                        dp[1][j] = dp[0][j] | dp[0][j - b]
                    else:
                        dp[1][j] = dp[0][j]
            else:
                for j in range(K):
                    if j >= b:
                        dp[0][j] = dp[1][j] | dp[1][j - b]
                    else:
                        dp[0][j] = dp[1][j]
        if sum(dp[(N - 1) % 2][j] for j in range(max(K - A[n], 0), K)) != 0:
            return True
        else:
            return False

    left = -1  # 不必要
    right = N  # 必要
    while left + 1 < right:
        mid = (left + right) // 2
        if f(mid):
            right = mid
        else:
            left = mid

    print(right)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,K = MI()
A = LI()
A.sort()


def f(n):  # Anが必要か否か
    B = [0] + [A[i] for i in range(N) if i != n]
    dp = [[0]*K for _ in range(2)]  # dp[i][j] = B1~Biを用いてjを作れるか(メモリ節約のため工夫してる)
    dp[0][0] = 1
    for i in range(1,N):
        b = B[i]
        if i % 2 == 1:
            for j in range(K):
                if j >= b:
                    dp[1][j] = dp[0][j] | dp[0][j-b]
                else:
                    dp[1][j] = dp[0][j]
        else:
            for j in range(K):
                if j >= b:
                    dp[0][j] = dp[1][j] | dp[1][j-b]
                else:
                    dp[0][j] = dp[1][j]
    if sum(dp[(N-1) % 2 == 1][j] for j in range(max(K-A[n],0),K)) != 0:
        return True
    else:
        return False


left = -1  # 不必要
right = N  # 必要
while left + 1 < right:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Time Limit Exceeded

Solution code:
import sys

def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,K = MI()
A = LI()
A.sort()


def f(n):  # Aiが必要か否か
    B = [0] + [A[i] for i in range(N) if i != n]
    dp = [[0]*K for _ in range(N)]  # dp[i][j] = B1~Biを用いてKを作れるか
    dp[0][0] = 1
    for i in range(1,N):
        b = B[i]
        for j in range(K):
            if j >= b:
                dp[i][j] = dp[i-1][j] | dp[i-1][j-b]
            else:
                dp[i][j] = dp[i-1][j]
    if sum(dp[N-1][j] for j in range(max(K-A[n],0),K)) != 0:
        return True
    else:
        return False


left = -1  # 不必要
right = N  # 必要
while left + 1 < right:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit


@jit
def solution(N, K, A):
    # O(K * N)解法
    #    「a以外の数字の組み合わせで作れる数字」を考えるため、両方向からdpテーブルを作る。
    if N == 1:
        return 0
    # dp1[i][k]: i番目（0-indexed）以前の数字の和でkを作れるか否か
    # dp2[j][k]: j番目（0-indexed）以降の数字の和でkを作れるか否か
    # iについてのfor loopで
    #     dp[j][k] = dp1[j][k] (j < i)
    #              = dp2[j][k] (j >= i)
    # となるように更新していく
    dp = np.zeros((N, K + 1), dtype=np.int)  # 最初はdp2で初期化
    dp[N - 1][0] = 1
    dp[N - 1][min(A[N - 1], K)] = 1
    for j in range(N - 2, -1, -1):
        dp[j] = dp[j + 1]
        dp[j][A[j]:] = np.maximum(dp[j][A[j]:], dp[j + 1][:-A[j]])
    # 「A[i] 以外の数字の組で K-A[i] ～ K-1 は作れない」ものの数を数える
    cnt = 0
    for i in range(N):
        # 次の式を満たす(x, y)が存在しなければA[i]は不必要：
        #     K - A[i] <= x + y <= K - 1
        #         x: ～i-1の要素, y: i+1～の要素
        a = A[i]
        if i == 0:
            if max(dp[1][max(0, K - a):K]) == 0:
                cnt += 1
            # dp1の反映
            dp[0] = np.zeros(K + 1, dtype=np.int)
            dp[0][0] = 1
            dp[0][min(K, a)] = 1
        elif i == N - 1:
            if max(dp[N - 2][max(0, K - a):K]) == 0:
                cnt += 1
        else:
            # dp2の累積和
            dp[i + 1] = dp[i + 1].cumsum()
            unnecessary = True
            for x in range(K + 1):
                if dp[i - 1][x] == 0:
                    continue
                # K - A[i] - x <= y <= K - 1 - x なるyの存在をチェック
                if 0 < K - a - x:
                    # dp[i + 1]はdp2の累積和になってる
                    if dp[i + 1][K - 1 - x] - dp[i + 1][K - a - x - 1] > 0:
                        unnecessary = False
                        break
                elif K - a - x <= 0 <= K - 1 - x:
                    if dp[i + 1][K - 1 - x] > 0:
                        unnecessary = False
                        break
            if unnecessary:
                cnt += 1
            # dp1の反映
            dp[i] = dp[i - 1]
            dp[i][A[i]:] = np.maximum(dp[i][A[i]:], dp[i - 1][:-A[i]])
    return cnt


def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    print(solution(N, K, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def solution(N, K, A):
    # O(K * N)解法
    #     partial_solutionの改良。
    #    「a以外の数字の組み合わせで作れる数字」を考えるため、両方向からdpテーブルを作る。
    if N == 1:
        return 0
    # dp1[i][k]: i番目（0-indexed）以前の数字の和でkを作れるか否か
    # dp2[j][k]: j番目（0-indexed）以降の数字の和でkを作れるか否か
    # iについてのfor loopで
    #     dp[j][k] = dp1[j][k] (j < i)
    #              = dp2[j][k] (j >= i)
    # となるように更新していく
    dp = np.zeros((N, K + 1), dtype=np.int)  # 最初はdp2で初期化
    dp[N - 1][0] = 1
    dp[N - 1][min(A[N - 1], K)] = 1
    for j in range(N - 2, -1, -1):
        dp[j] = dp[j + 1]
        dp[j][A[j]:] = np.maximum(dp[j][A[j]:], dp[j + 1][:-A[j]])
    # 「A[i] 以外の数字の組で K-A[i] ～ K-1 は作れない」ものの数を数える
    cnt = 0
    for i in range(N):
        # 次の式を満たす(x, y)が存在しなければA[i]は不必要：
        #     K - A[i] <= x + y <= K - 1
        #         x: ～i-1の要素, y: i+1～の要素
        a = A[i]
        if i == 0:
            if max(dp[1][max(0, K - a):K]) == 0:
                cnt += 1
            # dp1の反映
            dp[0] = np.zeros(K + 1, dtype=np.int)
            dp[0][0] = 1
            dp[0][min(K, a)] = 1
        elif i == N - 1:
            if max(dp[N - 2][max(0, K - a):K]) == 0:
                cnt += 1
        else:
            # dp2の累積和
            dp[i + 1] = dp[i + 1].cumsum()
            unnecessary = True
            for x in range(K + 1):
                if dp[i - 1][x] == 0:
                    continue
                # K - A[i] - x <= y <= K - 1 - x なるyの存在をチェック
                if 0 < K - a - x:
                    # dp[i + 1]はdp2の累積和になってる
                    if dp[i + 1][K - 1 - x] - dp[i + 1][K - a - x - 1] > 0:
                        unnecessary = False
                        break
                elif K - a - x <= 0 <= K - 1 - x:
                    if dp[i + 1][K - 1 - x] > 0:
                        unnecessary = False
                        break
            if unnecessary:
                cnt += 1
            # dp1の反映
            dp[i] = dp[i - 1]
            dp[i][A[i]:] = np.maximum(dp[i][A[i]:], dp[i - 1][:-A[i]])
    return cnt


def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    print(solution(N, K, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def solution(N, K, A):
    # O(K * N)解法
    #     partial_solutionの改良。
    #    「a以外の数字の組み合わせで作れる数字」を考えるため、両方向からdpテーブルを作る。
    if N == 1:
        return 0
    # dp1[i][k]: i番目（0-indexed）以前の数字の和でkを作れるか否か
    # dp2[j][k]: j番目（0-indexed）以降の数字の和でkを作れるか否か
    # iについてのfor loopで
    #     dp[j][k] = dp1[j][k] (j < i)
    #              = dp2[j][k] (j >= i)
    # となるように更新していく
    dp = [[0 for _ in range(K + 1)] for _ in range(N)]  # 最初はdp2で初期化
    dp[N - 1][0] = 1
    dp[N - 1][min(A[N - 1], K)] = 1
    for j in range(N - 2, -1, -1):
        for k in range(K + 1):
            dp[j][k] = dp[j + 1][k]
            if k >= A[j]:
                dp[j][k] = max(dp[j][k], dp[j + 1][k - A[j]])
    # 「A[i] 以外の数字の組で K-A[i] ～ K-1 は作れない」ものの数を数える
    cnt = 0
    for i in range(N):
        # 次の式を満たす(x, y)が存在しなければA[i]は不必要：
        #     K - A[i] <= x + y <= K - 1
        #         x: ～i-1の要素, y: i+1～の要素
        a = A[i]
        if i == 0:
            if max(dp[1][max(0, K - a):K]) == 0:
                cnt += 1
            # dp1の反映
            for k in range(K + 1):
                dp[0][k] = 0
            dp[0][0] = 1
            dp[0][min(K, a)] = 1
        elif i == N - 1:
            if max(dp[N - 2][max(0, K - a):K]) == 0:
                cnt += 1
        else:
            # dp2の累積和
            for k in range(1, K + 1):
                dp[i + 1][k] += dp[i + 1][k - 1]
            unnecessary = True
            for x in range(K + 1):
                if dp[i - 1][x] == 0:
                    continue
                # K - A[i] - x <= y <= K - 1 - x なるyの存在をチェック
                if 0 < K - a - x:
                    # dp[i + 1]はdp2の累積和になってる
                    if dp[i + 1][K - 1 - x] - dp[i + 1][K - a - x - 1] > 0:
                        unnecessary = False
                        break
                elif K - a - x <= 0 <= K - 1 - x:
                    if dp[i + 1][K - 1 - x] > 0:
                        unnecessary = False
                        break
            if unnecessary:
                cnt += 1
            # dp1の反映
            for k in range(K + 1):
                dp[i][k] = dp[i - 1][k]
                if k >= a:
                    dp[i][k] = max(dp[i][k], dp[i - 1][k - a])
    return cnt


def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    print(solution(N, K, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def partial_solution(N, K, A):
    # O(K * N**2)解法
    #     「aが不必要」
    #     ＝「aを含む良い集合の数字の和は K+a 以上」
    #     ＝「a以外の数字の組み合わせで K-a ～ K-1 は作れない」
    if N == 1:
        return 0
    cnt = 0
    for i in range(N):
        # dp[n][k]: n番目（1-indexed）までの数字の和でkを作れるか否か
        dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
        dp[0][0] = 1
        for j in range(N):
            a = A[j]
            if j == i:
                for k in range(K + 1):
                    # i番目（0-indexed）のAは使わない
                    dp[j + 1][k] = dp[j][k]
            else:
                for k in range(K + 1):
                    v = dp[j][k]
                    if k >= a:
                        v = max(v, dp[j][k - a])
                    dp[j + 1][k] = v
        lb, ub = max(0, K - A[i]), K - 1
        if sum(dp[N][lb:(ub + 1)]) == 0:
            cnt += 1
    return cnt


def solution(N, K, A):
    # O(K * N)解法
    #     partial_solutionの改良。
    #    「a以外の数字の組み合わせで作れる数字」を考えるため、両方向からdpテーブルを作る。
    if N == 1:
        return 0
    # dp1[i][k]: i番目（0-indexed）以前の数字の和でkを作れるか否か
    # dp2[j][k]: j番目（0-indexed）以降の数字の和でkを作れるか否か
    dp1 = [[0 for _ in range(K + 1)] for _ in range(N)]
    dp2 = [[0 for _ in range(K + 1)] for _ in range(N)]
    dp1[0][0] = 1
    dp1[0][min(A[0], K)] = 1
    dp2[N - 1][0] = 1
    dp2[N - 1][min(A[N - 1], K)] = 1
    for i in range(1, N):
        j = N - 1 - i
        a1, a2 = A[i], A[j]
        for k in range(K + 1):
            v1, v2 = dp1[i - 1][k], dp2[j + 1][k]
            if k >= a1:
                v1 = max(v1, dp1[i - 1][k - a1])
            if k >= a2:
                v2 = max(v2, dp2[j + 1][k - a2])
            dp1[i][k] = v1
            dp2[j][k] = v2
    # 「A[i] 以外の数字の組で K-A[i] ～ K-1 は作れない」ものの数を数える
    cnt = 0
    cumsum_dp2 = [0] * (K + 1)
    for i in range(N):
        # 次の式を満たす(x, y)が存在しなければA[i]は不必要：
        #     K - A[i] <= x + y <= K - 1
        #         x: ～i-1の要素, y: i+1～の要素
        a = A[i]
        if i == 0:
            if max(dp2[1][max(0, K - a):K]) == 0:
                cnt += 1
        elif i == N - 1:
            if max(dp1[N - 2][max(0, K - a):K]) == 0:
                cnt += 1
        else:
            cumsum_dp2[0] = dp2[i + 1][0]  # dp2の累積和
            for k in range(1, K + 1):
                cumsum_dp2[k] = cumsum_dp2[k - 1] + dp2[i + 1][k]
            unnecessary = True
            for x in range(K + 1):
                if dp1[i - 1][x] == 0:
                    continue
                # K - A[i] - x <= y <= K - 1 - x なるyの存在をチェック
                if 0 < K - a - x:
                    if cumsum_dp2[K - 1 - x] - cumsum_dp2[K - a - x - 1] > 0:
                        unnecessary = False
                        break
                elif K - a - x <= 0 <= K - 1 - x:
                    if cumsum_dp2[K - 1 - x] > 0:
                        unnecessary = False
                        break
            if unnecessary:
                cnt += 1
    return cnt


def check():
    import random
    random.seed(0)
    for N in range(1, 102, 10):
        for K in range(1, 102, 10):
            A = random.choices(range(1, 200+1), k=N)
            print('Checking: N={}, K={}'.format(N, K))
            sol = solution(N, K, A)
            psol = partial_solution(N, K, A)
            print('Sol: {}, Partial sol:{}'.format(sol, psol))
            assert sol == psol
    print('OK')


def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    print(solution(N, K, A))


if __name__ == '__main__':
    main()
    # check()

Submission status: Time Limit Exceeded

Solution code:
def partial_solution(N, K, A):
    # O(K * N**2)解法
    # 「aが不必要」＝「aを含む良い集合の数字の和は K+a 以上」
    #              ＝「a以外の数字の組み合わせで K-a ～ K-1 は作れない」
    cnt = 0
    for i in range(N):
        # dp[n][k]: n番目（1-indexed）までの数字の和でkを作れるか否か
        dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
        dp[0][0] = 1
        for j in range(N):
            a = A[j]
            if j == i:
                for k in range(K + 1):
                    # i番目（0-indexed）のAは使わない
                    dp[j + 1][k] = dp[j][k]
            else:
                for k in range(K + 1):
                    v = dp[j][k]
                    if k >= a:
                        v = max(v, dp[j][k - a])
                    dp[j + 1][k] = v
        lb, ub = max(0, K - A[i]), K - 1
        if sum(dp[N][lb:(ub + 1)]) == 0:
            cnt += 1
    return cnt


def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    print(partial_solution(N, K, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()

def main():
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    """
    （aが不要なカード）＝（A-{a}からK-a以上の最小の部分和を取った時、それがK以上）
    まで言い換えてドボン。。。
    部分和の全列挙しなくても和がKまでで打ち切っていいんだから、ここでdpの発想が出なかったのは切腹。
    まずは部分点解法を実装してみる。

    →次に二分探索でdpを行う回数を削減する。ai <= ajに対してajが不要ならばaiも不要なことが対偶を取って分かる。
    そこでAをソートしたうえで必要と不要の境目を見つければよい。

    →PypyだとO(NKlogN)は通らなかったので、O(NK)解法を実装。
    一度二分探索できる話は忘れて、A-{a}から作れる部分和は(aの左側からの部分和)+(aの右側からの部分和)と
    かけることに注意すれば、左側からとれる部分和と右側からとれる部分和を前計算しておけばよい。
    MLEするので右側のdp結果はビットで持つことにする。
    """
    rdp = [0 for _ in range(N)]  # rdp[i][j] = (a(-1),...,a(-i)の部分和でjを作れるか)
    rdp[0] = 1
    for i in range(1, N):
        for j in range(K):
            if (rdp[i - 1] >> j) & 1 or (j >= A[-i] and (rdp[i - 1] >> (j - A[-i])) & 1):
                rdp[i] |= 1 << j

    ldp = [0] * K  # ldp[i][j] = (a1,...,aiの部分和でjを作れるか)
    ldp[0] = 1
    S = [0] * (K + 1)
    ans = 0
    for i in range(1, N + 1):
        # A[i]が不要かチェック
        for j in range(K): S[j + 1] = S[j] + ((rdp[N - i] >> j) & 1)
        no_need = True
        for lval in range(K):
            if ldp[lval] == 0: continue
            rval = S[K - lval] - S[max(0, K - A[i] - lval)]
            if rval > 0:
                no_need = False
                break
        if no_need: ans += 1

        # ldp[i][:]の計算
        ldp2 = [0] * K
        for j in range(K):
            if ldp[j] == 1 or (j >= A[i] and ldp[j - A[i]] == 1):
                ldp2[j] = 1
        ldp = ldp2
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def main():
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    """
    （aが不要なカード）＝（A-{a}からK-a以上の最小の部分和を取った時、それがK以上）
    まで言い換えてドボン。。。
    部分和の全列挙しなくても和がKまでで打ち切っていいんだから、ここでdpの発想が出なかったのは切腹。
    まずは部分点解法を実装してみる。

    →次に二分探索でdpを行う回数を削減する。ai <= ajに対してajが不要ならばaiも不要なことが対偶を取って分かる。
    そこでAをソートしたうえで必要と不要の境目を見つければよい。
    """
    A.sort()

    def no_need_check(k):
        # dp[i][j] = (i個使って(ただしA[k]を除く)部分和jが作れるか)
        dp = 1  #dp[j]をjビット目が立っている形で表現
        for i in range(1, N + 1):
            if i == k: continue
            dp2 = 0
            for j in range(K + 1):
                if (dp >> j) & 1:
                    dp2 |= 1 << j
                    dp2 |= 1 << (min(K, j + A[i]))
            dp = dp2

        no_need = True
        for j in range(max(0, K - A[k]), K):
            if (dp >> j) & 1:
                no_need = False
                break
        return no_need

    # 左端が不要であるかチェック
    if not no_need_check(1):
        print(0)
        return
    
    # 右端が必要であるかチェック
    if no_need_check(N):
        print(N)
        return
    
    # 二分探索
    left = 1  # no_need
    right = N  # need
    while right - left > 1:
        mid = (left + right) // 2
        if no_need_check(mid):
            left = mid
        else:
            right = mid
    print(left)
        
        
    print()

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
def input(): return sys.stdin.readline().strip()

def main():
    N, K = map(int, input().split())
    A = np.zeros(N + 1, dtype=np.int64)
    A[1:] += np.array(input().split(), np.int64)
    """
    （aが不要なカード）＝（A-{a}からK-a以上の最小の部分和を取った時、それがK以上）
    まで言い換えてドボン。。。
    部分和の全列挙しなくても和がKまでで打ち切っていいんだから、ここでdpの発想が出なかったのは切腹。
    まずは部分点解法を実装してみる。

    →次に二分探索でdpを行う回数を削減する。ai <= ajに対してajが不要ならばaiも不要なことが対偶を取って分かる。
    そこでAをソートしたうえで必要と不要の境目を見つければよい。

    →PypyだとO(NKlogN)は通らなかったので、O(NK)解法を実装。
    一度二分探索できる話は忘れて、A-{a}から作れる部分和は(aの左側からの部分和)+(aの右側からの部分和)と
    かけることに注意すれば、左側からとれる部分和と右側からとれる部分和を前計算しておけばよい。
    """

    rdp = np.zeros((N, K), dtype=np.uint8)  # rdp[i][j] = (a(-1),...,a(-i)の部分和でjを作れるか)
    rdp[0][0] = 1
    for i in range(1, N):
        rdp[i] += rdp[i - 1]
        if A[-i] < K:
            rdp[i][A[-i]:] += rdp[i - 1][:(K - A[-i])]
            rdp[i] = np.clip(rdp[i], 0, 1)

    ldp = np.zeros(K, dtype=np.uint8)  # ldp[i][j] = (a1,...,aiの部分和でjを作れるか)
    ldp[0] = 1
    S = np.zeros(K + 1)
    ans = 0
    for i in range(1, N + 1):
        # A[i]が不要かチェック
        S[1:] = np.cumsum(rdp[N - i])
        no_need = True
        for lval in range(K):
            if ldp[lval] == 0: continue
            rval = S[K - lval] - S[max(0, K - A[i] - lval)]
            if rval > 0:
                no_need = False
                break
        if no_need: ans += 1

        # ldp[i][:]の計算
        if A[i] < K:
            ldp[A[i]:] += ldp[:(K - A[i])]
            ldp = np.clip(ldp, 0, 1)
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
def input(): return sys.stdin.readline().strip()

def main():
    N, K = map(int, input().split())
    A = np.concatenate([np.zeros(1, dtype=np.uint8), np.array(input().split(), np.int64)])
    """
    （aが不要なカード）＝（A-{a}からK-a以上の最小の部分和を取った時、それがK以上）
    まで言い換えてドボン。。。
    部分和の全列挙しなくても和がKまでで打ち切っていいんだから、ここでdpの発想が出なかったのは切腹。
    まずは部分点解法を実装してみる。

    →次に二分探索でdpを行う回数を削減する。ai <= ajに対してajが不要ならばaiも不要なことが対偶を取って分かる。
    そこでAをソートしたうえで必要と不要の境目を見つければよい。

    →PypyだとO(NKlogN)は通らなかったので、O(NK)解法を実装。
    一度二分探索できる話は忘れて、A-{a}から作れる部分和は(aの左側からの部分和)+(aの右側からの部分和)と
    かけることに注意すれば、左側からとれる部分和と右側からとれる部分和を前計算しておけばよい。
    """

    rdp = np.zeros((N, K), dtype=np.uint8)  # rdp[i][j] = (a(-1),...,a(-i)の部分和でjを作れるか)
    rdp[0][0] = 1
    for i in range(1, N):
        if A[-i] >= K:
            rdp[i] = rdp[i - 1]
        else:
            rdp[i] = rdp[i - 1] + np.concatenate([np.zeros(A[-i], dtype=np.uint8), rdp[i - 1][:(K - A[-i])]])
            rdp[i] = np.clip(rdp[i], 0, 1)

    ldp = np.zeros(K, dtype=np.uint8)  # ldp[i][j] = (a1,...,aiの部分和でjを作れるか)
    ldp[0] = 1
    ans = 0
    for i in range(1, N + 1):
        # A[i]が不要かチェック
        S = np.concatenate([np.zeros(1, dtype=np.uint8), np.cumsum(rdp[N - i])])
        no_need = True
        for lval in range(K):
            if ldp[lval] == 0: continue
            rval = S[K - lval] - S[max(0, K - A[i] - lval)]
            if rval > 0:
                no_need = False
                break
        if no_need: ans += 1

        # ldp[i][:]の計算
        if A[i] < K:
            ldp += np.concatenate([np.zeros(A[i], dtype=np.uint8), ldp[:(K - A[i])]])
            ldp = np.clip(ldp, 0, 1)
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def main():
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    """
    （aが不要なカード）＝（A-{a}からK-a以上の最小の部分和を取った時、それがK以上）
    まで言い換えてドボン。。。
    部分和の全列挙しなくても和がKまでで打ち切っていいんだから、ここでdpの発想が出なかったのは切腹。
    まずは部分点解法を実装してみる。

    →次に二分探索でdpを行う回数を削減する。ai <= ajに対してajが不要ならばaiも不要なことが対偶を取って分かる。
    そこでAをソートしたうえで必要と不要の境目を見つければよい。
    """
    A.sort()

    def no_need_check(k):
        # dp[i][j] = (i個使って(ただしA[k]を除く)部分和jが作れるか)
        dp = [1] + [0] * K
        for i in range(1, N + 1):
            if i == k: continue
            dp2 = [0] * (K + 1)
            for j in range(K + 1):
                if dp[j] == 1:
                    dp2[j] = 1
                    dp2[min(K, j + A[i])] = 1
            dp = dp2

        no_need = True
        for j in range(max(0, K - A[k]), K):
            if dp[j] != 0:
                no_need = False
                break
        return no_need

    # 左端が不要であるかチェック
    if not no_need_check(1):
        print(0)
        return
    
    # 右端が必要であるかチェック
    if no_need_check(N):
        print(N)
        return
    
    # 二分探索
    left = 1  # no_need
    right = N  # need
    while right - left > 1:
        mid = (left + right) // 2
        if no_need_check(mid):
            left = mid
        else:
            right = mid
    print(left)
        
        
    print()

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def main():
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    """
    （aが不要なカード）＝（A-{a}からK-a以上の最小の部分和を取った時、それがK以上）
    まで言い換えてドボン。。。
    部分和の全列挙しなくても和がKまでで打ち切っていいんだから、ここでdpの発想が出なかったのは切腹。
    まずは部分点解法を実装してみる。
    """
    ans = 0
    for k in range(1, N + 1):
        # dp[i][j] = (i個使って(ただしA[k]を除く)部分和jが作れるか)
        dp = [1] + [0] * K
        for i in range(1, N + 1):
            if i == k: continue
            dp2 = [0] * (K + 1)
            for j in range(K + 1):
                if dp[j] == 1:
                    dp2[j] = 1
                    dp2[min(K, j + A[i])] = 1
            dp = dp2

        
        no_need = True
        for j in range(max(0, K - A[k]), K):
            if dp[j] != 0:
                no_need = False
                break
        if no_need: ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections
N, K = map(int, input().split())
a = [int(x) for x in input().split() if int(x) < K]
a.sort()

def renew_dp(dp, List, K): #Listの部分和がiとなりうるならばdp[i]=True
    dp_ = dp.copy()
    for x in List:
        for i in range(x,K):
            if dp_[i]: continue 
            if dp[i-x]: dp_[i] = True
        dp = dp_.copy()
    return dp_


def binary_tree(List, base_List, K): #2分探索
    if len(List) == 0: return 0 #不要札無し
    center = len(List)//2 #2分する支点
    dp = collections.defaultdict(lambda:False)
    dp[0] = True
    List_without_center = base_List.copy()
    List_without_center.remove(List[center])
    dp = renew_dp(dp, List_without_center, K) #dp更新
    if any(dp[i] for i in range(K-List[center],K)): #必要(True)か不必要(False)かジャッジ
        result = center if len(List)==1 else binary_tree(List[:center], base_List, K) #2分木の末端まで再帰
    else:
        result = center+1 if len(List)==1 else binary_tree(List[center:], base_List, K) + center
    return result

ans = binary_tree(a, a, K) #ans以下のjについて、a[j]は不必要
print(ans)