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:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def can_delete(idx, A, K):

    dp = [False] * (K + 1)
    dp[0] = True
    for i in range(len(A)):
        if i == idx:
            continue

        for j in range(len(dp) - 1, -1, -1):
            if dp[j] and j + A[i] < len(dp):
                dp[j + A[i]] = True

    ok = True
    for i in range(K):
        if dp[i] and i + A[idx] >= K:
            ok = False
    return ok


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

    low, high = -1, len(A)
    while high - low > 1:
        idx = (low + high) // 2
        if can_delete(idx, A, K):
            low = idx
        else:
            high = idx

    print(low + 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def can_delete(idx, A, K):
    now = set()
    now.add(0)

    for i in range(len(A)):
        if i == idx:
            continue
        nex = set(now)
        for v in now:
            nex.add(v + A[i])
        now = nex

    ok = True
    for v in now:
        if v < K and  v + A[idx] >= K:
            ok = False
    return ok


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

    low, high = -1, len(A)
    while high - low > 1:
        idx = (low + high) // 2
        if can_delete(idx, A, K):
            low = idx
        else:
            high = idx

    print(low + 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def d_no_need(N, K, A):
    from bisect import bisect_left
    # 値がK以上の要素は単体で不必要でない要素になれる
    A.sort()
    a_sorted = A[:bisect_left(A, K)]
    ans = len(a_sorted)  # a_sortedの要素は不必要となりうる

    dp = [False] * K  # dp[k]:a_sortedの一部の和を取った値をKにできるか？
    dp[0] = True
    current_max = 0
    for idx, a in reversed(list(enumerate(a_sorted))):
        if current_max + a >= K:
            ans = idx
        for j in range(min(current_max, K - a) + 1):
            if dp[j] and j + a < K:
                current_max = max(current_max, j + a)
                dp[j + a] = True
    return ans

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(d_no_need(N, K, A))

Submission status: Time Limit Exceeded

Solution code:
def d_no_need(N, K, A):
    from bisect import bisect_left
    # 値がK以上の要素は単体で不必要でない要素になれる
    a_sorted = sorted(A)
    a_sorted = a_sorted[:bisect_left(a_sorted, K)]
    ans = len(a_sorted)  # a_sortedの要素は不必要となりうる

    dp = [False] * K  # dp[k]:a_sortedの一部の和を取った値をKにできるか？
    dp[0] = True
    current_max = 0
    for idx, a in list(enumerate(a_sorted))[::-1]:
        if current_max + a >= K:
            ans = idx
        for j in range(min(current_max, K - a) + 1):
            if dp[j] and j + a < K:
                current_max = max(current_max, j + a)
                dp[j + a] = True
    return ans

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(d_no_need(N, K, A))

Submission status: Time Limit Exceeded

Solution code:
def d_no_need(N, K, A):
    from bisect import bisect_left
    # 値がK以上の要素は単体で不必要でない要素になれる
    a_sorted = sorted(A)
    a_sorted = a_sorted[:bisect_left(a_sorted, K)]
    ans = len(a_sorted)  # a_sortedの要素は不必要となりうる

    dp = [False] * K  # dp[k]:a_sortedの一部の和を取った値をKにできるか？
    dp[0] = True
    current_max = 0
    for idx, a in list(enumerate(a_sorted))[::-1]:
        if current_max + a >= K:
            ans = idx
        for j in range(current_max + 1):
            if dp[j] and j + a < K:
                current_max = max(current_max, j + a)
                dp[j + a] = True
    return ans

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(d_no_need(N, K, A))

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from collections import Counter

n,k = li()
a = li()

a_ltk = [ai for ai in a if ai < k]
a_ltk.sort(reverse=True)
need = {ai:False for ai in a_ltk}

# 貪欲に足していく
for i in range(len(a_ltk)):
    cur = 0
    stack = []
    for j in range(i,len(a_ltk)):
        cur += a_ltk[j]
        stack.append(a_ltk[j])
        if cur >= k:
            for key in stack:
                need[key] = True
            stack.pop()
            cur -= a_ltk[j]

                
cnt = Counter(a_ltk)
ans = 0

for k,v in need.items():
    if not v:
        ans += cnt[k]
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
import queue
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret


@mt
def slv2(N, K, A):
    @lru_cache(maxsize=None)
    def f(w):
        if K - A[w] < 0:
            return True
        dp = [0] * (K)

        for i, a in enumerate(A):
            if i == w:
                continue
            tdp = dp[:]
            for j in range(K):
                if dp[j] and j + a < K:
                    tdp[j+a] = 1
            if a < K:
                tdp[a] = 1
            dp = tdp

        if sum(dp[K-A[w]:]) > 0:
            return True

        return False

    ans = 0
    for i in range(N):
        if not f(i):
            ans += 1

    return ans


@mt
def slv(N, K, A):
    @lru_cache(maxsize=None)
    def f(w):
        if K - A[w] <= 0:
            return True
        dp = [0] * (K)
        tdp = [0] * (K)

        for i, a in enumerate(A):
            if i == w:
                continue

            for j in range(K):
                tdp[j] += dp[j]
                if dp[j] and j + a < K:
                    tdp[j+a] = 1
            if a < K:
                tdp[a] = 1
            dp, tdp = tdp, dp

        if sum(dp[K-A[w]:]) > 0:
            return True

        return False

    A.sort()
    l = 0
    r = N-1
    while r-l > 1:
        c = (l+r)//2
        if f(c):
            r = c
        else:
            l = c

    if f(l):
        return l
    return r + 1 if not f(r) else l + 1


def main():
    N, K = read_int_n()
    A = read_int_n()
    print(slv(N, K, A))

    # for i in range(10000):
    #     N = random.randint(1, 50)
    #     K = random.randint(1, 50)
    #     A = [random.randint(1, 10) for _ in range(N)]
    #     x = slv(N, K, A[:])
    #     y = slv2(N, K, A[:])
    #     print(x, y)
    #     if x != y:
    #         print(N, K)
    #         print(' '.join(map(str, A)))
    #         return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
import queue
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret


@mt
def slv2(N, K, A):
    @lru_cache(maxsize=None)
    def f(w):
        if K - A[w] < 0:
            return True
        dp = [0] * (K)

        for i, a in enumerate(A):
            if i == w:
                continue
            tdp = dp[:]
            for j in range(K):
                if dp[j] and j + a < K:
                    tdp[j+a] = 1
            if a < K:
                tdp[a] = 1
            dp = tdp

        if sum(dp[K-A[w]:]) > 0:
            return True

        return False

    ans = 0
    for i in range(N):
        if not f(i):
            ans += 1

    return ans


@mt
def slv(N, K, A):
    @lru_cache(maxsize=None)
    def f(w):
        if K - A[w] <= 0:
            return True
        dp = [0] * (K)

        for i, a in enumerate(A):
            if i == w:
                continue
            tdp = dp[:]
            for j in range(K):
                if dp[j] and j + a < K:
                    tdp[j+a] = 1
            if a < K:
                tdp[a] = 1
            dp = tdp

        if sum(dp[K-A[w]:]) > 0:
            return True

        return False

    A.sort()
    l = 0
    r = N-1
    while r-l > 1:
        c = (l+r)//2
        if f(c):
            r = c
        else:
            l = c

    if f(l):
        return l
    return r + 1 if not f(r) else l + 1


def main():
    N, K = read_int_n()
    A = read_int_n()
    print(slv(N, K, A))

    # for i in range(10000):
    #     N = random.randint(1, 50)
    #     K = random.randint(1, 50)
    #     A = [random.randint(1, 10) for _ in range(N)]
    #     x = slv(N, K, A[:])
    #     y = slv2(N, K, A[:])
    #     print(x, y)
    #     if x != y:
    #         print(N, K)
    #         print(' '.join(map(str, A)))
    #         return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
src = list(map(int,input().split()))
src.sort(reverse=True)

def need(idx):
    a = src[idx]
    if a >= K: return True
    dp = 1
    for i in range(N):
        if i == idx: continue
        dp2 = dp
        b = src[i]
        for j in range(len(bin(dp))-2):
            if (dp & (1<<j)) == 0: continue
            if j+b < K-a:
                dp2 |= (1<<(j+b))
            elif j+b < K:
                return True
        dp = dp2
    return False

ok = -1
ng = N
while ng-ok > 1:
    m = (ok+ng)//2
    if need(m):
        ok = m
    else:
        ng = m
print(N - ok - 1)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
src = list(map(int,input().split()))
src.sort(reverse=True)

def need(idx):
    a = src[idx]
    if a >= K: return True
    dp = set([0])
    for i in range(N):
        if i == idx: continue
        dp2 = set()
        b = src[i]
        for v in dp:
            if v+b < K-a:
                dp2.add(v+b)
            elif v+b < K:
                return True
        dp |= dp2
    return False

ok = -1
ng = N
while ng-ok > 1:
    m = (ok+ng)//2
    if need(m):
        ok = m
    else:
        ng = m
print(N - ok - 1)

Submission status: Time Limit Exceeded

Solution code:
from copy import copy
N,K = map(int,input().split())
src = list(map(int,input().split()))
src.sort(reverse=True)

def need(idx):
    a = src[idx]
    if a >= K: return True
    dp = set([0])
    for i in range(N):
        if i == idx: continue
        dp2 = copy(dp)
        b = src[i]
        for v in dp:
            if v+b < K-a:
                dp2.add(v+b)
            elif v+b < K:
                return True
        dp = dp2
    return False

ok = -1
ng = N
while ng-ok > 1:
    m = (ok+ng)//2
    if need(m):
        ok = m
    else:
        ng = m
print(N - ok - 1)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))

dp1 = [[False]*K for _ in range(N)]
dp2 = [[False]*K for _ in range(N)]
# dp[x][y] x枚目まで使った時にyに出来るか
# K-ai <= ai < K となる部分集合を探す
dp1[0][0] = True
if a[0] < K:
    dp1[0][a[0]] = True 
for i in range(1,N):
    for j in range(K):
        dp1[i][j] = dp1[i-1][j] or (j-a[i] >= 0 and dp1[i-1][j-a[i]])

dp2[0][0] = True
if a[N-1] < K:
    dp2[0][a[N-1]] = True
for i in range(1,N):
    for j in range(K):
        dp2[i][j] = dp2[i-1][j] or (j-a[N-i-1] >= 0 and dp2[i-1][j-a[N-i-1]])
count = 0
for i in range(N):
    if K-a[i] <= 0:
        count += 1
        continue
    for j in range(K-a[i],K):
        f = False
        if i == 0:
            if dp2[N-2][j]:
                count += 1
                break
            else:
                continue
        elif i == N-1:
            if dp1[N-2][j]:
                count += 1
                break
            else:
                continue
        for k in range(j+1):
            if dp1[i-1][k] and dp2[N-i-2][j-k]:
                count += 1
                f = True
                break
        if f:
            break
print(N-count)

Submission status: Time Limit Exceeded

Solution code:
import random
N, K = map(int, input().split())
*V, = map(int, input().split())
random.shuffle(V)
A = [0]*(N+1)
B = [0]*(N+1)
MASK = 2**(K+1)-1
A[0] = 1
for i in range(N):
    if K <= V[i]:
        A[i+1] = A[i]
    else:
        A[i+1] = (A[i] | ((A[i] << V[i]) & MASK))
B[N] = 1 << K
for i in range(N-1, -1, -1):
    if K <= V[i]:
        B[i] = B[i+1]
    else:
        B[i] = (B[i+1] | (B[i+1] >> V[i]))

ans = N
for i in range(N):
    if K <= V[i]:
        ans -= 1
        continue
    a = A[i]; b = B[i+1]
    VM = 2**(V[i]+1)-2
    while a and b:
        if a & 1 and b & VM:
            ans -= 1
            break
        l = max((a & -a).bit_length()-1, 1)
        a >>= l; b >>= l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
*V, = map(int, input().split())
V.sort()
A = [0]*(N+1)
B = [0]*(N+1)
MASK = 2**(K+1)-1
A[0] = 1
for i in range(N):
    if K <= V[i]:
        A[i+1] = A[i]
    else:
        A[i+1] = (A[i] | ((A[i] << V[i]) & MASK))
B[N] = 1 << K
for i in range(N-1, -1, -1):
    if K <= V[i]:
        B[i] = B[i+1]
    else:
        B[i] = (B[i+1] | (B[i+1] >> V[i]))

ans = N
for i in range(N):
    if K <= V[i]:
        ans -= 1
        continue
    a = A[i]; b = B[i+1]
    VM = 2**(V[i]+1)-2
    while a and b:
        if a & 1 and b & VM:
            ans -= 1
            break
        l = max((a & -a).bit_length()-1, 1)
        a >>= l; b >>= l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
*V, = map(int, input().split())
V.sort()
A = [0]*(N+1)
B = [0]*(N+1)
MASK = 2**(K+1)-1
A[0] = 1
for i in range(N):
    if K <= V[i]:
        A[i+1] = A[i]
    else:
        A[i+1] = (A[i] | ((A[i] << V[i]) & MASK))
B[N] = 1 << K
for i in range(N-1, -1, -1):
    if K <= V[i]:
        B[i] = B[i+1]
    else:
        B[i] = (B[i+1] | (B[i+1] >> V[i]))

ans = N
for i in range(N):
    if K <= V[i]:
        ans -= 1
        continue
    a = A[i]; b = B[i+1]
    K0 = K-V[i]
    VM = 2**(V[i]+1)-2
    while a and b:
        if a & 1:
            if b & VM:
                ans -= 1
                break
        a >>= 1
        b >>= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
*V, = map(int, input().split())
V.sort()
A = [0]*(N+1)
B = [0]*(N+1)
MASK = 2**(K+1)-1
A[0] = 1
for i in range(N):
    if K <= V[i]:
        A[i+1] = A[i]
    else:
        A[i+1] = (A[i] | ((A[i] << V[i]) & MASK))
B[N] = 1 << K
for i in range(N-1, -1, -1):
    if K <= V[i]:
        B[i] = B[i+1]
    else:
        B[i] = (B[i+1] | (B[i+1] >> V[i]))

ans = N
for i in range(N):
    if K <= V[i]:
        ans -= 1
        continue
    a = A[i]; b = B[i+1]
    t = K
    K0 = K-V[i]
    for s in range(K+1):
        if a & 1 == 0:
            a >>= 1
            if not a: break
            continue
        while b and (s + t >= K or b & 1 == 0):
            t -= 1
            b >>= 1
        if not b: break
        if K0 <= s + t:
            ans -= 1
            break
        a >>= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
*V, = map(int, input().split())
V.sort()
A = [0]*(N+1)
B = [0]*(N+1)
MASK = 2**(K+1)-1
A[0] = 1
for i in range(N):
    if K <= V[i]:
        A[i+1] = A[i]
    else:
        A[i+1] = (A[i] | (A[i] << V[i])) & MASK
B[N] = 1 << K
for i in range(N-1, -1, -1):
    if K <= V[i]:
        B[i] = B[i+1]
    else:
        B[i] = (B[i+1] | (B[i+1] >> V[i])) & MASK

ans = N
for i in range(N):
    a = A[i]; b = B[i+1]
    t = K
    K0 = K-V[i]
    for s in range(K+1):
        if a & 1 == 0:
            a >>= 1
            if not a: break
            continue
        while t > -1 and (s + t >= K or b & 1 == 0):
            t -= 1
            b >>= 1
        if not b: break
        if K0 <= s + t:
            ans -= 1
            break
        a >>= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
*V, = map(int, input().split())
A = [0]*(N+1)
B = [0]*(N+1)
MASK = 2**(K+1)-1
A[0] = 1
for i in range(N):
    if K <= V[i]:
        A[i+1] = A[i]
    else:
        A[i+1] = (A[i] | (A[i] << V[i])) & MASK
B[N] = 1 << K
for i in range(N-1, -1, -1):
    if K <= V[i]:
        B[i] = B[i+1]
    else:
        B[i] = (B[i+1] | (B[i+1] >> V[i])) & MASK

ans = N
for i in range(N):
    a = A[i]; b = B[i+1]
    t = K
    K0 = K-V[i]
    for s in range(K+1):
        if a & 1 == 0:
            a >>= 1
            if not a: break
            continue
        while t > -1 and (s + t >= K or b & 1 == 0):
            t -= 1
            b >>= 1
        if not b: break
        if K0 <= s + t:
            ans -= 1
            break
        a >>= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
*V, = map(int, input().split())
A = [0]*(N+1)
B = [0]*(N+1)
MASK = 2**(K+1)-1
A[0] = 1
for i in range(N):
    if K <= V[i]:
        A[i+1] = A[i]
    else:
        A[i+1] = (A[i] | (A[i] << V[i])) & MASK
B[N] = 1 << K
for i in range(N-1, -1, -1):
    if K <= V[i]:
        B[i] = B[i+1]
    else:
        B[i] = (B[i+1] | (B[i+1] >> V[i])) & MASK

ans = N
for i in range(N):
    a = A[i]; b = B[i+1]
    t = K
    r = 0
    for s in range(K+1):
        if a & 1 == 0:
            a >>= 1
            continue
        while t > -1 and (s + t >= K or b & 1 == 0):
            t -= 1
            b >>= 1
        if t == -1:
            break
        r = max(r, s + t)
        a >>= 1
    if K-V[i] <= r < K:
        ans -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
*V, = map(int, input().split())
A = [0]*(N+1)
B = [0]*(N+1)
MASK = 2**(K+1)-1
A[0] = 1
for i in range(N):
    A[i+1] = (A[i] | (A[i] << min(K, V[i]))) & MASK
B[N] = 1
for i in range(N-1, -1, -1):
    B[i] = (B[i+1] | (B[i+1] << min(K, V[i]))) & MASK

ans = N
for i in range(N):
    a = A[i]; b = B[i+1]
    t = K
    r = 0
    for s in range(K+1):
        if a & (1 << s) == 0:
            continue
        while t > -1 and (s + t >= K or b & (1 << t) == 0):
            t -= 1
        if t == -1:
            break
        r = max(r, s + t)
    if K-V[i] <= r < K:
        ans -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

l, r = -1, N
m = (l + r) // 2

def check(m):
    global K, N
    dp = set()
    dp.add(0)
    for i in range(N):
        if i == m:
            continue
        s = set()
        for d in dp:
            s.add(d)
            if d + a[i] < K:
                s.add(d + a[i])
        dp = s
    for d in dp:
        if d + a[m] >= K:
            return True
    return False

while r - l > 1:
    if check(m):
        l = m
    else:
        r = m
    m = (l + r) // 2
print(N-m-1)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

l, r = -1, N
m = (l + r) // 2

def check(m):
    global K, N
    dp = [0] * (K+1)
    dp[0] = True
    for i in range(N):
        if i == m:
            continue
        for j in range(K-1, -1, -1):
            if j + a[i] >= K:
                dp[K] = dp[K] or dp[j]
            else:
                dp[j+a[i]] = dp[j+a[i]] or dp[j]
    for j in range(K-1, -1, -1):
        if dp[j] and j + a[m] >= K:
            # print('j: %d, a[m]: %d' % (j, a[m]))
            return True
    return False

while r - l > 1:
    if check(m):
        l = m
    else:
        r = m
    m = (l + r) // 2
print(N-m-1)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))

a = sorted(a)
ans = N
for i in range(N-1, -1, -1) :
    psum = 0
    for j in range(i, -1, -1) :
        if psum+a[j] < K :
            psum += a[j]
        else :
            ans = min(ans, j)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

def isNecessary(now) :
    psum = 0
    for i in range(N) :
        if i == now :
            continue
        psum += a[i]
        if psum >= K :
            return False
    else :
        return True

S = sum(a)
ans = 0
a = sorted(a, reverse=True)
l, r = 0, N-1
now = N//2
while True :
    if isNecessary(now) :
        r = now
    else :
        l = now
    now = (l+r)//2
    if r == l :
        if N==1 and a[0]<K :
            print(1)
        else :
            print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
N,K=map(int, input().split())
a=list(map(int, input().split()))
sum=0
for i in range(0,N):
  sum+=a[i]
if sum<K:#全部不必要
  print(N)
  sys.exit()
if sum==K:#全部必要
  print(0)
  sys.exit()
a.sort()
a.reverse()

#K未満の最大の数字のラベルはどこ？
l=N
for i in range(N-1,-1,-1):
  if a[i]<K:
    l=i
  else:
    break

if l==N:
  print(0)
  sys.exit()

count=N
#lまでの要素が必要か不要かチェック(使いまわし可能)
sum=0
for j in range(l,N):
  if sum+a[j]<K:
    sum+=a[j]
for i in range(0,l):  
  if sum+a[i]>=K:#必要ってことだ
    count-=1
#lからの要素は自分のことを抜かないといけないことに注意
for i in range(l,N):
  sum=0
  b=a[:]
  C=b.pop(i)
  for j in range(l-1,N-1):
    if sum+b[j]<K:
      sum+=b[j]
  if sum+C>=K:#必要ってことだ
    count-=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
N,K=map(int, input().split())
a=list(map(int, input().split()))
sum=0
for i in range(0,N):
  sum+=a[i]
if sum<K:#全部不必要
  print(N)
  sys.exit()
if sum==K:#全部必要
  print(0)
  sys.exit()
a.sort()
a.reverse()

#K未満の最大の数字のラベルはどこ？
l=N
for i in range(N-1,-1,-1):
  if a[i]<K:
    l=i
  else:
    break

if l==N:
  print(0)
  sys.exit()

count=N
#lまでの要素が必要か不要かチェック
for i in range(0,l):
  sum=0
  for j in range(l,N):
    if sum+a[j]<K:
      sum+=a[j]
  if sum+a[i]>=K:#必要ってことだ
    count-=1
#lからの要素は自分のことを抜かないといけないことに注意
for i in range(l,N):
  sum=0
  b=a[:]
  C=b.pop(i)
  for j in range(l-1,N-1):
    if sum+b[j]<K:
      sum+=b[j]
  if sum+C>=K:#必要ってことだ
    count-=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
#ABC56 D input
nk = list(map(int, input().split()))
N = nk[0]
K = nk[1]

A = sorted(list(map(int, input().split())))

count = 0
for a in A:
    new_a = A[:]
    new_a.remove(a)
    dp = [[-1 for i in range(N)] for j in range(K+1)]
    for i in range(N):
        dp[0][i] = True
    for i in range(1,K+1):
        dp[i][0] = False
    
    for i in range(1,K+1):
        for j in range(1, N):
            dp[i][j] = dp[i][j-1]
            if(i >= new_a[j-1]):
                dp[i][j] = dp[i][j] or dp[i-new_a[j-1]][j-1]
    res = False         
    for i in range(K-a,K):
        if(i >= 0):
            res = res or dp[i][N-1]
    
    if(res == False):
        count += 1
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, raw_input().split())
a = map(int, raw_input().split())

ans = 0
for i, ai in enumerate(a):
    s = set([ai])
    for j, bi in enumerate(a):
        ss = s.copy()
        if i == j: continue
        for val in s:
            ss.add(val + bi)
        s = ss
    for val in s:
        if val >= K and val - ai < K: break
    else:
        ans += 1
print ans

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split(' '))
a = list(map(int,input().split(' ')))

result = 0
for i in range(n):
    buf = a[:i]+a[i+1:]
    dp = [0]
    for j in range(n-1):
        buf2 = [dp[k]+buf[j] for k in range(j+1)]
        buf2 = [-1 if buf2_ >= k else buf2_ for buf2_ in buf2]
        dp.append(max(buf2))
    if max(dp) + a[i] < k:
        result += 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

N,K = map(int,raw_input().split())
lines = map(int,raw_input().split())

lines.sort(reverse=True)

ans = 0

for i in range(N):
    sum = 0
    for j in range(i,N):
            sum += lines[j]
            if sum >= K:
                ans = max(ans, j+1)
                sum -= lines[j]

print(N-ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

n, k = map(int, input().split())
cards = list(map(int, input().split()))

needs = 0
dp = [[False for _ in range(k)] for _ in range(n + 1)]
dp2 = [[False for _ in range(k)] for _ in range(n + 1)]

for l in range(n + 1):
    dp[l][0], dp2[l][0] = True, True

for i in range(1, n + 1):
    for j in range(1, k):
        prev = False if j - cards[i - 1] < 0 else dp[i - 1][j - cards[i - 1]]
        if dp[i - 1][j] or prev:
            dp[i][j] = True

        prev2 = False if j - cards[n - i] < 0 else dp2[i - 1][j - cards[n - i]]
        if dp2[i - 1][j] or prev2:
            dp2[i][j] = True

for i, val in enumerate(cards):
    if val >= k:
        needs += 1
        continue

    b = False
    for nv in range(k - val, k):
        if i == 0:
            if dp2[n - 1][nv]:
                needs += 1
                b = True
                break
            continue

        if i == n - 1:
            if dp[n - 1][nv]:
                needs += 1
                b = True
                break
            continue

        for nv2 in range(nv + 1):
            if dp[i][nv2] and dp2[n - i - 1][nv - nv2]:
                b = True
                needs += 1
                break
        if b: break

print(n - needs)

Submission status: Time Limit Exceeded

Solution code:



n, k = map(int, input().split())
cards = list(map(int, input().split()))

needs = 0
dp = [[False for _ in range(k)] for _ in range(n + 1)]
dp2 = [[False for _ in range(k)] for _ in range(n + 1)]
for l in range(n + 1):
    dp[l][0], dp2[l][0] = True, True

for i in range(1, n + 1):
    for j in range(1, k):
        prev = False if j - cards[i - 1] < 0 else dp[i - 1][j - cards[i - 1]]
        dp[i][j] = dp[i - 1][j] or prev

        prev2 = False if j - cards[n - i] < 0 else dp2[i - 1][j - cards[n - i]]
        dp2[i][j] = dp2[i - 1][j] or prev2

for i, val in enumerate(cards):
    if val >= k:
        needs += 1
        continue

    b = False
    for x, xb in enumerate(dp[i]):
        for y, yb in enumerate(dp2[n - i - 1]):
            if k - val <= x + y < k and xb and yb:
                b = True
                break

        if b:
            needs += 1
            break

print(n - needs)