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()))
b,c,d = 0,0,0
mod = 10**9+7
B = []
C = []
D = []
for a in A:
    if a < 0:
        b += 1
        B.append(a)
    elif a == 0:
        c += 1
        C.append(a)
    else:
        d += 1
        D.append(a)
if B:
    B.sort()
if D:
    D.sort(reverse = True)
if K > b+d:
    print(0)
elif K == b+d and K< N and b%2 == 1:
    print(0)
elif K == N:
    ans = 1
    for i in range(N):
        ans = ans * A[i] % mod
    print(ans)
elif b == N and K % 2 == 1:
    ans = 1
    for i in range(1,K+1):
        ans = ans*B[-i]%mod
    print(ans)
else:
    bi = 0
    di = 0
    ans = 1
    while(K>1):
        if (bi >= b-1) or (di+1< d and D[di]*D[di+1] > B[bi]*B[bi+1]):
            ans = ans*D[di]%mod
            ans = ans*D[di+1]%mod
            di += 2
        else:
            ans = ans*B[bi]%mod
            ans = ans*B[bi+1]%mod
            bi += 2
        K -= 2
    if K == 1:
        ans = ans * D[di] % 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

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
for i in range(k):
    if flag:
        flag = 0
        continue
    if double:
        temp, ind = double.pop(0)
        if ind == 1:
            p.pop(0)
            p.pop(0)
        res = (res * temp) % mod
        flag = 1
    else:
        res = (res * p.pop(0)) % mod
print(res)

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)

res = 1
if 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:
        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 = []
    while len(c_p)+len(c_m) < k:
        can_p = heapq.heappop(plus)
        can_m = heapq.heappop(minus)
        if can_p < can_m:
            heapq.heappush(c_p, -can_p)
        else:
            heapq.heappush(c_m, -can_m)
    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 c_p[0] < c_m[0]:
        # 最大の負を入れる/一番小さい負を除いて最大の正を入れる
        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:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
pm = 1
ans = 1
odd = False
if k%2 == 1:
    odd = True
for i in range(n):
    if a[i] == 0: a.pop(i)

if len(a) < k:
    print(0)
    sys.exit()
ispop = False if len(a) == n else True
n = len(a)
a.sort()
if odd and a[n - 1] < 0:
    for i in range(k):
        ans = (ans * a[n - 1 - i])%mod
    print(ans%mod)
    sys.exit()
for i in range(k//2):
    p = a[n-1] * a[n-2]
    m = a[0] * a[1]
    if p >= m:
        ans = (ans * p)%mod
        a.pop(n - 1)
        a.pop(n - 2)
    else:
        ans = (ans * m)%mod
        a.pop(1)
        a.pop(0)
    n -= 2
if k%2 == 1:
    if a[n - 1] > 0:
        ans = (ans * a[n - 1])%mod
    else:
        if ispop:
            ans = 0
        else:
            ans = (ans * a[n - 1])%mod
print(ans%mod)

Submission status: Runtime Error

Solution code:
MOD = (10 ** 9) + 7
n, k  = map(int, input().split())
a = list(map(int, input().split()))

negs = [-x for x in a if x < 0]
non_negs = [x for x in a if x >= 0]

if len(non_negs) == 0 and k % 2 == 1:
    negs.sort()
    ans = 1
    for i in range(k):
        ans = ans * -negs[i] % MOD
    print(ans)
    exit()

negs_p, non_negs_p = 0, 0

negs.sort(reverse = True)
non_negs.sort(reverse = True)

for i in range(k):
    if negs_p == len(negs):
        non_negs_p += 1
    elif non_negs_p == len(non_negs):
        negs_p += 1
    elif negs[negs_p] > non_negs[non_negs_p]:
        negs_p += 1
    else:
        non_negs_p += 1

if negs_p % 2 == 0 or k == n:
    ans = 1
    for i in range(negs_p):
        ans = ans * -negs[i] % MOD
    for i in range(non_negs_p):
        ans = ans * non_negs[i] % MOD
    print(ans)
    exit()

if negs_p == len(negs) or non_negs_p == 0:
    negs_p -= 1
    non_negs_p += 1
    ans = 1
    for i in range(negs_p):
        ans = ans * -negs[i] % MOD
    for i in range(non_negs_p):
        ans = ans * non_negs[i] % MOD
    print(ans)
    exit()

if non_negs_p == len(non_negs) or negs_p == 0:
    negs_p += 1
    non_negs_p -= 1
    ans = 1
    for i in range(negs_p):
        ans = ans * -negs[i] % MOD
    for i in range(non_negs_p):
        ans = ans * non_negs[i] % MOD
    print(ans)
    exit()


a = negs[negs_p - 1]
b = negs[negs_p]
c = non_negs[non_negs_p - 1]
d = non_negs[non_negs_p]

if a * b > c * d:
    negs_p += 1
    non_negs_p -= 1
else:
    negs_p -= 1
    non_negs_p += 1

negs_p += 1
non_negs_p -= 1
ans = 1
for i in range(negs_p):
    ans = ans * -negs[i] % MOD
for i in range(non_negs_p):
    ans = ans * non_negs[i] % MOD
print(ans)

Submission status: Runtime Error

Solution code:
from math import log2
from itertools import accumulate

epsilon = 10 ** -5

MOD = 10 ** 9 + 7

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

negs = []
poss = []
for A in As:
    if A > 0:
        poss.append(A)
    elif A < 0:
        negs.append(-A)

poss.sort(reverse = True)
negs.sort(reverse = True)

if len(poss) + len(negs) < K:
    print(0)
    exit()

if len(poss) == 0:
    if N > len(negs):
        if K % 2 == 1:
            print(0)
        else:
            ans = 1
            for n in negs[:K]:
                ans *= n
                ans %= MOD
            print(ans)
    else:
        if K % 2 == 1:
            ans = 1
            for n in negs[-K:]:
                ans *= n
                ans %= MOD
            print(-ans%MOD)
        else:
            ans = 1
            for n in negs[:K]:
                ans *= n
                ans %= MOD
            print(ans)
    exit()

if K == N:
    ans = 1
    for A in As:
        ans *= A
        ans %= MOD
    print(ans)



def mulmod(a, b):
    return a * b % MOD

logs_poss = [0.0] + [log2(p) for p in poss] 
logs_poss_csum = list(accumulate(logs_poss))

poss_mod_csum = [1] + list(accumulate(poss, mulmod))

logs_negs = [0.0] + [log2(n) for n in negs] 
logs_negs_csum = list(accumulate(logs_negs))

negs_mod_csum = [1] + list(accumulate(negs, mulmod))

max_log = -1
for minus in range(0, K+1, 2):
    plus = K - minus
    if plus <= len(poss) and minus <= len(negs):
        if max_log + epsilon < logs_poss_csum[plus] + logs_negs_csum[minus]:
            max_log = logs_poss_csum[plus] + logs_negs_csum[minus]
            max_mod = poss_mod_csum[plus] * negs_mod_csum[minus] % MOD
        elif max_log <= logs_poss_csum[plus] + logs_negs_csum[minus]:
            mod = poss_mod_csum[plus] * negs_mod_csum[minus] % MOD
            if mod > max_mod:
                max_log = logs_poss_csum[plus] + logs_negs_csum[minus]
                max_mod = poss_mod_csum[plus] * negs_mod_csum[minus] % MOD

print(max_mod)

Submission status: Runtime Error

Solution code:
#

import sys
input=sys.stdin.readline
MOD=10**9+7


def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    if N==1:
        print(A[0])
        exit()
    A.sort()
    A2n=[]
    for i in range(0,N,2):
        if A[i]<=0 and A[i+1]<=0:
            A2n.append(A[i]*A[i+1])
        else:
            break

    A.sort(reverse=True)
    ans=1
    if A[0]<=0 and K%2==1:
        for i in range(K):
            ans=(ans*A[i])%MOD
        print(ans)
        exit()
    ni=0
    i=0
    while(K>0):
        if len(A2n)-ni>0 and A[i]*A[i+1]<A2n[ni] and K>=2:
            ans=(ans*A2n[ni])%MOD
            K-=2
            ni+=1
        else:
            ans=(ans*A[i])%MOD
            i+=1
            K-=1
    print(ans)
            
    
    
if __name__=="__main__":
    main()

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:
                ans *= hu[qin]
                if r != 1:
                    ans %= MOD
                qin += 1
                flag = abs(flag-1)
            elif qin == -1:
                ans *= sei[pin]
                if r != 1:
                    ans %= MOD
                pin += 1
            else:
                if abs(sei[pin])>abs(hu[qin]):
                    ans *= sei[pin]
                    if r != 1:
                        ans %= MOD
                    pin += 1
                    if pin == p:
                        pin = -1
                else:
                    ans *= hu[qin]
                    if r != 1:
                        ans %= MOD
                    qin += 1
                    if qin == q:
                        qin = -1
                    flag = abs(flag-1)
            r -= 1
        if p+q == K:
            print(ans%MOD)
        else:
            if flag == 0:
                print(ans%MOD)
            else:
                ans /= q[qin-1]
                ans *= p[pin]
                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

def mod_inverse(a, p):
    mod = 1
    p_bin = bin(p-2)
    for i in range(len(p_bin) - 1, 1, -1):
        if i == len(p_bin) - 1:
            mul = a
            mul %= p
            mod *= (mul ** int(p_bin[i]))
            mod %= p
        else:
            mul = mul ** 2
            mul %= p
            mod *= (mul ** int(p_bin[i]))
            mod %= p
    return mod

a2 = [[abs(a[i]), abs(a[i]) // a[i]] for i in range(n)]
a2.sort(reverse = True)
ans = 1
count_m = 0
count_p = 0
max_p = float("inf")
max_m = -float("inf")
for i in range(k):
    ans *= a2[i][0]
    ans %= mod
    if a2[i][1] == -1:
        count_m += 1
        max_m = a2[i][0]
    else:
        count_p += 1
        max_p = a2[i][0]
if count_m % 2 == 0:
    print(ans)
else:
    num = k
    while num < n:
        temp = a2[num][1]
        if temp == -1:
            if max_p != float("inf"):
                ans *= mod_inverse(max_p, mod)
                ans %= mod
                ans *= a2[num][0]
                ans %= mod
                print(ans)
                break
            else:
                num += 1
        else:
            if max_m != -float("inf"):
                ans *= mod_inverse(max_m, mod)
                ans %= mod
                ans *= a2[num][0]
                ans %= mod
                print(ans)
                break
            else:
                num += 1
    else:
        a2.sort()
        ans = -1
        for i in range(k):
            ans *= a2[i][0]
            ans %= mod
        print(ans)

Submission status: Runtime Error

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

def solve():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    P = 10**9 + 7
    def mod_prod(a,b):
        return (a % P) * (b % P) % P

    def mod_fact(a):
        ret = 1
        for i in range(a):
            ret = ret * (i + 1) % P
        return ret

    def mod_pow(a, n):
        ret = 1
        while n > 0:
            if n % 2 == 1:
                ret = ret * a % P
            a = a * a % P
            n = n >> 1
        return ret

    def mod_div(a, b):
        b_inv = mod_pow(b, P - 2)
        return a * b_inv % P

    def mod_comb(a,b):
        ret = 1
        b = min(b, a - b)
        for i in range(b):
            ret *= a - i
            ret %= P
        ret = mod_div(ret, mod_fact(b))
        return ret

    A.sort(key=lambda x:-abs(x))

    topK = A[:K]
    rest = A[K:]

    if sum(1 if a < 0 else 0 for a in topK) % 2 == 0:
        ans = 1
        for a in topK:
            ans *= a
            ans %= P
        print(ans)
    else:
        ans1 = 0
        rest_negs = [a for a in rest if a < 0]
        topk_poss = [a for a in topK if a >= 0]
        if len(rest_negs) > 0 and len(topk_poss) > 0:
            ans1 = 1
            for a in topK:
                ans1 *= a
                ans1 %= P
            ans1 = mod_div(ans1, min(topk_poss))
            ans1 = ans1 * min(rest_negs) % P
        else:
            pass

        rest_poss = [a for a in rest if a >= 0]
        topk_negs = [a for a in topK if a < 0]
        if len(rest_poss) > 0 and len(topk_negs) > 0:
            ans2 = 1
            for a in topK:
                ans2 = ans2 * a % P
            ans2 = mod_div(ans1, max(topk_negs))
            ans2 = ans2 * max(rest_poss) % P

        print(max(ans1, ans2))

solve()

Submission status: Runtime Error

Solution code:
vN,K = map(int,input().split())
A = list(map(int,input().split()))
b,c,d = 0,0,0
mod = 10**9+7
B = []
C = []
D = []
for a in A:
    if a < 0:
        b += 1
        B.append(a)
    elif a == 0:
        c += 1
        C.append(a)
    else:
        d += 1
        D.append(a)
if B:
    B.sort()
if D:
    D.sort(reverse = True)
if K > b+d:
    print(0)
elif K == b+d and K< N and b%2 == 1:
    print(0)
elif K == N:
    ans = 1
    for i in range(N):
        ans = ans * A[i] % mod
    print(ans)
elif b == N and K % 2 == 1:
    ans = 1
    for i in range(1,K+1):
        ans = ans*B[-i]%mod
    print(ans)
else:
    bi = 0
    di = 0
    ans = 1
    while(K>1):
        if (bi >= b-1) or (di+1< d and D[di]*D[di+1] > B[bi]*B[bi+1]):
            ans = ans*D[di]%mod
            ans = ans*D[di+1]%mod
            di += 2
        else:
            ans = ans*B[bi]%mod
            ans = ans*B[bi+1]%mod
            bi += 2
        K -= 2
    if K == 1:
        ans = ans * D[di] % mod
    print(ans)

Submission status: Runtime Error

Solution code:
def inv_mod(a, p=10**9+7):
    p = abs(p)
    a %= p
    stack = []
    p0 = p
    while a > 1:
        d, a, p = p//a, p%a, a
        stack.append(d)
    x, y = 1, 0
    while stack:
        d = stack.pop()
        x, y = y-d*x, x
    return x % p0
MOD = 10**9 + 7
inpl = lambda: list(map(int,input().split()))
N, K = inpl()
A = inpl()
if K % 2:
    A.sort(reverse=True)
    if A[0] < 0:
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD
        print(ans)
        exit()
    elif A[0] == 0:
        print(0)
        exit()

A.sort(key=abs, reverse=True)
lastplus = None
lastminus = None
ans = 1
sign = 1
for i in range(K):
    ans *= A[i]
    ans %= MOD
    if A[i] > 0:
        lastplus = i
    elif A[i] < 0:
        lastminus = i
        sign *= -1
    else:
        print(0)
        exit()
if sign == 1:
    print(ans)
else:
    firstplus = firstminus = N
    for i in range(K,N):
        if A[i] > 0 and firstplus > i:
            firstplus = i
            if firstminus < N:
                break
        elif A[i] < 0 and firstminus > i:
            firstminus = i
            if firstplus < N:
                break
        else:
            break
    if lastplus and firstminus < N:
        ac = abs(A[lastplus]*A[firstminus])
    else:
        ac = -1
    if firstplus and lastminus < N:
        bd = abs(A[firstplus]*A[lastminus])
    else:
        bd = -1
    if bd >= ac:
        ans *= inv_mod(A[lastplus]) * A[firstminus] * (-1)
    else:
        ans *= inv_mod(A[lastminus]) * A[firstplus] * (-1)
    ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
aplus = []
aminus = []
for x in a:
  if x >= 0:
    aplus.append(x)
  else:
    aminus.append(x)
aplus = sorted(aplus, reverse=True)
aminus = sorted(aminus)
if k % 2 == 1 and len(aplus) == 0:
  ans = 1
  for i in range(k):
    ans *= aminus[-(i + 1)]
    ans %= mod
  print(ans)
  exit()
ans = 1
l = min(k, len(aminus))
lminus = l // 2 * 2
for i in range(lminus):
  ans *= aminus[i]
  ans %= mod
for i in range(k - lminus):
  ans *= aplus[i]
  ans %= mod
if ans == 0:
  print(ans)
  exit()
for i in range(lminus - 2, -1, -2):
  if k - i - 2 < 0 or aminus[i] * aminus[i + 1] >= aplus[k - i - 1] * aplus[k - i - 2]:
    break
  ans *= pow(aminus[i] * aminus[i + 1], mod - 2)
  ans *= aplus[k - i - 1] * aplus[k - i - 2]
  ans %= mod
print(ans)

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 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=0
while(l+2<=n and l+2<=K):
    if Minus[l]*Minus[l+1]<Plus[K-l-1]*Plus[K-l-2]:
        break
    l+=2
ans=1
for i in range(l):
    ans=ans*Minus[i]
    ans%=mod
for i in range(K-l):
    ans=ans*Plus[i]
    ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

mod = 10**9+7

cp = 0
cm = 0
for i in range(N):
    n = 1
    if A[i] < 0:
        n = -1
    elif A[i] == 0:
        n = 0
    A[i] = (abs(A[i]), n)
    if n > 0:
        cp += 1
    elif n < 0:
        cm += 1

if K > cp+cm:
    ans = 0
elif (cp == 0 and K%2 == 1) or (K == N and cm % 2 == 1):
    if N > cp+cm:
        ans = 0
    else:
        A.sort()
        ans = 1
        for i in range(K):
            ans *= A[i][0]
            ans %= mod
        ans *= -1
        ans %= mod
else:
    A.sort(reverse=True)
    cnt = 0
    ans = 1
    for i in range(K):
        ans *= A[i][0]
        ans %= mod
        if A[i][1] < 0:
            cnt += 1

    if cnt % 2 == 1:
        a1 = 1
        f11 = False
        f12 = False
        for i in range(K, N):
            if A[i][1] < 0:
                a1 *= A[i][0]
                f11 = True
        for i in range(K-1, -1, -1):
            if A[i][1] > 0:
                a1 /= A[i][0]
                f12 = True
        a2 = 1
        f21 = False
        f22 = False
        for i in range(K, N):
            if A[i][1] > 0:
                a2 *= A[i][0]
                f21 = True
        for i in range(K-1, -1, -1):
            if A[i][1] < 0:
                a2 /= A[i][0]
                f22 = True

        if a1 > a2 and f11 and f12 and f21 and f22:
            for i in range(K, N):
                if A[i][1] < 0:
                    ans *= A[i][0]
                    ans %= mod
            for i in range(K-1, -1, -1):
                if A[i][1] > 0:
                    ans *= pow(A[i][0], mod-2, mod)
                    ans %= mod
        elif f11 and f12 and f21 and f22:
            for i in range(K, N):
                if A[i][1] > 0:
                    ans *= A[i][0]
                    ans %= mod
            for i in range(K-1, -1, -1):
                if A[i][1] < 0:
                    ans *= pow(A[i][0], mod-2, mod)
                    ans %= mod
        elif f11 and f12:
            for i in range(K, N):
                if A[i][1] < 0:
                    ans *= A[i][0]
                    ans %= mod
            for i in range(K-1, -1, -1):
                if A[i][1] > 0:
                    ans *= pow(A[i][0], mod-2, mod)
                    ans %= mod
        else:
            for i in range(K, N):
                if A[i][1] > 0:
                    ans *= A[i][0]
                    ans %= mod
            for i in range(K-1, -1, -1):
                if A[i][1] < 0:
                    ans *= pow(A[i][0], mod-2, mod)
                    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
B = []
C = []
for i in range(N):
    a = A[i]
    if a < 0:
        b = -a
        B.append(b)
    else:
        b = a
        C.append(a)
S = []
while B and C:
    a = B[0]
    b = C[0]
    p = 0
    if a <= b:
        S.append(-a)
        B.pop(0)
    else:
        S.append(b)
        C.pop(0)
if B:
    for i in B:
        S.append(-i)
if C:
    for i in C:
        S.append(i)
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)
        
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
if K == N:
    if f < 0:
        ans = mod - ans
    print(ans)
if K != N:
    if f % 2 == 0:
        print(ans)
    else:
        ans1 *= r
        ans1 = ans1 % mod
        d = pow(p,mod-2,mod)
        ans1 *= d
        ans1 = ans2 % mod
        ans2 *= s
        ans2 = ans2 % mod
        d = pow(q,mod-2,mod)
        ans2 *= d
        ans2 = ans2 % mod
        if r*q > s*q:
            ans = ans1
        else:
            ans = ans2
        if s == 0:
            ans = mod - ans
        print(ans)

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)
    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
    if len(mi) >= k:
        ans = 1
        A = []
        if k & 1:
            k -= 1
            ans *= -heappop(ma)
        for _ in range(k):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        return
        while len(ma) >= 2 and len(A) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            if g1 * g2 < h1 * h2:
                print(ans)
                return
            ans *= pow(h1 * h2, mod - 2, mod)
            ans %= mod
            ans *= g1 * g2
            ans %= mod
        print(ans)
    else:
        L = len(mi)
        A = []
        X = k - L
        if len(mi) & 1:
            L -= 1
            X -= 1
            ans *= -heappop(ma)
        for i in range(L):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        for i in range(X):
            x = -heappop(ma)
            ans *= x
            ans %= mod
        while len(ma) >= 2 and len(A) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            if g1 * g2 < h1 * h2:
                print(ans)
                return
            ans *= pow(h1 * h2, mod - 2, mod)
            ans %= mod
            ans *= g1 * g2
            ans %= mod
        print(ans)
    return


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

Submission status: Runtime Error

Solution code:
import math

n,m = input().split()
n=(int)(n)
m=(int)(m)
x = [int(x) for x in input().split(" ")]
mp=1
for i in range(0,m):
    mp*=x[i]
pp=mp
l=n-m+1
for i in range(1,l):
    cp=(pp/x[i-1])*x[i+m-1]
    mp=max(mp,cp)
    pp=cp
l=mp;
M=1e9+7
if(l<0):
    r=l*(-1)
    r=math.ceil(r/M)
    l+=r*M
l%=M;
l=(int)(l)
print(l)

Submission status: Runtime Error

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    A=LI()
    Lp=[]
    Lm=[]
    Lz=[]
    for i in range(N):
        if A[i]==0:
            Lz.append(0)
        elif A[i]>0:
            Lp.append(A[i])
        else:
            Lm.append(A[i])
            
    Lp.sort(reverse=True)
    Lm.sort()
    
    Np=len(Lp)
    Nm=len(Lm)
    
    if len(Lp)+len(Lm)<K:#どうしても0が入る
        print(0)
        exit()
    if K==1:
        print(max(A))
        exit()
    if max(A)<0:#全部負
        if K%2==0:
            A.sort()
        else:
            A.sort(reverse=True)
        ans=1
        for i in range(K):
            ans=(ans*A[i])%mod
        print(ans)
        exit()
    
    Lp.append(0)
    Lp.append(0)
    Lm.append(0)
    Lm.append(0)
    nowp=0
    nowm=0
    
    ans=1
    if K%2==0:
        for i in range(K//2):
            a=Lp[nowp]*Lp[nowp+1]
            b=Lm[nowm]*Lm[nowm+1]
            if a>=b:
                ans=(ans*a)%mod
                nowp+=2
            else:
                ans=(ans*b)%mod
                nowm+=2
    else:
        ans=Lp[0]
        nowp+=1
        for i in range(K//2):
            a=Lp[nowp]*Lp[nowp+1]
            b=Lm[nowm]*Lm[nowm+1]
            if a>=b:
                ans=(ans*a)%mod
                nowp+=2
            else:
                ans=(ans*b)%mod
                nowm+=2
    print(ans)
        
            

        
 
    
            
            

main()