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()))
mod = 10**9+7

ans = 1
sei = 0
for i in a:
    if i>0:
        sei += 1

if max(0,k-sei)%2==0:
    b = sorted(a, key=lambda x: abs(x),reverse=True)
    buf = 0
    cnt = 0
    sei = []
    hu = []
    for i in b:
        if i>0:
            sei.append(i)
        else:
            hu.append(i)
    hu_seki = []
    for i in range(len(hu)//2):
        hu_seki.append(hu[i*2]*hu[i*2+1]%mod)
    
    for i in range(min(k,len(sei))):
        ans *= sei[i]
    if k>len(sei):
        for i in range(k-len(sei)//2):
            ans = ans*hu_seki%mod
        
    sei.sort()
    index = 0
    while index<len(hu) and index*2+1<len(sei):
        if sei[index*2]*sei[index*2+1]<hu_seki[index]:
            ans = ans//(sei[index*2]*sei[index*2+1])
            ans = ans*hu_seki[index]%mod
            index += 1
        else:
            break
    
    
else:
    b = sorted(a, key=lambda x: abs(x))
    for i in range(k):
        ans *= b[i]
        ans %= mod
print(ans%mod)

Submission status: Runtime Error

Solution code:

def main():
    MOD = 10**9+7
    n,k = map(int, input().split())
    al = list(map(int, input().split()))
    al_abs = []
    al_nl = []
    for a in al: 
        if a > 0: sig = 1
        elif a < 0 : 
            sig = -1
            al_nl.append(a)
        else: sig = 0
        al_abs.append((abs(a), sig))

    al_abs.sort(reverse=True)
    n_cnt = 0
    last_p = -1
    last_n = -1
    for i in range(k):
        a, sig = al_abs[i]
        if sig == -1:
            n_cnt+=1
            last_n = i
        elif sig == 1:
            last_p = i
    
    ans = 1
    if n_cnt%2 == 0:
        for i in range(k):
            a, sig = al_abs[i]
            ans *= a
            ans %= MOD
        print(ans)
        exit()


    next_p = -1
    next_n = -1 
    for i in range(k,n):
        a, sig = al_abs[i]
        if sig == 1 and next_p == -1:
            next_p = i
        elif sig == -1 and next_n == -1:
            next_n = i
        if next_n != -1 and next_p != -1:
            break

    comp_np = 0
    if next_p != -1:
        last_n_val = al_abs[last_n]
        next_p_val = al_abs[next_p]
        comp_np = next_p_val*(1.0)/last_n_val

    comp_pn = 0
    if next_n != -1 and last_p != -1:
        last_p_val = al_abs[last_p]
        next_n_val = al_abs[next_n]
        comp_pn = next_n_val*(1.0)/last_p_val

    if comp_np > comp_pn: 
        np_or_pn = True
    else:
        np_or_pn = False

    if comp_np == 0 and comp_pn == 0:
        if 0 in al:
            print(0)
            exit()
        else:
            al_nl.sort(reverse=True)
            for i in range(k):
                a = al_nl[i]
                ans *= (a)
                ans %= MOD
            print(ans)
            exit()


    print(next_p, next_n, comp_np, comp_pn)

    for i in range(k,n):
        if np_or_pn and i == last_n:
            continue
        if (not np_or_pn) and i == last_p:
            continue
        a, sig = al_abs[i]
        ans *= a
        ans %= MOD

    if np_or_pn:
        ans *= next_p_val
        ans %= MOD
    else:
        ans *= next_n_val
        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(' ')))

a.sort()

d = []
for _ in range(2):
    for i in a:
        d.append(i)

n = 2 * n
pro = 1
for i in range(k):
    pro *= d[i]

ans = pro
for i in range(k, n):
    pro = pro // d[i - k] * d[i]
    ans = max(ans, pro)

MOD = 1000000000 + 7

while ans < 0:
    ans += MOD

print(ans % MOD)

Submission status: Runtime Error

Solution code:
import sys
N,K=[int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]
mod=10**9+7
plus=[]
minus=[]
for a in A:
    if a>0:
        plus.append(a)
    elif a<0:
        minus.append(a)

if len(plus)+len(minus)<K:
    print(0)
    sys.exit(0)

if len(plus)==0:
    minus=sorted(minus,reverse=True)
    retval=1
    for i in minus[:K]:
        retval*=i
        retval=retval%mod
    print(retval%mod)
    sys.exit(0)


plus=sorted(plus,reverse=True)
minus=sorted(minus)

A=sorted(A,key=lambda w:abs(w),reverse=True)

retval=1
use_minus=0
for a in A[:K]:
    if a<0:
        use_minus+=1
    retval*=a
    retval=retval%mod

if use_minus%2==0:
    print(retval%mod)
else:
    inv=pow(minus[use_minus-1],10**9+5,10**9+7)
    retval*=inv
    use_plus=K-use_minus
    retval=retval*plus[use_plus]
    print(retval%mod)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate
import operator as op
mod = int(1e9+7)
n,k = map(int,input().split())
L=list(map(int,input().split()))
L.sort()
zero = L.count(0)
if zero>0:
    L.remove(0)

l1 = L[:k]
l2 = L[n-zero-k:]
pr1 = 1
pr2 = 1
count1=0
count2=0 
val1 = []
val2 = []

for i in range(k):
    pr1 = abs(pr1* l1[i])%mod
    if l1[i]<0:
        count1+=1
        pr1 = ((-1)**count1)*pr1
    pr2 = abs(pr2* l2[i])%mod
    if l2[i]<0:
        count2+=1
        pr2 = ((-1)**count2)*pr2

val = max(pr1,pr2)
print(val%mod)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
minus=0
ans=1

for i in  range(n):
    if a[i]<0:
        minus+=1
if len(a)-minus==0 and k%2==1:
    while k>=1:
        ans*=a[-1]
        del a[-1]
        k-=1

else:
    while k>=2:
        mi=a[0]*a[1]
        ma=a[-1]*a[-2]
        if mi>=ma:
            ans*=mi
            del a[0]
            del a[1]
        else:
            ans*=ma
            del a[-1]
            del a[-2]
        k-=2
    if k==1:
        ans*=max(a)
        k-=1
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
mod = 10**9 + 7

def sgn(v):
    return (v > 0) - (v < 0)

def compute_answer():
    v.sort(key=abs, reverse=True)
    prod = 1
    sg = 1
    for a in xrange(k):
        prod *= v[a]
        prod %= mod
        sg *= sgn(v[a])

    if sg >= 0:
        return prod

    if max(v) <= 0:
        prod = 1
        for a in xrange(-k,0):
            prod *= v[a]
            prod %= mod
        return prod

    def find_pair(comp):
        i = k-1
        while i >= 0 and comp(v[i]): i -= 1
        j = k
        while j < n and not comp(v[j]): j += 1
        if j == n: j = i
        return i, j
    i, j = find_pair(lambda w: w >= 0)
    I, J = find_pair(lambda w: w <= 0)
    if I >= 0 and v[j] * v[I] < v[i] * v[J]:
        i = I
        j = J

    prod = v[j]
    for a in xrange(k):
        if a != i:
            prod *= v[a]
            prod %= mod
    return prod

for cas in xrange(1):
    n, k = map(int, raw_input().strip().split())
    v = map(int, raw_input().strip().split())
    print compute_answer()

Submission status: Runtime Error

Solution code:
#                          JAI SHREE RAM

import math; from collections import *
import sys; from functools import reduce

# sys.setrecursionlimit(10**6)
def get_ints(): return map(int, input().strip().split())
def get_list(): return list(get_ints())
def get_string(): return list(input().strip().split())
def printxsp(*args): return print(*args, end="")
def printsp(*args): return print(*args, end=" ")

UGLYMOD = int(1e9)+7; SEXYMOD = 998244353; MAXN = int(1e5)

# sys.stdin=open("input.txt","r");sys.stdout=open("output.txt","w")

# for _testcases_ in range(int(input())):
n, k = get_ints()
li = get_list()
pos = []
neg = []
zeroes = 0
for i in li:
    if i < 0: neg.append(i)
    elif i > 0: pos.append(i)
    else: zeroes += 1
lengthOfPos, lengthOfNeg = len(pos), len(neg)
if (k - lengthOfPos) & 1:
    if zeroes:
        print("0")
    else:
        try: ans = reduce(lambda x, y: (x*y) % UGLYMOD, pos)
        except: ans = 1
        neg.sort(reverse = True)
        # print(neg)
        for i in range(k-lengthOfPos):
            ans  = (ans * neg[i]) % UGLYMOD
        print(ans)
else:
    pos.sort(reverse = True); positionOfPos = 0
    neg.sort(); positionOfNeg = 0
    if lengthOfNeg & 1:
        neg.pop()
        lengthOfNeg -= 1
    ans = 1
    while k > 1:
        try: negpower = neg[positionOfNeg] * neg[positionOfNeg+1]
        except: negpower = -float('inf')
        try: pospower = pos[positionOfPos] * pos[positionOfPos+1]
        except: pospower = -float('inf')
        if pospower >= negpower:
            positionOfPos += 2
            ans = (ans * (pospower % UGLYMOD)) % UGLYMOD
        else:
            ans = (ans * (negpower % UGLYMOD)) % UGLYMOD
            positionOfNeg += 2
        k -= 2
    if k == 1:
        ans = (ans * pos[positionOfPos]) % UGLYMOD
    print(ans)







'''
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
THE LOGIC AND APPROACH IS MINE @luctivud ( UDIT GUPTA )
Link may be copy-pasted here if it's taken from other source.
DO NOT PLAGIARISE.
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
'''

Submission status: Runtime Error

Solution code:
from sys import exit
from random import randrange
MOD = 10**9+7
n, k = map(int, input().split())
b = list(map(int, input().split()))
a = []
if n == k:
	ans = 1
	for x in b:
		ans *= x
		ans %= MOD
	print(ans)
	exit()
for x in b:
	if x != 0:
		a.append(x)
if len(a) < k:
	print(0)
	exit()

a.sort(key=lambda x: -abs(x))
#print(a)
ans = 1
minus = 0
for i in range(k):
	ans *= a[i]
	ans %= MOD
	if a[i] < 0:
		minus += 1

if minus%2 == 0:
	print(ans)
	exit()

if len(a) == k:
	if len(a) < n:
		print(0)
		exit()

for i in range(k, len(a)):
	if a[i] < 0:
		minus += 1

if minus == len(a):
	if len(a) < n:
		print(0)
		exit()
	ans = 1
	for i in range(k):
		ans *= a[-i-1]
		ans %= MOD
	print(ans)
	exit()

for i in range(k-1, -1, -1):
	if a[i] * a[k] < 0:
		p, q = a[i], a[k]
		break
for i in range(k, len(a)):
	if a[k-1] * a[i] < 0:
		r, s = a[k-1], a[i]
		break
if abs(q*r) >= abs(p*s):
	ans *= pow(p, MOD-2, MOD)
	ans *= q
	print(ans%MOD)
else:
	ans *= pow(r, MOD-2, MOD)
	ans *= s
	print(ans%MOD)

Submission status: Runtime Error

Solution code:
N, K, *A = map(int, open(0).read().split())

MOD = 10 ** 9 + 7
if sorted(A)[K - 1] == 0:
    print(0)
    exit()


if all(v <= 0 for v in A):
    x = sorted([v for v in A if v < 0])
    ans = 1
    if K % 2 == 0:
        for i in range(K):
            ans = ans * x[i] % MOD
    else:
        for i in range(N - K, N):
            ans = ans * x[i] % MOD
            
    print(ans)
    exit()


x = sorted([(abs(v), v // abs(v)) for v in A])
plus = []
minus = []
for i in range(K):
    v, s = x.pop()
    if s == 1:
        plus.append(v)
    else:
        minus.append(v)


if len(minus) % 2 != 0:
    p_cand = MOD
    m_cand = MOD
    while x:
        v, s = x.pop()
        if s == 1 and p_cand == MOD:
            p_cand = v
        elif s == -1 and m_cand == MOD:
            m_cand = v
    
    if p_cand == MOD and m_cand != MOD and plus:
        plus.pop()
        minus.append(m_cand)
    elif m_cand == MOD and p_cand != MOD and minus:
        minus.pop()
        plus.append(p_cand)
    elif p_cand != MOD and m_cand != MOD and plus and minus:
        p_val = plus.pop() * p_cand
        m_val = minus.pop() * m_cand
        
        if p_val > m_val:
            plus.append(p_val)
        else:
            minus.append(m_val)
            
ans = 1
for v in plus:
    ans = ans * v % MOD
for v in minus:
    ans = ans * v % MOD
print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
B = []
C = []
S = []
for i in range(N):
    a = A[i]
    if a < 0:
        b = -a
        B.append(b)
    else:
        b = a
        C.append(b)
    S.append(b)
S.sort()
B.sort()
i = 0
while b:
    if S[i] == B[0]:
        S[i] = -S[i]
        B.pop(0)
    i += 1

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np

def main():
	n,k=MI()
	A=LI()
	p=[]
	m=[]
	mod=10**9+7

	for i in A:
		if i>=0:
			p.append(i)
		else:
			m.append(i)
	p.sort(reverse=True)
	m.sort()
	#print(p,m)

	ans=1
	if p==[] and k%2==1:
		for i in range(k):
			ans*=m[-i-1]
			ans%=mod
			#print(k,ans)
	else:
		i=0
		j=0
		pl=len(p)
		ml=len(m)
		while k>=2:
			if i+2<=pl and j+2<=ml:
				pp=p[i]*p[i+1]
				mm=m[j]*m[j+1]
				if pp>mm:
					ans*=pp
					ans%=mod
					i+=2
				else:
					ans*=mm
					ans%=mod
					j+=2
			elif i+2<=pl:
				pp=p[i]*p[i+1]
				ans*=pp
				ans%=mod
				i+=2
			else:
				#print(i,j)
				mm=m[j]*m[j+1]
				ans*=mm
				ans%=mod
				j+=2
			k-=2

		if k==1:
			ans*=p[i]
			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()))
APlus = []
AMinus = []
for i in A:
    if 0 < i:
        APlus.append(i)
    elif 0 == i:
        pass
    elif i < 0:
        AMinus.append(i)
APlusBackup = APlus = sorted(APlus)
AMinusBackup = AMinus = sorted(AMinus)
count = 0
answer = 1
while count < K:
    #リストに2つ以上要素がある場合
    if count + 1 < K and 1 < len(APlus) and 1 < len(AMinus):
        if AMinus[0] * AMinus[1] < APlus[0] * APlus[1]:
            answer = answer * APlus.pop(0)
            answer = answer * APlus.pop(0)
            count += 2
        elif APlus[0] * APlus[1] < AMinus[0] * AMinus[1]:
            answer = answer * AMinus.pop(0)
            answer = answer * AMinus.pop(0)
            count += 2
        elif AMinus[0] * AMinus[1] == APlus[0] * APlus[1]:
            if count + 2 < K:
                if AMinus[2] <= APlus[2]:
                    answer = answer * APlus.pop(0)
                    answer = answer * APlus.pop(0)
                    count += 2
                else:
                    answer = answer * AMinus.pop(0)
                    answer = answer * AMinus.pop(0)
                    count += 2
    #リストに1つの要素がある場合
    else:
        try:
            answer = answer * APlus.pop(0)
            count += 1
        except:
            count = 0
            answer = 1
            APlus = sorted(APlusBackup, reverse = True)
            AMinus = sorted(AMinusBackup, reverse = True)
            while count < K:
                try:
                    if APlus[0] < AMinus[0]:
                        answer = answer * APlus.pop(0)
                        count += 1
                    elif AMinus[0] < APlus[0]:
                        answer = answer * AMinus.pop(0)
                        count += 1
                    elif APlus[0] == AMinus[0]:
                        if 1 < len(APlus) and 1 < len(AMinus):
                            if APlus[1] <= AMinus[1]:
                                answer = answer * APlus.pop(0)
                                count += 1
                            else:
                                answer = answer * AMinus.pop(0)
                                count += 1
                        else:
                            answer = answer * APlus.pop(0)
                            count += 1
                except:
                    answer = answer * AMinus.pop(0)
                    count += 1
            break
answer = answer % (10 ** 9 + 7)
print(answer)

Submission status: Runtime Error

Solution code:
rule=input().split()
N=int(rule[0])
K=int(rule[1])
data_pre=input().split()
data_pre_2=[int(s) for s in data_pre]
data=[]
import math
for i in range(N):
    num=math.fabs(data_pre_2[i])
    data.append(num)
data.sort()
data.reverse()
ans=1
for i in range(K):
    ans*=data[i]
print(int(ans%(10**9+7)))

Submission status: Runtime Error

Solution code:
MOD = 10**9+7

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

a = [int(_) for _ in input().split()]

m = list(filter(lambda x: x < 0, a))
p = list(filter(lambda x: x > 0, a))

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


if len(p)+len(m) < k:
    print(0)
    exit()
if len(p) == 0:
    ans = 1
    for i in range(k):
        ans = (ans*m[-i-1]) % MOD
    print(ans)
    exit()


i, j = 0, 0

m.append(0)
m.append(0)
p.append(0)
p.append(0)
ans = 1
for c in range(k//2):
    # print(i, j)
    if m[i]*m[i+1] >= p[j]*p[j+1]:
        ans = (ans*m[i]*m[i+1]) % MOD
        i += 2
    else:
        ans = (ans*p[j]*p[j+1]) % MOD

        j += 2
if k % 2 == 1:
    ans = (ans*p[i]) % MOD
print(ans)

Submission status: Runtime Error

Solution code:
import functools


def solve():
    n, k = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    A.sort(key=lambda x: -abs(x))

    prod = functools.reduce(lambda x, y: x * y, A[:k])
    if prod > 0:
        return prod
    smallest_pos = min((a for a in A[:k] if a > 0), default=None)
    smallest_neg = min((-a for a in A[:k] if a < 0), default=None)
    for a in A[k:]:
        if a > 0:
            if smallest_neg is not None:
                return -prod * a / smallest_neg
        elif a < 0:
            if smallest_pos is not None:
                return prod * a / smallest_pos

    return functools.reduce(lambda x, y: x * y, A[-k:])


print(solve() % 1000000007)

Submission status: Runtime Error

Solution code:
from collections import deque
n, k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10 ** 9 + 7

p = []
m = []
for i in a:
    if i > 0:p.append(i)
    elif i < 0:p.append(i)

p.sort(reverse=True)
m.sort()
double = []

for i in range(len(p) - 1):
    if i % 2 == 0:
        temp = p[i] * p[i + 1]
        double.append([temp, 1])
for i in range(len(m) - 1):
    if i % 2 == 0:
        temp = m[i] * m[i + 1]
        double.append([temp, 2])

double.sort(reverse=True)
res = 1
flag = 0
p = deque(p)
m = deque(m)
double = deque(double)
while k:
    if double and k - 2 >= 0:
        temp, ind = double.popleft()
        if ind == 1:
            p.popleft()
            p.popleft()
        else:
            m.popleft()
            m.popleft()
        res = (res * temp) % mod
        k -= 2
    else:
        if p:
            res = (res * p.popleft()) % mod
        else:
            res = (res * m.popleft()) % mod
        k -= 1
        
print(res)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
mod=10**9+7
A=list(map(int,input().split()))
A.sort(reverse=True)
Plus=[]
Minus=[]
Zero=[]
for i in range(N):
    if A[i]>0:
        Plus.append(A[i])
    elif A[i]<0:
        Minus.append(-A[i])
    else:
        Zero.append(A[i])
Plus.sort(reverse=True)
Minus.sort(reverse=True)
if K==N:
    ans=1
    for i in range(N):
        ans=ans*A[i]
        ans%=mod
    print(ans)
    exit()
if len(Plus)==0:
    if len(Zero)==0:
        if K%2==0:
            ans=1
            for i in range(K):
                ans=ans*Minus[i]
                ans%=mod
            print(ans)
        else:
            ans=1
            for i in range(K):
                ans=ans*Minus[-i-1]
                ans%=mod
            print((-ans)%mod)
    else:
        if len(Minus)<=K:
            if K%2==0:
                ans=1
                for i in range(K):
                    ans=ans*Minus[i]
                    ans%=mod
                print(ans)
            else:
                print(0)
        else:
            print(0)
    exit()
if len(Minus)==0:
    ans=1
    for i in range(K):
        ans=ans*A[i]
        ans%=mod
    print(ans)
    exit()
if len(Zero)>N-K:
    print(0)
    exit()
if len(Zero)+K==N:
    if len(Minus)%2==0:
        ans=1
        for i in range(N):
            if A[i]!=0:
                ans=ans*abs(A[i])
                ans%=mod
        print(ans)
    else:
        print(0)
    exit()
n=len(Plus)
m=len(Minus)
'''
+:x0,...,x(n-1)
-:y0,...,y(m-1)

x0*...x(K-l-1)*y0*...y(l-1)
yl*y(l+1)/x(K-l-1)*x(K-l-2)
これはlについて単調減少
<1となるはじめてのタイミングでbreak
'''
l=K-n
if l%2==1:
    l+=1
x=l
while(l<=m and l<=K):
    if (l+2)<=min(m,K) and Minus[l]*Minus[l+1]>=Plus[K-l-1]*Plus[K-l-2]:
        x=l+2
    l+=2
ans=1
for i in range(x):
    ans=ans*Minus[i]
    ans%=mod
for i in range(K-x):
    ans=ans*Plus[i]
    ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
import math
def maxProductSubarrayOfSizeK(A, n, k):

    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]
        return product

    i = 0

    j = n - 1

    if (k & 1):
        product *= A[j]
        j -= 1
        k -= 1

    k >>= 1

    for itr in range(k):

        # product from left pointers
        left_product = A[i] * A[i + 1]

        # product from right pointers
        right_product = A[j] * A[j - 1]

        if (left_product > right_product):
            product *= left_product
            i += 2

        else:
            product *= right_product
            j -= 2

    return product

n,k=map(int,input().split())
A=list(map(int,input().split()))
p=math.pow(10,9)+7
print(maxProductSubarrayOfSizeK(A,n,k)%p)

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(k):
			i = -(1+i)
			ans *= mina[i]
		print(ans % mod)
	else:
		for i in range(k):
			ans *= mina[i]
		print(ans % mod)
elif lp == 1:
	if n == k:
		mina.append(pra[0])
		mina.sort()
		for i in range(k):
			i = -(1+i)
			ans *= mina[i]
		print(ans % mod)
	else:
		if k % 2 == 0:
			for i in range(k):
				ans *= mina[i]
			print(ans % mod)
		else:
			ans *= pra[0] 
			for i in range(k-1):
				ans *= mina[i]
			print(ans % mod)
else:
	cp = lp-1
	cm = 0
	count = 0
	data = []
	
	while count < 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:
						#ans *= pra[cp]
						data.append(pra[cp])
						cp -= 1


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

		else:
			break

	data.sort()
	co = 0
	while co <= k:
		if k - co >= 2:
			if data[co] * data[co+1] >= 0:
				ans *= (data[co] * data[co+1]) % mod
				ans %= mod
				co += 2
			else:
				ans *= data[co]
				ans %= mod
				ans *= data[co+1]
				ans %= mod
				co += 2
		elif k -co == 1:
			ans *= data[co]
			ans %= mod
			co += 1
		else:
			break


		
	print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
s=1
c=0
l=0
r=-1
while True:
    if k-c>=2:
        if a[r]*a[r-1]>=a[l]*a[l+1]:
            s*=a[r]*a[r-1]
            r-=2
            c+=2
        else:
            s*=a[l]*a[l+1]
            l+=2
            c+=2
    else:
        if a[r]<0:
            s=1
            a=np.abs(a)
            a=list(a)
            a.sort()
            while True:
                s*=a[c1]
                c1+=1
                s%=10**9+7
                if c1==k:
                    s=-s
                    print(s%10**9+7)
                    exit()
        else:s*=a[r]
        c+=1
    s%=10**9+7
    if k==c:break
print(s)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= mod
        return ans

    neg = []
    pos = []
    for a in A:
        if a > 0:
            pos.append(a)
        elif a < 0:
            neg.append(a)
    if K > len(pos) + len(neg):
        return 0
    pos.sort()
    neg.sort(reverse=True)

    if len(neg) == N:
        res = 1
        for i in range(K):
            res *= neg[i]
            res %= mod
        return res

    ans = 1

    if K & 1:
        ans *= pos.pop()
        K -= 1
    # この時点でKは偶数
    while K > 1 and len(pos) > 1 and len(neg) > 1:
        K -= 2
        if pos[-1] * pos[-2] > neg[-1] * neg[-2]:
            ans *= pos.pop()
            ans *= pos.pop()
            ans %= mod
        else:
            ans *= neg.pop()
            ans *= neg.pop()
            ans %= mod
    while K > 1 and len(pos) > 1:
        K -= 2
        ans *= pos.pop()
        ans %= mod
        ans *= pos.pop()
        ans %= mod
    while K > 1 and len(neg) > 1:
        K -= 2
        ans *= neg.pop()
        ans %= mod
        ans *= neg.pop()
        ans %= mod
    return ans


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

Submission status: Runtime Error

Solution code:
MOD=10**9+7
import bisect
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls=sorted(ls)
s=bisect.bisect_left(ls,0)
t=bisect.bisect_right(ls,0)
mls=ls[:s]
pls=ls[t:]
M=s
P=N-t
ans=set()
#プラスの値にすること不可能か？
if (P==0 and K%2==1) or (N==K and M%2==1):
  #ゼロにできるか？
  if N-P-M>0:
    print(0)
  else:
    mls.reverse()
    mul=1
    if P==0:
      for i in range(K):
        mul*=mls[i]
    else:
      for i in range(N):
        mul*=ls[i]
    ans.add(mul)
else:
  pls.reverse()
  for a in range(K+1)[::2]:
  #  print(a,pls[:K-a+1],mls[:a])
    if K-a>P:
      continue
    if a>M:
      break
    mul=1
    for i in range(a):
      mul*=mls[i]
    for i in range(K-a):
      mul*=pls[i]
    ans.add(mul)
print(max(ans)%MOD)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
MOD = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, (input().split())))
ap = []
neg_cnt = 0
zero_cnt = 0
for a in A:
    if a<0:
        ap.append((-a, -1))
        neg_cnt += 1
    elif a==0:
        ap.append((0, 0))
        zero_cnt += 1
    else:
        ap.append((a, 1))
ap.sort(reverse=True)
# print(ap)
ans = 1
if neg_cnt==N and K%2:      # 正が無く、答えは負
    for i in range(K):
        ans *= ap[N-i-1][0] * ap[N-i-1][1]
        ans %= MOD
else:                       # 答えは正
    neg_num = 0
    for i in range(K):
        if ap[i][1] == -1:
            neg_num += 1
    if neg_num % 2:     # 負の数が奇数だったら、-1して偶数回にし、K+1個見る
        neg_num -= 1
        K += 1
    for i in range(K):
        if ap[i][1] == -1:  # 負の数だった、neg_num回まで
            if neg_num == 0:
                continue
            else:
                neg_num -= 1
        ans *= ap[i][0] * ap[i][1]
        ans %= MOD

print(ans)

Submission status: Runtime Error

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

    plus = [A[i] for i in range(N) if A[i] >= 0]
    minus = [A[i] for i in range(N) if A[i] < 0]

    ans = 1

    id = 0
    id2 = 0
    P = len(plus)
    M = len(minus)
    plus.sort(reverse=True)

    mod = 10**9 + 7

    if P == 0:
        if K % 2 == 0:
            minus.sort()
            for i in range(K):
                ans *= minus[i]
                ans %= mod
        else:
            minus.sort(reverse=True)
            for i in range(K):
                ans *= minus[i]
                ans %= mod

    elif M == 0:
        for i in range(K):
            ans *= plus[i]
            ans %= mod

    else:

        p = P // 2
        m = M // 2
        if K > (p+m)*2 and (K % 2 == 1 and P % 2 == 0):  # 絶対値が小さい方から貪欲
            A.sort(key=lambda x: abs(x))
            for i in range(K):
                ans *= A[i]
                ans %= mod

        else:  # 絶対値が大きい方から貪欲
            minus.sort()
            pp = [plus[i]*plus[i+1] for i in range(M // 2)]
            mm = [minus[i] * minus[i+1] for i in range(P//2)]

            id = 0
            id2 = 0

            pp.sort(reverse=True)
            mm.sort(reverse=True)

            for i in range((K // 2) - 1):
                if id == p - 1:
                    ans *= mm[id2]
                    id2 += 1
                elif id2 == m:
                    ans *= pp[id]
                    id += 1
                elif pp[id] >= mm[id2]:
                    ans *= pp[id]
                    id += 1
                else:
                    ans *= mm[id2]
                    id2 += 1

                ans %= mod

            if K % 2 == 1:
                if id == p-1:
                    ans *= mm[id2]
                    ans *= plus[id*2]
                else:
                    ans *= pp[id]
                    id += 1
                    ans *= pp[id*2]
            else:
                if id == p - 1:
                    ans *= mm[id2]
                    id2 += 1
                elif id2 == m:
                    ans *= pp[id]
                    id += 1
                elif pp[id] >= mm[id2]:
                    ans *= pp[id]
                    id += 1
                else:
                    ans *= mm[id2]
                    id2 += 1

    print(ans % mod)


main()