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=[int(x) for x in input().split()]
B=[]
C=[]
for i in range(N):
    if A[i]<0:
        B.append(A[i])
    else:
        C.append(A[i])
ans=1
mod=10**9+7

B=sorted(B)
C=sorted(C)

if N==K:
    for i in range(N):
        ans*=A[i]
    print(ans%mod)
    exit()
else:
    if len(C)==0:
        if K%2==1:
            for i in range(1,K+1):
                ans*=B[-i]
            print(ans%mod)
            exit()
        else:
            for i in range(K):
                ans*=B[i]
            print(ans%mod)
            exit()
    else:
        if K%2==1:
            x=C.pop(-1)
            ans*=x
            for i in range((K-1)//2):
                if C[-1]*C[-2]>=B[0]*B[1]:
                    [x,y]=[C.pop(-1),C.pop(-2)]
                    ans*=x*y
                else:
                    [x,y]=[B.pop(0),B.pop(1)]
                    ans*=x*y
            print(ans%mod)
            exit()
        else:
            for i in range((K-1)//2):
                if C[-1]*C[-2]>=B[0]*B[1]:
                    [x,y]=[C.pop(-1),C.pop(-2)]
                    ans*=x*y
                else:
                    [x,y]=[B.pop(0),B.pop(1)]
                    ans*=x*y
            print(ans%mod)
            exit()

Submission status: Runtime Error

Solution code:
n,k=map(int, input().split())
a = list(map(int, input().split()))
mod=10**9+7
if n==k:
    ans=1
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
minus=[i for i in a if i<0]
plus=[i for i in a if i>=0]

minus=sorted(minus)
plus=sorted(plus,reverse=True)
if k%2==1 and len(plus)==0:
    ans=1
    for i in range(k):
        ans*=abs(minus[-i-1])
        ans%=mod
    print((mod-ans)%mod)
    exit()

n_minus=len(minus)
n_plus=len(plus)

m_saiyo=0
for i in range(0, n_minus+1, 2): # i個minusから採用
    if i==0:
        continue
    if 0<=k-i<n_plus-1 and (minus[i-1]*minus[i-2])>=(plus[k-i]*plus[k-i+1]):
        m_saiyo=i
#print(m_saiyo)
ans=1

for i in range(m_saiyo):
    ans*=minus[i]
    ans%=mod
for i in range(k-m_saiyo):
    ans*=plus[i]
    ans%=mod

print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
MOD = 10**9+7
M = []
P = []
Z = []
for i in a:
    if i < 0:
        M.append(i)
    elif i > 0:
        P.append(i)
    else:
        Z.append(i)
P.sort(reverse=True)
M.sort()
lenZ = len(Z)
lenM = len(M)
lenP = len(P)
if n - k < lenZ:
    print(0)
    exit()
elif lenZ != 0 and n - k == lenZ and lenM % 2 == 1:
    print(0)
    exit()
elif n - k == lenZ:
    ans = 1
    for i in P:
        ans*=i
        ans%=MOD
    for i in M:
        ans*=i
        ans%=MOD
    if lenZ != 0 and lenM % 2 == 1: #必要ないと思うけど頭の中がこんがらがって居るので一応
        print(0)
        exit()
    print(ans)
    exit()
elif lenP == 0:
    M = M[::-1]
    ans = 1
    for i in range(k):
        ans*=M[i]
        ans%=MOD
    print(ans)
    exit()
count = 0
ans = []
i = 0
j = 0
if k % 2 == 1:
    ans.append(P[0])
    i+=1
    k-=1
    if k == 0:
        print(P[0])
        exit()
k //= 2
while count < k:
    if i+2>lenP:
        ans.append(M[j]*M[j+1])
        j+=2
        count+=1
        continue
    if j+2>lenM:
        ans.append(P[i]*P[i+1])
        i+=2
        count+=1
        continue
    p = P[i]*P[i+1]
    m = M[i]*M[i+1]
    if p > m:
        ans.append(p)
        i+=2
        count+=1
    else:
        ans.append(m)
        j+=2
        count+=1
intans = 1
for i in range(len(ans)):
    intans*=ans[i]
    intans%=MOD
print(intans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
S = []
for i in range(N):
    if A[i] > 0:
        p = i
        break
D = A[:p]
B = []
for i in D:
    B.append(i)
B.sort()
b = len(B)
C = A[p:]
for i in range(p):
    S.append(-A[i])
for i in range(p,N):
    S.append(A[i])
S.sort()
i = 0
while B:
    if S[i] == B[0]:
        S[i] = -S[i]
        B.pop(0)
    i += 1
def pow(a,b,mod):
    if b == 0:
        return 1
    else:
        if b % 2 == 0:
            return (pow(a,b//2,mod))**2%mod
        else:
            return (a*(pow(a,(b-1)//2,mod))**2)%mod
f = 0
p = 0
q = 0
mod = 10**9+7
ans = 1
for i in range(K):
    j = N - i - 1
    if S[j] < 0:
        q = S[j]
        f += 1
    else:
        p = S[j]
    ans *= max(S[j],-S[j])
    ans = ans % mod
r = 0
s = 0
for i in range(K,N):
    j = N - i - 1
    if S[j] < 0:
        r = min(S[j],r)
    else:
        s = max(S[j],s)
if N == K:
    print(ans)
    quit()
if b == N:
    print(ans)
    quit()
if f % 2 == 0:
    print(ans)
    quit()
if r*q > s*q:
    ans *= r
    ans %= mod
    d = pow(p,mod-2,mod)
    ans *= d
    ans %= mod
else:
    ans *= s
    ans %= mod
    d = -pow(-q,mod-2,mod)
    ans *= d
    ans %= mod
print(ans)

Submission status: Runtime Error

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

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

B=[]
C=[]
Z=[]

for a in A:
    if a>0:
        B.append(a)
    elif a<0:
        C.append(-a)
    else:
        Z.append(0)

B.sort(reverse=True)
C.sort(reverse=True)

if K==len(B)+len(C):
    ANS=1
    for b in B:
        ANS=ANS*b%mod
    for c in C:
        ANS=ANS*(-c)%mod

    if len(C)%2==1 and Z!=[]:
        print(0)
    else:
        print(ANS)
    sys.exit()

if K>len(B)+len(C):
    print(0)
    sys.exit()

if B==[]:
    if Z==[] and K%2==0:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
            
    elif Z==[] and K%2==1:
        C.reverse()
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(-ANS%mod)
        
    elif K%2==1:
        print(0)
    else:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod

    sys.exit()

if K<=len(B):
    S=1
    for i in range(K):
        S=S*B[i]%mod

    ind=0
    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

else:
    if (K-len(B))%2==0:
        S=1
        for i in range(len(B)):
            S=S*B[i]%mod

        for j in range(K-len(B)):
            S=S*C[j]%mod

        ind=K-len(B)

        while True:
            if ind+1<len(C) and len(B)-2-ind-ind>=0 and C[ind]*C[ind+1]>B[len(B)-1-ind]*B[len(B)-2-ind]:
                S=S*C[ind]*C[ind+1]*pow(B[len(B)-1-ind]*B[len(B)-2-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    else:
        S=1
        for i in range(len(B)-1):
            S=S*B[i]%mod

        for j in range(K-len(B)+1):
            S=S*C[j]%mod

        ind=K-len(B)+1
        

        while True:
            if ind+1<len(C) and len(B)-3-ind and C[ind]*C[ind+1]>B[len(B)-2-ind]*B[len(B)-3-ind]:
                S=S*C[ind]*C[ind+1]*pow(B[len(B)-2-ind]*B[len(B)-3-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    print(S%mod)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))[::-1]
mod=10**9+7
score=1

if K%2==1:  #これでKは偶数として扱えるようになった
    score*=A[0]
    A.pop(0)
    K-=1

print(A)

P,M=[],[]
for i in A:
    if i>0:
        P.append(i)
    else:
        M.append(i)

M=M[::-1]
t=0
p,m=0,0
while t<=K:
    if score<0:  #負であることが確定しているなら小さくなるようにする
        P=P[::-1]
        M=M[::-1]
    if t+2<=K:
        if 2*p+1<len(P) and 2*m+1<len(M):
            if P[2*p]*P[2*p+1] >= M[2*m]*M[2*m+1]:
                score*=P[2*p]*P[2*p+1]
                p+=1
                t+=2
            else:
                score*=M[2*m]*M[2*m+1]
                m+=1
                t+=2
        elif 2*p+1<len(P):
            score*=P[2*p]*P[2*p+1]
            p+=1
            t+=2
        else:
            score*=M[2*m]*M[2*m+1]
            m+=1
            t+=2
    elif t+1<=K:
        if 2*p<len(P):
            score*=P[2*p]
        else:
            score*=M[2*m]
        break
    else:
        break
    score%=mod

print(score%mod)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    if n == k:
        ans = a[0]
        for i in a[1:]:
            ans *= i
            ans %= mod
        print(ans)
        return
    mi = []
    ma = []
    a.sort()
    for ai in a:
        if ai <= 0:
            heappush(mi, ai)
        else:
            heappush(ma, -ai)
    X = []
    if not ma:
        ans = 1
        if k & 1:
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
        else:
            for i in range(k):
                ans *= a[i]
                ans %= mod
        print(ans)
        return
    while len(mi) >= 2:
        xx = heappop(mi)
        xy = heappop(mi)
        X.append(xx * xy)
    while len(ma) >= 2:
        xx = -heappop(ma)
        xy = -heappop(ma)
        X.append(xx * xy)
    X.sort()
    ans = 1
    for i in range(k // 2):
        ans *= X.pop()
        ans %= mod
    if k & 1:
        ans *= - heappop(ma)
        ans %= mod
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9+7
sei = []
hu = []
zero = []
for i in range(N):
    a = A[i]
    if a > 0:
        sei.append(a)
    elif a < 0:
        hu.append(a)
    else:
        zero.append(0)
sei.sort(reverse = True)
if len(zero) > N - K:
    print(0)
else:
    ans = 1
    p = len(sei)
    q = len(hu)
    if p == 0:
        hu.sort(reverse = True)
        for i in range(K):
            ans *= hu[i]
            ans %= MOD
        print(ans)
    elif q == 0:
        for i in range(K):
            ans *= sei[i]
            ans %= MOD
        print(ans)
    else:
        hu.sort()
        flag = 0
        pin = 0
        qin = 0
        r = K
        while r > 0:
            if pin == -1 and qin == -1:
                break
            elif pin == -1:
                qin += 1
                if qin == q:
                    qin = -1
                if flag == 1:
                    flag = 0
                else:
                    flag = 1
            elif qin == -1:
                pin += 1
                if pin == p:
                    pin = -1
            else:
                if abs(sei[pin])>abs(hu[qin]):
                    pin += 1
                    if pin == p:
                        pin = -1
                else:
                    qin += 1
                    if qin == q:
                        qin = -1
                    if flag == 0:
                        flag = 1
                    else:
                        flag = 0
            r -= 1
        if pin == -1:
            pin = p
        if qin == -1:
            qin = q
        if p+q == K:
            for i in range(p):
                ans *= sei[i]
                ans %= MOD
            for i in range(q):
                ans *= hu[q]
                ans %= MOD
            print(ans%MOD)
        else:
            if flag == 0:
                for i in range(pin):
                    ans *= sei[i]
                    ans %= MOD
                for j in range(qin):
                    ans *= hu[j]
                    ans %= MOD
                print(ans%MOD)
            else:
                if pin == p:
                    for i in range(pin-1):
                        ans *= sei[i]
                        ans %= MOD
                    for j in range(qin+1):
                        ans *= hu[j]
                        ans %= MOD
                    print(ans%MOD)
                else:
                    for i in range(pin+1):
                        ans *= sei[i]
                        ans %= MOD
                    for j in range(qin-1):
                        ans *= hu[j]
                        ans %= MOD
                    print(ans%MOD)

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9+7
a1 = []
a2 = []
cnt = 0
for i in a:
    if (i >= 0):
        a1.append(i)
    else:
        a2.append(-i)
a1.sort()
a2.sort()
#print(a1,a2)
if (n==k):
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
if (len(a1)==0):
    if (k%2==0):
        ans = 1
        for i in range(k):
            ans *= a2.pop()
            ans %= mod
        print(ans)
        exit()
    else:
        ans = 1
        for i in range(k):
            ans *= -a2[i]
            ans %= mod
        print(ans)
        exit()
elif (len(a2)==0):
    ans = 1
    for i in range(k):
        ans *= a1.pop()
        ans %= mod
    print(ans)
    exit()

bef1 = 0
bef2 = 0
ans = 1
for i in range(k):
    if (len(a1)==0):
        x = a2.pop()
        ans *= x
        ans %= mod
        cnt += 1
        continue
    if (len(a2)==0 or a1[-1]>=a2[-1]):
        x = a1.pop()
        ans *= x
        ans %= mod
        bef1 = x
    else:
        x = a2.pop()
        ans *= x
        ans %= mod
        cnt += 1
        bef2 = x
if (cnt%2==1):
    if len(a1)>0 and len(a2)>0:
        A = a1[-1]/bef2
        B = a2[-1]/bef1
        if (A>=B):
            ans *= a1[-1]
            ans *= pow(bef2,mod-2,mod)
            ans %= mod
        else:
            ans *= a2[-1]
            ans *= pow(bef1,mod-2,mod)
            ans %= mod
    elif (len(a1)==0):
        ans *= a2[-1]
        ans *= pow(bef1,mod-2,mod)
        ans %= mod
    else:
        ans *= a1[-1]
        ans *= pow(bef2,mod-2,mod)
        ans %= mod
    
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    A = sorted([int(x) for x in input().strip().split()])
    zeros = A.count(0)
    max_A = max(A)
    mod = 10 ** 9 + 7
    if max_A < 0:
        if K % 2:
            ans = 1
            for k in range(K):
                ans = (ans * A[-1-k]) % mod
            print(ans)
            return
        else:
            for k in range(K):
                ans = (ans * A[-1-k]) % mod
            print(ans)
            return
    elif max_A == 0:
        if A[-K] == 0:
            print(0)
            return
        else:
            if K % 2:
                ans = 1
                for k in range(K-K%2):
                    ans = (ans * A[k]) % mod
                print(ans)
                return
            else:
                for k in range(K):
                    ans = (ans * A[-1-k]) % mod
                print(ans)
                return
    else:
        if N - zeros < K:
            print(0)
            return
        elif N - zeros == K:
            if len([a for a in A if a < 0]) % 2:
                print(0)
                return
            else:
                ans = 1
                for a in A:
                    if a != 0:
                        ans = (ans * a) % mod
                print(ans)
                return
        ans = 1
        A.sort(key=lambda x: abs(x), reverse=True)
        minus = 0
        for k in range(K):
            if A[k] < 0:
                minus += 1
                minus_last = k
            ans = (ans * A[k]) % mod
        if minus % 2:
            for k in range(K):
                if k == minus_last:
                    continue
                ans = (ans * A[k]) % mod
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
li_a = list(map(int, input().split()))
mod = 10**9+7
li = []
lll = 0
for i in li_a:
    if i < 0:
        li.append((abs(i), -1))
        lll += 1
    else:
        li.append((i, 1))
li.sort()
if lll == n:
    ans = 1
    for i in range(k):
        ans *= -li[i][0]
        ans %= mod
    print(ans)
    exit()
ans = 1
guki = 1
for i in range(n-1, n-k-1, -1):
    ans *= li[i][0]
    ans %= mod
    guki *= li[i][1]
if guki > 0:
    print(ans)
else:
    P, M, p, m = 10**6, 1000000, 1000000, 1000000
    P1, M1, p1, m1 = True, True, True, True
    for i in range(n-k, n-1):
        if li[i][1] > 0:
            Plus = li[i][0]
            P = i
            P1 = False
            break
    for i in range(n-k, n-1):
        if li[i][1] < 0:
            Mini = li[i][0]
            M = i
            M1 = False
            break
    if n-k-1 >= 0:
        for i in range(n-k-1, -1, -1):
            if li[i][1] > 0:
                plus = li[i][0]
                p = i
                p1 = False
                break
        for i in range(n-k-1, -1, -1):
            if li[i][1] < 0:
                mini = li[i][0]
                m = i
                m1 = False
                break
    ans1 = 1
    ans2 = 1
    if (not P1) and (not m1):
        for i in range(n-1, n-k-1, -1):
            if i == P:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans1 *= li[m][0]
        ans1 %= mod
    if (not p1) and (not M1):
        for i in range(n-1, n-k-1, -1):
            if i == M:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans2 *= li[p][0]
        ans2 %= mod
    if p1 or P1 or M1 or m1:
        if mini/Plus > plus/Mini:
            print(ans1)
        else:
            print(ans2)
    else:
        ans = 1
        for i in range(k):
            ans *= -li[i][0]
            ans %= mod
        print(ans)

Submission status: Runtime Error

Solution code:
import heapq
from functools import reduce

MOD = 10**9+7
n, k = map(int, input().split())
a = list(map(int, input().split()))
plus = [i for i in a if i > 0]
plus.sort(reverse=True)
minus = [i for i in a if i < 0]
minus.sort(reverse=True)
zero = [i for i in a if i == 0]

res = 1
if len(plus) + len(minus) < k:
    res = 0
    print(res % MOD)
    exit()
if len(plus) + len(minus) == k:
    if len(minus) % 2 == 0:
        res = reduce(lambda a, b: a * b, plus, 1) * reduce(lambda a, b: a * b, minus, 1)
    else:
        res = 0
        print(res % MOD)
        exit()
elif len(minus) == 0:
    res = reduce(lambda a,b: a*b, plus[:k])
    print(res%MOD)
    exit()
elif len(plus) == 0:
    if k % 2 == 0:
        res = reduce(lambda a, b: a*b, minus[-k:])
        print(res%MOD)
        exit()
    else:
        if len(zero) > 0:
            res = 0
        else:
            res = reduce(lambda a,b: a*b, minus[:k])
        print(res%MOD)
        exit()
else:
    plus = [-i for i in plus]
    heapq.heapify(plus)
    heapq.heapify(minus)
    c_p = []
    c_m = []
    last_p = False
    while len(c_p)+len(c_m) < k:
        if len(plus) > 0:
            can_p = heapq.heappop(plus)
        else:
            can_p = 10**9+1
        if len(minus) > 0:
            can_m = heapq.heappop(minus)
        else:
            can_m = 10**9+1
        if can_p < can_m:
            heapq.heappush(c_p, -can_p)
            last_p = True
        else:
            heapq.heappush(c_m, -can_m)
            last_p = False
    if len(c_m) % 2 == 0:
        res = reduce(lambda a, b: a * b, c_p, 1) * reduce(lambda a, b: a * b, c_m, 1)
        print(res % MOD)
        exit()
    if last_p:
        # 最大の負を入れる/一番小さい負を除いて最大の正を入れる
        if len(minus) > 0:
            heapq.heappop(c_p)
            can_m = heapq.heappop(minus)
            heapq.heappush(c_m, -can_m)
        else:
            heapq.heappop(c_m)
            can_p = heapq.heappop(plus)
            heapq.heappush(c_p, -can_p)
    else:
        # 最大の正を入れる/一番小さい正を除いて最大の負を入れる
        if len(plus) > 0:
            heapq.heappop(c_m)
            can_p = heapq.heappop(plus)
            heapq.heappush(c_p, -can_p)
        else:
            heapq.heappop(c_p)
            can_m = heapq.heappop(minus)
            heapq.heappush(c_m, -can_m)
    res = reduce(lambda a, b: a * b, c_p, 1) * reduce(lambda a, b: a * b, c_m, 1)
    print(res % MOD)

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:
#!/usr/bin/env python
#pyrival orz
import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():
    n,k=map(int,input().split())
    a = [int(x) for x in input().split()]
    pv,nv,zr=[],[],[]
    for x in a:
        if x>0:
            pv.append(x)
        if x<0:
            nv.append(x)
        if x==0:
            zr.append(x)
    
    def posv(a,k):
        a.sort(lambda v:abs(v),reverse=True)
        ans=1
        nv=1
        for x in a:
            if k==0:
                break
            if x>0:
                ans=(ans*x)%mod
                k-=1
                continue
            if x<0:
                if nv>0 and k>1:
                    ans=(ans*nv*x)%mod
                    k-=2
                    nv=1
                else:
                    nv=x
        if k==0:
            return (ans,True)
    
    ans=posv(a,k)
    if ans[1]:
        print(ans[0])
        exit(0)
    
    if zr:
        print(0)
        exit(0)
    
    ans=1
    a=a[::-1]
    for x in a[:k]:
        ans=(ans*x)%mod
    print(ans)

# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

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

mod = 10**9 + 7

A = sorted(A, key=lambda x:-abs(x))

s = 1
ans = 1
for a in A[:K]:
  s *= np.sign(a)
  ans *= a
  ans %= mod
if s < 0:
  for a in A[K-1::-1]:
    if a > 0:
      x = a
  for b in A[K:]:
    if b < 0:
      y = b
  for c in A[K-1::-1]:
    if c < 0:
      z = c
  for d in A[K:]:
    if d > 0:
      w = d
  if b / a >= d / c:
    ans *= b
    ans %= mod
    ans *= pow(a, -1, mod=mod)
    ans %= mod
  else:
    ans *= d
    ans %= mod
    ans *= pow(c, -1, mod=mod)
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
class Solve:
    def __init__(self) -> None:
        self.n, self.k = map(int, input().split())
        self.a = list(map(int, input().split()))
        self.mod = 10 ** 9 + 7
        self.ans = -10 ** 20
        total = 1
        self.dfs(0, 0, True, total)
        self.dfs(0, 0, False, total)

        print(self.ans % self.mod)

    def mod_seki(self, x, y):
        # self.mod = 10 ** 7
        # return x * y % self.mod
        return x * y

    def dfs(self, idx, cnt, use, total):
        if cnt == self.k:
            self.ans = max(self.ans, total)
        elif idx < self.n:
            if use:
                total = self.mod_seki(total, self.a[idx])
                cnt += 1

            self.dfs(idx + 1, cnt, True, total)
            self.dfs(idx + 1, cnt, False, total)


def main():
    Solve()


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 = []
Z = []
for i in a:
    if i < 0:
        M.append(i)
    elif i > 0:
        P.append(i)
    else:
        Z.append(i)
P.sort(reverse=True)
M.sort()
lenZ = len(Z)
lenM = len(M)
lenP = len(P)
if n - k < lenZ:
    print(0)
    exit()
elif lenZ != 0 and n - k == lenZ and lenM % 2 == 1:
    print(0)
    exit()
elif n - k == lenZ:
    ans = 1
    for i in P:
        ans*=i
        ans%=MOD
    for i in M:
        ans*=i
        ans%=MOD
    if lenZ != 0 and len M % 2 == 1: #必要ないと思うけど頭の中がこんがらがって居るので一応
        print(0)
        exit()
    print(ans)
    exit()
elif lenP == 0:
    M = M[::-1]
    ans = 1
    for i in range(k):
        ans*=M[i]
        ans%=MOD
    print(ans)
    exit()
count = 0
ans = []
i = 0
j = 0
if k % 2 == 1:
    ans.append(P[0])
    i+=1
    k-=1
    if k == 0:
        print(P[0])
        exit()
k //= 2
while count < k:
    if i+2>lenP:
        ans.append(M[j]*M[j+1])
        j+=2
        count+=1
        continue
    if j+2>lenM:
        ans.append(P[i]*P[i+1])
        i+=2
        count+=1
        continue
    p = P[i]*P[i+1]
    m = M[i]*M[i+1]
    if p > m:
        ans.append(p)
        i+=2
        count+=1
    else:
        ans.append(m)
        j+=2
        count+=1
intans = 1
for i in range(len(ans)):
    intans*=ans[i]
    intans%=MOD
print(intans)

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)
    print(max(ans)%MOD)
else:
  als=sorted(ls, key=lambda x: -abs(x))
  mul=1
  for i in range(K):
    mul*=als[i]
  if mul>0:
    print(mul%MOD)
  else:
    ls2=als[:K]
    ls3=als[K:]
    ls2.sort()
    ls3.sort()
    ans=set()
    ans.add(mul*ls3[0]//ls2[-1])
    ans.add(mul*ls3[-1]//ls2[0])
    print(max(ans)%MOD)