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:
from collections import deque
import sys

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

mod = 10 ** 9 + 7
num = 0
Ans = 1

if A[-1] < 0 and K % 2 == 1:
    for i in range(K):
        Ans = Ans * A[i] % mod
    print(Ans)
    sys.exit()

while num < K:
    non_minus = A[-1] * A[-2]
    minus = A[0] * A[1]
    if num == K-1 or non_minus > minus:
        Ans = Ans * A.pop() % mod
        num += 1
    else:
        Ans = Ans * A.popleft() * A.popleft() % mod
        num += 2

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()))
#-------------
b = np.abs(a)
b.sort(reverse = True)
b_k = b[k]
a_new = [a[i] for i in range(len(a)) if np.abs(a)[i] > b_k]
 
comb = itertools.combinations(a_new,k)  
l = [list(_) for _ in comb]  
A = (functools.reduce(operator.mul,l[_]) for _ in range(len(l)))
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

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()))
#-------------
b = np.abs(a)
b.sort(reverse = True)
b_k = b[2*k]
a_new = [a[i] for i in range(len(a)) if np.abs(a)[i] > b_k]
 
comb = itertools.combinations(a_new,k)  
l = [list(_) for _ in comb]  
A = (functools.reduce(operator.mul,l[_]) for _ in range(len(l)))
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

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()))
#-------------
b = np.abs(a)
b.sort(reverse = True)
b_k = b[2k]
a_new = [a[i] for i in range(len(a)) if np.abs(a)[i] > b_k]

comb = itertools.combinations(a_new,k)  
l = [list(_) for _ in comb]  
A = (functools.reduce(operator.mul,l[_]) for _ in range(len(l)))
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

Submission status: Runtime Error

Solution code:
import numpy as np
n, k = map(int, input().split())
A = tuple(map(int, input().split()))
A = np.array(A)
mod = 10**9+7
cz = np.sum(np.where(A == 0, 1, 0))
ap = np.sort(A[np.where(A > 0, True, False)])[::-1]
am = np.sort(A[np.where(A < 0, True, False)])

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

elif n == len(am) + cz:
    # 全てが負の場合
    if k%2 == 1:
        # kが奇数の場合積は負、絶対値が小さい方から選ぶ
        if cz > 0:
            print(0)
        else:
            am = np.sort(am)[::-1]
            ans = am[:k].prod()
            print(ans%mod)
    else:
        # kが偶数の場合積は正、絶対値が大きい方から選ぶ
        am = np.sort(am)
        ans = am[:k].prod()
        print(ans%mod)
else:
    # kが奇数の場合、積は奇数個の正と偶数個の負で構成される
    # kが偶数の場合、積は偶数個の正と偶数個の負で構成される
    # kが奇数の場合は、必ず最大の正の値は積に含まれる
    # kが偶数の場合と同じ形にすることができる
    if k%2 == 1:
        k -= 1
        ans = ap[0]
        ap = ap[1:]
    else:
        ans = 1

    # 正の積
    for i in range(0, min(k, len(ap)), 2):
        ans *= (ap[i] * ap[i+1]) % mod
        ans %= mod
    # 負の積
    for i in range(0, max(0, k-len(ap)), 2):
        ans *= (am[i] * am[i-1]) % mod
        ans %= mod

    mans = ans
    pidx = min(k, len(ap))
    midx = max(0, k-len(ap))
    while pidx > 0 or 0 < midx < len(am):
        mans *= (am[midx] * am[midx+1])
        mans //= (ap[pidx-2] * ap[pidx-1])
        mans %= mod
        pidx -= 2
        midx += 2
        ans = max(mans, ans)
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n, k = map(int, input().split())
A = tuple(map(int, input().split()))
A = np.array(A)
mod = 10**9+7
cz = np.sum(np.where(A == 0, 1, 0))
ap = np.sort(A[np.where(A > 0, True, False)])[::-1]
am = np.sort(A[np.where(A < 0, True, False)])

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

elif n == len(am):
    # 全てが負の場合
    if k%2 == 1:
        # kが奇数の場合積は負、絶対値が小さい方から選ぶ
        if cz > 0:
            print(0)
        else:
            am = np.sort(am)[::-1]
            ans = am[:k].prod()
            print(ans%mod)
    else:
        # kが偶数の場合積は正、絶対値が大きい方から選ぶ
        am = np.sort(am)
        ans = am[:k].prod()
        print(ans%mod)
else:
    # kが奇数の場合、積は奇数個の正と偶数個の負で構成される
    # kが偶数の場合、積は偶数個の正と偶数個の負で構成される
    # kが奇数の場合は、必ず最大の正の値は積に含まれる
    # kが偶数の場合と同じ形にすることができる
    if k%2 == 1:
        k -= 1
        ans = ap[0]
        ap = ap[1:]
    else:
        ans = 1

    # 正の積
    for i in range(0, min(k, len(ap)), 2):
        ans *= (ap[i] * ap[i+1]) % mod
        ans %= mod
    # 負の積
    for i in range(0, max(0, k-len(ap)), 2):
        ans *= (am[i] * am[i-1]) % mod
        ans %= mod

    mans = ans
    pidx = min(k, len(ap))
    midx = max(0, k-len(ap))
    while pidx > 0 or 0 < midx < len(am):
        mans *= (am[midx] * am[midx+1])
        mans //= (ap[pidx-2] * ap[pidx-1])
        mans %= mod
        pidx -= 2
        midx += 2
        ans = max(mans, ans)
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n, k = map(int, input().split())
A = tuple(map(int, input().split()))
A = np.array(A)
mod = 10**9+7
cz = np.sum(np.where(A == 0, 1, 0))
ap = np.sort(A[np.where(A > 0, True, False)])[::-1]
am = np.sort(A[np.where(A < 0, True, False)])
absa = sorted(A, key=lambda x: abs(x), reverse=True)

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

elif n == len(am):
    # 全てが負の場合
    if k%2 == 1:
        # kが奇数の場合積は負、絶対値が小さい方から選ぶ
        am = np.sort(am)[::-1]
        ans = am[:k].prod()
        print(ans%mod)
    else:
        # kが偶数の場合積は正、絶対値が大きい方から選ぶ
        am = np.sort(am)
        ans = am[:k].prod()
        print(ans%mod)
else:
    # kが奇数の場合、積は奇数個の正と偶数個の負で構成される
    # kが偶数の場合、積は偶数個の正と偶数個の負で構成される
    # kが奇数の場合は、必ず最大の正の値は積に含まれる
    # kが偶数の場合と同じ形にすることができる
    if k%2 == 1:
        k -= 1
        ans = ap[0]
        ap = ap[1:]
    else:
        ans = 1

    # 正の積
    for i in range(0, min(k, len(ap)), 2):
        ans *= (ap[i] * ap[i+1]) % mod
        ans %= mod
    # 負の積
    for i in range(0, max(0, k-len(ap)), 2):
        ans *= (am[i] * am[i-1]) % mod
        ans %= mod

    mans = ans
    pidx = min(k, len(ap))
    midx = max(0, k-len(ap))
    while pidx > 0 or 0 < midx < len(am):
        mans *= (am[midx] * am[midx+1])
        mans //= (ap[pidx-2] * ap[pidx-1])
        mans %= mod
        pidx -= 2
        midx += 2
        ans = max(mans, ans)
    print(ans)

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7

N, K = mii()
A = lmii()

S = []
T = []

for a in A:
    if a < 0:
        T.append(a)
    else:
        S.append(a)

lenS = len(S)
lenT = len(T)

ok = False
if lenS > 0:
    if N == K:
        ok = lenT % 2 == 0
    else:
        ok = True
else:
    ok = K % 2 == 0

ans = 1
if not ok:
    A.sort(key=lambda x: abs(x))
    for i in range(K):
        ans *= A[i]
        ans %= MOD
else:
    S.sort()
    T.sort(reverse=True)
    if K % 2 == 1:
        ans *= S.pop()
    P = []
    while len(S) >= 2:
        x = S.pop()
        x *= S.pop()
        P.append(x)
    while len(T) >= 2:
        x = T.pop()
        x *= T.pop()
        P.append(x)
    P.sort(reverse=True)
    for i in range(K//2):
        ans *= P[i]
        ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
import heapq as hp
import bisect as bs
import sys
n,k = map(int, input().split())

a = sorted(list(map(int, input().split())))
index = bs.bisect_left(a, 0)

c = a[:index]
index = bs.bisect_right(a, 0)

b = a[index:]

if len(b) + len(c) < k:
  print(0)
  sys.exit()

if len(b) == 0 and k % 2 != 0:
  ans = 1
  c = list(reversed(c))
  for v in c[:k]:
    ans *= v
    ans %= 10**9+7
  
  print(ans)
  sys.exit()
  
  
if len(b) < k:
  if (k - len(b)) % 2 == 0:
    for i in range(k-len(b)):
      b.append(c.pop() * (-1))
  
  else:
    d = []
    c = reversed(c)
    for i in range(len(b)-1):
      d.append(c[i])
      
    for i in range(k-len(b)+1):
      b.append(c[i] * (-1))
  
  
while True:
  if len(c) < 2:
    break
  
  b1 = hp.heappop(b)
  b2 = hp.heappop(b)
    
  c1 = hp.heappop(c)
  c2 = hp.heappop(c)
    
  
  if b1*b2 <= c1*c2:
    hp.heappush(b, c1)
    hp.heappush(b, c2)
  else:
    break
    
ans = 1
for i in range(len(b)):
  ans *= b[i]
  ans %= 10 ** 9 + 7
  
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
import sys
import functools
import operator
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
comb = itertools.combinations(a,k)  
l = [list(_) for _ in comb]  
A = [functools.reduce(operator.mul,l[_]) for _ in len(l)] 
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
import sys
import functools
import operator
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
comb = itertools.combinations(a,k)  
l = (list(_) for _ in comb)
A = (functools.reduce(operator.mul,l[_]) for _ in range(len(l)))
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
import sys
import functools
import operator
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
comb = itertools.combinations(a,k)  
l = [list(i) for _ in comb]  
A = [functools.reduce(operator.mul,l[i]) for i in range(len(l))] 
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

n,k = readints()
a = readints()

mod = 10**9+7

ans = 1
if n==k:
    for x in a:
        ans *= x
        ans %= mod
else:
    plus = []
    minus = []
    zero = []
    for x in a:
        if x>=0:
            plus.append(x)
        elif x<0:
            minus.append(x)
    if len(minus)==n and k%2==1:
        minus.sort(reverse=1)
        for i in range(k):
            ans*=minus[i]
            ans %= mod
    else:
        plus.sort(reverse=1)
        minus.sort()
        i = 0
        j = 0
        if k%2==1:
            ans *= plus[0]
            i+=1
            k-=1
        lp = len(plus)
        lm = len(minus)
        while k>0:
            if i+1<lp and j+1<lm:
                if plus[i]*plus[i+1] > minus[i]*minus[i+1]:
                    ans *= plus[i]*plus[i+1]
                else:
                    ans *= minus[i]*minus[i+1]
            elif i+1<lp:
                ans *= plus[i]*plus[i+1]
            else:
                ans *= minus[i]*minus[i+1]
            ans %= mod
            k-=2
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
mod = 10**9+7

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=0)

def func(a):
    ans = 1
    for _a in a:
        ans = (ans*_a)%mod
    return ans

if len(a) == k:
    ans = func(a)
elif max(a)<0:
    ans = func(a[-k:])
else:
    a.sort(key=lambda x:abs(x), reverse=True)
    pos = a[:k]
    left = a[k:]
    if len([i for i in pos if i<0])%2==1:
        # 総積が負
        posneg = float('inf')
        pospos = -float('inf')
        leftneg = float('inf')
        leftpos = -float('inf')
        for i in pos[::-1]:
            if i < 0:
                posneg = i
                break
        for i in pos[::-1]:
            if i > 0:
                pospos = i
                break
        for i in left:
            if i < 0:
                leftneg = i
                break
        for i in left:
            if i > 0:
                leftpos = i
                break
        if abs(leftpos*pospos) > abs(leftneg*posneg):
            pos.remove(posneg)
            pos.append(leftpos)
        else:
            pos.remove(pospos)
            pos.append(leftneg)
    ans = func(pos)
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
import sys
import functools
import operator
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
if n>=2*k:
  a_plus = heapq.nlargest(k, a)
  a_minus = heapq.nsmallest(k, a)
  a_new = a_plus+a_minus
  comb = itertools.combinations(a_new,k)
else:
  comb = itertools.combinations(a,k)
  
l = [list(i) for i in comb]
  
A = [functools.reduce(operator.mul,l[i]) for i in l]
 
l_max = max(A)
waru = 10**9 + 7
 
mod = l_max % waru
print(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()))
a.sort(reverse=0)

def func(a):
    ans = 1
    for _a in a:
        ans = (ans*_a)%mod
    return ans

if len(a) == k:
    ans = func(a)
elif max(a)<0:
    ans = func(a[-k:])
else:
    a.sort(key=lambda x:abs(x), reverse=True)
    pos = a[:k]
    left = a[k:]
    if len([i for i in pos if i<0])%2==1:
        # 総積が負
        posneg = float('inf')
        pospos = -float('inf')
        leftneg = float('inf')
        leftpos = -float('inf')
        for i in pos[::-1]:
            if i < 0:
                posneg = i
                break
        for i in pos[::-1]:
            if i > 0:
                pospos = i
                break
        for i in left:
            if i < 0:
                leftneg = i
                break
        for i in left:
            if i > 0:
                leftpos = i
                break
        if leftpos*pospos > leftneg*posneg:
            pos.remove(posneg)
            pos.append(leftpos)
        else:
            pos.remove(pospos)
            pos.append(leftneg)
    ans = func(pos)
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
mod = 10**9+7

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=0)

def func(a):
    ans = 1
    for _a in a:
        ans = (ans*_a)%mod
    return ans

if len(a) == k:
    ans = func(a)
elif max(a)<0:
    ans = func(a[-k:])
else:
    a.sort(key=lambda x:abs(x), reverse=True)
    pos = a[:k]
    left = a[k:]
    if len([i for i in pos if i<0])%2==1:
        # 総積が負
        posneg = 1
        pospos = -1
        leftneg = 1
        leftpos = -1
        for i in pos[::-1]:
            if i < 0:
                posneg = i
                break
        for i in pos[::-1]:
            if i > 0:
                pospos = i
                break
        for i in left:
            if i < 0:
                leftneg = i
                break
        for i in left:
            if i > 0:
                leftpos = i
                break
        if leftpos*pospos > leftneg*posneg:
            pos.remove(posneg)
            pos.append(leftpos)
        else:
            pos.remove(pospos)
            pos.append(leftneg)
    ans = func(pos)
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
mod = 10**9+7

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=0)

def func(a):
    ans = 1
    for _a in a:
        ans = (ans*_a)%mod
    return ans

if len(a) == k:
    ans = func(a)
elif max(a)<0:
    ans = func(a[-k:])
else:
    a.sort(key=lambda x:abs(x), reverse=True)
    pos = a[:k]
    left = a[k:]
    if len([i for i in pos if i<0])%2==1:
        # 総積が負
        posneg = 1
        pospos = -1
        leftneg = 1
        leftpos = -1
        for i in pos[::-1]:
            if i < 0:
                posneg = i
                break
        for i in pos[::-1]:
            if i > 0:
                pospos = i
                break
        for i in left:
            if i < 0:
                leftneg = i
                break
        for i in left:
            if i > 0:
                leftpos = i
                break
        if leftpos*pospos < leftneg*posneg:
            pos.remove(posneg)
            pos.append(leftpos)
        else:
            pos.remove(pospos)
            pos.append(leftneg)
    ans = func(pos)
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
mod = 10**9+7

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=0)

def func(a):
    ans = 1
    for _a in a:
        ans = (ans*_a)%mod
    return ans

if len(a) == k:
    ans = func(a)
elif max(a)<0:
    ans = func(a[-k:])
else:
    a.sort(key=lambda x:abs(x), reverse=True)
    pos = a[:k]
    left = a[k:]
    if len([i for i in pos if i<0])%2==1:
        # 総積が負
        posneg = 1
        pospos = -1
        leftpos = 1
        rightpos = -1
        for i in pos[::-1]:
            if i < 0:
                posneg = i
                break
        for i in pos[::-1]:
            if i > 0:
                pospos = i
                break
        for i in left:
            if i < 0:
                leftneg = i
                break
        for i in left:
            if i > 0:
                leftneg = i
                break
        if leftpos*pospos < leftneg*posneg:
            pos.remove(posneg)
            pos.append(leftpos)
        else:
            pos.remove(pospos)
            pos.append(leftneg)
    ans = func(pos)
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
if n>=2*k:
  a_plus = heapq.nlargest(k, a)
  a_minus = heapq.nsmallest(k, a)
  a_new = a_plus+a_minus
  comb = itertools.combinations(a_new,k)
else:
  comb = itertools.combinations(a,k)
  
l = []
for i in comb:
  l.append(list(i))

one = [1]*len(l)
A =[one[i]*=l[i][j] for i in range(len(l)) for j in range(k)]

l_max = max(one)
waru = 10**9 + 7
 
mod = l_max % waru
print(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()))
a.sort(reverse=0)

def func(a):
    ans = 1
    for _a in a:
        ans = (ans*_a)%mod
    return ans

if len(a) == k:
    ans = func(a)
elif max(a)<0:
    ans = func(a[-k:])
else:
    a.sort(key=lambda x:abs(x), reverse=True)
    pos = a[:k]
    left = a[k:]
    if len([i for i in pos if i<0])%2==1:
        # 総積が負
        posneg = 1
        pospos = -1
        leftpos = 1
        rightpos = -1
        for i in pos[::-1]:
            if i < 0:
                posneg = i
                break
        for i in pos[::-1]:
            if i > 0:
                pospos = i
                break
        for i in left[::-1]:
            if i < 0:
                leftneg = i
                break
        for i in left[::-1]:
            if i > 0:
                leftneg = i
                break
        if leftpos*pospos < leftneg*posneg:
            pos.remove(posneg)
            pos.append(leftpos)
        else:
            pos.remove(pospos)
            pos.append(leftneg)
    ans = func(pos)
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
mod = 10**9+7

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=0)

def func(a):
    ans = 1
    for _a in a:
        ans = (ans*_a)%mod
    return ans

if len(a) == k:
    ans = func(a)
elif max(a)<0:
    ans = func(a[-k:])
else:
    a.sort(key=lambda x:abs(x), reverse=True)
    pos = a[:k]
    left = a[k:]
    if len([i for i in pos if i<0])%2==1:
        # 総積が負
        posneg = 1
        pospos = -1
        leftpos = 1
        rightpos = -1
        for i in pos[::-1]:
            if i < 0:
                posneg = i
                break
        for i in pos[::-1]:
            if i > 0:
                pospos = i
                break
        for i in left[::-1]:
            if i < 0:
                leftneg = i
                break
        for i in left[::-1]:
            if i > 0:
                leftneg = i
                break
        if leftpos/posneg > leftneg/pospos:
            pos.remove(posneg)
            pos.append(leftpos)
        else:
            pos.remove(pospos)
            pos.append(leftneg)
    ans = func(pos)
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np

input = sys.stdin.readline
mod = 1000000007


def S():
    return input().rstrip()


def I():
    return int(input())


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


n, k = MI()
a = np.array(list(MI()))

a.sort()
p = a[a > 0]
p = p[::-1]
m = a[a < 0]
lenp = len(p)
lenm = len(m)
# b = np.concatenate([a[a > 0], a[a < 0]])
# lenb = len(b)

ans = 1
if n == k:
    for i in range(k):
        ans *= a[i] % mod
        ans %= mod
elif len(p) + len(m) < k:
    ans = 0
elif lenp == 0:
    m = m[::-1]
    for i in range(k):
        ans *= m[i] % mod
        ans %= mod
else:
    ip, im = 0, 0
    for i in range(k):
        if ip == lenp:
            im = k - ip
            break
        if im == lenm:
            ip = k - im
            break

        if p[ip] >= abs(m[im]):
            ip += 1
        else:
            im += 1

    if im % 2 == 1:
        if p[ip] >= abs(m[im]):
            ip += 1
            im -= 1
        else:
            ip -= 1
            im += 1

    for i in range(ip):
        ans *= p[i] % mod
        ans %= mod

    for i in range(im):
        ans *= m[i] % mod
        ans %= mod

print(ans % mod)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
if n>=2*k:
  a_plus = heapq.nlargest(k, a)
  a_minus = heapq.nsmallest(k, a)
  a_new = a_plus+a_minus
  comb = itertools.combinations(a_new,k)
else:
  comb = itertools.combinations(a,k)
  
l = []
for i in comb:
  l.append(list(i))
  
A = []
one = [1]*len(l)
for i in l:
  for j in range(k):
    one[i]*=l[i][j]
    A.append(one[i])
    
l_max = max(one)
waru = 10**9 + 7
 
mod = l_max % waru
print(mod)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np

input = sys.stdin.readline
mod = 1000000007


def S():
    return input().rstrip()


def I():
    return int(input())


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


n, k = MI()
a = np.array(list(MI()))

a.sort()
p = a[a > 0]
p = p[::-1]
m = a[a < 0]
lenp = len(p)
lenm = len(m)
# b = np.concatenate([a[a > 0], a[a < 0]])
# lenb = len(b)

ans = 1
if n == k:
    for i in range(k):
        ans *= a[i] % mod
        ans %= mod
elif len(p) + len(m) < k:
    ans = 0
elif lenp == 0:
    m = m[::-1]
    for i in range(k):
        ans *= m[i] % mod
        ans %= mod
else:
    ip, im = 0, 0
    for i in range(k):
        if ip == lenp:
            im = k - ip
            break
        if im == lenm:
            ip = k - im
            break

        if p[ip] >= abs(m[im]):
            ip += 1
        else:
            im += 1

    if im % 2 == 1:
        ip -= 1
        im += 1

    for i in range(ip):
        ans *= p[i] % mod
        ans %= mod

    for i in range(im):
        ans *= m[i] % mod
        ans %= mod

print(ans % mod)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
import math
a=list(map(int,input.split()))
a.sort(key=lambda x: abs(x))
res=math.prod(a[:k])
if res>0:
  print(res)
else:
  res1=0
  res2=0
  if a[k]>0:
    if min(a[:k],key=lambda x: abs(x))<0:
      res//=min(a[:k],key=lambda x: abs(x))
      res*=a[k]
  print(res)

Submission status: Runtime Error

Solution code:
#![allow(non_snake_case)]
use std::io::{stdin, Read};
use std::str::FromStr;
fn read_option<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok()
}
fn read<T: FromStr>() -> T {
    let opt = read_option();
    opt.expect("failed to parse token")
}

fn main() {
    let N: usize = read();
    let K: usize = read();
    let mut vec: Vec<i64> = (0..N).map(|_| read()).collect();
    let MOD = 10_i64.pow(9) + 7;
    vec.sort();
    if vec.iter().all(|&x| x < 0) && K % 2 == 1 {
        vec.reverse();
        let mut tmp: i64 = 1;
        for &i in &vec[0..K] {
            tmp *= i as i64;
            tmp %= MOD;
        }
        println!("{}", tmp + MOD);
        return;
    }
    let mut negatives: Vec<i64> = vec
        .iter()
        .filter(|&x| x < &0)
        .copied()
        .map(|x| -x)
        .collect();
    let mut positives: Vec<i64> = vec.iter().filter(|&x| x >= &0).copied().collect();
    negatives.sort();
    positives.sort();
    let mut ans_vec: Vec<i64> = vec![];
    while ans_vec.len() != K {
        if positives.is_empty() {
            let v = negatives.pop().unwrap();
            ans_vec.push(-v);
            continue;
        }
        if negatives.len() < 2 {
            let v = positives.pop().unwrap();
            ans_vec.push(v);
            continue;
        }
        if K - ans_vec.len() == 1 {
            let v = positives.pop().unwrap();
            ans_vec.push(v);
            continue;
        }
        if positives.len() == 1 && K - ans_vec.len() >= 2 {
            let v1 = negatives.pop().unwrap();
            let v2 = negatives.pop().unwrap();
            ans_vec.push(-v1);
            ans_vec.push(-v2);
            continue;
        }
        let neg = negatives[negatives.len() - 1] * negatives[negatives.len() - 2];
        let pos = positives[positives.len() - 1] * positives[positives.len() - 2];
        if pos > neg {
            let v = positives.pop().unwrap();
            ans_vec.push(v);
        } else {
            let v1 = negatives.pop().unwrap();
            let v2 = negatives.pop().unwrap();
            ans_vec.push(-v1);
            ans_vec.push(-v2);
        }
    }
    let mut ans: i64 = 1;
    for v in ans_vec {
        ans *= v;
        ans %= MOD;
    }
    if ans < 0 {
        ans += MOD;
    }
    println!("{}", ans)
}

Submission status: Runtime Error

Solution code:
import itertools
import heapq
n,k = map(int,input().split())
a = list(map(int,input().split()))
if n>=2*k:
  a_plus = heapq.nlargest(k, a)
  a_minus = heapq.nsmallest(k, a)
  a_new = a_plus+a_minus
  comb = itertools.combinations(a_new,k)
else:
  comb = itertools.combinations(a,k)
  
l = []
for i in comb:
  l.append(list(i))
  
A = []
for i in range(len(l)):
  for j in range(k):
    A.append(1*=l[i][j])
    
l_max = max(one)
waru = 10**9 + 7
 
mod = l_max % waru
print(mod)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
n,k = map(int,input().split())
a = list(map(int,input().split()))
if n>=2*k:
  a_plus = heapq.nlargest(k, a)
  a_minus = heapq.nsmallest(k, a)
  a_new = a_plus+a_minus
  comb = itertools.combinations(a_new,k)
else:
  comb = itertools.combinations(a,k)
  
l = []
for i in comb:
  l.append(list(i))
  
one = [1]*len(l)
for i in range(len(l)):
  for j in range(k):
    one[i]*=l[i][j]
    one=[one[i] for i]
    
l_max = max(one)
waru = 10**9 + 7
 
mod = l_max % waru
print(mod)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9+7

if all(a>=0 for a in A):
    A.sort()
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()
if all(a<0 for a in A):
    A.sort(reverse=K%2==0)
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()

arr = []
for a in A:
    if a < 0:
        arr.append((-a,1))
    else:
        arr.append((a,0))

arr.sort()
pz = []
ng = []
for _ in range(K):
    v,s = arr.pop()
    if s:
        ng.append(v)
    else:
        pz.append(v)

if len(ng)%2 == 0:
    ans = 1
    for v in ng:
        ans *= v
        ans %= MOD
    for v in pz:
        ans *= v
        ans %= MOD
    print(ans)
    exit()

b = pz[-1] if pz else None
c = ng[-1] if ng else None
a = d = None
while arr and (a is None or d is None):
    v,s = arr.pop()
    if s:
        if a is None:
            a = v
    else:
        if d is None:
            d = v

if (a is None or b is None) and (c is None or d is None):
    assert False

ans = 1
if a is None or b is None:
    ans = d
    for v in ng[:-1]:
        ans *= v
        ans %= MOD
    for v in pz:
        ans *= v
        ans %= MOD
elif c is None or d is None:
    ans = a
    for v in ng:
        ans *= v
        ans %= MOD
    for v in pz[:-1]:
        ans *= v
        ans %= MOD
else:
    if a*c > b*d:
        ans = a
        for v in ng:
            ans *= v
            ans %= MOD
        for v in pz[:-1]:
            ans *= v
            ans %= MOD
    else:
        ans = d
        for v in ng[:-1]:
            ans *= v
            ans %= MOD
        for v in pz:
            ans *= v
            ans %= MOD
ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
n,k = map(int,input().split())
a = list(map(int,input().split()))
if n>=2k:
  a_plus = heapq.nlargest(k, a)
  a_minus = heapq.nsmallest(k, a)
  a_new = a_plus+a_minus
  comb = itertools.combinations(a_new,k)
else:
  comb = itertools.combinations(a,k)

l = []
for i in comb:
  l.append(list(i))
  
A = []
one = [1]*len(l)
for i in range(len(l)):
  for j in range(k):
    one[i]*=l[i][j]
    A.append(one[i])
    
l_max = max(one)
waru = 10**9 + 7
 
mod = l_max % waru
print(mod)

Submission status: Runtime Error

Solution code:
import itertools
n,k = map(int,input().split())
a = list(map(int,input().split()))
if n>2k:
  a_plus = heapq.nlargest(k, a)
  a_minus = heapq.nsmallest(k, a)
  a_new = a_plus+a_minus
  comb = itertools.combinations(a_new,k)
else:
  comb = itertools.combinations(a,k) 

 
l = []
for i in comb:
  l.append(list(i))
  
A = []
one = [1]*len(l)
for i in range(len(l)):
  for j in range(k):
    one[i]*=l[i][j]
    A.append(one[i])
    
l_max = max(one)
waru = 10**9 + 7
 
mod = l_max % waru
print(mod)