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:
import collections
N, K = map(int, input().split())
a = [int(x) for x in input().split() if int(x) < K]
a.sort()

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


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

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

Submission status: Time Limit Exceeded

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

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


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

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

Submission status: Time Limit Exceeded

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

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

def judge(a, dp, K): #aが必要(True)か不必要(False)か
    for i in range(K-a,K):
        if dp[i]:
            return True 
    return False

def binary_tree(List, base_List, K): #2分木探索
    if len(List) == 0: return 0
    center = len(List)//2 #2分する支点
    dp = {}
    dp = collections.defaultdict(lambda:False)
    dp[0] = True
    List_without_center = base_List.copy()
    List_without_center.remove(List[center])
    dp = renew_dp(dp, List_without_center, K) #dp更新
    if len(List) == 1: #2分木のゴール
        if judge(List[center], dp, K):
            result = center
        else:
            result = center+1
    else: #再帰的に探索
        if judge(List[center], dp, K):
            result = binary_tree(List[:center], base_List, K)
        else:
            result = binary_tree(List[center:], base_List, K) + center
    return result

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

Submission status: Time Limit Exceeded

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

ok = n
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2

    dp = [[False for j in range(k)] for i in range(n + 1)]
    dp[0][0] = True

    for i in range(n):
        for j in range(k):
            dp[i + 1][j] = dp[i + 1][j] or dp[i][j]
            if i != mid and j + a[i] < k:
                dp[i + 1][j + a[i]] = dp[i + 1][j + a[i]] or dp[i][j]
    
    flg = False
    for j in range(max(0, k - a[mid]), k):
        if dp[n][j]:
            flg = True
            break
    
    if flg:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    A.sort()
    mask = (1 << K) - 1

    noneed = -1; need = N
    while(need-noneed>1):
        #print(noneed,need)
        i = (need+noneed)//2
        if A[i]>=K:
            is_need = True
        else:
            dp = 1
            for j in range(N):
                a = A[j]
                if i == j:
                    continue
                dp |= ((dp << a) & mask)
            # print(dp,mask)

            val = max(i for i in range(K) if (dp >> i) & 1)


            is_need = (val+A[i]>=K)

            # print(is_need,i)

        if is_need:
            need = i
        else:
            noneed = i

    ans = noneed + 1

    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    A.sort()
    mask = (1 << K) - 1

    noneed = -1; need = N
    while(need-noneed>1):
        #print(noneed,need)
        i = (need+noneed)//2
        if A[i]>=K:
            is_need = True
        else:
            dp = 1
            for j in range(N):
                a = A[j]
                if i == j:
                    continue
                dp |= ((dp << a) & mask)
            # print(dp,mask)

            is_need = (dp > mask>>A[i])

            # print(is_need,i)

        if is_need:
            need = i
        else:
            noneed = i

    ans = noneed + 1

    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    A.sort()
    mask = (1 << K) - 1
    
    noneed = -1; need = N
    while(need-noneed>1):
        #print(noneed,need)
        i = (need+noneed)//2
        if A[i]>=K:
            is_need = True
        else:
            dp = 1
            for j in range(N):
                a = A[j]
                if i == j:
                    continue
                dp |= ((dp << a) & mask)
            # print(dp,mask)

            is_need = ((dp << (A[i])) > mask)

            # print(is_need,i)

        if is_need:
            need = i
        else:
            noneed = i

    ans = noneed + 1
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    A.sort()
    mask = (1 << K) - 1
    
    noneed = -1; need = N
    while(need-noneed>1):
        #print(noneed,need)
        i = (need+noneed)//2
        dp = 1
        for j in range(N):
            a = A[j]
            if i==j:
                continue
            dp |= ((dp<<a)&mask)
        #print(dp,mask)

        is_need = ((dp<<(A[i]))>mask)

        #print(is_need,i)

        if is_need:
            need = i
        else:
            noneed = i

    ans = noneed + 1
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    A.sort()
    mask = (1 << (K + 1)) - 1

    dp_L = [0]*(N+1)
    dp_R = [0]*(N+1)
    dp_L[0] = 1
    dp_R[N] = 1

    for i in range(N):
        a = A[i]
        dp_L[i+1] = dp_L[i]|((dp_L[i]<<a)&mask)

    for i in range(N)[::-1]:
        a = A[i]
        dp_R[i] = dp_R[i+1]|((dp_R[i+1]<<a)&mask)


    #print(dp_L)
    #print(dp_R)
    
    noneed = -1; need = N
    while(need-noneed>1):
        i = (need+noneed)//2
        a = A[i]
        is_need = False
        L = dp_L[i]
        R = dp_R[i+1]
        l = 0; r = K
        while(l<K):
            while ((not L&(1<<l)) and l<K):
                l += 1
            while((not R&(1<<r)) or (0<r and K<=l+r)):
                r -= 1
            #print(l,r)
            if r<0:
                break
            if K<=l+r:
                break

            if K<=l+r+a:
                is_need = True
                break

            l += 1

        if is_need:
            need = i
        else:
            noneed = i

    ans = noneed + 1
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    A.sort()
    dp_L = [set() for _ in range(N+1)]
    dp_R = [set() for _ in range(N+1)]
    dp_L[0].add(0)
    dp_R[N].add(0)
    for i in range(N):
        a = A[i]
        for n in dp_L[i]:
            dp_L[i+1].add(n)
            if n+a<K:
                dp_L[i+1].add(n+a)

    for i in range(N)[::-1]:
        a = A[i]
        for n in dp_R[i+1]:
            dp_R[i].add(n)
            if n+a<K:
                dp_R[i].add(n+a)

    for i in range(N+1):
        dp_L[i] = list(dp_L[i])
        dp_R[i] = list(dp_R[i])

    #print(dp_L)
    #print(dp_R)
    cnt = 0

    for i in range(N):
        a = A[i]
        flag = True
        L = dp_L[i]
        R = dp_R[i+1]
        l = 0; r = len(R)-1
        while(l<len(L)):
            while(0<r and K<=L[l]+R[r]):
                r -= 1
            #print(L[l]+R[r],l,r)
            if K<=L[l]+R[r]:
                break

            if K<=L[l]+R[r]+a:
                flag = False
                break

            l += 1

        if flag:
            cnt += 1
        else:
            break

    ans = cnt
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
mask = (1<<(k+1)) - 1
def sub(ii):
    dp = 1
    for i in range(n):
        if i==ii:
            continue
        dp |= (dp<<a[i]) & mask
#         for j in range(k-1, a[i]-1, -1):
#             dp[j] += dp[j-a[i]]
    val = max(i for i in range(k) if (dp>>i)&1)
    return val+a[ii]>=k
if sub(0):
    ans = 0
elif not sub(n-1):
    ans = n
else:
    l = 0
    r = n-1
    while l<r-1:
        m = (l+r)//2
        if sub(m):
            r = m
        else:
            l = m
    ans = l+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
def sub(ii):
    dp = 1
    mask = (1<<(k+1)) - 1
    for i in range(n):
        if i==ii:
            continue
        dp |= dp<<a[i]
        dp &= mask
#         for j in range(k-1, a[i]-1, -1):
#             dp[j] += dp[j-a[i]]
    val = max(i for i in range(k) if (dp>>i)&1)
    return val+a[ii]>=k
if sub(0):
    ans = 0
elif not sub(n-1):
    ans = n
else:
    l = 0
    r = n-1
    while l<r-1:
        m = (l+r)//2
        if sub(m):
            r = m
        else:
            l = m
    ans = l+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
def sub(ii):
    dp = 1
    for i in range(n):
        if i==ii:
            continue
        dp |= dp<<a[i]
#         for j in range(k-1, a[i]-1, -1):
#             dp[j] += dp[j-a[i]]
    val = max(i for i in range(k) if (dp>>i)&1)
    return val+a[ii]>=k
if sub(0):
    ans = 0
elif not sub(n-1):
    ans = n
else:
    l = 0
    r = n-1
    while l<r-1:
        m = (l+r)//2
        if sub(m):
            r = m
        else:
            l = m
    ans = l+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
def sub(ii):
    dp = [0]*(k)
    dp[0] = 1
    for i in range(n):
        if i==ii:
            continue
        for j in range(k-1, a[i]-1, -1):
            dp[j] += dp[j-a[i]]
    val = max(i for i in range(k) if dp[i]>0)
    return val+a[ii]>=k
if sub(0):
    ans = 0
elif not sub(n-1):
    ans = n
else:
    l = 0
    r = n-1
    while l<r-1:
        m = (l+r)//2
        if sub(m):
            r = m
        else:
            l = m
    ans = l+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys





def main():
    def mkns(a,s,m):
        if a==0:
            return s
        else:
            return (((s+1)<<a)|s) & m
    def biser(lst,func):
            n=len(lst)
            nh=n//2
            if n==1:
                if func(lst[0]):
                    return lst[0]
                else:
                    return -1
            if func(lst[nh]):
                return biser(lst[nh:],func)
            else:
                return biser(lst[:nh],func)
    
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    def isunnec(i): 
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=mkns(a[j],ss[i],pm)
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    
    for i in range(N):
         if a[i]>=K:
             break
         ss[i+1]=mkns(a[i],ss[i],pm)
         if isunnec(i):
             nn+=1
    print(nn)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        if func(lst[0]):
            return lst[0]
        else:
            return -1
    if func(lst[nh]):
        return biser(lst[nh:],func)
    else:
        return biser(lst[:nh],func)

def mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    def isunnec(i): 
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=(((ss[i]+1)<<a[j])|ss[i]) & pm
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    
    for i in range(N):
        if a[i]>=K:
            break
        ss[i+1]=(((ss[i]+1)<<a[i])|ss[i]) & pm
        if isunnec(i):
            nn+=1
    print(nn)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        if func(lst[0]):
            return lst[0]
        else:
            return -1
    if func(lst[nh]):
        return biser(lst[nh:],func)
    else:
        return biser(lst[:nh],func)

def mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    def isunnec(i): 
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=mkns(a[j],ss[i],pm)
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    
    for i in range(N):
         if a[i]>=K:
             break
         ss[i+1]=mkns(a[i],ss[i],pm)
         if isunnec(i):
             nn+=1
    print(nn)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        if func(lst[0]):
            return lst[0]
        else:
            return -1
    if func(lst[nh]):
        return biser(lst[nh:],func)
    else:
        return biser(lst[:nh],func)

def mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    def isunnec(i): 
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=mkns(a[j],ss[i],pm)
        # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    
    for i in range(N):
         if a[i]>=K:
             break
         ss[i+1]=mkns(a[i],ss[i],pm)
         if isunnec(i):
             nn+=1
        # for j in range(i+1,N):
        #     if a[j]>=K:
        #         break
        #     ss[i]=mkns(a[j],ss[i],pm)
        # # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        # if ss[i]&mask(K-a[i])==0:
        #     nn+=1
    # nn=biser(list(range(N)),isunnec)+1
    # print(list(map(bin,ss)))
    print(nn)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        if func(lst[0]):
            return lst[0]
        else:
            return -1
    if func(lst[nh]):
        return biser(lst[nh:],func)
    else:
        return biser(lst[:nh],func)

def mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    for i in range(N):
        ss[i+1]=mkns(a[i],ss[i],pm)
    def isunnec(i):
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=mkns(a[j],ss[i],pm)
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    nn=biser(list(range(N)),isunnec)+1
    print(nn)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        if func(lst[0]):
            return lst[0]
        else:
            return -1
    if func(lst[nh]):
        return biser(lst[nh:],func)
    else:
        return biser(lst[:nh],func)

def mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    for i in range(N):
        ss[i+1]=mkns(a[i],ss[i],pm)
    def isunnec(i):
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=mkns(a[j],ss[i],pm)
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    nn=biser(list(range(N)),isunnec)+1
    print(nn)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        if func(lst[0]):
            return lst[0]
        else:
            return -1
    if func(lst[nh]):
        return biser(lst[nh:],func)
    else:
        return biser(lst[:nh],func)

def mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    for i in range(N):
        if a[i]>=K:
            break
        ss[i+1]=mkns(a[i],ss[i],pm)
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=mkns(a[j],ss[i],pm)
        # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        if ss[i]&mask(K-a[i])==0:
            nn+=1
    # def isunnec(i):
    #     for j in range(i+1,N):
    #         if a[j]>=K:
    #             return False
    #         ss[i]=mkns(a[j],ss[i],pm)
    #     # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
    #     if ss[i]&mask(K-c)==0:
    #         return True
    #     return False
    # nn=biser(list(range(N)),isunnec)+1
    # print(list(map(bin,ss)))
    print(nn)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    for i in range(N):
        c=a[i]
        if c>=K:
            break
        ss[i+1]=mkns(c,ss[i],pm)
        a[i]=0
        for j in range(N):
            if a[j]>=K:
                break
            ss[i]=mkns(a[j],ss[i],pm)
        # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        if ss[i]&mask(K-c)==0:
            nn+=1
    # print(list(map(bin,ss)))
    print(nn)

if __name__=='__main__':
    main()