Problem:


Score: 400 points

Problem Statement

We have N integers A_1, A_2, ..., A_N.

There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Constraints

All values in input are integers.

2 \leq N \leq 2 \times 10^5

1 \leq K \leq \frac{N(N-1)}{2}

-10^9 \leq A_i \leq 10^9\ (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

4 3
3 3 -4 -2

Sample Output 1

-6

There are six ways to form a pair. The products of those pairs are 9, -12, -6, -12, -6, 8.

Sorting those numbers in ascending order, we have -12, -12, -6, -6, 8, 9. The third number in this list is -6.

Sample Input 2

10 40
5 4 3 2 -1 0 0 0 0 0

Sample Output 2

6

Sample Input 3

30 413
-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0

Sample Output 3

448283280358331064



Sample input:
4 3
3 3 -4 -2


Sample output:
-6

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,k = list(map(int, input().split()))
arr = list(map(int, input().split()))
lis=[]
for i in range(n):
  for j in range(i+1,n):
   heapq.heappush(lis,arr[i]*arr[j]);
for i in range(k):
 kk=heapq.heappop(lis)
print(kk);

Submission status: Time Limit Exceeded

Solution code:
n,k = list(map(int, input().split()))
arr = list(map(int, input().split()))
lis=[];
for i in range(n):
  for j in range(i+1,n):
   lis.append(arr[i]*arr[j]);
lis.sort()
print(lis[k-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools
n , k = map(int, input().split())
A = list(map(int, input().split()))

combi = list(itertools.combinations(A,2))
combi_multi = [a*b for a,b in combi]
combi_multi = sorted(combi_multi)

print(combi_multi[k-1])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
from itertools import combinations
L=[]
for i,j in combinations(A,2):
    L.append(i*j)
L.sort()
print(L[k-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,K = (int(x) for x in input().split())
A = np.array([int(x) for x in input().split()])
A.sort()
str = 'ok'

zero = len(A[A==0]) #0の数
pos = A[A > 0]
neg = A[A < 0]

p_cnt = len(pos)  #正の数
n_cnt = len(neg)  #負の数

#積の個数
p__cnt = (n_cnt * (n_cnt-1))//2 + (p_cnt * (p_cnt-1))//2
z__cnt = zero*(p_cnt+n_cnt) + (zero * (zero-1))//2
n__cnt = p_cnt*n_cnt

#K番目の値が負の場合
if K <= n__cnt:
    
    #二分探索の準備
    r = 0
    l = -pow(10,18)-1

    #二分探索
    while r-l != 1:
        mid = (l+r)//2
        cnt = 0
        cnt_p = p_cnt - 1

        '''
        尺取り法
        ある数が条件を満たさなくなった時点で次の数に変える
        '''
        
        for i in range(n_cnt):
            while cnt_p != -1:
                if pos[cnt_p]*neg[i] <= mid:
                    cnt_p -= 1
                    cnt += 1
                else:
                    break

            #cnt_p = 0になっているので元に戻す
            cnt_p = p_cnt - 1
                    
        if cnt < K:
            l = mid
        else:
            r = mid

    print(r)
            

#K番目の値が0のとき
elif K <= n__cnt + z__cnt:
    print(0)
    
#K番目の値が正の数の時
else:

    #Kから負と0になる組み合わせを引く
    K -= (z__cnt + n__cnt)
    
    #二分探索の準備
    r = pow(10,18)+1
    l = 0
    cnt = 0

    #二分探索
    while r-l != 1:
        mid = (l+r)//2
        cnt1 = 0

        #尺取り法で、ある数より下回る数を数える
        for i in range(p_cnt):
            tmp = 0
            
            for j in range(p_cnt):
                if pos[j]*pos[i] <= mid:
                    tmp += 1
                else:
                    break

            #同じやつを引く
            if pos[i]**2 <= mid:
                tmp -= 1

            cnt1 += tmp

        cnt1 = cnt1 // 2 #同じ組み合わせがあるので削除
        cnt2 = 0
        cnt_n = n_cnt - 1

        #尺取り法で、ある数より下回る数を数える
        for i in range(n_cnt-1,-1,-1):
            tmp = 0
            
            while cnt_n != -1:
                if neg[cnt_n]*neg[i] <= mid:
                    cnt_n -= 1
                    tmp += 1
                else:
                    break

            #同じやつを引く
            if neg[i]**2 <= mid:
                tmp -= 1

            cnt2 += tmp
            cnt_n = n_cnt - 1

        cnt2 = cnt2 // 2
        cnt = cnt1 + cnt2

        if cnt >= K:
            r = mid
        else:
            l = mid

    print(r)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import bisect

def position_in_neg(x):
    # y=n_pos-np.searchsorted(A_pos,x//A_neg,side='right')
    res=0
    for y in x//A_neg:
        res+=n_pos-bisect.bisect_right(A_pos, y)
    return res

def position_in_pos(x):
    # z=np.searchsorted(A_pos,-(-x//A_pos),side='left')
    # w=np.searchsorted(A_neg2,-(-x//A_neg2),side='left')
    res=0
    for y in -(-x//A_pos):
        res+=bisect.bisect_left(A_pos, y)
    for y in -(-x//A_neg2):
        res+=bisect.bisect_left(A_neg2, y)
    tmp=len(A_pos[A_pos**2<x])+len(A_neg2[A_neg2**2<x])
    return (res-tmp)//2

def position(x):
    if x<0:
        return position_in_neg(x)
    elif x==0:
        return n_pos*n_neg
    else:
        return position_in_pos(x)+n_pos*n_neg+(n_pos+n_neg)*n_zero+n_zero*(n_zero-1)//2


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

    A=np.array(A)
    global A_pos,A_neg,A_neg2,n_pos,n_neg,n_zero
    A_pos=np.sort(A[A>0])
    A_neg=np.sort(A[A<0])
    A_neg2=-A_neg[::-1]
    n_pos=len(A_pos)
    n_neg=len(A_neg)
    n_zero=N-n_pos-n_neg


    l=-pow(10,18)
    r=pow(10,18)
    while(r-l>1):
        mid=(l+r)//2
        if position(mid)<K:
            l=mid
        else:
            r=mid
    print(l)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=np.sort(-A_neg)
n_pos=len(A_pos)
n_neg=len(A_neg)
n_zero=N-n_pos-n_neg

def position_in_neg(x):
    y=n_pos-np.searchsorted(A_pos,x//A_neg,side='right')
    return y.sum()

def position_in_pos(x):
    z=np.searchsorted(A_pos,-(-x//A_pos),side='left')
    w=np.searchsorted(A_neg2,-(-x//A_neg2),side='left')
    tmp=0
    for v in A_pos:
        if v**2<x:
            tmp+=1
    for v in A_neg2:
        if v**2<x:
            tmp+=1

    return (z.sum()+w.sum()-tmp)//2

def position(x):
    if x<0:
        return position_in_neg(x)
    elif x==0:
        return n_pos*n_neg
    else:
        return position_in_pos(x)+n_pos*n_neg+(n_pos+n_neg)*n_zero+n_zero*(n_zero-1)//2

l=-pow(10,18)
r=pow(10,18)
while(r-l>1):
    mid=(l+r)//2
    if position(mid)<K:
        l=mid
    else:
        r=mid
print(l)

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = LI()
    N.sort()
    if N[0]==N[1] and N[0]!=N[2]:
        print("Yes")
    elif N[1]==N[2] and N[0]!=N[2]:
        print("Yes")
    else:
        print("No")
    return

def examB():
    N = I()
    A = LI()
    for a in A:
        if a%2==0:
            if a%3!=0 and a%5!=0:
                print("DENIED")
                return
    print("APPROVED")
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    d = defaultdict(int)
    for s in S:
        d[s] += 1
    t = max(d.values())
    ans = []
    for s in S:
        if d[s]==t:
            ans.append(s)
            d[s] = 0
    ans.sort()
    for v in ans:
        print(v)
    return

def examD():
    N, K = LI()
    A = LI()
    A_neg = []; neg = 0
    A_0 = []; num_0 = 0
    A_pos = []; pos = 0
    for a in A:
        if a<0:
            A_neg.append(-a)
            neg += 1
        elif a==0:
            A_0.append(a)
            num_0 += 1
        else:
            A_pos.append(a)
            pos += 1
    ans = 0
    A_neg.sort()
    A_pos.sort()
    #print(A_neg)
    #print(neg,pos,num_0)
    if neg*pos>=K:
        l = 1 ; r = inf+1
        while(r-l>1):
            now = (l+r)//2
            cur = 0
            for a in A_neg:
                next = bisect.bisect_left(A_pos,-(-now//a))
                cur += (pos-next)
                #print(next,now//a)
            if cur<K:
                r = now
            else:
                l = now
            #print(now,cur)
        ans = -l
    elif (pos+neg)*num_0 + num_0*(num_0-1)//2 + neg*pos>=K:
        ans = 0
    else:
        need = K-((pos+neg)*num_0 + num_0*(num_0-1)//2 + neg*pos)
        #print(need)
        l = 0; r = inf+1
        while(r-l>1):
            now = (l+r)//2
            cur = 0
            if neg>=2:
                for a in A_neg:
                    next = bisect.bisect_right(A_neg, now//a)
                    if a ** 2 <= now:
                        next -= 1
                    cur += next
            if pos>=2:
                for a in A_pos:
                    next = bisect.bisect_right(A_pos, now//a)
                    if a ** 2 <= now:
                        next -= 1
                    cur += next
            cur //= 2
            if cur<need:
                l = now
            else:
                r = now
            #print(now,cur,need)
        ans = r
    print(ans)
    return
"""
10 43
5 4 3 2 -1 0 0 0 0 0
"""

def examE():
    S = SI()
    N = len(S)
    flag = False
    ans = 0
    for i in range(N-1,-1,-1):
        #print(ans)
        cur = int(S[i])
        if flag:
            cur += 1
        if cur>=6:
            ans += 10-cur
            flag = True
        else:
            ans += cur
            flag = False
    if flag:
        ans += 1
    print(ans)
    return

def examE2():
    S = SI()
    N = len(S)
    dp = [[0]*2 for _ in range(N+2)]
    dp[0][1] = inf
    S = S[::-1]
    S += "0"
    for i in range(N+1):
        s = int(S[i])
        dp[i+1][0] = dp[i][0] + s
        dp[i+1][1] = dp[i][0] + (10-s)
        if s<9:
            dp[i+1][0] = min(dp[i+1][0],dp[i][1] + (s+1))
        dp[i+1][1] = min(dp[i+1][1],dp[i][1] + (10-s-1))
    #print(dp)
    ans = min(dp[-1][0],dp[-1][1])
    print(ans)
    return

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

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,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 = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""
4396817
"""

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = LI()
    N.sort()
    if N[0]==N[1] and N[0]!=N[2]:
        print("Yes")
    elif N[1]==N[2] and N[0]!=N[2]:
        print("Yes")
    else:
        print("No")
    return

def examB():
    N = I()
    A = LI()
    for a in A:
        if a%2==0:
            if a%3!=0 and a%5!=0:
                print("DENIED")
                return
    print("APPROVED")
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    d = defaultdict(int)
    for s in S:
        d[s] += 1
    t = max(d.values())
    ans = []
    for s in S:
        if d[s]==t:
            ans.append(s)
            d[s] = 0
    ans.sort()
    for v in ans:
        print(v)
    return

def examD():
    N, K = LI()
    A = LI()
    A_neg = []; neg = 0
    A_0 = []; num_0 = 0
    A_pos = []; pos = 0
    for a in A:
        if a<0:
            A_neg.append(-a)
            neg += 1
        elif a==0:
            A_0.append(a)
            num_0 += 1
        else:
            A_pos.append(a)
            pos += 1
    ans = 0
    A_neg.sort()
    A_pos.sort()
    #print(A_neg)
    #print(neg,pos,num_0)
    if neg*pos>=K:
        l = 1 ; r = A_neg[-1]*A_pos[-1]+1
        while(r-l>1):
            now = (l+r)//2
            cur = 0
            for a in A_neg:
                next = bisect.bisect_left(A_pos,-(-now//a))
                cur += (pos-next)
                #print(next,now//a)
            if cur<K:
                r = now
            else:
                l = now
            #print(now,cur)
        ans = -l
    elif (pos+neg)*num_0 + num_0*(num_0-1)//2 + neg*pos>=K:
        ans = 0
    else:
        need = K-((pos+neg)*num_0 + num_0*(num_0-1)//2 + neg*pos)
        #print(need)
        l = 0; r = 1
        if neg>=2:
            r = A_neg[-1]*A_neg[-2]
        if pos>=2:
            r = max(r,A_pos[-1]*A_pos[-2])
        while(r-l>1):
            now = (l+r)//2
            cur = 0
            if neg>=2:
                for a in A_neg:
                    next = bisect.bisect_right(A_neg, now//a)
                    if a ** 2 <= now:
                        next -= 1
                    cur += next
            if pos>=2:
                for a in A_pos:
                    next = bisect.bisect_right(A_pos, now//a)
                    if a ** 2 <= now:
                        next -= 1
                    cur += next
            cur //= 2
            if cur<need:
                l = now
            else:
                r = now
            #print(now,cur,need)
        ans = r
    print(ans)
    return
"""
10 43
5 4 3 2 -1 0 0 0 0 0
"""

def examE():
    S = SI()
    N = len(S)
    flag = False
    ans = 0
    for i in range(N-1,-1,-1):
        #print(ans)
        cur = int(S[i])
        if flag:
            cur += 1
        if cur>=6:
            ans += 10-cur
            flag = True
        else:
            ans += cur
            flag = False
    if flag:
        ans += 1
    print(ans)
    return

def examE2():
    S = SI()
    N = len(S)
    dp = [[0]*2 for _ in range(N+2)]
    dp[0][1] = inf
    S = S[::-1]
    S += "0"
    for i in range(N+1):
        s = int(S[i])
        dp[i+1][0] = dp[i][0] + s
        dp[i+1][1] = dp[i][0] + (10-s)
        if s<9:
            dp[i+1][0] = min(dp[i+1][0],dp[i][1] + (s+1))
        dp[i+1][1] = min(dp[i+1][1],dp[i][1] + (10-s-1))
    #print(dp)
    ans = min(dp[-1][0],dp[-1][1])
    print(ans)
    return

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

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,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 = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""
4396817
"""

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = LI()
    N.sort()
    if N[0]==N[1] and N[0]!=N[2]:
        print("Yes")
    elif N[1]==N[2] and N[0]!=N[2]:
        print("Yes")
    else:
        print("No")
    return

def examB():
    N = I()
    A = LI()
    for a in A:
        if a%2==0:
            if a%3!=0 and a%5!=0:
                print("DENIED")
                return
    print("APPROVED")
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    d = defaultdict(int)
    for s in S:
        d[s] += 1
    t = max(d.values())
    ans = []
    for s in S:
        if d[s]==t:
            ans.append(s)
            d[s] = 0
    ans.sort()
    for v in ans:
        print(v)
    return

def examD():
    N, K = LI()
    A = LI()
    A_neg = []; neg = 0
    A_0 = []; num_0 = 0
    A_pos = []; pos = 0
    for a in A:
        if a<0:
            A_neg.append(-a)
            neg += 1
        elif a==0:
            A_0.append(a)
            num_0 += 1
        else:
            A_pos.append(a)
            pos += 1
    ans = 0
    A_neg.sort()
    A_pos.sort()
    #print(A_neg)
    #print(neg,pos,num_0)
    if neg*pos>=K:
        l = 1 ; r = A_neg[-1]*A_pos[-1]+1
        while(r-l>1):
            now = (l+r)//2
            cur = 0
            for a in A_neg:
                next = bisect.bisect_left(A_pos,-(-now//a))
                cur += (pos-next)
                #print(next,now//a)
            if cur<K:
                r = now
            else:
                l = now
            #print(now,cur)
        ans = -l
    elif (N-num_0)*num_0+num_0*(num_0-1)//2+neg*pos>=K:
        ans = 0
    else:
        need = K-((pos+neg)*num_0 + num_0*(num_0-1)//2 + neg*pos)
        #print(need)
        l = 0; r = 1
        if neg>=2:
            r = A_neg[-1]*A_neg[-2]+1
        if pos>=2:
            r = max(r,A_pos[-1]*A_pos[-2]+1)
        while(r-l>1):
            now = (l+r)//2
            cur = 0
            if neg>=2:
                for a in A_neg:
                    next = bisect.bisect_right(A_neg, now//a)
                    if a ** 2 <= now:
                        next -= 1
                    cur += next
            if pos>=2:
                for a in A_pos:
                    next = bisect.bisect_right(A_pos, now//a)
                    if a ** 2 <= now:
                        next -= 1
                    cur += next
            cur //= 2
            if cur<need:
                l = now
            else:
                r = now
            #print(now,cur,need)
        ans = r
    print(ans)
    return
"""
10 43
5 4 3 2 -1 0 0 0 0 0
"""

def examE():
    S = SI()
    N = len(S)
    flag = False
    ans = 0
    for i in range(N-1,-1,-1):
        #print(ans)
        cur = int(S[i])
        if flag:
            cur += 1
        if cur>=6:
            ans += 10-cur
            flag = True
        else:
            ans += cur
            flag = False
    if flag:
        ans += 1
    print(ans)
    return

def examE2():
    S = SI()
    N = len(S)
    dp = [[0]*2 for _ in range(N+2)]
    dp[0][1] = inf
    S = S[::-1]
    S += "0"
    for i in range(N+1):
        s = int(S[i])
        dp[i+1][0] = dp[i][0] + s
        dp[i+1][1] = dp[i][0] + (10-s)
        if s<9:
            dp[i+1][0] = min(dp[i+1][0],dp[i][1] + (s+1))
        dp[i+1][1] = min(dp[i+1][1],dp[i][1] + (10-s-1))
    #print(dp)
    ans = min(dp[-1][0],dp[-1][1])
    print(ans)
    return

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

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,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 = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""
4396817
"""

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = LI()
    N.sort()
    if N[0]==N[1] and N[0]!=N[2]:
        print("Yes")
    elif N[1]==N[2] and N[0]!=N[2]:
        print("Yes")
    else:
        print("No")
    return

def examB():
    N = I()
    A = LI()
    for a in A:
        if a%2==0:
            if a%3!=0 and a%5!=0:
                print("DENIED")
                return
    print("APPROVED")
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    d = defaultdict(int)
    for s in S:
        d[s] += 1
    t = max(d.values())
    ans = []
    for s in S:
        if d[s]==t:
            ans.append(s)
            d[s] = 0
    ans.sort()
    for v in ans:
        print(v)
    return

def examD():
    N, K = LI()
    A = LI()
    A_neg = []; neg = 0
    A_0 = []; num_0 = 0
    A_pos = []; pos = 0
    for a in A:
        if a<0:
            A_neg.append(-a)
            neg += 1
        elif a==0:
            A_0.append(a)
            num_0 += 1
        else:
            A_pos.append(a)
            pos += 1
    ans = 0
    A_neg.sort()
    A_pos.sort()
    #print(A_neg)
    #print(neg,pos,num_0)
    if neg*pos>=K:
        l = 0 ; r = A_neg[-1]*A_pos[-1]
        while(r-l>1):
            now = (l+r)//2
            cur = 0
            for a in A_neg:
                next = bisect.bisect_right(A_pos,now//a)
                cur += (pos-next)
            if cur<K:
                r = now
            else:
                l = now
            #print(now,cur)
        ans = -r
    elif (N-num_0)*num_0+num_0*(num_0-1)//2+neg*pos>=K:
        ans = 0
    else:
        need = K-((pos+neg)*num_0 + num_0*(num_0-1)//2 + neg*pos)
        #print(need)
        l = 0; r = 1
        if neg>=2:
            r = A_neg[-1]*A_neg[-2]+1
        if pos>=2:
            r = max(r,A_pos[-1]*A_pos[-2]+1)
        while(r-l>1):
            now = (l+r)//2
            cur = 0
            if neg>=2:
                for a in A_neg:
                    next = bisect.bisect_right(A_neg, now//a)
                    if a ** 2 <= now:
                        next -= 1
                    cur += next
            if pos>=2:
                for a in A_pos:
                    next = bisect.bisect_right(A_pos, now//a)
                    if a ** 2 <= now:
                        next -= 1
                    cur += next
            cur //= 2
            if cur<need:
                l = now
            else:
                r = now
            #print(now,cur,need)
        ans = r
    print(ans)
    return
"""
10 43
5 4 3 2 -1 0 0 0 0 0
"""

def examE():
    S = SI()
    N = len(S)
    flag = False
    ans = 0
    for i in range(N-1,-1,-1):
        #print(ans)
        cur = int(S[i])
        if flag:
            cur += 1
        if cur>=6:
            ans += 10-cur
            flag = True
        else:
            ans += cur
            flag = False
    if flag:
        ans += 1
    print(ans)
    return

def examE2():
    S = SI()
    N = len(S)
    dp = [[0]*2 for _ in range(N+2)]
    dp[0][1] = inf
    S = S[::-1]
    S += "0"
    for i in range(N+1):
        s = int(S[i])
        dp[i+1][0] = dp[i][0] + s
        dp[i+1][1] = dp[i][0] + (10-s)
        if s<9:
            dp[i+1][0] = min(dp[i+1][0],dp[i][1] + (s+1))
        dp[i+1][1] = min(dp[i+1][1],dp[i][1] + (10-s-1))
    #print(dp)
    ans = min(dp[-1][0],dp[-1][1])
    print(ans)
    return

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

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,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 = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""
4396817
"""

Submission status: Time Limit Exceeded

Solution code:


import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=np.sort(-A_neg)

np=len(A_pos)
nn=len(A_neg)
nz=N-np-nn
n_post=np*(np-1)//2+(nn*(nn-1))//2
n_zero=nz*(np+nn)+nz*(nz-1)//2
n_neg=np*nn



#array内で積がx未満になるペアの数
def syakutori_pos1(x):
    res=0
    j=np-1
    y1=-(-x//A_pos)
    for i in range(np):
        tmp=0
#         j=n-1

        while j!=-1:
            
            if A_pos[j]>=y1[i]:
                j-=1
            else:
                break
        
        tmp+=j+1
        if A_pos[i]**2<x:
            tmp-=1

        res+=tmp
    res=res//2
    return res


def syakutori_pos2(x):
    res=0
    j=nn-1
    y2=-(-x//A_neg2)
    for i in range(nn):
        tmp=0
#         j=n-1

        while j!=-1:
            
            if A_neg2[j]>=y2[i]:
                j-=1
            else:
                break
        
        tmp+=j+1
        if A_neg2[i]**2<x:
            tmp-=1

        res+=tmp
    res=res//2
    return res


#array内で積がx未満になるペアの数

def syakutori_neg(x):
    yn=x//A_neg
#     print(A_pos,y)
    res=0
    i=0
    j=np-1
    for z in reversed(yn):
        while(j!=-1):
            if z<A_pos[j]:
                j-=1
            else:
                break
#         print(z,j+1)
        res+=j+1
    return np*nn-res



def syakutori(x):
    if x>0:
        return syakutori_pos1(x)+syakutori_pos2(x)+n_neg+n_zero
    elif x==0:
        return n_neg
    else:
        return syakutori_neg(x)




r=10**18
l=-10**18
while(r-l>1):
    mid=(l+r)//2
    z=syakutori(mid)
#     z= count_pair(mid)
#     print(l,r)
    if z < K:
        l=mid
    else:
        r=mid
print(l)

Submission status: Time Limit Exceeded

Solution code:


import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=np.sort(-A_neg)

np=len(A_pos)
nn=len(A_neg)
nz=N-np-nn
n_post=np*(np-1)//2+(nn*(nn-1))//2
n_zero=nz*(np+nn)+nz*(nz-1)//2
n_neg=np*nn

#array内で積がx未満になるペアの数
def syakutori_pos1(x):
    res=0
    j=np-1
    for i in range(np):
        tmp=0
#         j=n-1
        y=-(-x//A_pos[i])
        while j!=-1:
            
            if A_pos[j]>=y:
                j-=1
            else:
                break
        
        tmp+=j+1
        if A_pos[i]**2<x:
            tmp-=1

        res+=tmp
    res=res//2
    return res

def syakutori_pos2(x):
    res=0
    j=nn-1
    for i in range(nn):
        tmp=0
#         j=n-1
        y=-(-x//A_neg2[i])
        while j!=-1:
            
            if A_neg2[j]>=y:
                j-=1
            else:
                break
        
        tmp+=j+1
        if A_neg2[i]**2<x:
            tmp-=1

        res+=tmp
    res=res//2
    return res


#array内で積がx未満になるペアの数
def syakutori_neg(x):
    y=x//A_neg
#     print(A_pos,y)
    res=0
    i=0
    j=np-1
    for z in reversed(y):
        while(j!=-1):
            if z<A_pos[j]:
                j-=1
            else:
                break
#         print(z,j+1)
        res+=j+1
    return np*nn-res



def syakutori(x):
    if x>0:
        return syakutori_pos1(x)+syakutori_pos2(x)+n_neg+n_zero
    elif x==0:
        return n_neg
    else:
        return syakutori_neg(x)




r=10**18
l=-10**18
while(r-l>1):
    mid=(l+r)//2
    z=syakutori(mid)
#     z= count_pair(mid)
#     print(l,r)
    if z < K:
        l=mid
    else:
        r=mid
print(l)

Submission status: Time Limit Exceeded

Solution code:


import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=np.sort(-A_neg.copy())
nz=len(A[A==0])
np=len(A_pos)
nn=len(A_neg)
n_post=np*(np-1)//2+(nn*(nn-1))//2
n_zero=nz*(np+nn)+nz*(nz-1)//2
n_neg=np*nn

#array内で積がx未満になるペアの数
def syakutori_pos(x,array):
    n=len(array)
    res=0
    j=n-1
    for i in range(n):
        tmp=0
#         j=n-1
        y=-(-x//array[i])
        while j!=-1:
            
            if array[j]>=y:
                j-=1
            else:
                break
        
        tmp+=j+1
        if array[i]**2<x:
            tmp-=1

            
        res+=tmp
    res=res//2
    return res



#array内で積がx未満になるペアの数
def syakutori_neg(x):
    y=x//A_neg
#     print(A_pos,y)
    res=0
    i=0
    j=np-1
    for z in reversed(y):
        while(j!=-1):
            if z<A_pos[j]:
                j-=1
            else:
                break
#         print(z,j+1)
        res+=j+1
    return np*nn-res



def syakutori(x):
    if x>0:
        return syakutori_pos(x,A_pos)+syakutori_pos(x,A_neg2)+n_neg+n_zero
    elif x==0:
        return n_neg
    else:
        return syakutori_neg(x)




r=10**18
l=-10**18
while(r-l>1):
    mid=(l+r)//2
    z=syakutori(mid)
#     z= count_pair(mid)
#     print(l,r)
    if z < K:
        l=mid
    else:
        r=mid
print(l)

Submission status: Time Limit Exceeded

Solution code:
#array内で積がx未満になるペアの数
def syakutori_pos(x,array):
    n=len(array)
    res=0
    j=n-1
    for i in range(n):
        tmp=0
#         j=n-1
        y=-(-x//array[i])
        while j!=-1:
            
            if array[j]>=y:
                j-=1
            else:
                break
        
        tmp+=j+1
        if array[i]**2<x:
            tmp-=1
        res+=tmp
    res=res//2
    return res



#array内で積がx未満になるペアの数
def syakutori_neg(x,array_pos,array_neg):
    n_pos=len(array_pos)
    n_neg=len(array_neg)
    y=x//array_neg
#     print(A_pos,y)
    res=0
    i=0
    j=n_pos-1
    for z in reversed(y):
        while(j!=-1):
            if z<array_pos[j]:
                j-=1
            else:
                break
#         print(z,j+1)
        res+=j+1
    return n_pos*n_neg-res


import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=np.sort(-A_neg.copy())
n_post=(len(A_pos)*(len(A_pos)-1)//2)+(len(A_neg)*(len(A_neg)-1))//2
n_zero=len(A[A==0])*(len(A_pos)+len(A_neg))+len(A[A==0])*(len(A[A==0])-1)//2
n_neg=len(A_pos)*len(A_neg)

def syakutori(x):
    if x>0:
        return syakutori_pos(x,A_pos)+syakutori_pos(x,A_neg2)+n_neg+n_zero
    elif x==0:
        return n_neg
    else:
        return syakutori_neg(x,A_pos,A_neg)




r=10**18
l=-10**18
while(r-l>1):
    mid=(l+r)//2
    z=syakutori(mid)
#     z= count_pair(mid)
#     print(l,r)
    if z < K:
        l=mid
    else:
        r=mid
print(l)

Submission status: Time Limit Exceeded

Solution code:
#array内で積がx未満になるペアの数
def syakutori_pos(x,array):
    n=len(array)
    res=0
    j=n-1
    for i in range(n):
        tmp=0
#         j=n-1
        y=-(-x//array[i])
        while j!=-1:
            
            if array[j]>=y:
                j-=1
            else:
                break
        
        tmp+=j+1
        if array[i]**2<x:
            tmp-=1
        res+=tmp
    res=res//2
    return res



# #array内で積がx未満になるペアの数
# def syakutori_neg(x,array_pos,array_neg):
#     n_pos=len(array_pos)
#     n_neg=len(array_neg)
#     y=-(-x//array_neg)

#     res=0
#     j=0
#     k=-1
#     for i in range(n_pos):
#         tmp=0

#         while k<n_neg-1:     
#             if y[k+1]<=array_pos[i]:
#                 k+=1
#             else:
#                 break
# #         print(k,y[k])
#         j=max(j,k)
#         while j<n_neg-1:
#             if array_pos[i]<=y[j]:
#                 j+=1
#             else:
#                 break

#         tmp+=j-k+1
#         res+=j-k
#     return n_pos*n_neg-res

def syakutori_neg(x,array_pos,array_neg):
    n_pos=len(array_pos)
    n_neg=len(array_neg)
    y=x//array_neg
    res=0

    for z in y:
        res+=len(A_pos[A_pos>z])
    return res


import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=np.sort(-A_neg.copy())
n_post=(len(A_pos)*(len(A_pos)-1)//2)+(len(A_neg)*(len(A_neg)-1))//2
n_zero=len(A[A==0])*(len(A_pos)+len(A_neg))+len(A[A==0])*(len(A[A==0])-1)//2
n_neg=len(A_pos)*len(A_neg)

def syakutori(x):
    if x>0:
        return syakutori_pos(x,A_pos)+syakutori_pos(x,A_neg2)+n_neg+n_zero
    elif x==0:
        return n_neg
    else:
        return syakutori_neg(x,A_pos,A_neg)




r=10**18
l=-10**18
while(r-l>1):
    mid=(l+r)//2
    z=syakutori(mid)
#     z= count_pair(mid)
#     print(l,r)
    if z < K:
        l=mid
    else:
        r=mid
print(l)