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:
import copy
from sys import exit
n, k = map(int, input().split())
A = list(map(int, input().split()))

mod = 10**9 + 7

plus = []
minus = []
for a in A:
    if a >= 0:
        plus.append(a)
    else:
        minus.append(a)
plus.sort()
minus.sort(reverse=True)

def is_ans_plus():
    if len(plus) > 0:
        if n == k:
            if len(minus) % 2 == 0:
                return True
            else:
                return  False
        else:
            return True
    else:
        if k % 2 == 0:
            return True
        else:
            return False

ans = 1
if is_ans_plus():
    if k % 2 == 1:
        ans *= plus.pop()
        k -= 1
    for i in range(k // 2):
        plus_pair, minus_pair = -1, -1
        if len(plus) >= 2:
            plus_pair = plus[-1] * plus[-2]
        if len(minus) >= 2:
            minus_pair = minus[-1] * minus[-2]
        if plus_pair >= minus_pair:
            ans *= plus_pair
            plus.pop()
            plus.pop()
        else:
            ans *= minus_pair
            minus.pop()
            minus.pop()
        ans %= mod
else:
    ans = 1
    for i in range(k):
        ans *= minus[i]
        ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
import heapq
from collections import defaultdict, deque
from decimal import *
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))
mod=1000000007

'''E Multiplication 4'''
n,k=rm()
a=rl()
pos=[]
neg=[]
for i in a:
    if i>=0:
        pos.append(i)
    elif i<0:
        neg.append(i)

pos.sort(reverse=True)
neg.sort()
negg=[::-1]

for i in range(1,len(pos)):
    pos[i]=(pos[i-1]*pos[i])
for j in range(1,len(neg)):
    neg[j]=(neg[j-1]*neg[j])
    negg[j]=(negg[j-1]*negg[j])

if len(pos)==0:
    if k%2==0:
        print(neg[k-1]%mod)
    else:
        print(negg[k-1]%mod)
elif len(neg)==0:
    print(pos[k-1]%mod)
else:
    maxi=-math.inf
    for i in range(0,k+1,2):
        if i==0:
            if k-i<=len(pos):
                maxi=max(maxi,pos[k-i-1])
        elif k-i==0:
            if i<=len(neg):
                maxi=max(maxi,neg[i-1])
        elif i<=len(neg) and k-i<=len(pos):
            maxi=max(maxi,neg[i-1]*pos[k-i-1])
    print(maxi)

Submission status: Runtime Error

Solution code:
import bisect
N,K = map(int, input().split())
A_list = [int(e) for e in input().split()]

#負・0・正の三つに分ける
A_list.sort(reverse=False)
zero_left = bisect.bisect_left(A_list,0)
zero_right = bisect.bisect_right(A_list,0)

A_list_minus = A_list[:zero_left]
A_list_zero = A_list[zero_left:zero_right]
A_list_plus = A_list[zero_right:]

minus_num = len(A_list_minus)
zero_num = len(A_list_zero)
plus_num = len(A_list_plus)

if plus_num+(minus_num//2)*2 >= K and ((minus_num//2)*2<=K or K%2 ==0):
    # + に出来る
    A_list_minus.sort(reverse=True)
    A_list_plus.sort(reverse=False)
    ans = 1
    cnt = 0
    mm = 0
    pp = 0
    while 1:
        # + と - から2個ずつ(-,-でも+になるように)選んでいく。マイナス側はラス1を残しておく
        if cnt == K-2 and ans > 0 and mm == 0:
            mm = A_list_minus[-1]*A_list_minus[-2]
        elif len(A_list_minus)>=3 and mm == 0:
            mm = A_list_minus[-1]*A_list_minus[-2]
        else:
            mm = 0
            
        if len(A_list_plus)>=2 and pp == 0:
            pp = A_list_plus[-1]*A_list_plus[-2]
        else:
            pp = 0
        
        if mm >= pp:
            ans *= mm
            A_list_minus.pop(-1)
            A_list_minus.pop(-1)
            mm = 0
        else:
            ans *= pp
            A_list_plus.pop(-1)
            A_list_plus.pop(-1)
            pp = 0
            
        cnt += 2
        
        if cnt == K:
            break
        elif cnt == K-1:
            if ans < 0:
                ans *= A_list_minus[-1]
            else:
                ans *= A_list_plus[-1]
            break
            
elif zero_num != 0:
    # 0 に出来る
    ans = 0
else:
    # - にしか出来ない
    A_list_minus.sort(reverse=False)
    A_list_plus.sort(reverse=True)
    ans = 1
    cnt = 0
    mm = 10**10
    pp = 10**10
    while 1:
        # + と - から絶対値が小さいものを1個ずつ選んでいく。ラス1は残しておく
        
        if len(A_list_minus)>=2 and mm == 10**10:
            mm = A_list_minus[-1]
        else:
            mm = 10**10
        if len(A_list_plus)>=2 and pp == 10**10:
            pp = A_list_plus[-1]
        else:
            pp =10**10
        
        if abs(mm) >= pp:
            ans *= pp
            A_list_plus.pop(-1)
            pp = 10**10
        else:
            ans *= mm
            A_list_minus.pop(-1)
            mm = 10**10
            
        cnt += 1
        
        if cnt == K-1 and K%2==1:
            if ans < 0:
                ans *= A_list_minus[-1]
            elif ans > 0:
                ans *= A_list_plus[-1]
            break
        elif cnt == K-1 and K%2==0:
            if ans < 0:
                ans *= A_list_minus[-1]
            elif ans > 0:
                ans *= A_list_plus[-1]
            break    
            
            
        elif cnt == K-2 and len(A_list_minus) == 1 and len(A_list_plus) == 1: #両方ともラス1残しなので、K-2での止まり防止
            ans *= A_list_minus[-1]*A_list_plus[-1]
            break
            
print(ans%(7+10**9))

Submission status: Runtime Error

Solution code:
import bisect
N,K = map(int, input().split())
A_list = [int(e) for e in input().split()]

#負・0・正の三つに分ける
A_list.sort(reverse=False)
zero_left = bisect.bisect_left(A_list,0)
zero_right = bisect.bisect_right(A_list,0)

A_list_minus = A_list[:zero_left]
A_list_zero = A_list[zero_left:zero_right]
A_list_plus = A_list[zero_right:]

minus_num = len(A_list_minus)
zero_num = len(A_list_zero)
plus_num = len(A_list_plus)

if plus_num+(minus_num//2)*2 >= K:
    # + に出来る
    A_list_minus.reverse(True)
    A_list_plus.reverse(False)
    ans = 1
    cnt = 0
    mm = 0
    pp = 0
    while 1:
        # + と - から2個ずつ(-,-でも+になるように)選んでいく。マイナス側はラス1を残しておく
        if len(A_list_minus)>=3 and mm == 0:
            mm = A_list_minus[-1]*A_list_minus[-2]
        else:
            mm = 0
            
        if len(A_list_plus)>=2 and pp == 0:
            pp = A_list_plus[-1]*A_list_plus[-2]
        else:
            pp = 0
        
        if mm >= pp:
            ans *= mm
            A_list_minus.pop(-1)
            A_list_minus.pop(-1)
            mm = 0
        else:
            ans *= pp
            A_list_plus.pop(-1)
            A_list_plus.pop(-1)
            pp = 0
            
        cnt += 2
        
        if cnt == K:
            break
        elif cnt == K-1:
            if ans < 0:
                ans *= A_list_minus[-1]
            else:
                ans *= A_list_plus[-1]
            break
            
elif zero_num != 0:
    # 0 に出来る
    ans = 0
else:
    # - にしか出来ない
    A_list_minus.reverse(False)
    A_list_plus.reverse(True)
    ans = 1
    cnt = 0

    while 1:
        # + と - から絶対値が小さいものを1個ずつ選んでいく。ラス1は残しておく
        if len(A_list_minus)>=2 and mm == 10**10:
            mm = A_list_minus[-1]
        else:
            mm = 10**10
        if len(A_list_plus)>=2 and pp == 10**10:
            pp = A_list_plus[-1]
        else:
            pp =10**10
        
        if abs(mm) >= pp:
            ans *= pp
            A_list_plus.pop(-1)
            pp = 10**10
        else:
            ans *= mm
            A_list_minus.pop(-1)
            mm = 10**10
            
        cnt += 1
        
        elif cnt == K-1:
            if ans < 0:
                ans *= A_list_minus[-1]
            elif ans > 0:
                ans *= A_list_plus[-1]
            break
        elif cnt == K-2 and len(A_list_minus) == 1 and len(A_list_plus) == 1: #両方ともラス1残しなので、K-2での止まり防止
            ans *= A_list_minus[-1]*A_list_plus[-1]
            break
            
print(ans)

Submission status: Runtime Error

Solution code:
#関数リスト
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

n, k = MI()
mylist = LI()
plus = [i for i in mylist if i >= 0]
plus.sort(reverse = True)
minus = [i for i in mylist if i < 0]
minus.sort()
mod = 10e9 + 7
index = k
result = 1

while index > 0:
    if index == 1:
        if len(plus) != 0:
            result *= plus[0]
            plus = plus[1:]
            index -= 1
        else:
            result *= minus[-1]
            index -= 1
    else:
        if len(plus) == 0:
            if index % 2 == 0:
                for i in range(index):
                    result *= minus[i]
                index = 0
            else:
                index2 = len(minus)
                for i in range(index):
                    result *= minus[index2-1-i]
                index = 0
        elif len(plus) == 1:
            if len(minus) >= 2:
                if minus[0]*minus[1] > plus[1]:
                    result *= minus[0]*minus[1]
                    index -= 2
                    minus = minus[2:]
                else:
                    result *= plus[0]
                    plus = []
                    index -= 1
            else:
                result *= plus[0]*minus[0]
                index -= 2
        else:
            if len(minus) <= 1:
                result *= plus[0]
                plus = plus[1:]
                index -= 1
            else:
                if minus[0]*minus[1] > plus[0]*plus[1]:
                    result *= minus[0]*minus[1]
                    index -= 2
                    minus = minus[2:]
                else:
                    result *= plus[0]
                    index -= 1
                    plus = plus[1:]
print(int(result % mod))

Submission status: Runtime Error

Solution code:
#関数リスト
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

n, k = MI()
mylist = LI()
plus = [i for i in mylist if i >= 0]
plus.sort(reverse = True)
minus = [i for i in mylist if i < 0]
minus.sort()
mod = 10e9 + 7
index = k
result = 1

while index > 0:
    if index == 1:
        if len(plus) != 0:
            result *= plus[0]
            plus = plus[1:]
            index -= 1
        else:
            result *= minus[-1]
            index -= 1
    else:
        if len(plus) == 0:
            if index % 2 == 0:
                for i in range(index):
                    result *= minus[i]
                index = 0
            else:
                index2 = len(minus)
                for i in range(index):
                    result *= minus[index2-1-i]
                index = 0
        elif len(plus) == 1:
            if len(minus) >= 2:
                if minus[0]*minus[1] > plus[1]:
                    result *= minus[0]*minus[1]
                    index -= 2
                    minus = minus[2:]
                else:
                    result *= plus[0]
                    plus = []
                    index -= 1
            else:
                result *= plus[0]*minus[0]
                index -= 2
        else:
            if len(minus) <= 1:
                result *= plus[0]
                plus = plus[1:]
                index -= 1
            else:
                if minus[0]*minus[1] > plus[0]*plus[1]:
                    result *= minus[0]*minus[1]
                    index -= 2
                    minus = minus[2:]
                else:
                    result *= plus[0]
                    index -= 1
                    plus = plus[1:]
print(int(result % mod))

Submission status: Runtime Error

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K:
        if(i >= K-1 or len(M)<=1 or P[0]*P[1]>=M[0]*M[1]):
            i +=1
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            i +=2
            ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod


print(ans2)

Submission status: Runtime Error

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a >= 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K:
        if(i >= K-1 or len(M)<=1 or P[0]*P[1]>=M[0]*M[1]):
            i +=1
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            i +=2
            ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod


print(ans2)

Submission status: Runtime Error

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K:
        if(i >= K-1 or len(M)<=1 or P[0]*P[1]>M[0]*M[1]):
            i +=1
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            i +=2
            ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod


print(ans2)

Submission status: Runtime Error

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0
 
if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K-1:
        if(len(P)>=2 and len(M)>=2):
            if(P[0]*P[1]<=M[0]*M[1]):
                i +=2
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                i +=1
                ans2 = -ans2*heapq.heappop(P)*%mod
        elif len(P)==1:
            if len(M)>=2 and -P[0] <= M[0]*M[1]:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
            else:
                ans2 = -ans2*heapq.heappop(P)%mod
                i += 1
        elif len(P)==0:
            if len(M)>=2:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
        elif len(M)<=1:
            ans2 = -ans2*heapq.heappop(P)%mod
            i += 1
    while i < K:
        i += 1
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            ans2 = ans2*heapq.heappop(M)%mod

print(ans2)

Submission status: Runtime Error

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

A.sort()
ans = 1
if k == n:
  for a in A:
    ans = a * ans % mod
  exit(print(ans))

if A[-1] <= 0:
  if k%2 == 0:
    for a in A[:k]:
      #ans = ans * a % mod
  else:
    for a in A[-k:]:
      ans = ans * a % mod
  exit(print(ans))
elif A[0] > 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
else:
  i = 1
  while (A[i] < 0) & (k >= 2):
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]*A[-k]:
      ans = ans * x*y % mod
      k -= 2
    else:break
    i += 2
    if i > n:break
  if k == 0: exit(print(ans))
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))

Submission status: Runtime Error

Solution code:
import itertools
import heapq
import sys
import functools
import operator
import numpy as np
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
a_high = sorted(a , reverse=True)
a_high_k = a_high[:k]
a_low = sorted(a)
a_low_k = a_low[:k]
a_new = a_high_k + a_low_k
D = [[a_new[i+j-k] for j in range(k)] for i in range(2k)]
A = (functools.reduce(operator.mul,D[_]) for _ in range(len(D)))
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()
a.sort(key = lambda x:abs(x), reverse=True)

use = a[:k]
ans = 1
f = 0
plus = -1
minus = -1
for i in use:
    if i < 0:
        f ^= 1
    if i >= 0:
        plus = i
    else:
        minus = i
    ans *= abs(i)
    ans %= mod

if f == 0:
    print(ans)
else:
    if max(a) < 0:
        ans = 1
        for i in range(n-1, n-k-1,-1):
            ans *= abs(a[i])
            ans %= mod
        if k % 2:
            print((-ans) % mod)
        else:
            print(ans)
    else:
        ret1 = -inf
        ret2 = inf
        if min(a[k:]) >= 0:
            if plus != -1:
                ret1 = plus * max(a[k:])
                ans *= pow(minus, mod-2, mod)
                ans %= mod
        elif min(a[k:]) < 0:
            if minus != -1:
                ret2 = minus * min(a[k:])
                ans *= pow(minus, mod-2, mod)
                ans %= mod
        if ret1 >= ret2:
            ans *= ret1
            ans %= mod
        else:
            ans *= ret2
            ans %= mod
        print(ans)

Submission status: Runtime Error

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

a = list(map(int, input().split()))
a_pos = list(sorted(filter(lambda x: x > 0, a)))
a_neg = list(sorted(filter(lambda x: x < 0, a), reverse=True))

mod = 10 ** 9 + 7
ans = 1

if len(a_pos) == 0 and k % 2:
    for i in a_neg[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

while k > 0:
    if k == 1 or len(a_neg) <= 1:
        if len(a_pos) == 0:
            ans *= a_neg.pop()
        elif len(a_pos) > 0:
            ans *= a_pos.pop()
        k -= 1
    elif len(a_pos) <= 1:
        ans *= a_neg.pop() * a_neg.pop()
        k -= 2
    
    elif a_pos[-1] * a_pos[-2] > a_neg[-1] * a_neg[-2]:
        ans *= a_pos.pop()
        k -= 1
    elif a_pos[0] * a_pos[1] <= a_neg[-1] * a_neg[-2]:
        ans *= a_neg.pop() * a_neg.pop()
        k -= 2
    ans %= mod

else:
    print(ans)

Submission status: Runtime Error

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

a = list(map(int, input().split()))
a_pos = list(sorted(filter(lambda x: x > 0, a), reverse=True))
a_neg = list(sorted(filter(lambda x: x < 0, a)))

mod = 10 ** 9 + 7
ans = 1

if len(a_pos) == 0 and k % 2:
    for i in a_neg[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

while k > 0:
    if k == 1 or len(a_neg) <= 1:
        if len(a_pos) == 0:
            ans *= a_neg.pop()
        elif len(a_pos) > 0:
            ans *= a_pos.pop()
        k -= 1
    elif len(a_pos) <= 1:
        ans *= a_neg.pop() * a_neg.pop()
        k -= 2
    
    elif a_pos[0] * a_pos[1] > a_neg[0] * a_neg[1]:
        ans *= a_pos.pop(0)
        k -= 1
    elif a_pos[0] * a_pos[1] <= a_neg[0] * a_neg[1]:
        ans *= a_neg.pop(0) * a_neg.pop(0)
        k -= 2
    ans %= mod

print(ans)

Submission status: Runtime Error

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

mod = 10 ** 9 + 7
plus = []
zero = []
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)
lp = len(plus)
lm = len(minus)

if len(zero) + K > N:
  print(0)
  exit()
elif lp == 0: 
  if K % 2 == 1:
    if len(zero) > 0:
      print(0)
      exit()
    else:
      for k in range():
        ans = ans * (-1) * minus[- k - 1] % mod  
      print(ans)
      exit()
  else:
    for k in range(K):
      ans = ans * (-1) * minus[k] % mod
    print(ans)
    exit()
elif lm == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  exit()

p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m]:
    p += 1
    if p == lp:
      m = K - p  
      break
  else:
    m += 1
    if m == lm:
      p = K - m
      break

def main(mp, mm, plus, minus, mod, K):
  if mp > len(plus) or mm > len(minus):
    exit()
  ans = 1
  for k in range(mp):
    ans = ans * plus[k] % mod
  for k in range(mm):
    ans = ans * (-1) * minus[k] % mod
  print(ans)
  exit()

if m%2 == 0:
  main(p, m, plus, minus, mod, K)
else:
  if p == lp:
    if m != lm:
      main(p - 1, m + 1, plus, minus, mod, K)
    else:
      if len(zero) > 0:
        print(0)
        exit()
      else:
        main(p, m, plus, minus, mod, K)
  elif m == lm:
    main(p + 1, m - 1, plus, minus, mod, K)
  elif p == 0:
    main(p + 1, m - 1, plus, minus, mod, K)
  else:
    if plus[p] * plus[p - 1] > minus[m - 1] * minus[m]:
      main(p + 1, m - 1, plus, minus, mod, K)
    else:
      main(p - 1, m + 1, plus, minus, mod, K)

Submission status: Runtime Error

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

mod = 10 ** 9 + 7
plus = []
zero = []
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)
lp = len(plus)
lm = len(minus)

if len(zero) + K > N:
  print(0)
  exit()
elif lp == 0: 
  if K % 2 == 1:
    if len(zero) > 0:
      print(0)
      exit()
    else:
      for k in range():
        ans = ans * (-1) * minus[- k - 1] % mod  
      print(ans)
      exit()
  else:
    for k in range(K):
      ans = ans * (-1) * minus[k] % mod
    print(ans)
    exit()
elif lm == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  exit()

p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m]:
    p += 1
    if p == lp:
      m = K - p  
      break
  else:
    m += 1
    if m == lm:
      p = K - m
      break

def main(mp, mm, plus, minus, mod, K):
  if mp < 0 or mm < 0:
    exit()  
  ans = 1
  for k in range(mp):
    ans = ans * plus[k] % mod
  for k in range(mm):
    ans = ans * (-1) * minus[k] % mod
  print(ans)
  exit()

if m%2 == 0:
  main(p, m, plus, minus, mod, K)
else:
  if p == lp:
    if m != lm:
      main(p - 1, m + 1, plus, minus, mod, K)
    else:
      if len(zero) > 0:
        print(0)
        exit()
      else:
        main(p, m, plus, minus, mod, K)
  elif m == lm:
    main(p + 1, m - 1, plus, minus, mod, K)
  elif p == 0:
    main(p + 1, m - 1, plus, minus, mod, K)
  else:
    if plus[p] * plus[p - 1] > minus[m - 1] * minus[m]:
      main(p + 1, m - 1, plus, minus, mod, K)
    else:
      main(p - 1, m + 1, plus, minus, mod, K)

Submission status: Runtime Error

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

mod = 10 ** 9 + 7
plus = []
zero = []
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)
lp = len(plus)
lm = len(minus)

if len(zero) + K > N:
  print(0)
  exit()
elif lp == 0: 
  if K % 2 == 1:
    if len(zero) > 0:
      print(0)
      exit()
    else:
      for k in range():
        ans = ans * (-1) * minus[- k - 1] % mod  
      print(ans)
      exit()
  else:
    for k in range(K):
      ans = ans * (-1) * minus[k] % mod
    print(ans)
    exit()
elif lm == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  exit()

p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m]:
    p += 1
    if p == lp:
      m = K - p  
      break
  else:
    m += 1
    if m == lm:
      p = K - m
      break

def main(mp, mm, plus, minus, mod, K):
  ans = 1
  for k in range(mp):
    ans = ans * plus[k] % mod
  for k in range(mm):
    ans = ans * (-1) * minus[k] % mod
  print(ans)
  exit()

if m%2 == 0:
  main(p, m, plus, minus, mod, K)
else:
  if p == lp:
    if m != lm:
      main(p - 1, m + 1, plus, minus, mod, K)
    else:
      if len(zero) > 0:
        print(0)
        exit()
      else:
        main(p, m, plus, minus, mod, K)
  elif m == lm:
    main(p + 1, m-1, plus, minus, mod, K)
  elif p == 0:
    main(p + 1, m-1, plus, minus, mod, K)
  else:
    if plus[p] * plus[p-1] > minus[m-1] * minus[m]:
      main(p + 1, m-1, plus, minus, mod, K)
    else:
      main(p - 1, m + 1, plus, minus, mod, K)

Submission status: Runtime Error

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

mod = 10 ** 9 + 7
plus = []
zero = []
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)
lp = len(plus)
lm = len(minus)

if len(zero) + K > N:
  print(0)
  exit()
elif lp == 0: 
  if K % 2 == 1:
    if len(zero) > 0:
      print(0)
      exit()
    else:
      for k in range():
        ans = ans * (-1) * minus[- k - 1] % mod  
      print(ans)
      exit()
  else:
    for k in range(K):
      ans = ans * (-1) * minus[k] % mod
    print(ans)
    exit()
elif lm == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  exit()

p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m]:
    p += 1
    if p == lp:
      m = K - p  
      break
  else:
    m += 1
    if m == lm:
      p = K - m
      break

def main(mp, mm, plus, minus, mod, K):
  ans = 1
  for k in range(mp):
    ans = ans * plus[k] % mod
  for k in range(mm):
    ans = ans * (-1) * minus[k] % mod
  print(ans)
  exit()

if m%2 == 0:
  main(p, m, plus, minus, mod, K)
else:
  if p == lp:
    if m != lm:
      main(p-1, m, plus, minus, mod, K)
    else:
      if len(zero) > 0:
        print(0)
        exit()
      else:
        main(p, m, plus, minus, mod, K)
  elif m == lm:
    main(p, m-1, plus, minus, mod, K)
  elif p == 0:
    main(p, m-1, plus, minus, mod, K)
  else:
    if plus[p] * plus[p-1] > minus[m-1] * minus[m]:
      main(p, m-1, plus, minus, mod, K)
    else:
      main(p-1, m, plus, minus, mod, K)

Submission status: Runtime Error

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K-1:
        i += 1
        if(len(P)>=2 and len(M)>=2):
            i +=1
            if(P[0]*P[1]<M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                ans2 = ans2*(heapq.heappop(P)*heapq.heappop(P))%mod
        elif len(P)==1:
            if len(M)>=2 and -P[0] < M[0]*M[1]:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 1
            else:
                ans2 = -ans2*heapq.heappop(P)%mod
        elif len(P)==0:
            ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            i += 1
        elif len(M)<=1:
            ans2 = -ans2*heapq.heappop(P)%mod
    if i < K:
        ans2 = -ans2*heapq.heappop(P)%mod


print(ans2)

Submission status: Runtime Error

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

mod = 10 ** 9 + 7
plus = []
zero = []
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)
lp = len(plus)
lm = len(minus)

if lp == 0 and K % 2 == 1:
  for k in range(K):
    ans = ans * minus[- k - 1] % mod
  ans = -1 * ans % mod  
  print(ans)
  exit()
if lp == 0 and K % 2 == 0:
  for k in range(K):
    ans = ans * minus[k] % mod
  print(ans)
  exit()
if lm == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  exit()
if len(zero) + K > N:
  print(0)
  exit()

p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m]:
    p += 1
    if p == lp:
      m = K - p  
      break
  else:
    m += 1
    if m == lm:
      p = K - m
      break

def main(mp, mm, plus, minus, mod, K):
  p = 0
  m = 0
  ans = 1
  if mp == 0:
    for _ in range(K):
      ans = ans * minus[_] % mod
  elif mm == 0:
    for _ in range(K):
      ans = ans * plus[_] % mod
  else:
    for _ in range(K):
      if plus[p] >= minus[m]:
        ans = ans * plus[p] % mod
        p += 1
        if p == mp:
          for j in range(K - p - m):
            ans = ans * minus[m + j] % mod
          break
      else:
        ans = ans * minus[m] % mod
        m += 1
        if m == mm:
          for j in range(K - p - m):
            ans = ans * plus[p + j] % mod
          break  
  print(ans)
  exit()

if m%2 == 0:
  main(lp, lm, plus, minus, mod, K)
else:
  if p == lp:
    if m != lm:
      main(lp-1, lm, plus, minus, mod, K)
    else:
      if len(zero) > 0:
        print(0)
        exit()
      else:
        main(lp, lm, plus, minus, mod, K)
  elif m == lm:
    main(lp, lm-1, plus, minus, mod, K)
  elif p == 0:
    main(lp, lm-1, plus, minus, mod, K)
  else:
    if plus[p] * plus[p-1] > minus[m-1] * minus[m]:
      main(lp, lm-1, plus, minus, mod, K)
    else:
      main(lp-1, lm, plus, minus, mod, K)