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 = list(map(int, input().split()))

A_minus = []
A_plus = []
A_zero_count = 0

for a in A:
    if a > 0:
        A_plus.append(a)
    elif a == 0:
        A_zero_count += 1
    else:
        A_minus.append(a)

A_plus.sort(reverse=True)
A_minus.sort()

MOD = 10 ** 9 + 7


def get_all_mul(area):
    ans = 1
    for a_check in area:
        ans = mul(ans, a_check)
    return ans


def mul(mul_a, mul_b):
    return (mul_a * mul_b) % MOD


def solve():
    ans = 1
    if N == K:
        return get_all_mul(A)

    if K + A_zero_count > N:
        return 0

    if len(A_plus) == 0:
        if A_zero_count == 0:
            if K & 1:
                return get_all_mul(A_minus[-K:])
            else:
                return get_all_mul(A_minus[:K])
        else:
            if K & 1:
                return 0
            else:
                return get_all_mul(A_minus[:K])
    elif len(A_minus) == 0:
        return get_all_mul(A_plus[:K])
    else:
        if K + A_zero_count == N:
            if len(A_minus) & 1:
                return 0
            else:
                return mul(get_all_mul(A_minus), get_all_mul(A_plus))

        A_plus.append(0)
        A_minus.append(0)
        plus_choice_num = 0
        minus_choice_num = 0
        last_plus_choice = 0
        last_minus_choice = 0
        for _ in range(K):
            if A_plus[plus_choice_num] > -A_minus[minus_choice_num]:
                ans = mul(ans, A_plus[plus_choice_num])
                last_plus_choice = A_plus[plus_choice_num]
                plus_choice_num += 1
            else:
                ans = mul(ans, A_minus[minus_choice_num])
                last_minus_choice = A_minus[minus_choice_num]
                minus_choice_num += 1
        if minus_choice_num & 1 == 0:
            return ans
        else:
            if last_plus_choice * A_plus[plus_choice_num] >= last_minus_choice * A_minus[minus_choice_num]:
                change = mul(-last_minus_choice, A_plus[plus_choice_num])
            else:
                change = mul(-last_plus_choice, A_plus[minus_choice_num])
            return mul(ans, change)

print(solve())

Submission status: Runtime Error

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

def do():
    n, k = map(int, input().split())
    dat = list(map(int, input().split()))
    buf = []
    nump, numm, numz = 0, 0, 0
    for i in range(n):
        if dat[i] == 0:
            numz += 1
        elif dat[i] > 0:
            nump += 1
            buf.append([dat[i], dat[i]])
        elif dat[i] < 0:
            numm += 1
            buf.append([dat[i], -dat[i]])
    indm = []
    indp = []
    # +と-を足してもk個に満たないなら 0 をかけるしかないので
    if len(buf) < k:
        print(0)
        return

    for i in range(n):
        if buf[i][0] < 0:
            indm.append(i)
        else:
            indp.append(i)
    buf.sort(key=lambda x: x[1], reverse=True)

    #print(nump, numm, numz)
    #print(buf)
    #print(indm)
    #print(indp)

    res = 1
    lastp = None
    lastm = None
    flagPosi = True
    
    for i in range(k):
        res *= buf[i][0]
        res %= mod
        if buf[i][0] > 0:
            lastp = buf[i][0]
        elif buf[i][0] < 0:
            lastm = buf[i][0]
            flagPosi = not flagPosi

    # k個選んで正なら、無条件にオッケー
    if flagPosi:
        print(res%mod)
        return

    def do2(): # negaしか作れないなら最も小さい値
        buf.sort(key=lambda x: x[1], reverse=False)
        res2 = 1
        for i in range(k):
            res2 *= buf[i][0] % mod
            res2 %= mod
        print(res2%mod)

    def do3(anti, kawari): # negaしか作れないなら最も小さい値
        ispass = False
        buf.sort(key=lambda x: x[1], reverse=True)
        res2 = 1
        for i in range(k):
            if ispass is False and buf[i][0] == anti:
                ispass = True
                continue
            res2 *= buf[i][0] % mod
            res2 %= mod
        res2 *= kawari
        print(res2%mod)

    # 負の場合は二パターン
    # 1. 正を抜いて、次に大きい負をかける
    # 2. 負を抜いて、次に大きい正をかける
    nextp = None
    nextm = None
    for i in range(k, len(buf)):
        if buf[i][0] > 0 and nextp is None:
            nextp = buf[i][0]
        elif buf[i][0] < 0 and nextm is None:
            nextm = buf[i][0]
    #print("---",lastp, lastm, nextp,nextm)
    if (lastp is None or nextm is None) and (lastm is None or nextp is None):
        # この場合、動かせないので負しかないから
        do2()
        return
    if lastp is not None and lastm is not None and nextp is not None and nextm is not None:
        # 全部あるなら戦い
        #if abs(nextm / lastp) > abs(nextp / lastm):
        if abs(nextm / 1) > abs(nextp / 1):
            # pをmにした方がいいので
            do3(lastp, nextm)
            return
        else:
            do3(lastm, nextp)
            return
    # この場合、どっちしかないので
    if (lastp is None or nextm is None) and lastm is not None and lastp is not None:
        # この場合、 m-> p
        do3(lastm, nextp)
        return
    elif lastp is not None and nextm is not None:
        do3(lastp, nextm)
        return

do()

Submission status: Runtime Error

Solution code:
import sys
mod=10**9+7
n,k=map(int,input().split())
ax=list(map(int,input().split()))
a=[]

chkm=1
for i in range(n):
    if ax[i]>0: a.append([abs(ax[i]),1]);chkm=0
    elif ax[i]<0: a.append([abs(ax[i]),-1])
    else: a.append([0,0])
a=sorted(a,reverse=True)

if chkm==1:
    ans=1
    for i in range(k):
        ans=ans*a[n-1-i][0]%mod
    print((mod-ans)%mod)
    sys.exit()


lp,lm=[],[]
cntm=0;ans=1
for i in range(k):
    [p,sgn]=a[i]
    ans=ans*p%mod
    if sgn==1: lp.append(p)
    elif sgn==-1:
        lm.append(p)
        cntm=(cntm+1)%2
    elif sgn==0: ans=0;break

if cntm==0 or ans==0: print(ans%mod);sys.exit()

newp,newm=-1,-1
for i in range(k+1,n):
    if a[i][1]==-1: newm=a[i][0];break
for i in range(k+1,n):
    if a[i][1]>=0: newp=a[i][0];break

x=1 if (lp and newm!=-1) else 0
y=1 if (lm and newp!=-1) else 0

if x==1 and y==1:
    if newp*lp[-1]>=newm*lm[-1]:
        ans=ans*inv(lm[-1],mod)*newp
    else:
        ans=ans*inv(lp[-1],mod)*newm

elif x==-1 and y==1: ans=ans*inv(lm[-1],mod)*newp
elif x==1 and y==-1: ans=ans*inv(lp[-1],mod)*newm
else: ans=0
print(ans%mod)



def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

Submission status: Runtime Error

Solution code:
import sys

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

A.sort(reverse=True)

P = []
M = []
Ans = []
p = 0
m = 0

for i in range(N):
    if 0 <= A[i]:
        P.append(A[i])
    else:
        M.append(A[i])

M.sort()

if K % 2 == 1 and len(P) != 0:
    Ans.append(P[p])
    p += 1
elif K % 2 == 1 and len(P) == 0:
    M.sort(reverse=True)
elif len(M) == 0:
    answer = 1
    for i in range(K):
        answer = (answer * P[i]) % 1000000007

    print(answer)
    sys.exit()

while len(Ans) < K:

    #Mのストックがもうない時
    if m+1 >= len(M):
        Ans.append(P[p])
        if len(Ans) == K:
            break
        Ans.append(P[p + 1])
        p += 2
    elif p+1 >= len(P):
        Ans.append(M[m])
        if len(Ans) == K:
            break
        Ans.append(M[m + 1])
        m += 2
    else:
        if P[p]*P[p+1] < M[m]*M[m+1]:
            Ans.append(M[m])
            Ans.append(M[m+1])
            m += 2
        else:
            Ans.append(P[p])
            Ans.append(P[p + 1])
            p += 2

answer = 1
for i in range(K):
    answer = (answer * Ans[i]) % 1000000007

print(answer)

Submission status: Runtime Error

Solution code:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, k = MAP()
a = sorted(LIST())

if k == 1:
    ans = a[n-1]
elif k % 2 == 0:
    b = sorted([abs(a[i]) for i in range(n)], reverse=True)
    ans = 1
    for i in range(k):
        ans = ( ans * b[i] ) % (10**9+7)
else:
    if a[n-1] == 0:
        ans = 0
    elif a[n-1] < 0:
        ans = 1
        for i in range(k):
            ans = ( ans * a[n-1-i] ) % (10**9+7)
    else:
        ans = 1
        for i in range(k):
            ans = ( ans * a[n-1-i] ) % (10**9+7)
            ans = min(0, ans % (10**9+7))
        for i in range(2,k,2):
            ans = max(ans, ans//a[n-k+i-2]//a[n-k+i-1]*a[i-2]*a[i-1])
            ans = min(0, ans % (10**9+7))
        ans = ans % (10**9+7)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

mod = 10 ** 9 + 7

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

if N == K:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
    print(ans)
    sys.exit()

A = np.array(A)

plus = A[A>0]
minus = A[A<0]
zero = A[A==0]

if len(zero) > N - K:
    print(0)
    sys.exit()

if len(minus) == N:
    if K % 2 == 0:
        minus = np.sort(minus)
    else:
        minus = np.sort(minus)[::-1]
    ans = 1
    for i in range(K):
        ans *= minus[i]
        ans %= mod
    print(ans)
    sys.exit()

plus = np.sort(plus)[::-1]
minus *= -1
minus = np.sort(minus)[::-1]

if K % 2 == 1:
    ans = plus[0]
    K -= 1
    p = (len(plus)-1) // 2
    m = len(minus) // 2
    
    n_p = [plus[2*i+1] * plus[2*i+2] for i in range(p)]
    n_m = [minus[2*i] * minus[2*i+1] for i in range(m)]
else:
    ans = 1
    p = len(plus) // 2
    m = len(minus) // 2
    
    n_p = [plus[2*i] * plus[2*i] for i in range(p)]
    n_m = [minus[2*i] * minus[2*i+1] for i in range(m)]

K //= 2

p_index = 0
m_index = 0
for i in range(K):
    if p_index == len(n_p):
        ans *= n_m[m_index]
        ans %= mod
        m_index += 1
    elif m_index == len(n_m):
        ans *= n_p[p_index]
        ans %= mod
        p_index += 1
    else:
        if n_p[p_index] > n_m[m_index]:
            ans *= n_p[p_index]
            ans %= mod
            p_index += 1
        else:
            ans *= n_m[m_index]
            ans %= mod
            m_index += 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

mod = int(10e8+7)

n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))

a_ = np.abs(a)
isN = (a!=a_).astype(int)

a = a[np.argsort(a_)[::-1]]
isN = isN[np.argsort(a_)[::-1]]
a_ = np.sort(a_)[::-1]

numN = np.sum(isN)
numP = n-numN

if k==1:
    print(np.max(a))
    sys.exit()

if np.sum(isN[:k])%2==0:
    ans = 1
    for i in range(k):
        ans *= a_[i]
        ans %= mod
    print(int(ans))
    sys.exit()

if not numP:
    k = isP
    ans = 1
    for i in range(1, k+1)[::-1]:
        ans *= -a_[-i]
        ans %= mod

    print(int(ans))
    sys.exit()

maxN = 0
maxP = 0

for i in range(k, n):
    if isN[i]:
        maxN = i
        break

for i in range(k, n):
    if not isN[i]:
        maxP = i
        break

minN = n
minP = n

for i in range(k)[::-1]:
    if isN[i]:
        minN = i
        break

for i in range(k)[::-1]:
    if not isN[i]:
        minP = i
        break

ans_1 = 1

for i in range(k):
    if i == minP:
        if maxN:
            ans_1 *= a_[maxN]
            ans_1 %= mod
        continue

    ans_1 *= a_[i]
    ans_1 %= mod

ans_2 = 1

for i in range(k):
    if i == minN:
        if maxP:
            ans_2 *= a_[maxP]
            ans_2 %= mod
        continue

    ans_2 *= a_[i]
    ans_2 %= mod

print(int(max(ans_1, ans_2)))

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(key=lambda x: abs(x), reverse=True)
ans = 1
if len([v for v in A if v <= 0]) == N:
    for i in range(K):
        ans *= A[-(i + 1)]
        if abs(ans) > mod:
            ans %= mod
else:
    num_hu = len([v for v in A[:K] if v < 0])
    if num_hu % 2 == 0:
        for i in range(K):
            ans *= A[i]
            if abs(ans) > mod:
                ans %= mod
    else:
        if A[K - 1] < 0:
            if len([v for v in A[K:] if v > 0]):
                idx = K
                while True:
                    if A[idx] > 0:
                        break
                    idx += 1
                for i in range(K - 1):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
                ans *= A[idx]
            else:
                idx = K - 2
                while True:
                    if A[idx] > 0:
                        break
                    idx -= 1
                for i in range(idx):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
                ans *= A[K]
                for i in range(idx + 1, K):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
        else:
            if len([v for v in A[K:] if v < 0]):
                idx = K
                while True:
                    if A[idx] < 0:
                        break
                    idx += 1
                for i in range(K - 1):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
                ans *= A[idx]
            else:
                idx = K - 2
                while True:
                    if A[idx] < 0:
                        break
                    idx -= 1
                for i in range(idx):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
                ans *= A[K]
                for i in range(idx + 1, K):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
print(ans % mod)

Submission status: Runtime Error

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def product(A):
    T = 1
    for a in A:
        T *= a
    return T


def solve():
    N, K = read_ints()
    A = read_ints()
    positives, negatives = [], []
    zero = 0
    modulo = 10**9+7
    while A:
        a = A.pop()
        if a > 0:
            positives.append(a)
        elif a < 0:
            negatives.append(a)
        else:
            zero += 1
    if len(positives) == 0:
        if len(negatives) < 2:
            return 0
    positives.sort()
    negatives.sort(reverse=True)
    if len(positives) == 0:
        if K%2 == 1:
            if zero:
                return 0
            else:
                return product(negatives[:K])%modulo
        else:
            return product(negatives[-K:])%modulo
    T = 1
    while K:
        if K >= 2 and len(negatives) > 1 and len(positives) > 1 and negatives[-1]*negatives[-2] > positives[-1]*positives[-2]:
            T = (T*negatives.pop()*negatives.pop())%modulo
            K -= 2
        elif len(positives) > 0:
            T = (T*positives.pop())%modulo
            K -= 1
        elif len(negatives) > 1:
            if K > 2:
                T = (T*negatives.pop()*negatives.pop())%modulo
                K -= 2
            else:
                T = (T*negatives.pop(0))%modulo
                K -= 1
        else:
            T = (T*negatives.pop())%modulo
            K -= 1
    return T


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

Submission status: Runtime Error

Solution code:
def modInverse(a, m) :
	return power(a, m - 2, m) 
      
# To compute x^y under modulo m 
def power(x, y, m) : 
      
    if (y == 0) : 
        return 1
          
    p = power(x, y // 2, m) % m 
    p = (p * p) % m 
  
    if(y % 2 == 0) : 
        return p  
    else :  
        return ((x * p) % m) 
  
# Function to return gcd of a and b 
def gcd(a, b) : 
    if (a == 0) : 
        return b 
          
    return gcd(b % a, a) 


















P = 1000000007

n,k=map(int,input().split())
a = [int(i) for i in input().split()]
ans = 1
neg = 0
for i in a:
	if i<0:neg+=1
if neg==n:
	a.sort(reverse=True)
	for i in range(k):
		ans = (ans*a[i])%P
	print(ans)
	exit(0)

a.sort()
l = 0
r = n-1
while k>0:
	if k>1:
		Ol = a[l]*a[l+1]
		Or = a[r]*a[r-1]
		if Ol > Or:
			ans = (ans*(Ol%P))%P
			l+=2
		else:
			ans = (ans*(Or%P))%P
			r-=2
		k-=2
	else:
		if a[r]==0:
			ans = (ans * modInverse(a[r+1],P))%P
			ans = (ans * (a[l]*a[l+1])%P)%P
		else: ans = (ans*a[r])%P
		k-=1
print(ans)
# ~ -1 -1 0 2 3

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = sorted(map(int, input().split()), reverse = True, key = lambda x: abs(x))

nn = len([ai for ai in a if ai < 0])
ans = 1
if nn == n:
    for i in range(k):
        ans *= a[::-1][i]
    print(ans % (10**9 + 7))
    exit()

cnt = 0
mspn = float("inf")
msnn = -float("inf")
for i in range(k):
        ans *= a[i]
        if a[i] < 0:
            cnt += 1
            msnn = max(msnn, a[i])
        else:
            mspn = min(mspn, a[i])

mbnn = 0
if len([ai for ai in a[i+1:] if ai < 0]) > 0:
    mnnn = [ai for ai in a[i+1:] if ai < 0][0]
    
if cnt%2 == 1:
    ans1 = ans // msnn * max(a[i+1:])
    ans2 = ans // mspn * mbnn
    print(max(ans1, ans2) % (10**9 + 7))
else:
    print(ans % (10**9 + 7))

Submission status: Runtime Error

Solution code:
n,k = map(int, raw_input().split(' '))
ais = map(int , raw_input().split(' '))

pos = [ai for ai in ais if ai > 0]
pos.sort(key = lambda x:-x)
neg = [-ai for ai in ais if ai < 0]
neg.sort(key = lambda x:-x)

def g(neg, k):
	i = len(neg) -1
	r = 1
	while(k):
		r *= -neg[i]
		i -=1
		k -=1
		r %= (10 ** 9) + 7
	return r
def gg(pos, k):
	r =  1
	for i in range(k):
		r *= pos[i]
		r %= (10 **9) + 7
	return r
def f(pos,neg, k):

	if len(pos) == 0: return g(neg, k)
	if len(neg) <= 1: return gg(pos, k)

	i,j = 0,0
	p = 1
	mod = (10 ** 9) + 7
	while(k >= 2):
		if j + 1 < len(neg):
			if neg[j] * neg[j+1] > pos[i] * (pos[i+1] if i+1 < len(pos) else 1):
				p *= neg[j] * neg[j+1]
				p %= mod
				j+=1
				k -= 2
			else:
				p *= pos[i]
				i+=1
				p %= mod
				k -=1
	while(k):
		p *= pos[i]
		p %+ mod
		k-=1
		i+=1
	return p
print f(pos,neg, k)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
large_p = 10**9 + 7
from collections import deque
from copy import deepcopy
from operator import mul
from functools import reduce

def main():
    n, k, *a = map(int, read().split())
    if n == 1:
        print(a[0])
        sys.exit()
    elif n == 2:
        r = max(a[0], a[1], a[0] * a[1])
        print(r)
        sys.exit()
    a2 = [i for i in a if i > 0] #plus
    a3 = [-i for i in a if i < 0] #minus
    a2.sort(reverse=True)
    a3.sort(reverse=True)
    res = deepcopy(a2[:k+1])
    resd = deque(res)
    a3d = deque(a3)
    a2dd = deque()
    a3dd = deque()
    cnt = 0
    while cnt < k:
        if a3d and resd[-1] < a3d[0]:
            a2dd.append(resd.pop())
            t = a3d.popleft()
            resd.appendleft(t)
            a3dd.append(t)
            cnt += 1
        else:
            break
    r = reduce(mul, resd)
    if r < 0:
        r = r // a3dd[-1] * -1
        r *= a2dd[-1]
    r = r % large_p
    if r < 0:
        r += large_p
    print(r)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import bisect
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]

rrn = lambda n: [ rr() for _ in xrange(n)]
MOD = 10**9+7
N, K = rrm()
arr = rrm()
def solve(N, K, arr):
    if N ==K:
        ans = arr[0]
        for i in range(1, N):
            ans*= arr[i] %MOD
        return ans %MOD
    neg, pos = [], []
    has = False
    for num in arr:
        if num<0:
            neg.append(num)
        elif num>0:
            pos.append(num)
        else:
            has = True
    neg = sorted(neg)
    pos = sorted(pos)
    pos_prefix = [1]
    for i in range(len(pos)-1, -1, -1):
        pos_prefix.append(pos_prefix[-1]*pos[i] )
    neg_prefix = [1]
    for i in range(len(neg)):
        neg_prefix.append(neg_prefix[-1]*neg[i] )
    if has:
        ans = 0
    neg_len = min(K-K%2, len(neg)-len(neg)%2)
    ans = float('-inf')
    for i in range(0, neg_len+2, 2):
        pre = neg_prefix[i]
        need = K-i
        if need<=len(pos):
            after = pos_prefix[need]
            ans = max(ans, pre*after)
    if ans > float('-inf'):
        return ans
    else:
        neg_len = min(len(neg), K)
        ans = 1
        for i in range(1, neg_len+1):
            ans*=neg[-i]
        if neg_len<K:
            for i in range(1, K-neg_len+1):
                ans *= pos[i]
        return ans
            
        
print(solve(N,K, arr) % (10**9+7))

Submission status: Runtime Error

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

if N - A.count(0) < K:
    print(0)
    exit(0)

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


ans = 1
if K % 2 == 1 and len(plus) == 0:
    minus.sort(reverse=True)
    for i in range(K):
        ans *= minus[i]
        ans %= MOD
    print(ans)
    exit(0)

plus.sort(reverse=True)
minus.sort()

i = 0
j = 0

if K % 2 == 1 and len(plus) > 0:
    ans = plus[0]
    K -= 1
    plus = plus[1:]

for _ in range(K//2):
    if i+1 >= len(plus):
        ans *= (minus[j] * minus[j+1])
        ans %= MOD
        j += 2
        continue
    elif j+1 >= len(minus):
        ans *= (plus[i] * plus[i+1])
        ans %= MOD
        i += 2
        continue

    a = plus[i] * plus[i+1]
    b = minus[j] * minus[j+1]
    if a > b:
        ans *= a
        i += 2
    else:
        ans *= b
        j += 2
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    from collections import Counter
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    posi = [a for a in A if a > 0]
    nega = [a for a in A if a < 0]
    posi.sort(reverse=True)
    nega.sort(reverse=True)
    A.sort(reverse=True, key=abs)
    if len(posi) + len(nega) < K:
        # 0を含まなければいけないとき
        return print(0)

    ans = modint(1)
    if K % 2 == 1 and len(posi) < K:
        # 結果が負数
        # 絶対値が小さいやつをK個取ってくる
        A.sort(key=abs)
        for a in A[:K]:
            ans *= a
    else:
        # 結果が正になるように注意しなければいけない
        # skipしてかけるものがなくなったらこわい
        # 負数がK以下の奇数個しかないとハマる
        if sum(a < 0 for a in A[:K]) % 2 == 0:
            for a in A[:K]:
                ans *= a
        else:
            ans1 = []  # 正を取り除く
            ans2 = []  # 負を取り除く
            posi = [a for a in A[:K] if a > 0]
            nega = [a for a in A[:K] if a < 0]
            p_remove = False
            for a in A[:K][::-1]:
                if a > 0 and not p_remove:
                    p_remove = True
                    continue
                ans1.append(a)
            n_remove = False
            for a in A[:K][::-1]:
                if a < 0 and not n_remove:
                    n_remove = True
                    continue
                ans2.append(a)
            mul1 = 0  # 一番大きい正
            mul2 = 0  # 　一番大きい負
            for a in A[K:]:
                if mul1 == 0 and a > 0:
                    mul1 = a
                if mul2 == 0 and a < 0:
                    mul2 = a
                if mul1 != 0 and mul2 != 0:
                    break
            ans1.append(mul2)
            ans2.append(mul1)
            s1 = sum(abs(a) for a in ans1)
            s2 = sum(abs(a) for a in ans2)

            if len(posi) == 0 or mul2 == 0:
                for a in ans2:
                    ans *= a
            elif len(nega) == 0 or mul1 == 0:
                for a in ans1:
                    ans *= a
            else:
                if s1 < s2:
                    for a in ans2:
                        ans *= a
                elif s1 > s2:
                    for a in ans1:
                        ans *= a
                else:
                    raise RuntimeError
                    s1_3 = sum(abs(a) <= 5 for a in ans1)
                    s2_3 = sum(abs(a) <= 5 for a in ans2)
                    if s1_3 < s2_3:
                        for a in ans2:
                            ans *= a
                    elif s1_3 > s2_3:
                        for a in ans1:
                            ans *= a
                    else:
                        for a in ans1:
                            ans *= a
    print(int(ans) % MOD)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7
p, n = [], []
flag = False

for Ai in A:
    if Ai==0:
        flag = True
    elif Ai>0:
        p.append(Ai)
    else:
        n.append(Ai)

if len(p)==0 and K%2==1:
    if 0 in A:
        print(0)
    else:
        n.sort(reverse=True)
        ans = 1
        
        for ni in n[:K]:
            ans *= ni
            ans %= MOD
        
        print(ans)
    exit()
    
if K==N:
    ans = 1
    
    for Ai in A:
        ans *= Ai
        ans %= MOD
    
    print(ans)
    exit()

p.sort(reverse=True)
n.sort()

if K%2==0:
    l = []
    
    for i in range(len(p)//2):
        l.append(p[2*i]*p[2*i+1])
    
    for i in range(len(n)//2):
        l.append(n[2*i]*n[2*i+1])

    l.sort(key=lambda x: abs(x), reverse=True)
    ans = 1
    
    for i in range(K//2):
        ans *= l[i]
        ans %= MOD
else:
    ans = p[0]
    l = []
    
    for i in range(len(p)//2):
        l.append(p[2*i]*p[2*i+1])
    
    for i in range(len(n)//2):
        l.append(n[2*i]*n[2*i+1])
    
    l.sort(key=lambda x: abs(x), reverse=True)
    
    for i in range(K//2):
        ans *= l[i]
        ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
n = [int(i) for i in input().split()]

plus = list()
minus = list()
for i in input().split():
  if int(i) > 0:
    plus.append(int(i))
  else:
    minus.append(int(i))
    
plus.sort()
minus.sort(reverse=True)
ans = 1
k = n[1]
while k != 0:
  if k == 1:
    ans *= plus[0]
    k = 0
  if plus[0]*plus[1] < minus[0]*minus[1]:
    ans *= minus[0]*minus[1]
    del minus[0]
    del minus[0]
  else:
    ans *= plus[0]*plus[1]
    del plus[0]
    del plus[0]
  k -= 2
print(ans%(10**9 + 7))