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: Wrong Answer

Solution code:
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
if N==1:
    if K-a[0]<=0:
        print(1)
    else:
        print(0)
    exit()
def dp(i):
    res=[[0 for k in range(K)] for j in range(N-1)]
    L=[]
    for j in range(N):
        if i!=j:
            L.append(j)
    for j in range(N-1):
        for k in range(K):
            if j==0:
                if k==a[L[j]] or k==0:
                    res[j][k]=1
                else:
                    res[j][k]=0
                continue
            if res[j-1][k]==1:
                if k+a[L[j]]<K:
                    res[j][k+a[L[j]]]=1
                res[j][k]=1
    return res

def check(i):
    table=dp(i)[N-2]
    for j in range(max(K-a[i],0),K):
        if table[j]==1:
            return False
    return True
X=sorted([(a[i],i) for i in range(N)])
low=-1
high=N
while((high-low)>1):
    mid=(high+low)//2
    #range(low,mid) or range(mid,high)
    flag=check(X[mid][1])
    if flag:
        low=mid
    else:
        high=mid
print(low+1)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
x=[int(p) for p in input().split()]
x.sort()
x = x[::-1]
pp=0
ans=0
print(x)
for a in x:
  if pp+a < K:
    pp+=a
    ans+=1
  else:
    ans=0
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
x=[int(p) for p in input().split()]
x.sort()
x = x[::-1]
pp=0
ans=0
print(x)
for a in x:
  print(ans)
  if pp+a < K:
    pp+=a
    ans+=1
  else:
    ans=0
print(ans)

Submission status: Wrong Answer

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

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

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

aN.sort(reverse=True)

need = [False] * N
for i in range(N):
    if aN[i] >= K:
        need[i] = True
    else:
        sm = aN[i]
        for j in range(i+1, N):
            sm += aN[j]
            # 複数で条件を満たせば、それに含まれるものは必要
            if sm >= K:
                for k in range(i, j+1):
                    need[k] = True
                break
print(need.count(False))

Submission status: Wrong Answer

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

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

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

aN.sort(reverse=True)

need = [False] * N
for i in range(N):
    if need[i]:
        continue
    if aN[i] >= K:
        need[i] = True
    else:
        sm = aN[i]
        for j in range(i+1, N):
            sm += aN[j]
            # 複数で条件を満たせば、それに含まれるものは必要
            if sm >= K:
                for k in range(i, j+1):
                    need[k] = True
                break
print(need.count(False))

Submission status: Wrong Answer

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

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

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

aN.sort(reverse=True)

need = [False] * N
for i in range(N):
    if need[i]:
        continue
    if aN[i] >= K:
        need[i] = True
    else:
        sm = aN[i]
        need[i] = True
        for j in range(i+1, N):
            sm += aN[j]
            need[j] = True
            if sm >= K:
                break
        # 最後まで見てもダメだったらこの先は全部いらない
        else:
            for k in range(i, N):
                need[k] = False
            print(need.count(False))
            exit()
print(need.count(False))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))

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

need = 0
for n in range(N):  # 何枚目のカードについての判定か
    # dp1[k]:= 1 ~ i - 1までのカードを使って数jが作れるか
    dp1 = [0] * (K + 1)
    dp1[0] = 1
    for i in range(n):
        for j in range(K, -1, -1):
            if A[i] > j:
                continue
            dp1[j] = dp1[j - A[i]]

    # dp2[k] := N ~ i + 1までのカードを使って数jが作れるか
    dp2 = [0] * (K + 1)
    dp2[0] = 1
    for i in range(n + 1, N):
        for j in range(K, -1, -1):
            if A[i] > j:
                continue
            dp2[j] = dp2[j - A[i]]
    dp2 = list(accumulate(dp2))

    for k in range(K + 1):
        # 1 ~ i - 1番目まででkが作れない
        if not dp1[k]:
            continue

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

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

        # 累積和を用いてkと組み合わせて、条件の範囲内に対応する値がN ~ i + 1までのカードで作れるかを判定
        if dp2[K - k] - dp2[K - A[n] - k - 1] > 0:
            need += 1
            break

print(N - need)

Submission status: Wrong Answer

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

# すべての数が必要（どうやってもよい集合を作れない）
if sum(A) <= K:
    print(0)
    exit()
    
# K以上の数は常に必要
A = sorted([a for a in A if a < K])

# すべての数が必要(どの1枚をとってもよい集合)
if not A:
    print(0)
    exit()

# 絶対に不要な数0、絶対に必要な数を架空のカードとして追加
A = [0] + A + [float('inf')]

N = len(A)
# にぶたん: 数Xが不要である
ok, ng = -1, N  # indexで管理することに注意
while abs(ok - ng) > 1:
    Xi = (ok + ng) // 2
    X = A[Xi]    # X抜きのリストを作る
    A2 = A[:]
    A2.remove(X)

    # dp[j] := 数jが作れるか
    dp = [False] * (K + 1)
    dp[0] = True
    flg = False  # 二重ループ抜け用

    for i in range(N - 1):
        for j in range(K + 1)[::-1]:
            # 架空のカードは使わない
            if A2[i] in (0, float('inf')):
                continue

            # 数hが作れるか判定するのにjより大きな数は調べる意味がない
            if A2[i] > j:
                continue

            dp[j] = dp[j - A2[i]]
            if dp[j] and K - X <= j < K:
                ng = Xi
                flg = True
                break

        if flg:
            flg = False
            break
    else:
        ok = Xi

print(ok)

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # K以上の数は常に必要
    A = sorted([a for a in A if a < K])
    
    # 絶対に不要な数0、絶対に必要な数を架空のカードとして追加
    A = [0] + A + [float('inf')]
    
    N = len(A)
    # にぶたん: 数Xが不要である
    ok, ng = -1, N  # indexで管理することに注意
    while abs(ok - ng) > 1:
        Xi = (ok + ng) // 2
        X = A[Xi]    # X抜きのリストを作る
        A2 = A[:]
        A2.remove(X)
    
        creatable = {0}
        flg = False  # 二重ループ抜け用
        for a in A2:
            # 架空のカードははじく
            if a == 0 or a == float('inf'):
                continue
    
            tmp = set()
            for n in creatable:
                # Xは必要
                if K - X <= n + a < K:
                    ng = Xi
                    flg = True
                    break
    
                else:
                    tmp.add(n)
                    tmp.add(n + a)
    
            if flg:
                break
            creatable = tmp
    
        else:
            # Xは不要
            ok = Xi
    
    print(ok)

main()

Submission status: Wrong Answer

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

# K以上の数は常に必要
A = sorted([a for a in A if a < K])

# 絶対に不要な数0、絶対に必要な数を架空のカードとして追加
A = [0] + A + [float('inf')]

N = len(A)
# にぶたん: 数Xが不要である
ok, ng = 0, N  # indexで管理することに注意
while abs(ok - ng) > 1:
    Xi = (ok + ng) // 2
    X = A[Xi]

    # X抜きのリストを作る
    A2 = A[:]
    A2.remove(X)

    creatable = {0}
    flg = False  # 二重ループ抜け用
    for a in A2:
        # 架空のカードははじく
        if a == 0 or a == float('inf'):
            continue

        tmp = set()
        for n in creatable:
            # Xは必要
            if K - X <= n + a < K:
                ng = Xi
                flg = True
                break

            else:
                tmp.add(n)
                tmp.add(n + a)

        if flg:
            break
        creatable = tmp

    else:
        # Xは不要
        ok = Xi

print(ok)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if a[0] >= K:
    print(0)
    exit()

a = [a[i] for i in range(N) if a[i]<K]
a.reverse()
N = len(a)
ans = N
dp = [False]*K
dp[0] = True
Smax = 0
for i,a_ in reversed(list(enumerate(a))):
    if Smax + a_ >= K:
        ans = i
    updated = True
    for j in range(min(Smax,K-a_-1),-1,-1):
        if dp[j]:
            dp[j+a_]=True
            if updated:
                Smax = max(Smax,j+a_)
                updated = False

print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if a[0] >= K:
    print(0)
    exit()
elif sum(a) < K:
    print(N)
    exit()
a = [a[i] for i in range(N) if a[i]<K]
N = len(a)
dp = [[0]*(K+1) for i in range(N+1)]
for i in range(N):
    i = N-i-1
    for j in range(K):
        if j < a[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-a[i]]+a[i])
print(0)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if a[0] >= K:
    print(0)
    exit()
elif sum(a) < K:
    print(N)
    exit()

dp = [[0]*(K+1) for i in range(N+1)]
for i in range(N):
    i = N-i-1
    for j in range(K):
        if j < a[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-a[i]]+a[i])
print(0)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
w = 0
for i in range(N):
    w += a[i]
    if w >= K:
        break
if w < K:
    print(N)
elif i==0:
    print(0)
else:
    a = a[:i+1]
    for j in range(i):
        w -= a[j]
        if w < K:
            break
    print(j)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
N, K = map( int, input().split())
A = list( map( int, input().split()))
ans = N
for i in range(N):
    B = [0]
    V = [0]*(K+1)
    for j in range(N):
        if j == i:
            continue
        a = A[j]
        C = []
        for b in B:
            if b + a <= K:
                if V[b+a] == 0:
                    V[b+a] = b+a
                    C.append(b+a)
        B = deepcopy(C)
    v = max(V)
    if v < K and K <= v+A[i]:
        ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [int(_) for _ in input().split()]
A.sort()
Inf = 5001

def DP(i, K, memo = {}):
    if i == 0 and K == 0:
        return 0
    elif i == 0:
        return Inf
    elif K <= A[i-1]:
        return 1
    try:
        return memo[(i, K)]
    except KeyError:
        if K - A[i-1] >= 0:
            ret = min(DP(i-1, K, memo), DP(i-1, K-A[i-1], memo) + 1)
        else:
            ret = DP(i-1, K, memo)
        memo[(i, K)] = ret
        return ret

memo = {}
if sum(A) < K:
    print(N)
else:
    for i in range(N):
        if DP(i+1, K, memo) < Inf:
            print(i+1 - DP(i+1, K, memo))
            break

Submission status: Wrong Answer

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()
                
cnt = Counter(a_ltk)
ans = 0

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

Submission status: Wrong Answer

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
            break
                
cnt = Counter(a_ltk)
ans = 0

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

Submission status: Wrong Answer

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

a = sorted(a)[::-1]
ans = n
sm = 0

for i in range(0, n):
    if sm + a[i] < k:
        sm += a[i];
    else:
        ans = min(ans, i);

print(ans)

Submission status: Wrong Answer

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


@mt
def slv(N, K, A):
    A.sort()

    s = 0
    ans = N
    for i in range(N-1, -1, -1):
        if s + A[i] < K:
            s += A[i]
        else:
            ans = i
            break
    return ans


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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 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

        print(w, dp, dp[K-A[w]:])
        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))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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 slv(N, K, A):
    @lru_cache(maxsize=None)
    def f(w):
        if K - A[w] < 0:
            return True
        dp = [False] * (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] = True
            if a < K:
                tdp[a] = True
            dp = tdp

        for b in dp[K-A[w]:]:
            if b:
                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))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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 slv(N, K, A):
    def f(w):
        dp = [False] * (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] = True
            if a < K:
                tdp[a] = True
            dp = tdp

        for b in dp[K-A[w]:]:
            if b:
                return True

        return False

    A.sort()
    l = 0
    r = N-1
    while r-l > 1:

        if f((l+r)//2):
            r = (l+r)//2
        else:
            l = (l+r)//2

    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))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,K = inpl()
aa = inpl()

ans = SUM = 0
l = r = 0
hituyou = [0]*N
for l in range(N):
	while SUM < K and r < N:
		SUM += aa[r]
		r += 1
	if r == N and SUM < K:
		break

	for i in range(l,r):
		if SUM - aa[i] < K:
			hituyou[i] = 1

	SUM -= aa[l]

print(N-sum(hituyou))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,K = inpl()
aa = inpl()

if sum(aa) < K:
	print(N)
else:
	ans = 0
	l = r = 0
	SUM = 0
	for l in range(N):
		while SUM < K and r < N:
			SUM += aa[r]
			r += 1

		if SUM - aa[l] > K:
			ans +=  1
		SUM -= aa[l]
		
	print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(N):
    b = a[:i] + a[i + 1:]

    dp = [[False for _ in range(K + 1)] for _ in range(N)]
    for x in range(N):
        dp[x][0] = True

    for x in range(N - 1):
        for y in range(K + 1):
            if dp[x][y]:
                dp[x + 1][y] = dp[x][y]
            if y + b[x] <= K:
                dp[x + 1][y + b[x]] = dp[x][y]

    if sum(dp[N - 1][K - a[i]:K]) == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))

    a = sorted(a)
    re = a[::-1]

    ans = n
    for i in range(n):
        wa = 0
        for j in range(i,n):
            wa += re[j]
            if wa >= k:
                ans = n - j -1
                break

        if wa < k:
            #print(ans)
            break

    for i in a[:ans]:
        tmp = a.count(i)
        if tmp > 1:
            ans+= (tmp-1)

    print(ans)

if __name__ == "__main__":
        main()

Submission status: Wrong Answer

Solution code:

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))

    re = sorted(a)[::-1]

    ans = n
    for i in range(n):
        wa = 0
        for j in range(i,n):
            wa += re[j]
            if wa >= k:
                ans = n - j -1
                break

        if wa < k:
            print(ans)
            exit()


if __name__ == "__main__":
        main()

Submission status: Wrong Answer

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

if src[-1] >= K:
    print(0)
    exit()
sm = 0
for i,a in enumerate(src):
    if a >= K: continue
    sm += a
    if sm >= K:
        print(N-i-1)
        exit()
print(N)

Submission status: Wrong Answer

Solution code:
import bisect
N, K = map(int, input().split())
a = sorted(map(int, input().split()))

# K以上のカードは単体で条件を満たすから考えない
A = a[:bisect.bisect_left(a, K, lo=0, hi=N)][::-1]

tmp = 0
result = 0
tmp_n = 0
tmp_card = float("inf")
for i in A:
    if tmp_card!=i:
        result += 1
    if tmp+i >= K:
        tmp -= A[tmp_n]
        tmp_n += 1
        result = 0
        tmp_card = i
    tmp += i

print(result)

Submission status: Wrong Answer

Solution code:
import bisect
N, K = map(int, input().split())
a = sorted(map(int, input().split()))

# K以上のカードは単体で条件を満たすから考えない
A = a[:bisect.bisect_left(a, K, lo=0, hi=N)][::-1]

tmp = 0
result = 0
tmp_n = 0

for i in A:
    result += 1
    if tmp+i >= K:
        tmp -= A[tmp_n]
        tmp_n += 1
        result = 0
    tmp += i
print(result)

Submission status: Wrong Answer

Solution code:
import bisect
N,K = map(int, input().split())
a = sorted(map(int, input().split()))

# K以上のカードは単体で条件を満たすから考えない
A = a[:bisect.bisect_left(a, K, lo=0, hi=N)]

tmp = 0
result = 0
for n, i in enumerate(A[::-1]):
    if tmp + i <= K:
        tmp += i
    else:
        result += 1

if sum(a) < K:
    print(N)
else:
    print(result)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
a_sum = sum(a)
if a_sum < K:
    print(N)
    exit()
if a_sum == K:
    print(0)
    exit()
count = 0
for i in a:
    if a_sum - i >= K:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
a_sum = sum(a)
if a_sum < K:
    print(N)
    exit()
if a_sum == K:
    print(0)
    exit()
count = 0
L = [i for i in a if i < K]
L_sum = sum(L)
if L_sum < K:
    print(len(L))
    exit()
if L_sum == K:
    print(0)
    exit()
for i in L:
    if L_sum - i >= K:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n,k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
a,num,ans = sorted(a),0,0
for i in range(n-1,-1,-1):
	if num+a[i]<k: num+=a[i]
	else: ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
n,k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
a.sort()
a,flag = a[:bisect_left(a,k)][::-1],False
if a: b = [a[0]]
for i in range(1,len(a)):
	b.append(b[-1]+a[i])
	if b[-1]>=k:
		flag = True
		break
if flag: print(len(a)-(i+1))
else: print(len(a))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
j = sorted(list(map(int, input().split())))
ans = n
j = list(filter(lambda x: x<k, j))
for i in range(len(j)):
    tmp = 0
    for m in range(i, len(j)):
        tmp += j[m]
        if tmp >= k:
            for h in range(m - i):
                tmp -= j[h]
                if tmp < k:
                    print(i+h)
                    exit()
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
j = sorted(list(map(int, input().split())))
ans = n
for i in range(n-1):
    if sum(j[i:i+2]) >= k:
        ans = i
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import random
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]))

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
    l = 1
    while a and b and l:
        if a & 1 and b & VM:
            ans -= 1
            break
        l = max((a & -a).bit_length()-1, (b & -b).bit_length()-V[i])
        a >>= l; b >>= l
print(ans)

Submission status: Wrong Answer

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.bit_length()-1, 1)
        a >>= l; b >>= l
print(ans)

Submission status: Wrong Answer

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
    l = 1
    while a and b and l:
        if a & 1 and b & VM:
            ans -= 1
            break
        l = a.bit_length()-1
        a >>= l; b >>= l
print(ans)