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:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    ans = - 10**18

    from bisect import bisect_left, bisect_right


    N, K = LMIIS()
    A = LMIIS()
    A.sort()
    num_negative = bisect_left(A,0)
    num_zero = bisect_right(A,0) - num_negative
    num_positive = N - num_negative - num_zero
    
    inf = 10**18+1
    
    # 答えが負
    if num_negative * num_positive >= K:
        u = 0
        l = A[0]*A[-1]
        # def g(i,x):
            # up = N
            # lp = num_negative + num_zero
            # min_m = N
            # mp = (up+lp)//2
            # while up-lp > 1:
            #     mp = (up+lp)//2
            #     if A[i] * A[mp] < x:
            #         up = mp
                    
            #         min_m = min(min_m,mp)
            #     else:
            #         lp = mp
            # mp = (up+lp)//2
            # if A[i] * A[mp] < x:

            #     min_m = min(min_m,mp)

            # return max(N-min_m,0)
            

        # def f(x):
        #     ans = 0
        #     for i in range(num_negative):
        #         ans += g(i,x)
        #     return ans

        max_m = l
        while u-l > 1:
            m = (u+l)//2

            ans = 0
            for i in range(num_negative):
                up = N
                lp = num_negative + num_zero
                min_m = N
                mp = (up+lp)//2
                while up-lp > 1:
                    mp = (up+lp)//2
                    if A[i] * A[mp] < m:
                        up = mp
                        
                        min_m = mp
                    else:
                        lp = mp
                mp = (up+lp)//2
                if A[i] * A[mp] < m:

                    min_m = mp













                ans += max(N-min_m,0)








            if ans >= K:
                u = m
            else:
                l = m
                max_m = max(max_m,m)
        return max_m

    # 答えがゼロ
    elif num_negative * num_positive + num_negative * num_zero + num_positive * num_zero + num_zero*(num_zero-1)//2 >= K:
        return 0

    # 答えが正
    else:
        K -= num_negative * num_positive +\
             num_negative * num_zero +\
             num_positive * num_zero + num_zero*(num_zero-1)//2

        def f(i,x):
            unn = i
            lnn = 0
            min_m = N
            mnn = (unn+lnn)//2
            anspp = N
            while unn-lnn > 1:
                mnn = (unn+lnn)//2
                if A[i] * A[mnn] < x:
                    unn = mnn
                    ans = mnn
                else:
                    lnn = mnn
            mnn = (unn+lnn)//2
            if A[i] * A[mnn] < x:
                    anspp = mnn
            anspp = max(i - anspp,0)
            # ans = max(ans,0)
            return anspp

        def g(i,x):
            upp = N
            lpp = i+1
            max_m = num_negative + num_zero -1
            mpp = (upp+lpp)//2
            while upp-lpp > 1:
                mpp = (upp+lpp)//2
                if A[i] * A[mpp] < x:
                    lpp = mpp
                    max_m = mpp
                else:
                    upp = mpp
            mpp = (upp+lpp)//2
            if A[i] * A[mpp] < x:
                max_m = mpp
            
            

            anspp = max_m - i
            

            anspp = max(anspp,0)

            
            return anspp
            
        def h(x):
            ans = 0
            for i in range(1,num_negative):
                ans += f(i,x)
            preans = ans
            
            for i in range(num_negative+num_zero,N-1):
                ans += g(i,x)

            return ans
        




        u = max(A[0]*A[1],A[-1]*A[-2])+1
        l = 1
        max_m = 1
        while u-l > 1:
            m = (u+l)//2

            ans = 0
            for i in range(1,num_negative):
                #
                unn = i
                lnn = 0
                min_m = N
                mnn = (unn+lnn)//2
                anspp = N
                while unn-lnn > 1:
                    mnn = (unn+lnn)//2
                    if A[i] * A[mnn] < m:
                        unn = mnn
                        anspp = mnn
                    else:
                        lnn = mnn
                mnn = (unn+lnn)//2
                if A[i] * A[mnn] < m:
                        anspp = mnn
                anspp = max(i - anspp,0)









                
                ans += anspp
            preans = ans
            
            for i in range(num_negative+num_zero,N-1):
                #
                upp = N
                lpp = i+1
                max_mpp = num_negative + num_zero -1
                mpp = (upp+lpp)//2
                while upp-lpp > 1:
                    mpp = (upp+lpp)//2
                    if A[i] * A[mpp] < m:
                        lpp = mpp
                        max_mpp = mpp
                    else:
                        upp = mpp
                mpp = (upp+lpp)//2
                if A[i] * A[mpp] < m:
                    max_mpp = mpp
                
                

                anspp = max_mpp - i
                

                anspp = max(anspp,0)








                ans += anspp


            if ans >= K:
                u = m
            else:
                l = m
                max_m = m

        return max_m




if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import itertools

n, k = map(int, raw_input().split())
ns = map(int, raw_input().split())

cb = itertools.combinations(ns, 2)
gotcha = sorted(a*b for a,b in cb)[k - 1]

print gotcha

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(m) for m in input().split()]
a = [int(m) for m in input().split()]

c = (n * (n - 1) ) / 2

s_a = sorted(a)
s_b = sorted(a)

l = []

for i in range(n):
    for j in range(n):
        if j >= i:
            continue
        l += [s_a[i] * s_b[j]]

s_l = sorted(l)
print(s_l[k-1])

Submission status: Time Limit Exceeded

Solution code:
import heapq
import itertools
N, K = map(int, input().split())
arr = list(map(int, input().split()))

pos, neg, z = [], [], []

for a in arr:
  if a < 0:
    neg.append(a)
  elif a > 0:
    pos.append(a)
  else:
    z.append(a)
    
n_pos, n_neg, n_z = len(pos), len(neg), len(z)
#print(n_pos, n_z, n_neg)
n_pro_neg = n_neg * n_pos
n_pro_z = n_z * (n_neg + n_pos) + n_z * (n_z - 1) // 2
n_pro_pos = n_pos * (n_pos - 1) // 2 + n_neg * (n_neg - 1) // 2

#print(n_pro_neg, n_pro_z, n_pro_pos)
if 0 <= K <= n_pro_neg:
  print(sorted([
    vn * vp
    for vn, vp in itertools.product(neg, pos)
  ])[K-1])
elif n_pro_neg < K <= n_pro_neg + n_pro_z:
  print(0)
else:
  print(sorted(
    [
      v1 * v2
      for v1, v2 in itertools.combinations(neg, 2)
    ]
    +
    [
      v1 * v2
      for v1, v2 in  itertools.combinations(pos, 2)
    ]
  )[K-n_pro_neg - n_pro_z -1])

Submission status: Time Limit Exceeded

Solution code:
def calc(N, K, A):
    A.sort()
    (n_n, n_0, n_p) = (0, 0, 0)
    for a in A:
        if a < 0:
            n_n += 1
        elif a == 0:
            n_0 += 1
        else:
            n_p = N - n_n - n_0
    A_n = sorted(A[:n_n], key=lambda x: -x)
    A_p = A[n_n + n_0:]
    k_n = n_n * n_p
    k_0 = 0 if n_0 == 0 else n_0 * (n_0 - 1) // 2 + n_0 * (N - n_0)
    if K <= k_n:
        M = sum([[a_n * a_p for a_p in A_p] for a_n in A_n], [])
        M.sort()
        return M[K - 1]
    elif K <= k_n + k_0:
        return 0
    else:
        M1 = sum([[A_n[i] * A_n[j] for j in range(i + 1, n_n)]
                  for i in range(n_n)], [])
        M2 = sum([[A_p[i] * A_p[j] for j in range(i + 1, n_p)]
                  for i in range(n_p)], [])
        M = sorted(M1 + M2)
        return M[K - k_n - k_0 - 1]


(N, K) = tuple([int(s) for s in input().split()])
A = [int(s) for s in input().split()]
print(calc(N, K, A))

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
N, K = map(int, input().split())
arr = list(map(int, input().split()))


v =sorted([v1 * v2
	for v1, v2 in itertools.combinations(arr, 2)
   ])[K - 1]

print(v)

Submission status: Time Limit Exceeded

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

digits = list(map(int, input().split(' ')))

prods = [ digits[i]*digits[j] for i in range(n-1) for j in range(i+1,n) ]
prods.sort()
print(prods[k-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools 
def input(): return sys.stdin.readline().rstrip()

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

    def isOK(n):
        c = 0
        for a in A:
            ok = -1
            ng = N
            if a < 0:
                ok, ng = ng, ok

            while abs(ok - ng) > 1:
                m = (ok + ng) // 2
                if a * A[m] < n:
                    ok = m
                else:
                    ng = m
            c += N - ok if a < 0 else ng
            if a * a < n:
                c -= 1
        return c // 2 < K

    INF = 10 ** 18 + 1
    left = - INF
    right = INF

    while right - left > 1:
        mid = (left + right) // 2

        if isOK(mid):
            left = mid
        else:
            right = mid
    print(left)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools 
def input(): return sys.stdin.readline().rstrip()



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

    def isOK(n):
        c = 0
        for a in A:
            ok = -1
            ng = N
            if a < 0:
                ok, ng = ng, ok

            while abs(ok - ng) > 1:
                m = (ok + ng) // 2
                if a * A[m] < n:
                    ok = m
                else:
                    ng = m
            c += N - ok if a < 0 else ng
            if a * a < n:
                c -= 1
        return c // 2 < K

    INF = 10 ** 18 + 1
    left = - INF
    right = INF

    while right - left > 1:
        mid = (left + right) // 2

        if isOK(mid):
            left = mid
        else:
            right = mid
    print(left)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K = [int(x) for x in input().rstrip().split()]
l = [int(x) for x in input().rstrip().split()]
seki = []
ans = -100000000
for i in range(N):
    for j in range(i+1,N):
        s = l[i]*l[j]
        seki.append(s)

seki.sort()
print(seki[K-1])

Submission status: Time Limit Exceeded

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

li = []
for a,b in itertools.combinations(A, 2):
  heapq.heappush(li, a*b)
ans = -1
for _ in range(K):
  ans = heapq.heappop(li)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, K = map(int,input().split())
A = list(map(int,input().split()))
l = list(itertools.combinations(A,2))
ans = [a*b for a,b in l]
print(sorted(ans)[K-1])

Submission status: Time Limit Exceeded

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

n,k = map(int, input().split())
a= list(map(int, input().split()))
a.sort()
r=10**18+1
l=-10**18-1
while r-l>1:
    m = (r + l) // 2
    count=0
    for i in range(n):
        if a[i]>0:
            x=m//a[i]
            y=bisect.bisect_right(a,x)
            if y<=i:
                count+=y
            else:
                count+=y-1
        elif a[i]<0:
            x=-(m//-a[i])
            y=bisect.bisect_left(a,x)
            y1=n-y
            if y>i:
                count+=y1
            else:
                count+=y1-1
        else:
            if m>=0:
                count+=n-1
    if count//2>=k:
        r=m
    else:
        l=m
print(r)

Submission status: Time Limit Exceeded

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

li = []
for i in range(n):
    for j in range(i + 1, n):
      li.append(a_list[i] * a_list[j])

print(sorted(li)[k - 1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
k = input().split()
a = input().split()
alist = np.array([int(s) for s in a])
 
muls = []

for i in range(int(k[0])-1):
  a1 = alist[i]
  muls.extend([a1 * a2 for a2 in alist[i+1:]])
muls.sort()
print(muls[int(k[1])-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
k = input().split()
alist = np.array(input().split())
 
muls = []

r1 = int(k[0])-1
for i in range(r1):
  a1 = int(alist[i])
  na = np.array(alist[i+1:])
  muls.extend(list(map(lambda x: int(x)*a1,na)))
muls.sort()
print(muls[int(k[1])-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
k = input().split()
alist = np.array(input().split())
 
muls = []

r1 = int(k[0])-1
for i in range(r1):
  a1 = alist[i]
  na = np.array(alist[i+1:])
  for a2 in na:
    muls.append( int(a1) * int(a2) )
muls.sort()
print(muls[int(k[1])-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

k = input().split()
alist = np.array([int(s) for s in input().split()])

muls = []

for i in range(int(k[0])-1):
  a1 = alist[i] * alist[i+1:]
  muls.extend( a1 )

muls.sort()
print(muls[int(k[1])-1])

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    ans = - 10**18

    from bisect import bisect_left, bisect_right


    N, K = LMIIS()
    A = LMIIS()
    A.sort()
    num_negative = bisect_left(A,0)
    num_zero = bisect_right(A,0) - num_negative
    num_positive = N - num_negative - num_zero
    
    inf = 10**18+1
    
    # 答えが負
    if num_negative * num_positive >= K:
        u = 0
        l = A[0]*A[-1]
        def g(i,x):
            up = N
            lp = num_negative + num_zero
            min_m = N
            mp = (up+lp)//2
            while up-lp > 1:
                mp = (up+lp)//2
                if A[i] * A[mp] < x:
                    up = mp
                    
                    min_m = min(min_m,mp)
                else:
                    lp = mp
            mp = (up+lp)//2
            if A[i] * A[mp] < x:

                min_m = min(min_m,mp)

            return max(N-min_m,0)
            

        def f(x):
            ans = 0
            for i in range(num_negative):
                ans += g(i,x)
            return ans

        max_m = l
        while u-l > 1:
            m = (u+l)//2
            if f(m) >= K:
                u = m
            else:
                l = m
                max_m = max(max_m,m)
        return max_m

    # 答えがゼロ
    elif num_negative * num_positive + num_negative * num_zero + num_positive * num_zero + num_zero*(num_zero-1)//2 >= K:
        return 0

    # 答えが正
    else:
        K -= num_negative * num_positive +\
             num_negative * num_zero +\
             num_positive * num_zero + num_zero*(num_zero-1)//2

        def f(i,x):
            u = i
            l = 0
            min_m = N
            m = (u+l)//2
            ans = N
            while u-l > 1:
                m = (u+l)//2
                if A[i] * A[m] < x:
                    u = m
                    # min_m = min(min_m,m)
                    ans = m
                else:
                    l = m
            m = (u+l)//2
            if A[i] * A[m] < x:
                    ans = m


            ans = max(i - ans,0)
            # ans = max(ans,0)
            return ans

        def g(i,x):
            u = N
            l = i+1
            max_m = num_negative + num_zero -1
            m = (u+l)//2
            while u-l > 1:
                m = (u+l)//2
                if A[i] * A[m] < x:
                    l = m
                    max_m = m
                else:
                    u = m
            m = (u+l)//2
            if A[i] * A[m] < x:
                max_m = m
            
            

            ans = max_m - i
            

            ans = max(ans,0)

            
            return ans
            
        def h(x):
            ans = 0
            for i in range(1,num_negative):
                ans += f(i,x)
            preans = ans
            
            for i in range(num_negative+num_zero,N-1):
                ans += g(i,x)

            return ans
        




        u = max(A[0]*A[1],A[-1]*A[-2])+1
        l = 1
        max_m = 1
        while u-l > 1:
            m = (u+l)//2
            if h(m) >= K:
                u = m
            else:
                l = m
                max_m = m

        return max_m




if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

k = input().split()
alist = np.array([int(s) for s in input().split()])

muls = []
f = 0
for i in range(int(k[0])-1):
  a1 = alist[i]
  for a2 in np.array(alist[i+1:]):
    muls.append( a1 * a2 )
muls.sort()
print(muls[int(k[1])-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

k = input().split()
alist = np.array(input().split())

muls = []
f = 0
for i in range(int(k[0])-1):
  a1 = alist[i]
  for a2 in np.array(alist[i+1:]):
    muls.append( int(a1) * int(a2) )
muls.sort()
print(muls[int(k[1])-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

k = input().split()
alist = np.array(input().split())

muls = []
f = 0
for i in range(int(k[0])-1):
  a1 = alist[i]
  for a2 in list(alist[i+1:]):
    muls.append( int(a1) * int(a2) )
muls.sort()
print(muls[int(k[1])-1])

Submission status: Time Limit Exceeded

Solution code:
k = input().split()
alist = input().split()

muls = []
f = 0
for i in range(int(k[0])-1):
  a1 = alist[i]
  for a2 in list(alist[i+1:]):
    muls.append( int(a1) * int(a2) )
muls.sort()
print(muls[int(k[1])-1])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split(" "))
a = sorted(list(map(int, input().split(" "))))
nums = []
total = int(N * (N -1) / 2)

if K < total / 2:
    flag = 0
    for i in range(N):
        if flag == 1 and a[i] < 0:
            continue
        for j in range(i + 1, N):
            num = a[i] * a[j]
            nums.append(a[i] * a[j])
            if a[i] >= 0:
                if j + 1 < N and len(nums) >= K and a[i] * a[j + 1] > sorted(nums)[K - 1]:
                    break
            else:
                if len(nums) >= K and a[i] * a[N - 1] > sorted(nums)[K - 1]:
                    break 
           
        if len(nums) >= K:
            if i + 1 < N and a[i + 1] < 0 and a[i + 1] * a[N - 1] > sorted(nums)[K - 1]:
                flag = 1
            if i + 2 < N and a[i + 1] >= 0 and a[i + 1] * a[i + 2] > sorted(nums)[K - 1]:
                print(sorted(nums)[K - 1])
                # print(len(nums))
                exit()
    print(sorted(nums)[K - 1])
    # print(len(nums))
    
else:
    flag = 0
    a = a[::-1]
    for i in range(N):
        if flag == 1 and a[i] >= 0:
            continue
        elif flag == 1 and a[i] < 0:
            a = a[: i] + a[i:][:: -1]
            flag = 0
        for j in range(i + 1, N):
            num = a[i] * a[j]
            nums.append(a[i] * a[j])
            if j + 1 < N and len(nums) >= total + 1 - K and a[i] * a[j + 1] < sorted(nums, reverse=True)[total - K]:
                break
           
        if len(nums) >= total + 1 - K:
            if i + 2 < N and a[i + 1] >= 0 and a[i + 1] * a[i + 2] < sorted(nums, reverse=True)[total - K]:
                flag = 1
            if i + 2 < N and a[i + 1] < 0 and a[i + 1] * a[i + 2] < sorted(nums, reverse=True)[total - K]:
                print(sorted(nums, reverse=True)[total - K])
                # print(len(nums))
                exit()
                
    print(sorted(nums, reverse=True)[total - K])
    # print(len(nums))

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

array = list(map(int, input().split()))

hq = []

for i in range(len(array)):
    for j in range(i + 1, len(array)):
        tmp = -1 * array[i] * array[j]
        if len(hq) >= k and hq[0] < tmp:
            heapq.heappop(hq)
            heapq.heappush(hq, tmp)
        elif len(hq) < k:
            heapq.heappush(hq, tmp)

print(hq[0] * -1)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split(" "))
a = sorted(list(map(int, input().split(" "))))
nums = []
total = int(N * (N -1) / 2)

if K < total / 2:
    flag = 0
    for i in range(N):
        if flag == 1 and a[i] < 0:
            continue
        for j in range(i + 1, N):
            num = a[i] * a[j]
            nums.append(a[i] * a[j])
           
        if len(nums) >= K:
            if i + 1 < N and a[i + 1] < 0 and a[i + 1] * a[N - 1] > sorted(nums)[K - 1]:
                flag = 1
            if i + 2 < N and a[i + 1] >= 0 and a[i + 1] * a[i + 2] > sorted(nums)[K - 1]:
                print(sorted(nums)[K - 1])
                exit()
    print(sorted(nums)[K - 1])
    
else:
    flag = 0
    a = a[::-1]
    for i in range(N):
        if flag == 1 and a[i] >= 0:
            continue
        elif flag == 1 and a[i] < 0:
            a = a[: i] + a[i:][:: -1]
            flag = 0
        for j in range(i + 1, N):
            num = a[i] * a[j]
            nums.append(a[i] * a[j])
           
        if len(nums) >= total + 1 - K:
            if i + 2 < N and a[i + 1] >= 0 and a[i + 1] * a[i + 2] < sorted(nums, reverse=True)[total - K]:
                flag = 1
            if i + 2 < N and a[i + 1] < 0 and a[i + 1] * a[i + 2] < sorted(nums, reverse=True)[total - K]:
                print(sorted(nums, reverse=True)[total - K])
                exit()
                
    print(sorted(nums, reverse=True)[total - K])

Submission status: Time Limit Exceeded

Solution code:
import collections

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

array = (list(map(int, input().split())))

product_array = []

for i in range(n):
    for j in range(n - (i + 1)):
        product_array.append(array[i] * array[i + j + 1])

product_array.sort()

print(product_array[k - 1])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split(" "))
a = sorted(list(map(int, input().split(" "))))
nums = []
# print(int(N * (N -1) /2))
for i in range(N):
    for j in range(i + 1, N):
        num = a[i] * a[j]
        nums.append(a[i] * a[j])
        if a[i] < 0 and a[i] * a[N - 1] > max(nums) and len(nums) >= K:
            print(sorted(nums)[K -1])
            # print(len(nums))
            exit()
        if j + 1 <= N -1 and a[i] >= 0 and a[i] * a[j + 1] > max(nums) and len(nums) >= K:
            print(sorted(nums)[K -1])
            # print(len(nums))
            exit()
print(sorted(nums)[K - 1])
# print(len(nums))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split(" "))
a = sorted(list(map(int, input().split(" "))))
nums = []
for i in range(N):
    for j in range(i + 1, N):
        nums.append(a[i] * a[j])
    if i + 2 <= N -1:
        if a[i + 1] * a[i + 2] > max(nums) and len(nums) >= K:
            print(sorted(nums)[K -1])
            exit()
print(sorted(nums)[K - 1])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
nc=0
zc=0
pc=0
for i in range(n): #負数の数(nc)、0の数(zc)、正数の数(pc)を数える
 if arr[i]<0:
   nc+=1
 elif arr[i]==0:
   zc+=1
 else:
   pc+=1
ncc=nc*pc #積が負となるペアの個数を求める
zcc=zc*(nc+pc)+(zc*(zc-1))//2 #積が0となるペアの個数を求める
pcc=(nc*(nc-1))//2+(pc*(pc-1))//2 #積が正となるペアの個数を求める
if k<=ncc: #K番目の値が負の場合
 arr1=[]
 arr2=[]
 for i in range(n): #負数、正数をそれぞれ昇順に並べる
   if arr[i]<0:
     arr1.append(-arr[i])
   elif arr[i]>0:
     arr2.append(arr[i])
 arr1=arr1[::-1]
 c1=len(arr1)
 c2=len(arr2)
 l=0
 r=10**18+1
 k=ncc-k
 while r-l!=1:
   mid=(l+r)//2
   cnt=0
   pos=c2-1
   for i in range(c1): #各負数ごとに積が勝手に決めた値midよりも小さくなる正数の個数を求め足し合わせる(しゃくとり法)
     while pos!=-1:
       if arr2[pos]>mid//arr1[i]:
         pos-=1
       else:
         break        
     cnt+=pos+1
   if cnt>k: #勝手に決めた値mid以下の個数がK個以上であれば真の値はmid以下
     r=mid
   else: #そうでなければ真の値はmid以上
     l=mid
 print(-r)
elif k<=(ncc+zcc): #K番目の値が0の場合
 print(0)
else: #K番目の値が正の場合
 arr1=[]
 arr2=[]
 for i in range(n): #負数、正数をそれぞれ昇順に並べる
   if arr[i]<0:
     arr1.append(-arr[i])
   elif arr[i]>0:
     arr2.append(arr[i])
 arr1=arr1[::-1]
 c1=len(arr1)
 c2=len(arr2)
 l=0
 r=10**18+1
 k-=(ncc+zcc) #正数の中で小さい順にK番目の数を調べたいので負数、0の数を取り除く
 while r-l!=1:
   mid=(l+r)//2
   cnt1=0
   pos1=c1-1
   for i in range(c1): #各負数ごとに積が勝手に決めた値midよりも小さくなる負数の個数を求め足し合わせる(しゃくとり法)
     tmp=0
     while pos1!=-1:
       if arr1[pos1]>mid//arr1[i]:
         pos1-=1
       else:
         break
     tmp+=pos1+1
     if arr1[i]**2<mid: #各要素について、自身を2回選んだ場合の積が勝手に決めた値mid以下なら条件を満たすペアの個数を1減らす
       tmp-=1
     cnt1+=tmp
   cnt1=cnt1//2 #上記の処理では同じペアが2回数えられているので個数を半分にする
   cnt2=0
   pos2=c2-1
   for i in range(c2): #各正数ごとに積が勝手に決めた値midよりも小さくなる正数の個数を求め足し合わせる(しゃくとり法)
     tmp=0
     while pos2!=-1:
       if arr2[pos2]>mid//arr2[i]:
         pos2-=1
       else:
         break
     tmp+=pos2+1
     if arr2[i]**2<mid:
       tmp-=1 #各要素について、自身を2回選んだ場合の積が勝手に決めた値mid以下なら条件を満たすペアの個数を1減らす
     cnt2+=tmp
   cnt2=cnt2//2 #上記の処理では同じペアが2回数えられているので個数を半分にする
   cnt=cnt1+cnt2
   if cnt>=k: #勝手に決めた値mid以下の個数がK個以上であれば真の値はmid以下
     r=mid
   else: #そうでなければ真の値はmid以上
     l=mid
 print(r)

Submission status: Time Limit Exceeded

Solution code:
data1=[int(x) for x in input().split()]
data2=[int(x) for x in input().split()]
ls=[]
for i in range(len(data2)):
  for j in range(i+1,len(data2)):
    ls.append(data2[i]*data2[j])
ls.sort()
print(ls[data1[1]-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, K = map(int, input().split())
data = [int(i) for i in input().split()]

c = list(itertools.combinations(data, 2))

top = []
for i in range(K):
  top.append(c[i][0] * c[i][1])
top.sort()
c = c[K:]
for i in c:
  t = i[0] * i[1]
  if t < max(top):
    top.append(t)
    top.sort()
    top = top[:K]
    
print(top[-1])

Submission status: Time Limit Exceeded

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

d_plus = sorted([i for i in a if i>=0])
d_minus = sorted([i for i in a if i<0])

d = []
if len(d_plus)*len(d_minus) > K:
  for i in d_plus:
    for j in d_minus:
      d.append(i*j)
  print(sorted(d)[K-1])
else:
  for i in range(len(d_plus)):
    for j in range(i,len(d_plus)):
      if i==j:
        continue
      else:
        d.append(d_plus[i]*d_plus[j])
  for i in range(len(d_minus)):
    for j in range(i,len(d_minus)):
      if i==j:
        continue
      else:
        d.append(d_minus[i]*d_minus[j])
  print(sorted(d)[K-1-len(d_plus)*len(d_minus)])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math

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

inList.sort()

if inList[0] * inList[N-1] <= 0:
  l_ba = inList[0] * inList[N-1] - 1
else:
  l_ba = inList[0] * inList[1] - 1

r_ba = max(inList[0] * inList[1], inList[N-2] * inList[N-1]) + 1

l_first = l_ba
r_first = r_ba

x = int(0.5 * (l_ba + r_ba))

for time in range(int(math.log2(r_first - l_first)) + 3):
  count = 0
  Ans = l_first
  
  for indx in range(N):
    if inList[indx] <= 0:
      for mulIndx in range(indx, -1, -1):
        if inList[indx] * inList[mulIndx] <= x:
          if indx != mulIndx:
            count += 1
            Ans = max(Ans, inList[indx] * inList[mulIndx])
        else:
          break
    elif inList[indx] > 0:
      for mulIndx in range(indx):
        if inList[indx] * inList[mulIndx] <= x:
          if indx != mulIndx:
            count += 1
            Ans = max(Ans, inList[indx] * inList[mulIndx])
        else:
          break
  
#  print(l_ba, x, r_ba, count)
  
  if count == K:
    break
  elif count < K:
    l_ba = x
    x = int(0.5 * (l_ba + r_ba))
  else:
    r_ba = x
    x = int(0.5 * (l_ba + r_ba))
  
  if (r_ba - l_ba) == 1:
    x = r_ba
    l_ba = r_ba
    break
  elif l_ba == r_ba:
    break
  
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

inList.sort()

if inList[0] * inList[N-1] <= 0:
  l_ba = inList[0] * inList[N-1] - 1
else:
  l_ba = inList[0] * inList[1] - 1

r_ba = max(inList[0] * inList[1], inList[N-2] * inList[N-1]) + 1

l_first = l_ba
r_first = r_ba

x = int(0.5 * (l_ba + r_ba))

for time in range(2 * int(math.log2(r_first - l_first)) + 1):
  count = 0
  Ans = l_first
  
  for indx in range(N):
    if inList[indx] <= 0:
      for mulIndx in range(indx, -1, -1):
        if inList[indx] * inList[mulIndx] <= x:
          if indx != mulIndx:
            count += 1
            Ans = max(Ans, inList[indx] * inList[mulIndx])
        else:
          break
    elif inList[indx] > 0:
      for mulIndx in range(indx):
        if inList[indx] * inList[mulIndx] <= x:
          if indx != mulIndx:
            count += 1
            Ans = max(Ans, inList[indx] * inList[mulIndx])
        else:
          break
  
#  print(l_ba, x, r_ba, count)
  
  if count == K:
    break
  elif count < K:
    l_ba = x
    x = int(0.5 * (l_ba + r_ba))
  else:
    r_ba = x
    x = int(0.5 * (l_ba + r_ba))
  
  if (r_ba - l_ba) == 1:
    x = r_ba
    l_ba = r_ba
    break
  elif l_ba == r_ba:
    break
  
print(Ans)