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 sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n,k = m()

a = l()

a.sort()

mina = []

pra = []

for i in range(n):
	if a[i] >= 0:
		pra.append(a[i])
	else:
		mina.append(a[i])

lp = len(pra)

lm = len(mina)
ans = 1
if lp == 0:
	if k % 2 != 0:
		for i in range(0,k,2):
			if i == k-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		for i in range(0,k,2):
			ans *= (mina[i]*mina[i+1]) % mod
			ans %= mod
		print(ans % mod)
elif lp == 1:
	if n == k:
		ans *= pra[0]
		for i in range(0,lp,2):
			if i == lp-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		if k % 2 == 0:
			for i in range(0,k,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
		else:
			ans *= pra[0] 
			for i in range(0,k-1,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
else:
	cp = lp-1
	cm = 0
	count = 0
	#data = []
	
	for _ in range(k):
		if cp != -1 and cm != lm:
			if abs(mina[cm]) <= pra[cp]:
				if cp == 0:
					if (k-lp) % 2 == 0:
						count += 1
						#ans *= pra[cp]
						#data.append(pra[cp])
						cp -= 1
					else:
						count += 1
						#ans *= mina[cm]
						#data.append(mina[cm])
						cm += 1

				else:
					count += 1
					#ans *= pra[cp]
					#data.append(pra[cp])
					cp -= 1
			else:
				if cm == lm-1:
					if lm % 2 == 0:
						count += 1
						#ans *= mina[cm]
						#data.append(mina[cm])
						cm += 1
					else:
						count += 1
						#ans *= pra[cp]
						#data.append(pra[cp])
						cp -= 1


				else:
					count += 1
					#ans *= mina[cm]
					#data.append(mina[cm])
					cm += 1
		elif cp != lp:
			#ans *= pra[cp]
			#data.append(pra[cp])
			cp -= 1
			count += 1
		elif cm != lm:
			#ans *= mina[cm]
			#data.append(mina[cm])
			cm += 1
			count += 1

		else:
			break
	if cm % 2 != 0:
		anss = 1

		if cp-1 != -1 and cm + 1 != lm:
			if pra[cp-1]/-mina[cm] >= -mina[cm+1]/pra[cp]:
				cp -= 1
				cm -= 1
			else:
				cp += 1
				cm += 1
		elif cp-1 != -1:
			cp -= 1
			cm -= 1
		else:
			cp += 1
			cm += 1
		

	#data.sort()
	co = 0

	for i in range(0,cm,2):
		ans *= (mina[i] * mina[i+1]) % mod
		ans %= mod
	for i in range(lp-1,cp,-1):
		ans *= pra[i] % mod
		ans %= mod


		
	print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

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

    if len(minus) == 0:
        A.sort(reverse=True)
        res = 1
        for i in range(k):
            res = (res * A[i]) % mod
        print(res)
    elif len(plus) == 0:
        res = 1
        if k % 2 != 0:
            A.sort(reverse=True)
            for i in range(k):
                res = (res * A[i]) % mod
        else:
            A.sort()
            for i in range(k):
                res = (res * A[i]) % mod
        print(res)
    else:
        minus.sort()
        plus.sort(reverse=True)
        if len(plus) > 1 and len(minus) > 1:
            dp = [0 for _ in range(k + 1)]
            dp[0] = 1
            dp[1] = plus[0] % mod
            dp[2] = max(minus[0] * minus[1] % mod, plus[0] * plus[1] % mod)
            for i in range(3, k + 1):
                if i % 2 != 0:
                    dp[i] = dp[i - 1] * plus[i] % mod
                else:
                    dp[i] = max(dp[i - 1] * plus[i] % mod, dp[i - 2] * minus[i - 1] * minus[i] % mod)
            print(dp[-1])
        else:
            if len(plus) == 1:
                dp = [0 for _ in range(k + 1)]
                dp[0] = 1
                for i in range(1, k + 1):
                    if i % 2 != 0:
                        dp[i] = dp[i - 1] * plus[0] % mod
                    else:
                        dp[i] = max(dp[i - 2] * minus[i - 1] * minus[i] % mod)
                print(dp[-1])
            else:
                res = 1
                for i in range(k):
                    res = (res * plus[i]) % mod
                print(res)


if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
def maxProductSubarrayOfSizeK(A, n, k): 
  
    MOD = 10**9+7
    A.sort()   
    product = 1
    

        
  
    if (A[n - 1] == 0 and (k & 1)): 
        return 0
  
    if (A[n - 1] <= 0 and (k & 1)) : 
        for i in range(n - 1, n - k + 1, -1): 
            product *= A[i] 
            product %= MOD
        return product 
  
    i = 0  
    j = n - 1
  
    if (k & 1): 
        product *= A[j] 
        j-= 1
        k-=1
  
    k >>= 1
  
    for itr in range( k) : 
  
        left_product = A[i] * A[i + 1] 
  
        right_product = A[j] * A[j - 1] 
  
        if (left_product > right_product) : 
            product *= left_product 
            product %= MOD
            i += 2
          
        else : 
            product *= right_product 
            product %= MOD
            j -= 2
  
    return product

N,K = map(int,input().split())
A = list(map(int,input().split()))
print((maxProductSubarrayOfSizeK(A, N, K))% MOD)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9+7
P = []
M = []
zero = []
for a in A:
    if a>0:
        P.append(a)
    elif a<0:
        M.append(a)
    else:
        zero.append(a)
if N==K and zero: print(0);exit()
if len(P)==0:
    if K%2==0:
        ans = 1
        if len(M)>=K:
            M.sort(reverse=True)
            for i in range(K):
                ans *=M[i]
                ans %=mod
            print(ans);exit()
        else: print(0);exit()
    else:
        ans = 1
        if len(M)>=K:
            M.sort()
            for i in range(K):
                ans *=M[i]
                ans %=mod
            print(ans);exit()
        else: print(0);exit()
P.sort(reverse=True)
M.sort(reverse=True)
if K==1:
    A.sort()
    print(A[-1]);exit()
if len(P)>=K:
    ans = 1
    P = P[:K]
    for i in range(K):
        ans *=P[i]
        ans %=mod
    while P:
        while len(M)>=2:
            a1 = M.pop()
            a2 = M.pop()
            b1 = P.pop()
            b2 = P.pop()
            if a1*a2 > b1*b2:
                ans = ans/b1
                ans = ans/b2
                ans *=a1*a2
                ans %=mod
            else:
                break
        break
else:
    ans = 1
    
    K -=len(P)
    if K>len(M):print(0);exit()
    else:
        if K%2!=0:
            if zero:print(0);exit()
            else:
                for i in range(len(P)-1):
                    ans *=P[i]
                    ans %=mod
                if K+1<=len(M):
                    while P:
                        while len(M)>=2:
                            a1 = M.pop()
                            a2 = M.pop()
                            b1 = P.pop()
                            b2 = P.pop()
                            if a1*a2 > b1*b2:
                                ans = ans/b1
                                ans = ans/b2
                                ans *=a1*a2
                                ans %=mod
                            else:
                                break
                        break
                else:
                    print(0);exit()
        else:
            for i in range(len(P)):
                    ans *=P[i]
                    ans %=mod
                if K<=len(M):
                    while P:
                        while len(M)>=2:
                            a1 = M.pop()
                            a2 = M.pop()
                            b1 = P.pop()
                            b2 = P.pop()
                            if a1*a2 > b1*b2:
                                ans = ans/b1
                                ans = ans/b2
                                ans *=a1*a2
                                ans %=mod
                            else:
                                break
                        break
                else:
                    print(0);exit()
print(int(ans%mod))

Submission status: Runtime Error

Solution code:
import pprint

def main():
    n, k = list(map(int, input().split()))
    a_list = list(map(int, input().split()))

    a_list.sort(reverse=True, key=abs)

    prod = 1
    prod_elem_count = 0

    list_treverse_head = 0

    minus_value_hold = None
    while prod_elem_count < k:
        elem = a_list[list_treverse_head]
        if elem > 0:
            prod *= elem
            prod = prod % (10 ** 9 + 7)
            prod_elem_count += 1
        else:
            if minus_value_hold != None:
                prod *= minus_value_hold
                prod = prod % (10 ** 9 + 7)
                minus_value_hold = None

                prod *= elem
                prod = prod % (10 ** 9 + 7)
                
                prod_elem_count += 2
            else:
                minus_value_hold = elem

        list_treverse_head += 1
    
    # pprint.pprint(a_list)
    print(prod)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

for i in range(n):
    if a[i]<0:
        m.append(a[i])
    else:
        p.append(a[i])
m.sort(reverse=True)
p.sort()
ans=1

if len(m)==n and k%2==1:
    for i in range(k):
        ans*=m[i]
        ans%=mod

elif k==1:
    ans=p[-1]

elif len(m)==1:
    if n==k:
        for i in range(len(p)):
            ans*=p[i]
            ans%=mod
        ans%m[-1]
    else:
        for i in range(k):
            ans*=p[i]
            ans%=mod

elif len(p)==1:
    if n==k:
        for i in range(len(m)):
            ans*=m[i]
            ans%=mod
        ans%p[-1]
    elif k%2==0:
        for i in range(k):
            ans*=m[i]
            ans%=mod
    else:
        for i in range(k-1):
            ans*=m[i]
            ans%=mod
        ans*=p[-1]

else:
    cnt=0
    for i in range(k-2):
        if len(m)==0:
            ans*=p.pop()
        elif len(p)==0:
            lm=m.pop()
            ans*=lm
            cnt+=1
        else:
            if abs(m[-1])<p[-1]:
                ans*=p.pop()
            else:
                lm=m.pop()
                ans*=lm
                cnt+=1
        ans%=mod
    
    if cnt%2==0:
        if len(p)>1 and len(m)>1:
            ans*=max(p[-1]*p[-2],m[-1]*m[-2])
        elif len(p)<2:
            ans*=m[-1]*m[-2]
        else:
            ans*=p[-1]*p[-2]
    elif len(m)>0:
        ans*=p[-1]*m[-1]
    else:
        ans=pow(lm,mod-2,mod)*p[-1]*p[-2]


print(ans%mod)

Submission status: Runtime Error

Solution code:
import sys, math
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=lambda x: abs(x))[::-1]
P = int(1e9+7)

ans = 1
hu = None
sei = None
flg = False
for a in A:
    flg = a > 0
    if flg:
        break
if not flg:
    for i in range(1, K+1):
        ans = (ans * A[-i]) % P
    print(ans)
    sys.exit()
if K == N:
    for a in A:
        ans = (ans * a) % P
    print(ans)
    sys.exit()

for i, a in zip(range(K), A):
    if a > 0:
        if not sei:
            ans = (ans * sei) % P
        sei = a
    else:
        if not hu:
            hu = a
        else:
            ans = (ans * a * hu) % P
            hu = None

ptn1, ptn2 = -math.inf, -math.inf
if hu:
    if sei:
        for i in range(K, N):
            if A[i] > 0:
                ptn1 = sei * A[i]
                break
        for i in range(K, N):
            if A[i] <= 0:
                ptn2 = hu * A[i]
                break
        ans = (ans * max(ptn1, ptn2)) % P
    else:
        for i in range(K, N):
            if A[i] > 0:
                ans = (ans*A[i])%P
                break
else:
    ans = (ans * sei) % P
print(ans % P)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
neg = []
pos = []
mod = 10**9+7
zeros = 0
for i in a:
  if i < 0:
    neg.append(i)
  elif i==0:
    zeros+=1
  else:
    pos.append(i)
neg.sort(reverse=True)
if len(pos) == 0:
  if zeros != 0:
    print(0)
  else:
    p = 1
    if k&1:
      for i in neg[:k]:
        p *= i
    else:
      for i in neg[::-1][:k]:
        p *= i
    print(p%mod)
else:
  pos.sort()
  a = neg+pos+[0]*zeros
  p = 1
  for i in a[:k]:
    p *= i
  m = p
  j = 0
  for i in a[k:]:
    p *= i
    p = p//a[j]
    m = max(m,p)
    j+=1
  print(m%mod)

Submission status: Runtime Error

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

M = 10 ** 9 + 7

A_minus = []
A_plus = []
n_zero = 0
n_plus = 0
n_minus = 0
for elm in input().split(" "):
    num = int(elm)
    if num == 0:
        n_zero += 1
    elif num > 0:
        A_plus.append(num)
        n_plus += 1
    else:
        A_minus.append(num)
        n_minus += 1

k0 = (k // 2) * 2
n_minus0 = (n_minus // 2) * 2
n_plus0 = (n_plus // 2) * 2

if n_plus + n_minus0 < k:
    if n_zero > 0:
        out = 0
    else:
        out = 1
        for A in A_plus:
            out = (out * A) % M
        for A in A_minus:
            out = (out * A) % M
else:
    A_plus = sorted(A_plus, reverse=True)
    A_minus = sorted(A_minus, reverse=True)

    half_k = k0 // 2

    if n_plus >= 2:
        cur_plus = A_plus[0] * A_plus[1] 
        pi = 2
    else:
        cur_plus = None
        pi = 0
        
    if n_minus >= 2:
        cur_minus = A_minus[0] * A_minus[1] 
        mi = 2
    else:
        cur_minus = None
        mi = 0

    count = 0
    countp = 0
    countm = 0
    out = 1
    for i in range(half_k):
        condp = cur_plus is not None
        condm = cur_minus is not None

        if condp and condm:
            count += 2
            if cur_plus > cur_minus:
                countp += 2
                cur_plus = cur_plus % M
                out = (out * cur_plus) % M

                diff = n_plus - countp
                if diff >= 2 and k - count >= 2:
                    cur_plus = A_plus[pi] * A_plus[pi+1] 
                    pi += 2
                else:
                    cur_plus = None
            else:
                countm += 2
                cur_minus = cur_minus % M
                out = (out * cur_minus) % M

                diff = n_minus - countm
                if diff >= 2 and k - count >= 2:
                    cur_minus = A_minus[mi] * A_minus[mi+1] 
                    mi += 2
                else:
                    cur_minus = None
        elif condp:
            count += 2
            if True:
                countp += 2
                cur_plus = cur_plus % M
                out = (out * cur_plus) % M

                diff = n_plus - countp
                if diff >= 2 and k - count >= 2:
                    cur_plus = A_plus[pi] * A_plus[pi+1] 
                    pi += 2
                else:
                    cur_plus = None

        elif condm:
            count += 2
            if True:
                countm += 2
                cur_minus = cur_minus % M
                out = (out * cur_minus) % M

                diff = n_minus - countm
                if diff >= 2 and k - count >= 2:
                    cur_minus = A_minus[mi] * A_minus[mi+1] 
                    mi += 2
                else:
                    cur_minus = None
        else:
            break
        
    nokori = k - count
    #print("nokori", nokori, "mi", mi)
    for i in range(nokori):
        if n_plus - countp >= 1:
            out = (out * A_plus[pi]) % M
            pi += 1
            countp += 1
        else:
            out = (out * A_minus[mi]) % M
            mi += 1
            countm += 1

print(out)

Submission status: Runtime Error

Solution code:
def solmax(a,i,j):
    if j==0:
            return 1
    if i==j:
        return p[i]
    if i not in sma.keys():
        sma[i]={}
    if j not in sma[i].keys():
        u=solmax(a,i-1,j)
        if a[i-1]>0:
            u=max(u,solmax(a,i-1,j-1)*a[i-1])
        elif a[i-1]<0:
            u=max(u,solmin(a,i-1,j-1)*a[i-1])
        else:
            u=max(u,0)
        sma[i][j]=u
    return sma[i][j]
def solmin(a,i,j):
    if j==0:
        return 1
    if i==j:
        return p[i]    
    if i not in smi.keys():
        smi[i]={}
    if j not in smi[i].keys():
        u=solmin(a,i-1,j)
        if a[i-1]>0:
            u=min(u,solmin(a,i-1,j-1)*a[i-1])
        elif a[i-1]<0:
            u=min(u,solmax(a,i-1,j-1)*a[i-1])
        else:
            u=min(u,0)
        smi[i][j]=u
    return smi[i][j]
sma={}
smi={}
s=input().split(' ') 
n=int(s[0])
k=int(s[1])
s=input().split(' ')
a=[int(d) for d in s]
p=[1]
for i in range(n):
    p.append(p[-1]*a[i])
print(solmax(a,n,k)%1000000007)

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
mod = 10**9 + 7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a_plus = [int(x) for x in a if x > 0]
a_minus = [int(x) for x in a if x < 0]
a_abs = [abs(x) for x in a]
a_abs = sorted(a_abs, key=lambda x: abs(x))[::-1]
a = sorted(a, key=lambda x: abs(x))[::-1]
a_plus = sorted(a_plus, key=lambda x: abs(x))[::-1]
a_minus = sorted(a_minus, key=lambda x: abs(x))[::-1]

def calc(x):
    res = 1
    for i in x:
        res*=i
        res %= mod 
    return res
max_a = a[:k]
max_a_minus = []
max_a_plus = []
cnt = 0
for i in max_a:
    if i == 0:
        print(0)
        sys.exit()
    if i < 0:
        cnt += 1
        max_a_minus.append(i)
    else:
        max_a_plus.append(i)

if cnt % 2 ==0:
    print(calc(max_a))
    sys.exit()

minus_cnt = cnt
plus_cnt = k - cnt
from copy import deepcopy
if len(a_minus) <= cnt and len(a_plus) <= plus_cnt:
    ans = -float('inf')
elif len(a_minus) <= cnt:
    if len(max_a_minus) == 0:
        ans = -float("inf")
    else:
        max_a_minus.pop()
        max_a_plus.append(a_plus[plus_cnt])
        ans = calc(max_a_plus + max_a_minus)
elif len(a_plus) <= plus_cnt:
    if len(max_a_plus) == 0:
        ans = -float("inf")
    else:
        max_a_plus.pop()
        max_a_minus.append(a_minus[cnt])
        ans = calc(max_a_minus + max_a_plus)
else:
    flag1 = 1
    flag2 = 1
    if len(max_a_minus) == 0:
        ans1 = -float("inf")
        flag1 = 0
    if len(max_a_plus) == 0:
        ans2 = -float("inf")
        flag2 = 0
    if flag1:
        c1 = deepcopy(max_a_minus)
        c2 = deepcopy(max_a_plus)
        c1.pop()
        c2.append(a_plus[plus_cnt])
        ans1 = calc(c1 + c3)
    if flag2:
        c3 = deepcopy(max_a_minus)
        c4 = deepcopy(max_a_plus)
        c4.pop()
        c3.append(a_minus[cnt])
        ans2 = calc(c2 + c4)
    ans = max(ans1, ans2)
a_abs = a_abs[::-1]
ans2 = -calc(a_abs[:k])
if ans > ans2:
    print(ans%mod)
else:
    print(ans2%mod)

Submission status: Runtime Error

Solution code:
import bisect

n, k = [int(i) for i in input().split()]
a  = [int(i) for i in input().split()]

minus = []
positive = []
aller = []
zero = 0
for i in a:
    if i < 0:
        minus.append(-i)
    elif i > 0:
        positive.append(i)
    else:
        zero += 1


positive.sort()
minus.sort()

aller = positive + minus[:-2]
aller.sort()

if n == k:
    if zero >= 1:
        print(0)
    else:
        res = 1
        for i in a:
            res *= i
            res %= 10**9 + 7
        print(res)   
elif n - k < zero:
    print(0)
elif minus == 1:
    if k == len(positive) + 1 and zero >= 1:
        print(0)
    elif k == len(positive) + 1 and zero == 0:
        res = 1
        for i in a:
            res *= i
            res %= 10**9 + 7
        print(res)   
    else:
        res = 1
        for i in positive[::-1][:k]:
            res *= i
            res %= 10**9 + 7
        print(res)  
elif minus == 0:
    if k - len(positive) > 0:
        print(0)
    else:
        res = 1
        for i in positive[:k]:
            res *= i
            res %= 10**9 + 7
        print(res)  
elif k - len(positive) == 2:
    aller = []

    for i in a:
        if i < 0:
            aller.append([i, -i])
        elif i > 0:
            aller.append([i, i])
        else:
            aller.append([0, 0])

    aller.sort(key=lambda student: student[0])

    aller = aller[::-1]

    cur = 0
    res = 1
    while cur < k - 2:
        res *= aller[cur][0]
        res %= 10**9 + 7
        cur += 1

    aller = aller[k - 2:]
    now = cur
    while cur < k:
        if aller[now][1] > 0:
            now += 1
        else:
            res *= aller[now][1]
            res %= 10**9 + 7
            cur += 1

    print(res)
else:
    aller = []

    for i in a:
        if i < 0:
            aller.append([i, -i])
        elif i > 0:
            aller.append([i, i])
        else:
            aller.append([0, 0])

    aller.sort(key=lambda student: student[0])

    aller = aller[::-1]

    cur = 0
    res = 1
    while cur < k - 2:
        res *= aller[cur][0]
        res %= 10**9 + 7
        cur += 1

    aller = aller[k - 2:]
    now = cur
    while cur < k:
        if aller[now][1] > 0:
            now += 1
        else:
            res *= aller[now][1]
            res %= 10**9 + 7
            cur += 1

    print(res)

Submission status: Runtime Error

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

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7

    a.sort()
    ret = 1
    if k % 2 == 0 or a[-1] >= 0:
        l = 0
        r = -1
        mlt1 = a[0] * a[1]
        mlt2 = a[-2] * a[-1]
        for _ in range(k//2):
            if mlt1 >= mlt2:
                ret *= mlt1 % mod
                l += 2
                if l <= n-1:
                    mlt1 = a[l+1] * a[l]
            else:
                ret *= mlt2 % mod
                r -= 2
                if r >= -n+1:
                    mlt2 = a[r-1] * a[r]
            ret %= mod

        if k % 2 == 1:
            ret *= a[r]
            ret %= mod

    else:
        for i in range(k):
            ret *= a[n-1-i]
            ret %= mod

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N=10**9+7
n , k = map(int, input().split())
x = list(map(int,input().split()))
posi=[]
nega=[]
ze=[]
p=0
ne=0
z=0

for i in range(n):
    if x[i]<0:
        nega.append(x[i]*(-1))
        ze.append([x[i]*(-1),-1])
        ne+=1
    elif x[i]>0:
        posi.append(x[i])
        ze.append([x[i],1])
        p+=1
    else:
        z+=1

if n+p<k:
    print('0')
    exit

elif k%2==1 and p==0:
    if z>=1:
        print('0')
        exit()
    else:
        ans=1
        nega.sort()
        for i in range(k):
            ans*=nega[i]
            ans%=N
        print(ans*(-1)%N)
elif k%2==1:
    ze.sort(key = lambda x:x[0],reverse=True)
    ans=1
    fu=1
    for i in range(k):
        ans*=ze[i][0]
        fu*=ze[i][1]
        ans%=N
    if fu==-1:
        st=0
        gl=0
        for j in range(min(k,n-k)):
            if ze[k-j]<0 and st==0:
                st=k-j
            if ze[k+j]>0 and gl==0:
                gl=k+j
        for i in range(k):
            if i!=st:
                ans*=ze[i][0]
                ans%=N
            ans*=ze[gl]
            ans%=N
    print(ans)
else:
    ab=nega+posi
    ab.sort(reverse=True)
    ans=1
    for i in range(k):
        ans*=ab[i]
        ans%=N
    print(ans)

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n,k = m()

a = l()

a.sort()

mina = []

pra = []

for i in range(n):
	if a[i] >= 0:
		pra.append(a[i])
	else:
		mina.append(a[i])

lp = len(pra)

lm = len(mina)
ans = 1
if lp == 0:
	if k % 2 != 0:
		for i in range(0,k,2):
			if i == k-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		for i in range(0,k,2):
			ans *= (mina[i]*mina[i+1]) % mod
			ans %= mod
		print(ans % mod)
elif lp == 1:
	if n == k:
		ans *= pra[0]
		for i in range(0,lp,2):
			if i == lp-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		if k % 2 == 0:
			for i in range(0,k,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
		else:
			ans *= pra[0] 
			for i in range(0,k-1,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
else:
	cp = lp-1
	cm = 0
	count = 0
	#data = []
	
	for _ in range(k):
		if cp != -1 and cm != lm:
			if abs(mina[cm]) <= pra[cp]:
				if cp == 0:
					if (k-lp) % 2 == 0:
						count += 1
						#ans *= pra[cp]
						#data.append(pra[cp])
						cp -= 1
					else:
						count += 1
						#ans *= mina[cm]
						#data.append(mina[cm])
						cm += 1

				else:
					count += 1
					#ans *= pra[cp]
					#data.append(pra[cp])
					cp -= 1
			else:
				if cm == lm-1:
					if lm % 2 == 0:
						count += 1
						#ans *= mina[cm]
						#data.append(mina[cm])
						cm += 1
					else:
						count += 1
						#ans *= pra[cp]
						#data.append(pra[cp])
						cp -= 1


				else:
					count += 1
					#ans *= mina[cm]
					#data.append(mina[cm])
					cm += 1
		elif cp != lp:
			#ans *= pra[cp]
			#data.append(pra[cp])
			cp -= 1
			count += 1
		elif cm != lm:
			#ans *= mina[cm]
			#data.append(mina[cm])
			cm += 1
			count += 1

		else:
			break
	if cm % 2 != 0:
		anss = 1

		if pra[cp-1]/-mina[cm] >= -mina[cm+1]/pra[cp]:
			cp -= 1
			cm -= 1
		else:
			cp += 1
			cm += 1
		

	#data.sort()
	co = 0

	for i in range(0,cm,2):
		ans *= (mina[i] * mina[i+1]) % mod
		ans %= mod
	for i in range(lp-1,cp,-1):
		ans *= pra[i] % mod
		ans %= mod


		
	print(ans)

Submission status: Runtime Error

Solution code:
import math
import fractions
import collections
import itertools
import pprint
N,K=map(int,input().split())
A=list(map(int,input().split()))
plist=[]
mlist=[]
ans=1
p=10**9+7
for i in range(N):
    if A[i]>=0:
        plist.append(A[i])
    else:
        mlist.append(A[i])
if len(plist)==0:
    if K%2==1:
        A.sort(reverse=True)
    else:
        A.sort()
    for i in range(K):
        ans=(ans*A[i])%p
    print(ans%p)
elif len(plist)==1:
    #print(plist,mlist)
    mlist.sort()
    if K%2==1:
        ans=plist[0]
    for i in range(K-1):
        ans=(ans*mlist[i])%p
    print(ans%p)
else:
    ans=1
    plist.sort(reverse=True)
    mlist.sort()
    pmap=[]
    mmap=[]
    if K%2==1:
        ans=plist[0]
        plist.pop(0)
        K=K-1
    #print(plist,mlist)
    for i in range(0,len(plist)-1,2):
        pmap.append(plist[i]*plist[i+1])
    for i in range(0,len(mlist)-1,2):
        mmap.append(mlist[i]*mlist[i+1])
    #print(K)
    mapnum=K//2
    #print(mapnum)
    #print(pmap,mmap,ans)
    for i in range(mapnum):
        if (len(pmap)>0)and(len(mmap)>0):
            if pmap[0]>mmap[0]:
                ans=(ans*pmap[0])%p
                pmap.pop(0)
            else:
                ans=(ans*mmap[0])%p
                mmap.pop(0)
        elif len(pmap)==0:
            ans = (ans * mmap[0]) % p
            mmap.pop(0)
        else:
            ans = (ans * pmap[0]) % p
            pmap.pop(0)
    print(ans)

Submission status: Runtime Error

Solution code:
import math
from numba import jit
x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a=input()
al=[int(i) for i in a.split()]
al.sort()
plus=sum([1 for x in al if x>0])
minus=sum([1 for x in al if x<0])
zero=n-plus-minus
f=0
if n==minus and round(k/2)-k/2!=0:
    f=1
if zero==0 and round(minus/2)-minus/2!=0 and n==k:
    f=1
a=1
if f==0:
    @jit
    def aaa(al,k)
        for i in range(math.floor(k/2)):
            a1=al[0]*al[1]
            a2=al[-1]*al[-2]
            if a1>=a2:
                a*=a1
                del al[0]
                del al[0]
            else:
                a*=a2
                del al[-1]
                del al[-1]
            a=a%(10**9+7)
        if math.floor(k/2)-k/2!=0:
                a*=max(al)
        return(a%(10**9+7))
    print(aaa(al,k))
else:
    def checkio(al):
        return sorted(al, key=abs)
    al=checkio(al)
    for i in range(k):
        a*=al[i]
        a=a%(10**9+7)
    print(a)