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: Memory Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc056/tasks/arc070_b
def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    # O(K * N)解法
    #    「a以外の数字の組み合わせで作れる数字」を考えるため、両方向からdpテーブルを作る。
    if N == 1:
        print(0)
        return
    # 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～の要素
        if i == 0:
            if max(dp[1][max(0, K - A[i]):K]) == 0:
                cnt += 1
            # dp1の反映
            for k in range(K + 1):
                dp[0][k] = 0
            dp[0][0] = 1
            dp[0][min(K, A[i])] = 1
        elif i == N - 1:
            if max(dp[N - 2][max(0, K - A[i]):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[i] - x:
                    # dp[i + 1]はdp2の累積和になってる
                    if dp[i + 1][K - 1 - x] - dp[i + 1][K - A[i] - x - 1] > 0:
                        unnecessary = False
                        break
                elif K - A[i] - 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[i]:
                    dp[i][k] = max(dp[i][k], dp[i - 1][k - A[i]])
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Memory 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を作れるか否か
    # 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):
        a = A[j]
        for k in range(K + 1):
            v = dp[j + 1][k]
            if k >= a:
                v = max(v, dp[j + 1][k - a])
            dp[j][k] = v
    # 「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):
                v = dp[i - 1][k]
                if k >= a:
                    v = max(v, dp[i - 1][k - a])
                dp[i][k] = v
    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: Memory 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を作れるか否か
    # 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):
        a = A[j]
        for k in range(K + 1):
            v = dp[j + 1][k]
            if k >= a:
                v = max(v, dp[j + 1][k - a])
            dp[j][k] = v
    # 「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(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:
            cumsum_dp2[0] = dp[i + 1][0]  # dp2の累積和
            for k in range(1, K + 1):
                cumsum_dp2[k] = cumsum_dp2[k - 1] + dp[i + 1][k]
            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:
                    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
            # dp1の反映
            for k in range(K + 1):
                v = dp[i - 1][k]
                if k >= a:
                    v = max(v, dp[i - 1][k - a])
                dp[i][k] = v
    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: Memory 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の右側からの部分和)と
    かけることに注意すれば、左側からとれる部分和と右側からとれる部分和を前計算しておけばよい。
    """
    rdp = [[0] * K for _ in range(N)]  # rdp[i][j] = (a(-1),...,a(-i)の部分和でjを作れるか)
    rdp[0][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][j] = 1

    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]
        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: Memory 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の右側からの部分和)と
    かけることに注意すれば、左側からとれる部分和と右側からとれる部分和を前計算しておけばよい。
    """
    rdp = [[0] * K for _ in range(N)]  # rdp[i][j] = (a(-1),...,a(-i)の部分和でjを作れるか)
    rdp[0][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][j] = 1

    ldp = [0] * K  # ldp[i][j] = (a1,...,aiの部分和でjを作れるか)
    ldp[0] = 1
    ans = 0
    for i in range(1, N + 1):
        # A[i]が不要かチェック
        S = [0] + list(accumulate(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][:]の計算
        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: Memory 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の右側からの部分和)と
    かけることに注意すれば、左側からとれる部分和と右側からとれる部分和を前計算しておけばよい。
    """
    ldp = [[0] * K for _ in range(N)]  # ldp[i][j] = (a1,...,aiの部分和でjを作れるか)
    ldp[0][0] = 1
    for i in range(1, N):
        for j in range(K):
            if ldp[i - 1][j] == 1 or (j >= A[i] and ldp[i - 1][j - A[i]] == 1):
                ldp[i][j] = 1
    
    rdp = [[0] * K for _ in range(N)]  # rdp[i][j] = (a(-1),...,a(-i)の部分和でjを作れるか)
    rdp[0][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][j] = 1

    ans = 0
    for i in range(1, N + 1):
        #print("ldp[{}]={}".format(i - 1, ldp[i-1]))
        #print("rdp[{}]={}".format(N-i, rdp[N-i]))
        S = [0] + list(accumulate(rdp[N - i]))
        no_need = True
        for lval in range(K):
            if ldp[i - 1][lval] == 0: continue
            rval = S[K - lval] - S[max(0, K - A[i] - lval)]
            #print("lval={}, rval={}".format(lval, rval))
            if rval > 0:
                no_need = False
                break
        if no_need: ans += 1
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Memory Limit Exceeded

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
a = list(map(int, input().split()))
cum_right = [[0] * K for _ in range(N+1)]
cum_right[-1][0] = 1
for i in range(N)[::-1]:
    for j in range(K):
        cum_right[i][j] = cum_right[i+1][j]
        if j >= a[i]:
            cum_right[i][j] |= cum_right[i+1][j-a[i]]
    cum_right[i+1] = list(accumulate([0] + cum_right[i+1]))
ans = 0
dp_left = [0] * K
dp_left[0] = 1
for i in range(N):
    for j in range(K):
        if not dp_left[j]:
            continue
        if cum_right[i+1][K-j] - cum_right[i+1][max(0, K-a[i]-j)] > 0:
            break
    else:
        ans += 1

    ndp_left = [0] * K
    for j in range(K):
        ndp_left[j] = dp_left[j]
        if j >= a[i]:
            ndp_left[j] |= dp_left[j-a[i]]
    dp_left = ndp_left
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
a = list(map(int, input().split()))
dp_right = [[0] * K for _ in range(N+1)]
dp_right[-1][0] = 1
for i in range(N)[::-1]:
    for j in range(K):
        dp_right[i][j] = dp_right[i+1][j]
        if j >= a[i]:
            dp_right[i][j] |= dp_right[i+1][j-a[i]]
ans = 0
dp_left = [0] * K
dp_left[0] = 1
for i in range(N):
    cum = list(accumulate([0] + dp_right[i+1]))
    for j in range(K):
        if not dp_left[j]:
            continue
        if cum[K-j] - cum[max(0, K-a[i]-j)] > 0:
            break
    else:
        ans += 1

    ndp_left = [0] * K
    for j in range(K):
        ndp_left[j] = dp_left[j]
        if j >= a[i]:
            ndp_left[j] |= dp_left[j-a[i]]
    dp_left = ndp_left
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
a = list(map(int, input().split()))
dp_left = [[0] * K for _ in range(N+1)]
dp_right = [[0] * K for _ in range(N+1)]
dp_left[0][0] = dp_right[-1][0] = 1
for i in range(N):
    for j in range(K):
        dp_left[i+1][j] = dp_left[i][j]
        if j >= a[i]:
            dp_left[i+1][j] |= dp_left[i][j-a[i]]
        dp_right[N-i-1][j] = dp_right[N-i][j]
        if j >= a[N-i-1]:
            dp_right[N-i-1][j] |= dp_right[N-i][j-a[N-i-1]]
ans = 0
for i in range(N):
    cum = list(accumulate([0] + dp_right[i+1]))
    for j in range(K):
        if not dp_left[i][j]:
            continue
        if cum[K-j] - cum[max(0, K-a[i]-j)] > 0:
            break
    else:
        ans += 1
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
a = list(map(int, input().split()))
dp_left = [[0] * K for _ in range(N+1)]
dp_right = [[0] * K for _ in range(N+1)]
dp_left[0][0] = dp_right[-1][0] = 1
for i in range(N):
    for j in range(K):
        dp_left[i+1][j] = dp_left[i][j]
        if j >= a[i]:
            dp_left[i+1][j] |= dp_left[i][j-a[i]]
        dp_right[N-i-1][j] = dp_right[N-i][j]
        if j >= a[N-i-1]:
            dp_right[N-i-1][j] |= dp_right[N-i][j-a[N-i-1]]
cum_right = [list(accumulate([0] + dp_right[i])) for i in range(N+1)]
ans = 0
for i in range(N):
    for j in range(K):
        if not dp_left[i][j]:
            continue
        if cum_right[i+1][K-j] - cum_right[i+1][max(0, K-a[i]-j)] > 0:
            break
    else:
        ans += 1
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    a=LI()#下位の連続するn枚が不要なはず
    a.sort(reverse = True)
    
    
    #i番目までを使ってjが作れるかどうか
    dp=[[0]*K for _ in range(N+1)]
    dp[0][0]=1
    for i in range(N):
        for j in range(K):
            if dp[i][j]==1:
                dp[i+1][j]=1
                jj=j+a[i]
                if jj<K:
                    dp[i+1][jj]=1
                    
                    
    #i番目以降を使ってjが作れるかどうか
    dp2=[[0]*K for _ in range(N+1)]
    dp2[-1][0]=1
    for i in range(N):
        for j in range(K):
            if dp2[-1-i][j]==1:
                dp2[-2-i][j]=1
                jj=j+a[-1-i]
                if jj<K:
                    dp2[-2-i][jj]=1
    
    #累積和チックに
    for i in range(N+1):
        for j in range(K-1):
            dp[i][j+1]+=dp[i][j]
                    
                    
    #x番目の数が必要かどうかの判定 
    #必要なものだけで構成された集合をもとに考えれば良いわけではない，不必要な分も考えなければならない             
    def ch(x):
        if a[x]>=K:
            return True
        else:
            #dp2でsを作り，dpで，K-s未満，K-a[x]-s以上のものが作れれば良い，
            #この範囲内で1が一つでもあれば良いので，累積和の差分が1以上ならok
            for s in range(K-a[x]):
                if dp2[x+1][s]==1:
                    if dp[x][K-s-1] - dp[x][K-a[x]-s-1]>=1:
                        return True
        return False
    
                        
    ng=N
    ok=-1
    while abs(ok-ng)>1:
        med=(ok+ng)//2
        
        if ch(med):
            ok=med
        else:
            ng=med
            
    print(N-(ok+1))
    
    
   
    
            
    
    
    

main()

Submission status: Memory Limit Exceeded

Solution code:
def main():
    import sys
    from array import array
    input = sys.stdin.readline

    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    dp_left = [array('I', [0] * K) for _ in range(N + 1)]
    dp_right = [array('I', [0] * K) for _ in range(N + 1)]
    dp_left[0][0] = 1
    dp_right[0][0] = 1
    for i, a in enumerate(A):
        for j in range(K):
            if dp_left[i][j]:
                dp_left[i + 1][j] = 1
                if j + a < K:
                    dp_left[i + 1][j + a] = 1
    for i, a in enumerate(reversed(A)):
        for j in range(K):
            if dp_right[i][j]:
                dp_right[i + 1][j] = 1
                if j + a < K:
                    dp_right[i + 1][j + a] = 1

    ok = N
    ng = -1
    mid = (ok+ng)//2
    while ok - ng > 1:
        a = A[mid]
        if a >= K:
            ok = mid
            mid = (ok+ng)//2
            continue
        flg = 0
        l = 0
        r = K-1
        while True:
            if dp_right[N-mid-1][r]:
                break
            r -= 1
        while True:
            if K-a <= l+r < K:
                flg = 1
                break
            elif l+r >= K:
                r -= 1
                if r < 0:
                    break
                while True:
                    if dp_right[N-mid-1][r]:
                        break
                    r -= 1
            else:
                l += 1
                if l >= K:
                    break
                while True:
                    if dp_left[mid][l]:
                        break
                    l += 1
                    if l >= K:
                        break
        if flg:
            ok = mid
        else:
            ng = mid
        mid = (ok+ng)//2
    print(ng+1)


if __name__ == '__main__':
    main()

Submission status: Memory Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    dp_left = [[0] * K for _ in range(N + 1)]
    dp_right = [[0] * K for _ in range(N + 1)]
    dp_left[0][0] = 1
    dp_right[0][0] = 1
    for i, a in enumerate(A):
        for j in range(K):
            if dp_left[i][j]:
                dp_left[i + 1][j] = 1
                if j + a < K:
                    dp_left[i + 1][j + a] = 1
    for i, a in enumerate(reversed(A)):
        for j in range(K):
            if dp_right[i][j]:
                dp_right[i + 1][j] = 1
                if j + a < K:
                    dp_right[i + 1][j + a] = 1

    ok = N
    ng = -1
    mid = (ok+ng)//2
    while ok - ng > 1:
        a = A[mid]
        if a >= K:
            ok = mid
            mid = (ok+ng)//2
            continue
        flg = 0
        l = 0
        r = K-1
        while True:
            if dp_right[N-mid-1][r]:
                break
            r -= 1
        while True:
            if K-a <= l+r < K:
                flg = 1
                break
            elif l+r >= K:
                r -= 1
                if r < 0:
                    break
                while True:
                    if dp_right[N-mid-1][r]:
                        break
                    r -= 1
            else:
                l += 1
                if l >= K:
                    break
                while True:
                    if dp_left[mid][l]:
                        break
                    l += 1
                    if l >= K:
                        break
        if flg:
            ok = mid
        else:
            ng = mid
        mid = (ok+ng)//2
    print(ng+1)


if __name__ == '__main__':
    main()

Submission status: Memory Limit Exceeded

Solution code:
class cumsum:
    def __init__(self, A):
        self.n = len(A)
        self.data = [0]*self.n
        for i in range(self.n):
            self.data[i] = self.data[i-1]+A[i]
    def query(self, l, r):
        if self.n<=l:
            return 0
        if r<0:
            return 0
        if l<0:
            x = 0
        else:
            x = self.data[l]
        if r>=self.n:
            y = self.data[-1]
        else:
            y = self.data[r]
        return y-x

N, K = map(int, input().split())
a = list(map(int, input().split()))
a = [i for i in a if i<=K]
N = len(a)
dp1 = [[0]*(K+1) for _ in range(N+1)]
dp2 = [[0]*(K+1) for _ in range(N+1)]
dp1[-1][0] = 1
for i in range(-1, N-1):
    for j in range(K):
        if j+a[i+1]<=K:
            dp1[i+1][j+a[i+1]]|=dp1[i][j]
        dp1[i+1][j]|=dp1[i][j]
a.reverse()
dp2[-1][0] = 1
for i in range(-1, N-1):
    for j in range(K):
        if j+a[i+1]<=K:
            dp2[i+1][j+a[i+1]]|=dp2[i][j]
        dp2[i+1][j]|=dp2[i][j]
dp2.reverse()
ans = 0
a.reverse()
for i in range(N):
    sy = cumsum(dp2[(i+2)%(N+1)])
    for j in range(K+1):
        if dp1[i-1][j]:
            if sy.query(K-a[i]-1-j, K-1-j):
                ans+=1
                break
print(N-ans)

Submission status: Memory Limit Exceeded

Solution code:
class cumsum:
    def __init__(self, A):
        self.n = len(A)
        self.data = [0]*self.n
        for i in range(self.n):
            self.data[i] = self.data[i-1]+A[i]
    def query(self, l, r):
        if self.n<=l:
            return 0
        if r<0:
            return 0
        if l<0:
            x = 0
        else:
            x = self.data[l]
        if r>=self.n:
            y = self.data[-1]
        else:
            y = self.data[r]
        return y-x

N, K = map(int, input().split())
a = list(map(int, input().split()))
a = [i for i in a if i<=K]
N = len(a)
dp1 = [[0]*(K+1) for _ in range(N+1)]
dp2 = [[0]*(K+1) for _ in range(N+1)]
dp1[-1][0] = 1
for i in range(-1, N-1):
    for j in range(K):
        if j+a[i+1]<=K:
            dp1[i+1][j+a[i+1]]|=dp1[i][j]
        dp1[i+1][j]|=dp1[i][j]
a.reverse()
dp2[-1][0] = 1
for i in range(-1, N-1):
    for j in range(K):
        if j+a[i+1]<=K:
            dp2[i+1][j+a[i+1]]|=dp2[i][j]
        dp2[i+1][j]|=dp2[i][j]
dp2.reverse()
ans = 0
a.reverse()
for i in range(N):
    x = dp1[i-1]
    y = dp2[(i+2)%(N+1)]
    sy = cumsum(y)
    for j in range(K+1):
        if x[j]:
            if sy.query(K-a[i]-1-j, K-1-j):
                ans+=1
                break
print(N-ans)

Submission status: Memory Limit Exceeded

Solution code:
def main():
    def accumulate(X):
        ret = [X[0]]
        for x in X[1:]:
            ret.append(ret[-1] + x)
        return ret
    
    N, K = map(int, raw_input().split())
    A = list(map(int, raw_input().split()))

    # K以上の数はすべて必要なのでA未満の数だけを考える
    A = sorted([a for a in A if a < K], reverse=True)
    N = len(A)

    # dp1[i][k] := 1 ~ iまでのカードを使って数kが作れるか
    dp1 = [[0] * (K + 1) for i in range(N + 1)]
    dp1[0][0] = 1
    # dp2[i][k] := N ~ iまでのカードを使って数kが作れるか
    dp2 = [[0] * (K + 1) for i in range(N + 1)]
    dp2[0][0] = 1

    # dpテーブルを計算
    for i in range(1, N + 1):
        for k in range(K + 1):
            dp1[i][k] = max(dp1[i][k], dp1[i - 1][k])
            if A[i - 1] <= k:
                dp1[i][k] = max(dp1[i][k], dp1[i - 1][k - A[i - 1]])

            dp2[i][k] = max(dp2[i][k], dp2[i - 1][k])
            if A[N - i] <= k:
                dp2[i][k] = max(dp2[i][k], dp2[i - 1][k - A[N - i]])

    # 累積和を取っておく
    for i in range(N + 1):
        dp2[i] = list(accumulate(dp2[i]))

    # ansを計算
    need = 0
    for i in range(1, N + 1):
        for k in range(K + 1):
            # 1 ~ i番目まででkが作れない
            if not dp1[i - 1][k]:
                continue

            # 1 ~ i番目までだけで必要な条件が作れる
            if K - A[i - 1] <= k < K:
                need += 1
                break

            # 範囲外参照
            if K - A[i - 1] - k - 1 < 0:
                continue

            if dp2[N - i][K - k] - dp2[N - i][K - A[i - 1] - k - 1] > 0:
                need += 1
                break

    print(N - need)

main()

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split())
A = tuple(map(int, input().split()))

dp_left = np.zeros((N + 1, K), dtype=bool)
dp_right = np.zeros((N + 1, K), dtype=bool)
dp_left[0, 0] = 1
dp_right[N, 0] = 1

for i in range(N):
    dp_left[i + 1] = dp_left[i]
    dp_right[N - i - 1] = dp_right[N - i]
    if (a := A[i]) < K:
        dp_left[i + 1, a:] |= dp_left[i, :-a]
    if (a := A[N - i - 1]) < K:
        dp_right[N - i - 1, a:] |= dp_right[N - i, :-a]

ans = 0
for i, a in enumerate(A):
    left_true = np.nonzero(dp_left[i])[0]
    right_true = np.nonzero(dp_right[i + 1])[0]

    ss = np.searchsorted(right_true, K - left_true) - 1
    if all(right_true[ss] + left_true + a < K):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    nonzeros = [1]
    for a in As:
        ndp = nonzeros[-1]
        if a <= K:
            ndp |= (nonzeros[-1] % (1 << (K-a))) << a
        nonzeros.append(ndp)
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()