Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Constraints

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

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

The possible products of the three chosen elements are -24, -12, -8, and -6, so the maximum product is -6.

We print this value modulo (10^9+7), that is, 1000000001.

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

The possible products of the one chosen element are -1 and 1000000000, so the maximum product is 1000000000.

Sample Input 4

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

Sample Output 4

999983200

Be sure to print the product modulo (10^9+7).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
A=sorted(list(map(int,input().split())) , key=abs , reverse=1)
import bisect as bi
# print(A)
# import numpy as np
# G=np.prod(A[:k])
def seki(A,mod=10**9+7):
    now=1
    for i in A:
        i=abs(i)
        if i>0 : now*=i
        # if i<0 : now*=i
        if i==0 :return 0
        if now>0 : now%=mod
    return now


# G=seki(A[:k])

mod=10**9+7
# if G>=0 : print(G%mod) ; exit()
if sum([A[i]>0 for i in range(n)])==0 and k%2==1:
  print((-seki(A[n-k:]))%mod) ;exit()
if n==k and len(A[bi.bisect_left(A,-1):])%2==1 :
    print((-seki(A))%mod) ;exit()
if sum([i<0 for i in A[:k]])%2==0 :
    print(seki(A[:k])%mod) ; exit()
  
  
# done=0 ; done2=0
# # ch=-73267983297 ; ch2=-9263498381621
# 
# for i in range(k-1,-1,-1):
#     if A[i]<0 and done==0:
#         for j in range(i+1,n):
#             if A[j]>=0: 
#                 # ch=G*A[j]//A[i]
#                 x1=A[j] ; y1=A[i]
#                 done=1
#                 break
#     if A[i]>0 and done2==0:
#         for j in range(i+1,n):
#             if A[j]<=0: 
#                 # ch2=G*A[j]//A[i]
#                 x2=A[j] ; y2=A[i]
#                 done2=1
#                 break
# #     if done==1 and done2==1 : break
# 
# G=seki(A[:k])
# G=-G
# if done and done2 :
#     if x1 * y2 > x2 * y1 :
#         print((G*x1//y1)%mod)
#     else:
#         print((G*x2//y2)%mod)
# elif done==1:
#     print((G*x1//y1)%mod)
# elif done2==1:
#     print((G*x2//y2)%mod)
        
CH=A[:k]
NO=A[k:]
done=0 ; done2=0
x1,x2,y1,y2=0,0,0,0
if sum([i<0 for i in CH])==0 : #CH全部+
    done=1
if sum([i<0 for i in NO])==0 : #NO全部+
    done2=1
if done==0:
    y1= [i for i in CH if i<0][-1]
    x1= [i for i in NO if i>0][0]
if done2==0:
    y2= [i for i in CH if i>0][-1]
    x2= [i for i in NO if i<0][0]

if x1 * y2 > x2 * y1 :
    print((-seki(CH)*x1//y1)%mod)
else:
    print((-seki(CH)*x2//y2)%mod)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
A=sorted(list(map(int,input().split())) , key=abs , reverse=1)
# print(A)
# import numpy as np
# G=np.prod(A[:k])
def seki(A,mod=10**9+7):
    now=1
    for i in A:
        now*=i %mod
        now%=mod
    return now


G=seki(A[:k])

mod=10**9+7
if G==0 or sum([i<0 for i in A[:k]])%2==0 : print(G%mod) ; exit()
if sum([A[i]>0 for i in range(n)])==0 and k%2==1:
  print(seki(A[n-k:])) ; exit()
  
  
  
done=0 ; done2=0
ch=-73267983297 ; ch2=-9263498381621

for i in range(k-1,-1,-1):
    if A[i]<0 and done==0:
        for j in range(i+1,n):
            if A[j]>=0: 
                # ch=G*A[j]//A[i]
                x1=A[j] ; y1=A[i]
                done=1
                break
    if A[i]>0 and done2==0:
        for j in range(i+1,n):
            if A[j]>=0: 
                # ch2=G*A[j]//A[i]
                x2=A[j] ; y2=A[i]
                done2=1
                break
    if done==1 and done2==1 : break

if x1 * y2 > x2 * y1 :
    print((G*x1//y1)%mod)
else:
    print((G*x2//y2)%mod)

Submission status: Runtime Error

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

B=[]
onlyminus=True
for i in range(N):
    if A[i]>=0:
        B.append([A[i],1])
        onlyminus=False
    else:
        B.append([abs(A[i]),-1])

C=[]
ans=1
div=7+10**9

if onlyminus:
    A.sort(reverse=True)
    for i in range(K):
        ans*=A[i]
else:
    B.sort(reverse=True)
    cnt=0
    for i in range(K):
        C.append(B[i])
        if B[i][1]==-1:
            cnt+=1

    if cnt%2==1:
        Ck=copy.deepcopy(C[-1])
        del C[-1]
        i=K
        if Ck[1]==1:
            while B[i][1]==1:
                i+=1
        else:
            while B[i][1]==-1:
                i+=1
        C.append(B[i])

    for i in range(K):
        ans*=C[i][0]

print(ans%div)

Submission status: Runtime Error

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
if N == K:
    result = 1
    for i in range(K):
        result = result * A[i] % M
    print(result)
    exit()
minus = [i for i in A if i < 0]
l_minus = len(minus)
plus = [i for i in A if i > 0]
l_plus = len(plus)
plus.sort(reverse=1)
minus.sort()
if len(plus) == 0 and K % 2 == 1:
    result = 1
    for i in range(K):
        result = result * minus[-i-1] % M
    print(result)
    exit()
if l_plus + l_minus < K:
    print(0)
    exit()

m_x = 0
p_x = 0
max_mm = -1
if (m_x+1) * 2 <= l_minus:
    max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
max_pp = -1
if (p_x+1) * 2 <= l_plus:
    max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
counter = 0
array = []
while counter * 2 + 1 < K:
    if max_pp > max_mm:
        array.append(plus[p_x * 2])
        array.append(plus[p_x * 2 + 1])
        p_x += 1
        if (p_x+1) * 2 <= l_plus:
            max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
        else:
            max_pp = -1

    else:
        array.append(minus[m_x * 2])
        array.append(minus[m_x * 2 + 1])
        m_x += 1
        if (m_x+1) * 2 <= l_minus:
            max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
        else:
            max_mm = -1
    counter += 1
if K%2 == 1:
    array.append(plus[p_x * 2])
result = 1
for each in array:
    result = result * each % M
print(result)

Submission status: Runtime Error

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
if N == K:
    result = 1
    for i in range(K):
        result = result * A[i] % M
    print(result)
    exit()
minus = [i for i in A if i < 0]
l_minus = len(minus)
plus = [i for i in A if i >= 0]
l_plus = len(plus)
plus.sort(reverse=1)
minus.sort()
if len(plus) == 0 and K % 2 == 1:
    result = 1
    for i in range(K):
        result = result * minus[-i-1] % M
    print(result)
    exit()

m_x = 0
p_x = 0
max_mm = -1
if (m_x+1) * 2 <= l_minus:
    max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
max_pp = -1
if (p_x+1) * 2 <= l_plus:
    max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
counter = 0
array = []
while counter * 2 + 1 <= K:
    if max_pp > max_mm:
        array.append(plus[p_x * 2])
        array.append(plus[p_x * 2 + 1])
        p_x += 1
        if (p_x+1) * 2 <= l_plus:
            max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
        else:
            max_pp = -1

    else:
        array.append(minus[m_x * 2])
        array.append(minus[m_x * 2 + 1])
        m_x += 1
        if (m_x+1) * 2 <= l_minus:
            max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
        else:
            max_mm = -1
    counter += 1
if K%2 == 1:
    array.append(plus[p_x * 2])
result = 1
for each in array:
    result = result * each % M
print(result)

Submission status: Runtime Error

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
if N == K:
    result = 1
    for i in range(K):
        result = result * A[i] % M
    print(result)
    exit()
minus = [i for i in A if i <= 0]
l_minus = len(minus)
plus = [i for i in A if i > 0]
l_plus = len(plus)
plus.sort(reverse=1)
minus.sort()
if len(plus) == 0 and K % 2 == 1:
    result = 1
    for i in range(K):
        result = result * minus[-i-1] % M
    print(result)
    exit()

m_x = 0
p_x = 0
max_mm = -1
if (m_x+1) * 2 <= l_minus:
    max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
max_pp = -1
if (p_x+1) * 2 <= l_plus:
    max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
counter = 0
array = []
while counter * 2 + 1 <= K:
    if max_pp > max_mm:
        array.append(plus[p_x * 2])
        array.append(plus[p_x * 2 + 1])
        p_x += 1
        if (p_x+1) * 2 <= l_plus:
            max_pp = plus[p_x * 2] * plus[p_x * 2 + 1]
        else:
            max_pp = -1
    elif max_pp == -1 and max_mm == -1:
        break
    else:
        array.append(minus[m_x * 2])
        array.append(minus[m_x * 2 + 1])
        m_x += 1
        if (m_x+1) * 2 <= l_minus:
            max_mm = minus[m_x * 2] * minus[m_x * 2 + 1]
        else:
            max_mm = -1
    counter += 1
if K%2 == 1:
    array.append(plus[p_x * 2])
result = 1
for each in array:
    result = result * each % M
print(result)

Submission status: Runtime Error

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
A = sorted(A, key=abs, reverse=1)
# 負の数になる場合
if max(A) < 0:
    result = 1
    for i in range(K):
        result = result * A[-i-1] % M
    print(result)
    exit()

minimum_minus_id = K
minimum_plus_id = K
minus_count = 0

for i in range(K):
    if A[i] < 0:
        minus_count += 1
        minimum_minus_id = i
    else:
        minimum_plus_id = i
result = 1

if minus_count%2 == 1:
    # 一番小さい負の数を正の数にするか、一番小さい正の数を負の数にするか
    second_minus_id = N
    second_plus_id = N

    for i in range(K, N):
        if A[i] >= 0:
            second_plus_id = i
            break
    for i in range(K, N):
        if A[i] < 0:
            second_minus_id = i
            break
    if second_minus_id == N or minimum_plus_id == K:
        A[minimum_minus_id] = A[second_plus_id]
    elif second_plus_id == N:
        A[minimum_plus_id] = A[second_minus_id]
    elif minimum_minus_id == K:
        pass
    else:
        if A[minimum_minus_id] * A[second_minus_id ] > A[minimum_plus_id] * A[second_plus_id]:
            A[minimum_plus_id] = A[second_minus_id]
        else:
            A[minimum_minus_id] = A[second_plus_id]

for i in range(K):
    result = result * A[i] % M
print(result)

Submission status: Runtime Error

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
A = sorted(A, key=abs, reverse=1)
# 負の数になる場合
if max(A) < 0:
    result = 1
    for i in range(K):
        result = result * A[-i-1] % M
    print(result)
    exit()

minimum_minus_id = K
minimum_plus_id = K
minus_count = 0

for i in range(K):
    if A[i] < 0:
        minus_count += 1
        minimum_minus_id = i
    else:
        minimum_plus_id = i
result = 1

if minus_count%2 == 1:
    # 一番小さい負の数を正の数にするか、一番小さい正の数を負の数にするか
    second_minus_id = N
    second_plus_id = N

    for i in range(K, N):
        if A[i] >= 0:
            second_plus_id = i
            break
    for i in range(K, N):
        if A[i] < 0:
            second_minus_id = i
            break
    if second_minus_id == N or minimum_plus_id == K:
        A[minimum_minus_id] = A[second_plus_id]
    elif second_plus_id == N:
        A[minimum_plus_id] = A[second_minus_id]

    else:
        if A[minimum_minus_id] * A[second_minus_id ] > A[minimum_plus_id] * A[second_plus_id]:
            A[minimum_plus_id] = A[second_minus_id]
        else:
            A[minimum_minus_id] = A[second_plus_id]

for i in range(K):
    result = result * A[i] % M
print(result)

Submission status: Runtime Error

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
A = sorted(A, key=abs, reverse=1)
# 負の数になる場合
if max(A) < 0:
    result = 1
    for i in range(K):
        result = result * A[-i-1] % M
    print(result)
    exit()

minimum_minus_id = K
minimum_plus_id = K
minus_count = 0

for i in range(K):
    if A[i] < 0:
        minus_count += 1
        minimum_minus_id = i
    else:
        minimum_plus_id = i
result = 1

if minus_count%2 ==1:
    # 一番小さい負の数を正の数にするか、一番小さい正の数を負の数にするか
    second_minus_id = N
    second_plus_id = N

    for i in range(K, N):
        if A[i] >= 0:
            second_plus_id = i
            break
    for i in range(K, N):
        if A[i] < 0:
            second_minus_id = i
            break
    if second_minus_id == N:
        A[minimum_minus_id] = A[second_plus_id]
    elif second_plus_id == N:
        A[minimum_plus_id] = A[second_minus_id]
    else:
        if A[minimum_minus_id] * A[second_minus_id ] > A[minimum_plus_id] * A[second_plus_id]:
            A[minimum_plus_id] = A[second_minus_id]
        else:
            A[minimum_minus_id] = A[second_plus_id]

for i in range(K):
    result = result * A[i] % M
print(result)

Submission status: Runtime Error

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
A = sorted(A, key=abs, reverse=1)
# 負の数になる場合
if max(A) < 0:
    result = 1
    for i in range(K):
        result = result * A[-i-1] % M
    print(result)
    exit()

minimum_minus_id = K
minimum_plus_id = K
minus_count = 0

for i in range(K):
    if A[i] < 0:
        minus_count += 1
        minimum_minus_id = i
    else:
        minimum_plus_id = i
result = 1

if minus_count%2 ==1:
    # 一番小さい負の数を正の数にするか、一番小さい正の数を負の数にするか
    second_minus_id = N
    second_plus_id = N

    for i in range(K, N):
        if A[i] >= 0:
            second_plus_id = i
            break
    for i in range(K, N):
        if A[i] < 0:
            second_minus_id = i
            break
    if second_minus_id == N:
        A[minimum_minus_id] = A[second_plus_id]
    else:
        if A[minimum_minus_id] * A[second_minus_id ] > A[minimum_plus_id] * A[second_plus_id]:
            A[minimum_plus_id] = A[second_minus_id]
        else:
            A[minimum_minus_id] = A[second_plus_id]

for i in range(K):
    result = result * A[i] % M
print(result)

Submission status: Runtime Error

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
M = 10**9 + 7
A = sorted(A, key=abs, reverse=1)
# 負の数になる場合
if max(A) < 0:
    result = 1
    for i in range(K):
        result = result * A[-i-1] % M
    print(result)
    exit()

minimum_minus_id = K
minimum_plus_id = K
minus_count = 0

for i in range(K):
    if A[i] < 0:
        minus_count += 1
        minimum_minus_id = i
    else:
        minimum_plus_id = i
result = 1

if minus_count%2 ==1:
    # 一番小さい負の数を正の数にするか、一番小さい正の数を負の数にするか
    max_mm = A[minimum_minus_id]
    second_minus_id = N
    max_pp = A[minimum_plus_id]
    second_plus_id = N

    for i in range(K, N):
        if A[i] >= 0:
            second_minus_id = i
            break
    for i in range(K, N):
        if A[i] < 0:
            second_plus_id = i
            break
    if second_minus_id == N:
        A[minimum_minus_id] = A[second_plus_id]
    else:
        if A[minimum_minus_id] * A[second_minus_id ] > A[minimum_plus_id] * A[second_plus_id]:
            A[minimum_plus_id] = A[second_minus_id]
        else:
            A[minimum_minus_id] = A[second_plus_id]

for i in range(K):
    result = result * A[i] % M
print(result)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9+7
plus,minus = [],[]

for i in range(N):
  if A[i] < 0:
    minus.append(A[i])
  else:
    plus.append(A[i])

plus.sort(reverse=True)
ans = 1

if N == K:
  for a in A:
    ans *= a
elif plus == []:
  if K%2 == 0:
    minus.sort()
    for i in range(K):
      ans *= minus[i]
  else:
    minus.sort(reverse=True)
    for i in range(K):
      ans *= minus[i]
elif minus == []:
  for i in range(K):
      ans *= plus[i]
else:
  minus.sort()
  for i in range(1,len(plus)):
    plus[i] *= plus[i-1]
  for i in range(1,len(minus)):
    minus[i] *= minus[i-1]
  for i in range(K):
    ans = max(plus[K-1],minus[K-1])
    if i < len(plus) and K-i+1 < len(minus):
      ans = max(ans,plus[i]*minus[K-i])
  
print(ans%mod)

Submission status: Runtime Error

Solution code:
import copy

N,K = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9+7
A.sort()
ans = 1
num1,num2 = 1,1
num = 0
if K%2 == 0:
  for i in range(0,K,2):
    ans *= (A[-i-1]*A[-i-2])
  num2 = copy.copy(ans)
  for i in range(0,K,2):
    num1 *= (A[i]*A[i+1])
    num2 //= (A[N-K+1-i]*A[N-K-i])
    ans = max(ans, num1*num2)
else:
  for i in range(K):
    ans *= A[-i-1]
  num2 = copy.copy(ans)
  for i in range(K):
    num1 *= A[i]
    num2 //= A[N-K-i]
    ans = max(ans, num1*num2)%mod
print(ans%mod)

Submission status: Runtime Error

Solution code:
import numpy as np

a = np.array(a)

a_sort_raw = sorted(a)
a_arg_raw = np.argsort(a)

a_abs = list(map(abs,a))
a_abs = np.array(a_abs)

a_sort = sorted(a_abs,reverse=True)

a_arg = np.argsort(-a_abs)
a_arg_r = np.argsort(a_abs)

a_pow = 1

if all([1 if i < 0 else 0 for i in a]):
    for i in range(k):
        a_pow *= a[a_arg_r[i]]

else:
    for i in range(k):
        a_pow *= a[a_arg[i]]

    a_arg_k = a_arg[0:k]
    a_arg_k_ = a_arg[k:]
    
    if a_pow < 0:
        a_pow_p = 1
        for i in reversed(a_arg_k):
            if a[i] < 0:
                for j in a_arg_k_:
                    if a[j] > 0:
                        a_pow_p = a_pow/a[i]*a[j]
                        break
                break
                
        a_pow_m = 1
        for i in reversed(a_arg_k):
            if a[i] > 0:
                for j in a_arg_k_:
                    if a[j] < 0:
                        a_pow_m = a_pow/a[i]*a[j]
                        break
                break
        if a_pow_p > a_pow_m:
            a_pow = a_pow_p
            print(a_pow_p)
        else:
            a_pow = a_pow_m
            print(a_pow_m)

output = a_pow % (10**9 + 7)
print(output)

Submission status: Runtime Error

Solution code:
"""
9 5
-4 -3 -2 -1 0 1 2 3
"""

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
Am = []
Ap = []
for a in A:
    if a < 0:
        Am.append(a)
    else:
        Ap.append(a)

mod = 10**9 + 7

ans = 1

if N == K:
    for a in A:
        ans *= a
        ans %= mod

elif A[-1] < 0:
    if K % 2 = 1
        for i in range(K):
            ans *= Am[-1-i]
            ans %= mod
    else:
        for i in range(K):
            ans *= Am[i]
            ans %= mod

else:
    if K%2 == 1:
        ans *= Ap[-1]
        ans %= mod
        K -= 1
        del Ap[-1]
    Amd = []     
    Apd = []
    for i in range(len(Ap)//2):
        Apd.append(Ap[-1-(2*i)]*Ap[-1-(2*i+1)])
    for i in range(len(Am)//2):
        Amd.append(Am[2*i]*Am[2*i+1])
    Apd.append(-1)
    Amd.append(-1)
    
    ip = 0
    im = 0
    while K > 0:
        if Apd[ip] >= Amd[im]:
            ans *= Apd[ip]
            ip += 1
        else:
            ans *= Amd[im]
            im += 1
        ans %= mod
        K -= 2


ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
import time
t0 = time.time()
def wait(s):
    while time.time() - t < s:
        pass

N, K = map(int, input().split())
A = [(int(x), abs(int(x))) for x in input().split()]

MOD = 10 ** 9 + 7

if K == 1:
    A.sort(key=lambda x: -x[0])
    ans = A[0][0] % MOD
    wait(0.9)
else:
    A.sort(key=lambda x: -x[1])

    # A

    ans = 1
    pos = 1
    for i in range(K-2):
#         print(ans)
        ans = (ans * A[i][1]) % MOD
        if A[i][0] > 0:
            pass
        elif A[i][0] < 0:
            pos *= -1
        else:
            pos = 0

    # ans, pos

    if pos == 0:
        ans = 0
        wait(1)
    elif pos > 0:
        pp_c = 0
        pp = 1
        mm_c = 0
        mm = 1
        for i in range(K-2, N):
            if pp_c < 2 and A[i][0] > 0:
                pp *= A[i][0]
                pp_c += 1
            if mm_c < 2 and A[i][0] < 0:
                mm *= A[i][0]
                mm_c += 1
            if pp_c >= 2 and mm_c >= 2:
                break
        if pp_c == mm_c == 2:
            ans = (ans * max(pp, mm)) % MOD
            wait(1.1)
        elif pp_c == 2:
            ans = (ans * pp) % MOD
            wait(1.2)
        elif mm_c == 2:
            ans = (ans * mm) % MOD
            wait(1.3)
        else:
            if A[-1][0] == 0:
                ans = 0
                wait(1.4)
            else:
                ans = (ans * pp * mm) % MOD
                wait(1.5)
    elif pos < 0:
        pp_c = 0
        pp = 1
        mm_c = 0
        mm = 1
        for i in range(K-2, N):
            if pp_c == 0 and A[i][0] > 0:
                pp *= A[i][0]
                pp_c += 1
            if mm_c == 0 and A[i][0] < 0:
                mm *= A[i][0]
                mm_c += 1
            if pp_c == 1 and mm_c == 1:
                break
        if pp_c == mm_c == 1:
            ans = (ans * pp * mm) % MOD
            wait(1.6)
        else:
            ans = 1
            count = 0
            for i in range(N-1, -1, -1):
                if A[i][0] == 0: continue
                ans = (ans * A[i][0]) % MOD
                count += 1
                if count == K:
                    break
            if count < K:
                ans = 0
                wait(1.7)
print(ans)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7

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

neg = []
zero = 0
pos = []
for a in A:
    if a < 0:
        neg.append(a)
    else:
        pos.append(a)

pos.sort()
neg.sort(reverse=True)

if len(pos) == 0:
    res = 1
    A = A[:K] if K % 2 == 1 else A[-K:]
    for a in A:
        res *= a
        res %= mod
else:
    res = 1
    while K > 1 and len(pos) > 1 and len(neg) > 1:
        if pos[-1] * pos[-2] > neg[-1] * neg[-2]:
            res *= pos.pop()
            res %= mod
            res *= pos.pop()
            res %= mod
        else:
            res *= neg.pop()
            res %= mod
            res *= neg.pop()
            res %= mod
        K -= 2
    while K > 1 and len(pos) > 1:
        res *= pos.pop()
        res %= mod
        res *= pos.pop()
        res %= mod
        K -= 2
    while K > 1 and len(neg) > 1:
        res *= pos.pop()
        res %= mod
        res *= pos.pop()
        res %= mod
        K -= 2
    while K and pos:
        res *= pos.pop()
        res %= mod
        K -= 1
    while K and neg:
        res *= neg.pop()
        res %= mod
        K -= 1


print(res)

Submission status: Runtime Error

Solution code:
a, b = map(int,input().split())
li = list(map(int,input().split()))

xx = 10**9+7
li = sorted(li,key = abs)

def mut(lis):
    res = 1
    for i in lis:
        res*=i
    return res

if all([i<0 for i in li]):
    res = 1
    for i in li[:b]:
        res *= i
    print (int(res%xx))
else:
    res1,res2 = 0,0
    if mut(li[-b:])<0:
        for i in range(b):
            if li[-i]<0:
                res1 = 1/li[-i]
            elif li[-i]>0:
                res2 = 1/li[-i]
        for i in range(len(li) - b):
            if li[i]<0:
                res1 *= li[i]
            elif li[i]>0:
                res2 *= li[i]
        print(int(mut(li[-b:])*max(res1,res2)%xx))
    else:
        print(int(mut(li[-b:])%xx))

Submission status: Runtime Error

Solution code:
a, b = map(int,input().split())
li = list(map(int,input().split()))

xx = 1e+9+7
li = sorted(li,key = abs)

def mut(lis):
    res = 1
    for i in lis:
        res*=i
    return res

if all([i<0 for i in li]):
    res = 1
    for i in li[:b]:
        res *= i
    print (int(res%xx))
else:
    while mut(li[-b:])<0:
        for i in li[-b:]:
            if i < 0:
                li.pop(li.index(i))
                break
    print(int(mut(li[-b:])%xx))

Submission status: Runtime Error

Solution code:
xx = 1e+9+7
li = sorted(li,key = abs)

def mut(lis):
    res = 1
    for i in lis:
        res*=i
    return res

if all([i<0 for i in li]):
    res = 1
    for i in li[:b]:
        res *= i
    print (int(res%xx))
else:
    while mut(li[-b:])<0:
        for i in li[-b:]:
            if i < 0:
                li.pop(li.index(i))
                break
    print(int(mut(li[-b:])%xx))

Submission status: Runtime Error

Solution code:
INF = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
plus_lst, minus_lst = [], []
plus, minus = 0, 0
ans = 1
if K == N:
  for i in A:
    ans = (ans * i) % INF
  ans %= INF
  print(ans)
else:
  for _ in range(N):
    a = A.pop()
    if a >= 0:
      plus_lst += [a]
      # plus += 1
    else:
      minus_lst += [-a]
      # minus += 1
  if K % 2 and plus == 0:
    minus_lst = sorted(minus_lst)
    for i in range(K):
      ans = (ans * minus_lst[i]) % INF
    ans *= -1
    ans %= INF
    print(ans)
  else:
    plus_lst = sorted(plus_lst, reverse=True)
    minus_lst = sorted(minus_lst, reverse=True)
    a = plus_lst.pop(0) if plus_lst else 0
    b = plus_lst.pop(0) if plus_lst else 0
    c = minus_lst.pop(0) if minus_lst else 0
    d = minus_lst.pop(0) if minus_lst else 0
    for i in range(K//2):
      plus_num = a * b
      minus_num = c * d
      if plus_num > minus_num:
        ans = (ans * plus_num) % INF
        a = plus_lst.pop(0) if plus_lst else 0
        b = plus_lst.pop(0) if plus_lst else 0
      else:
        ans = (ans * minus_num) % INF
        c = minus_lst.pop(0) if minus_lst else 0
        d = minus_lst.pop(0) if minus_lst else 0
    if K % 2 == 1:
      ans = (ans * a) % INF
    print(ans)

Submission status: Runtime Error

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
D,E=[],[]
zcnt,scnt,fcnt=0,0,0
for i in A:
  if i==0:
    zcnt+=1
    D.append(0)
  elif i>0:
    D.append(i)
    scnt+=1
  else:
    E.append(i)
    fcnt+=1
mod=10**9+7
ans=1
if K==N:
  for i in A:
    ans*=i
    ans%=mod
  print(ans)
  exit()
if K%2==1 and max(A)<0:
  A=sorted(A)[::-1]
  for i in range(K):
    ans*=A[i]
    ans%=mod
  print(ans)
  exit()
if K>scnt+fcnt:
  print(0)
  exit()
D,E=sorted(D)[::-1],sorted(E)
#print(D,E)
ans=1
a,b=0,0
for i in range(K//2):
  if len(D)>=2 and len(E)>=2:
    d,e=D[a]*D[a+1],E[b]*E[b+1]
    if d>e:
      ans*=d
      a+=2
      ans%=mod
    else:
      ans*=e
      b+=2    
      ans%=mod
  elif len(D)>=2 and len(E)<2:
    d=D[a]*D[a+1]
    ans*=d
    a+=2
    ans%=mod
  elif len(D)<2 and len(E)>=2:
    e=E[b]*E[b+1]
    ans*=e
    b+=2
    ans%=mod

if K%2==1:
  Z=[]
  if a!=scnt:
    Z.append(D[a])
  if b!=fcnt:
    Z.append(E[-1])
  if 0 in A:
    Z.append(0)
  ans*=max(Z)
  ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
from functools import reduce
from operator import mul,add

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

lista = sorted(lista,key = lambda x:abs(x),reverse=True)
ans = reduce(mul,lista[0:k])

buff = 0
if ans < 0 and lista[-1] < 0 and k % 2 == 1:
  print(ans%1000000007)
  exit()
if ans < 0:
  para = ans
  ans /= lista[k]
  tmp = lista[k]
  while 1:
    k+=1
    if lista[k] > 0:
      para *= buff
      ans *= lista[k]
      ans = max(para,ans)
      break
    else:
      if not buff:
        buff = lista[k]
    
        
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 1

if k == n:
    for i in range(n):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
if max(a) < 0 and k%2 == 1:
    a.sort(reverse=True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()

plus, minus = [], []
for i in range(n):
    if a[i] >= 0: plus.append(a[i])
    else: minus.append(a[i])

plus.sort()
minus.sort(reverse=True)
while k > 0:
    if len(plus) >= 2: nump = plus[-1] * plus[-2]
    elif len(plus) == 1: nump = plus[-1]
    else: nump = -10**10
    if len(minus) >= 2: numm = minus[-1] * minus[-2]
    elif len(minus) == 1: numm = minus[-1]
    else: numm == -10**10
    if nump > numm or k == 1:
        ans *= plus.pop()
        ans %= mod
        k -= 1
    else:
        ans *= minus.pop()
        ans *= minus.pop()
        ans %= mod
        k -= 2
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 1

if k == n:
    for i in range(n):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
if max(a) < 0:
    a.sort(reverse=True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()

plus, minus = [], []
for i in range(n):
    if a[i] >= 0: plus.append(a[i])
    else: minus.append(a[i])

plus.sort()
minus.sort(reverse=True)
while k > 0:
    if len(plus) >= 2: nump = plus[-1] * plus[-2]
    elif len(plus) == 1: nump = plus[-1]
    else: nump = -10**10
    if len(minus) >= 2: numm = minus[-1] * minus[-2]
    elif len(minus) == 1: numm = minus[-1]
    else: numm == -10**10
    if nump > numm or k == 1:
        ans *= plus.pop()
        ans %= mod
        k -= 1
    else:
        ans *= minus.pop()
        ans *= minus.pop()
        ans %= mod
        k -= 2
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 1

if k == n:
    for i in range(n):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
if max(a) < 0:
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()

plus, minus = [], []
for i in range(n):
    if a[i] >= 0: plus.append(a[i])
    else: minus.append(a[i])

plus.sort()
minus.sort(reverse=True)
while k > 0:
    if len(plus) >= 2: nump = plus[-1] * plus[-2]
    elif len(plus) == 1: nump = plus[-1]
    else: nump = -10**10
    if len(minus) >= 2: numm = minus[-1] * minus[-2]
    elif len(minus) == 1: numm = minus[-1]
    else: numm == -10**10
    if nump > numm or k == 1:
        ans *= plus.pop()
        ans %= mod
        k -= 1
    else:
        ans *= minus.pop()
        ans *= minus.pop()
        ans %= mod
        k -= 2
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 1

if k == 1:
    print(max(a))
    exit()

lst = []
minus = []
for i in range(n):
    if a[i] >= 0:
        lst.append([a[i], 1])
    else:
        minus.append(a[i])

if k % 2 == 1 and lst != []:
    lst.sort(key=lambda x: x[0])
    ans *= lst.pop()[0]
    k -= 1
elif k % 2 == 1 and lst == []:
    a.sort(reverse=True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()

minus.sort(reverse=True)
while minus != []:
    if len(minus) >= 2:
        a = minus.pop()
        b = minus.pop()
        lst.append([a*b, 2])
    else:
        a = minus.pop()
        lst.append([a, 1])

lst.sort(key=lambda x: x[0])
while k > 0:
    lst1 = lst.pop()
    lst2 = lst.pop()
    if [lst1[1], lst2[1]] == [1, 1]:
        ans *= lst1[0]
        ans %= mod
        ans *= lst2[0]
        ans %= mod
    elif [lst1[1], lst2[1]] == [1, 2]:
        ans *= lst2[0]
        ans %= mod
        lst.append(lst1)
    elif [lst1[1], lst2[1]] == [2, 1]:
        ans *= lst1[0]
        ans %= mod
        lst.append(lst2)
    else:
        ans *= lst1[0]
        ans %= mod
        lst.append(lst2)
    k -= 2
print(ans)