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:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, K = LI()
A = LI()

def abssort(A):
    return sorted(A, key = lambda x:abs(x), reverse= True)

tmps = []
A_abs = abssort(A)
for i in range(K):
    # tmp *= A_abs[i]
    tmps.append(A_abs[i])

cnt = 0
for i in range(K):
    if tmps[i] < 0:
        cnt += 1
if cnt % 2 == 0:
    ans = 1
    for i in range(K):
        ans *= tmps[i]
        ans = ans % mod
    print(ans)
    sys.exit()
else:
    tmp_1 = copy.deepcopy(tmps)
    tmp_2 = copy.deepcopy(tmps)
    tmp_1.reverse()
    tmp_2.reverse()
    tmp_2_ = 0
    tmp_1_ = 0
    # -を一つ消す
    for i in range(K):
        if tmp_1[i] < 0:
            tmp_1.remove(tmp_1[i])
            break
    # + を一つたす
    for i in range(K, N):
        if A_abs[i] > 0:
            tmp_1.append(A_abs[i])
            tmp_1_ = 1
            break
    else:
        # +がなかった時
        tmp_1 = []
        tmp_1_ = -1 
        A_abs.reverse()
        for i in range(K):
            tmp_1.append(A_abs[i])

    # +を消して-を追加
    cnt = 0
    for i in range(K):
        if tmp_2[i] > 0:
            tmp_2.remove(tmp_2[i])
            cnt += 1
            break
    if cnt == 1:
        for i in range(K, N):
            if A_abs[i] < 0:
                tmp_2.append(A_abs[i])
                tmp_2_ = 1
                break
        else:
            tmp_2_ = 0
    else:
        tmp_2_ = -1
# print(tmp_1, tmp_2)






tmp_1_m = 1
tmp_2_m = 1
for i in range(K):
    tmp_1_m *= tmp_1[i]
    tmp_1_m = tmp_1_m % mod
    tmp_2_m *= tmp_2[i]
    tmp_2_m = tmp_2_m % mod

# print(tmp_1_, tmp_2_)
if tmp_2_ == 0:
    print(tmp_1_m)
elif tmp_1_ == 1 and tmp_2_ == -1:
    print(tmp_1_m)
elif tmp_1_ == -1 and tmp_2_ == 1:
    print(tmp_2_m)
elif tmp_1_ == 1 and tmp_2_ == 1:
    for i in range(K):
        if tmp_1[i] == tmp_2[i]:
            pass
        elif tmp_1[i] > tmp_2[i]:
            print(tmp_2_m)
            sys.exit()
        else:
            print(tmp_1_m)
            sys.exit()
else:
    for i in range(K):
        if tmp_1[i] == tmp_2[i]:
            pass
        elif tmp_1[i] > tmp_2[i]:
            print(tmp_1_m)
            sys.exit()
        else:
            print(tmp_2_m)
            sys.exit()

Submission status: Runtime Error

Solution code:
'''n=int(input())
l=[]
M=(10**9)+7
count=0
for i in range(6):
	l.append(int(input()))



dp=[[[[[[[-1]*7 for _ in range(11)] for _ in range(11)] for _ in range(11)] for _ in range(11)] for _ in range(11)] for _ in range(11)]

def countWays(last,a,b,c,d,e,f,i):
    if a+b+c+d+e+f==0:
        return 1

    if (dp[a][b][c][d][e][f][last] != -1):  
        return dp[a][b][c][d][e][f][last]
    ans=0
    if (last == 0): 
        if b:ans+=countWays(1,a,b-1,c,d,e,f,i)
        if e:ans+=countWays(4,a,b,c,d,e-1,f,i)  
    elif (last == 1): 
        if a:ans+=countWays(0,a-1,b,c,d,e,f,i)
        if c:ans+=countWays(2,a,b,c-1,d,e,f,i)  
    elif (last == 2): 
        if d:ans+=countWays(3,a,b,c,d-1,e,f,i)
        if f:ans+=countWays(5,a,b,c,d,e,f-1,i) 
    elif (last == 3): 
        if a:ans+=countWays(0,a-1,b,c,d,e,f,i)
        if c:ans+=countWays(2,a,b,c-1,d,e,f,i)  
    elif (last == 4): 
        if d:ans+=countWays(3,a,b,c,d-1,e,f,i)
        if f:ans+=countWays(5,a,b,c,d,e,f-1,i)  
    elif (last == 5): 
        if b:ans+=countWays(1,a,b-1,c,d,e,f,i)
        if e:ans+=countWays(4,a,b,c,d,e-1,f,i) 
  
    dp[a][b][c][d][e][f][last]=ans
    return ans

def countUtil(i): 
    return (countWays(0,l[0],l[2],l[1],l[4],l[3],l[5],i) + 
            countWays(1,l[0],l[2],l[1],l[4],l[3],l[5],i) + 
            countWays(2,l[0],l[2],l[1],l[4],l[3],l[5],i))


di={}
oo=sum(l)
print(countUtil(15))
for a in range(11):
	for b in range(11):
		for c in range(11):
				for d in range(11):
						for e in range(11):
								for f in range(11):
									for k in range(7):
										if dp[a][b][c][d][e][f][k]!=-1:
											fi=a+b+c+d+e+f
											if fi in di:
												di[fi]+=dp[a][b][c][d][e][f][k]
											else:
												di[fi]=dp[a][b][c][d][e][f][k]
print(di)

'''
import math
import bisect
import copy
#import time
import itertools
#map(int,input().split())
#int(x) for x in input().split()
#for _ in range(int(input()))
M=10**9+7
n,k=map(int,input().split())
l=[int(x) for x in input().split()]
l.sort(reverse=True)
p=1
p1=1
for i in range(k):
	if l[i]<0:
		p=(p*l[i])
	else:
		p=(p*l[i])%M


f=0
if p<0:
	f=1
	p=p/l[k-1]
	for i in range(k,len(l)):
		if l[i]>0:
			p=(p*l[i])%M
			f=0
			break

if f==1:
	p=p*l[k-1]

l=l[::-1]
for i in range(k):
	if l[i]<0:
		p1=(p1*l[i])
	else:
		p1=(p1*l[i])%M


f=0
if p1<0:
	f=1
	p1=p1/l[k-1]
	for i in range(k,len(l)):
		if l[i]>0:
			p1=(p1*l[i])%M
			f=0
			break

if f==1:
	p1=p1*l[k-1]

ans=max(p,p1)
print(int(ans%M))

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):
            # 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:
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)

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:
def main():

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

    mod = pow(10, 9) + 7

    pos = []
    neg = []
    zero = 0
    for v in A:
        if v > 0: pos.append(v)
        elif v < 0: neg.append(v)
        else: zero += 1

    # zero is needed
    if len(pos) + len(neg) < K:
        return 0

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

    cnt_p, cnt_n = 0, 0
    h = []
    for v in pos:
        h.append([v, 1])
    for v in neg:
        h.append([-v, -1])

    h.sort(reverse = True)
    v = 1
    for k in range(K):
        if h[k][1] > 0:
            cnt_p += 1
        else:
            cnt_n += 1

    if cnt_n % 2 == 0: # when positive
        v = 1
        for i in range(cnt_p):
            v *= pos[i]
            v %= mod
        for j in range(cnt_n):
            v *= abs(neg[j])
            v %= mod
        return v % mod
    else: # when negative
        if cnt_p < len(pos) and cnt_n < len(neg) and cnt_p > 0 and cnt_n > 0: # both are not full
            if pos[cnt_p] * pos[cnt_p-1] > abs(neg[cnt_n]) * abs(neg[cnt_n-1]):
                cnt_p += 1
                cnt_n -= 1
            else:
                cnt_p -= 1
                cnt_n += 1
            v = 1
            for i in range(cnt_p):
                v *= pos[i]
                v %= mod
            for j in range(cnt_n):
                v *= abs(neg[j])
                v %= mod
            return v
        elif cnt_p < len(pos) and cnt_n > 0:
            cnt_p += 1
            cnt_n -= 1
            v = 1
            for i in range(cnt_p):
                v *= pos[i]
                v %= mod
            for j in range(cnt_n):
                v *= abs(neg[j])
                v %= mod
            return v % mod
        elif cnt_n < len(neg) and cnt_p > 0:
            cnt_p -= 1
            cnt_n += 1
            for i in range(cnt_p):
                v *= pos[i]
                v %= mod
            for j in range(cnt_n):
                v *= abs(neg[j])
                v %= mod
            return v % mnod
        else:
            if zero > 0:
                return 0
            else:
                pos.sort()
                neg.sort(reverse = True)
                h = []
                for v in pos:
                    h.append([v, 1])
                for v in neg:
                    h.append([-v, -1])
                v = 1
                for i in range(K):
                    v *= h[i][0] * h[i][1]
                    v %= mod
                return v % mod



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

Submission status: Runtime Error

Solution code:
def main():
    N, K = input_ints()
    A = input_int_list_in_line()

    Ap = []
    An = []
    Az = []
    for a in A:
        if a == 0:
            Az.append(a)
        elif a > 0:
            Ap.append(a)
        else:
            An.append(a)

    if len(An) == N and K % 2 == 1:
        An.sort(reverse=True)
        prod = 1
        for i in An[:K]:
            prod *= i

        print_ans(prod)
        exit()

    if len(Ap) == 0 and K % 2 == 1:
        print(0)
        exit()

    if N - len(Az) < K:
        print(0)
        exit()

    if N == K:
        prod = 1
        for i in A:
            prod *= i

        print_ans(prod)
        exit()

    if K == 1:
        print_ans(max(A))
        exit()

    prod = 1

    An.sort(reverse=False)

    if len(An) % 2 == 1:
        An.pop(-1)

    An2 = []

    for i in range(len(An) // 2):
        An2.append(An[i*2] * An[i*2 + 1])

    i = 0
    j = 0

    while K > 0:
        if j not in range(len(An2)):
            prod = (prod * Ap[i]) % (10**9 + 7)
            i += 1
            K -= 1
            continue

        if i not in range(len(Ap)):
            prod = (prod * An2[j]) % (10**9 + 7)
            j += 1
            K -= 1
            continue

        if K >= 2 and Ap[i] < An2[j]:
            prod = (prod * An2[j]) % (10**9 + 7)
            j += 1
            K -= 2
            continue
        else:
            prod = (prod * Ap[i]) % (10**9 + 7)
            i += 1
            K -= 1
            continue

    print_ans(prod)


def print_ans(n: int):
    print(n % (10**9 + 7))


def input_ints():
    line_list = input().split()

    if len(line_list) == 1:
        return int(line_list[0])
    else:
        return map(int, line_list)


def input_int_list_in_line():
    return list(map(int, input().split()))


def input_int_tuple_list(n: int):
    return [tuple(map(int, input().split())) for _ in range(n)]


main()

Submission status: Runtime Error

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
import bisect as bs
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
def adj(n): return [[] for _ in range(n)]

#整数問題セット
def gcd(numbers): return func.reduce(frac.gcd, numbers)
def lcm(numbers): return func.reduce(LCM, numbers)
def inv(a): return pow(a, MOD-2, MOD) #逆元
def comb(n,r):
    ans = 1
    for i in range(r): ans *= n-i; ans *= inv(r-i); ans %= MOD
    return ans

n,k = imap()
a = iarr()
b = np.array([[num, abs(num)] for num in a])
b = b[b[:,1][::-1].argsort(), : ]
c = b[:,0]

ans = 1
for i in range(k):
    ans *= c[i]
    ans = ans%MOD if ans>0 else -(-ans%MOD)

i = k
while ans < 0:
    ans // c[i]
    i += 1
    if i >= n: break
    ans *= c[i]
    ans = ans%MOD if ans>0 else -(-ans%MOD)
    
if ans > 0: print(ans)
else:
    ans = 1
    d = c[::-1]
    for i in range(k):
        ans *= d[i]
        ans = ans%MOD if ans<0 else -(-ans%MOD)
    print(ans)

Submission status: Runtime Error

Solution code:
# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7
    As = [(abs(a), a<0) for a in A]
    As.sort()
    As = As[::-1]


    # 大きい順
    last_plus = None
    last_minus = None
    is_minus = False
    ans = 1
    for a, m in As[:K]:
        ans = (ans * a) % MOD
        is_minus ^= m
        if m:
            last_minus = a
        else:
            last_plus = a
    
    # print(As)
    # print(ans, is_minus)
    # print(last_minus, last_plus)
    # 絶対値の大きい順に選択して、答えが負のとき
    if is_minus:
        # 答えが負の場合はK番目以降の最も絶対値の大きい正負の数を探す
        next_plus = None
        next_minus = None
        for a, m in As[K:]:
            if m and next_minus == None:
                next_minus = a
            elif not m and next_plus == None:
                next_plus = a
        # print(next_minus, next_plus)
        # Aが負の数だけの場合
        if next_plus == None:
            if last_plus == None:
                ans = 1
                for a, m in As[-K:]:
                    ans = (ans * a) % MOD
                ans = MOD - ans
            else:
                ans = (ans * modinv(last_plus)) % MOD
                ans = (ans * next_minus) % MOD
        elif next_minus == None:
                ans = (ans * modinv(last_minus)) % MOD
                ans = (ans * next_plus) % MOD
        else:
            a = last_plus * next_plus
            b = last_minus * next_minus
            if a > b:
                ans = (ans * modinv(last_minus)) % MOD
                ans = (ans * next_plus) % MOD
            else:
                ans = (ans * modinv(last_plus)) % MOD
                ans = (ans * next_minus) % MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

Ps = [-a for a in As if a > 0]
Qs = [a for a in As if a < 0]
Zs = [ 0 for a in As if a == 0]
D  = int(1E9 + 7)

heapq.heapify(Ps)
heapq.heapify(Qs)

k = 0
r = 1

while k < K:

    if len(Ps) == 0 and len(Qs) == 0:
        k = 0
        break

    if (K - k) == 1:
        p = - heapq.heappop(Ps)
        r = (r * (p % D)) % D
        k += 1

    elif len(Qs) < 2:
        p1 = - heapq.heappop(Ps)
        p2 = - heapq.heappop(Ps)
        p  = p1 * p2
        r  = (r * (p % D)) % D
        k += 2

    else: 
        p1 = - heapq.heappop(Ps)
        p2 = - heapq.heappop(Ps)
        p  = p1 * p2

        q1 = - heapq.heappop(Qs)
        q2 = - heapq.heappop(Qs)
        q  = q1 * q2

        if p > q:
            r  = (r * (p % D)) % D
            heapq.heappush(Qs, -q1)
            heapq.heappush(Qs, -q2)
        else:
            r  = (r * (q % D)) % D
            heapq.heappush(Ps, -p1)
            heapq.heappush(Ps, -p2)

        k += 2

print(r)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Submission status: Runtime Error

Solution code:
[N, K] = [int(i) for i in input().split()]
A = sorted([int(i) for i in input().split()], reverse=True)
D = 10**9 + 7

S = 1
i = K
top = 0
tail = N-1

f = 1
if A[0] < 0:
  f = -1

s1 = A[top] * A[top+1]
s2 = A[tail] * A[tail-1]
  
while i > 0:
  if i == 1:
    S *= A[top]
    break
  else:
    if s1 * f > s2 * f:
      S *= s1
      top += 2
      s1 = A[top] * A[top+1]
    else:
      S *= s2
      tail -= 2
	  s2 = A[tail] * A[tail-1]
  i -= 2
      
print((S+D)%D)

Submission status: Runtime Error

Solution code:
N, K = list(map(int,input().split()))
A = list(map(int,input().split()))
A = sorted(A, reverse = True, key = lambda x:abs(x))
 
cnt = 0
for i in A[:K]:
  if i < 0:
    cnt += 1
    
if cnt % 2 == 0:
 
  ans = 1
  for i in range(K):
    ans *= A[i]
    ans = ans%(10**9+7)
  print(ans)
else:
  if all([i <= 0 for i in A]):
    if K % 2 == 0:
      for i in range(K):
        ans *= A[i]
        ans = ans%(10**9+7)
    if K % 2 == 1:
      A = sorted(A, key = lambda x:abs(x))
      for i in range(K):
        ans *= A[i]
        ans = ans%(10**9+7)
    else:
      if any([i <= 0 for i in A[K:]]):
        
        for j in A[K:]:
          if j <= 0:
            keep = j
            break
        A_rev = A[:K]
        A_rev = A[::-1]
        ans = 1
        flag = 1
        for i in range(K):
          if A_rev[i] > 0 and flag == 1:
            ans *= keep
          else:
            ans *= A_rev[i]
        print(ans)
            
       
            
            
    print(ans)

Submission status: Runtime Error

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

ans = 1

p_list, m_list = [], []
for i in a:
    if i<0: m_list.append(i)
    elif i>0: p_list.append(i)
    else: zero_flag = True

n = len(p_list)+len(m_list)

if n<k:
    print(0)
    sys.exit()
if k==n:
    for i in p_list:
        ans *= i
        ans %= mod
    for i in m_list:
        ans *= i
        ans %= mod
    print(ans)
    sys.exit()

if n==len(m_list):
    if zero_flag:
        print(0)
        sys.exit()
    else:
        ans = m_list[-1]
        for i in range(1, k):
            ans *= m_list[n-i-1]
            ans %= mod
        print(ans)
        sys.exit()


p_num, m_num = len(p_list)-1, 0

while k>0:
    p_mul, m_mul = 0, 0
    
    if k==3:
        if m_mul+1<len(m_list) and p_mul+1==2:
            m_mul = m_list[m_num]*m_list[m_num+1]*p_list[p_num]
            p_mul = p_list[p_num]*p_list[p_num-1]*m_list[m_num]
            if p_mul>m_mul:
                ans *= p_mul
            else:
                ans *= m_mul
            if ans<0 and zero_flag:
                ans = 0
        elif m_mul+1<len(m_list) and p_mul+1<len(p_list):
            m_mul = m_list[m_num]*m_list[m_num+1]*p_list[p_num]
            p_mul = p_list[p_num]*p_list[p_num-1]*m_list[m_num]
            mm_mul = p_list[p_num]*p_list[p_num-1]*p_list[p_num-2]
            if p_mul>m_mul and p_mul>mm_mul:
                ans *= p_mul
            elif m_mul>p_mul and m_mul>mm_mul:
                ans *= m_mul
            else:
                ans *= mm_mul
            if ans<0 and zero_flag:
                ans = 0
        ans %= mod    
        break
    if k==1:
        if p_num<0:
            if zero_flag:
                print(0)
                sys.exit()
        ans *= p_list[p_num]
        ans %= mod
        break
    if m_mul+1<len(m_list):
        m_mul = m_list[m_num]*m_list[m_num+1]
    if p_mul+1<len(p_list):
        p_mul = p_list[p_num]*p_list[p_num-1]
    if p_mul>m_mul:
        ans *= p_mul
        ans %= mod
        p_num -= 2
    else:
        ans *= m_mul
        ans %= mod
        m_num += 2
    k -= 2
print(ans)

Submission status: Runtime Error

Solution code:
import math
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:
    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[1]
        else:
            a*=a2
            del al[-1]
            del al[-2]
        a=a%(10*9+7)
    if math.floor(k/2)-k/2!=0:
            a*=max(al)
    print(a%(10**9+7))
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)

Submission status: Runtime Error

Solution code:

//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() //sortなどの引数を省略したい
#define SIZE(x) ll(x.size()) //sizeをsize_tからllに直しておく
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define Umap unordered_map
#define Uset unordered_set

signed main(){
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    
    sort(a.begin(), a.end(), greater<int>());
    bool b = false;
    for(int i = n-k; i < n;i++){
        if (i < 0){
            b = true;
            break;
        }
    }
    if (b && k % 2 == 0){
        reverse(a.begin(), a.end());
    }
    
    ll e = 1;
    for(int i = 0; i < k; i++){
        e *= a[i];
        ll f = e % MOD;
        if (f<0){
            f += MOD;
        }
        e = f;
    }
    cout << e << endl;
    
    
}

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)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

MOD=10**9+7

def main():
    N,K = map(int, input().split())
    A = list(map(int,input().split()))
    n_neg = 0
    n_pos = 0
    for a in A:
        if a < 0:
            n_neg += 1
        else:
            n_pos += 1
    flag = True
    if K % 2 != 0:
        tmp = K-n_pos
        if tmp > 0 and tmp % 2 != 0:
            flag = False

    A = sorted(A, key=abs, reverse=flag)
    negatives = []
    positives = []

    while True:
        if len(negatives) + len(positives) == K:
            if flag:
                if len(negatives) % 2 == 0:
                    break
                else:
                    negatives.pop(-1)
            else:
                break
        a = A.pop(0)
        if a < 0:
            negatives.append(a)
        else:
            positives.append(a)
    ans = 1
    for n in positives:
        ans *= n
        ans %= MOD
    for n in negatives:
        ans *= n
        ans %= MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
pmax, m = 1, 1e9+7
for i in range(k):
    pmax *= a[i]
    pmax %= m
prev = pmax
for i in range(1, n-k+1):
    curr = (prev / a[i-1]) * a[i-k+1]
    curr %= m
    pmax = max(pmax, curr)
    prev = curr
print(int((pmax + m) % m))