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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)



@mt
def slv(N, K, A):
    pa = [a for a in A if a > 0]
    na = [-a for a in A if a < 0]
    if len(pa) + len(na) < K:
        return 0

    M = 10**9+7

    if len(pa) != 0 or K % 2 == 0:
        # positive
        pa.sort()
        na.sort()
        ans = 1
        if K % 2 == 1:
            ans *= pa.pop()
            K -= 1
        for _ in range(K//2):
            if len(pa) >= 2 and len(na) >= 2:
                if pa[-1] * pa[-2] > na[-1] * na[-2]:
                    ans *= pa[-1] * pa[-2]
                    pa.pop()
                    pa.pop()
                else:
                    ans *= na[-1] * na[-2]
                    na.pop()
                    na.pop()
            elif len(pa) >= 2:
                ans *= pa[-1] * pa[-2]
                pa.pop()
                pa.pop()
            else:
                ans *= na[-1] * na[-2]
                na.pop()
                na.pop()
            ans %= M

    else:
        # negative
        pa.sort(reverse=True)
        na.sort(reverse=True)
        ans = 1
        for _ in range(K):
            if pa and na:
                if pa < na:
                    ans *= pa[-1]
                    pa.pop()
                else:
                    ans *= -na[-1]
                    na.pop()
            elif pa:
                ans *= pa[-1]
                pa.pop()
            else:
                ans *= -na[-1]
                na.pop()
            ans %= M

    return ans


def main():
    N, K = read_int_n()
    A = read_int_n()
    print(slv(N, K, A))


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

plus = []
minus = []
zero = []
for i in range(n):
    if a[i] < 0:
        minus.append(abs(a[i]))
    elif a[i] > 0:
        plus.append(a[i])
    else:
        zero.append(0)


len_p = len(plus)
len_m = len(minus)
len_z = len(zero)

is_z = False
is_p = False
if len_z != 0:
    is_z = True

cnt = 2 * (len_m // 2) + len_p
if cnt >= k:
    is_p = True
if len_p == 0 and k % 2 == 1:
    is_p = False

if is_p:
    minus = sorted(minus, reverse=True)
    plus = sorted(plus, reverse=True)
    ans = 1
    if k % 2 == 1:
        k -= 1
        ans = plus[0]
        del plus[0]
    tmp = []
    for i in range(len(minus) // 2):
        tmp.append(minus[2 * i] * minus[2 * i + 1])
    for i in range(len(plus) // 2):
        tmp.append(plus[2 * i] * plus[2 * i + 1])
    tmp = sorted(tmp, reverse=True)
    for i in range(k // 2):
        ans *= tmp[i]
        ans %= MOD
    print(ans)
    exit()

elif is_z:
    print(0)
    exit()

else:
    minus = sorted(minus)
    ans = -1
    for i in range(k):
        ans *= minus[i]
        ans %= MOD
    print(ans)
    exit()

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)
        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 = []
        if len(mi) & 1:
            k -= 1
            L -= 1
            ans *= -heappop(ma)
        X = k - L
        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:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a_n=[]#aのうち負の数のlist
a_p=[]#aのうち正の数のlist
b=[]
z=0
for i in range(len(a)):
  if a[i]<=0:
    a_n.append(a[i])
  if a[-(i+1)]>=0:
    a_p.append(a[-(i+1)])
  else:
    z=z+1

if len(a_p)==0:
  ans=1
  for i in range(k):
    ans=(ans*a_n[i])%1000000007
else:
  ans=1
  j=0
  jn=0
  jp=0
  while j<k-2:
    if (jn>=len(a_n)-1):
      ans=(ans*a_p[jp])%1000000007
      jp=jp+1
      j=j+1
    elif (jp>=len(a_p)):
      ans=(ans*a_n[jn]*a_n[jn+1])%1000000007
      jn=jn+2
      j=j+2
    elif a_n[jn]*a_n[jn+1]>=a_p[jp]*a_p[jp+1]:
      ans=(ans*a_n[jn]*a_n[jn+1])%1000000007
      jn=jn+2
      j=j+2
    else:
      ans=(ans*a_p[jp])%1000000007
      jp=jp+1
      j=j+1
  if j==k-2:
    if(jp>=len(a_p)):
      ans=(ans*a_n[jn]*a_n[jn+1])%1000000007
    elif(jn>=len(a_n)):
      ans=(ans*a_p[jp]*a_p[jp+1])%1000000007
    else:
      ans=(ans*max(a_n[jn]*a_n[jn+1],a_p[jp]*a_p[jp+1]))%1000000007
  else:
    if(jp>=len(a_p)):
      ans=(ans*a_n[jn])%1000000007
    else:
      ans=(ans*a_p[jp])%1000000007

print(ans)

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7

n, k = map(int, input().split())
alst = list(map(int, input().split()))
alst.sort()

if alst[-1] <= 0:
    ans = 1 
    alst.sort(reverse = True)
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

blst = []
for num in alst:
    try:
        blst.append([abs(num), abs(num) // num])
    except ZeroDivisionError:
        blst.append([abs(num), 1])
blst.sort(reverse = True )
minus = 0
last_minus = 0
last_plus = 0
ans_lst = []
for i in range(k):
    if blst[i][1] == -1:
        minus += 1
        last_minus = blst[i][0]
    else:
        last_plus = blst[i][0]
    ans_lst.append(blst[i][0])

next_minus = 0
next_plus = 0

for i in range(k, n):
    if blst[i][1] == -1:
        next_minus = blst[i][0]
    else:
        next_plus = blst[i][0]

if minus % 2 == 0:
    ans = 1
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

else:
    minus_s = last_minus * next_minus
    plus_s = last_plus * next_plus
    ans = 1
    if minus_s > plus_s:
        ans_lst.remove(last_plus)
        ans_lst.append(next_minus)
    else:
        ans_lst.remove(last_minus)
        ans_lst.append(next_plus)
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
from itertools import combinations
import math
n,k=map(int,input().split())
a=list(map(int,input().split()))
x=combinations(a,k)
res=float("-inf")
mod=(10**9)+7
for i in x:
  res=max(res,math.prod(i))
print(res%mod)

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# import numpy as np
sys.setrecursionlimit(int(pow(10,6)))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("out.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

# @lru_cache(None)

t=1
# t=int(input())
for _ in range(t):
    n,k=L()
    A=L()
    A.sort()
    x=bl(A,0)
    y=br(A,0)
    neg=A[:x]
    pos=A[y:][::-1]
    if len(pos)==0:
        neg=neg[::-1]
        neg=[1]+neg
        for i in range(1,len(neg)):
            neg[i]*=neg[i-1]
        print(neg[k]%mod)
        exit()
    
    neg=[1]+neg
    for i in range(1,len(neg)):
        neg[i]*=neg[i-1]

    pos=[1]+pos
    for i in range(1,len(pos)):
        pos[i]*=pos[i-1]
    mx=neg[min(k,len(neg)-1)]
    for i in range(0,len(neg),2):
        if (k-i)>=0 and (k-i)<len(pos):
            curr=neg[i]*pos[(k-i)]
            mx=max(curr,mx)

    # print(mx)
    print(mx%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()))
    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()
        
    while(K>0):
        if len(A2n)>0 and A[0]*A[1]<A2n[0] and K>=2:
            ans=(ans*A2n[0])%MOD
            K-=2
            A2n.pop(0)
        else:
            ans=(ans*A[0])%MOD
            A.pop(0)
            K-=1
    print(ans)
            
    
    
if __name__=="__main__":
    main()

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
        for i in range(K, N):
            if A[i][1] < 0:
                a1 *= A[i][0]
        for i in range(K-1, -1, -1):
            if A[i][1] > 0:
                a1 /= A[i][0]
        a2 = 1
        for i in range(K, N):
            if A[i][1] > 0:
                a2 *= A[i][0]
        for i in range(K-1, -1, -1):
            if A[i][1] < 0:
                a2 /= A[i][0]

        if a1 > a2:
            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 A and B:
    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 A:
        S.append(-i)
if C:
    for i in A:
        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,mod))%mod
if K == N:
    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
        print(ans)

Submission status: Runtime Error

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

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

if len(M) + len(P) < K:
  print(0)
  exit()
elif len(M) + len(P) == K:
  ans = 1
  for i in M:
    ans = ans * i % MOD
  for i in P:
    ans = ans * i % MOD
  if len(M) % 2 == 1:
    ans *= -1
    ans += MOD
  print(ans)
  exit()

M.sort(reverse = True)
P.sort(reverse = True)

if len(P) == 0:
  ans = 1
  if K % 2 == 0:
    for i in range(K):
      ans = ans * M[i] % MOD
  else:
    for i in range(K):
      ans = ans * M[-1 -i] % MOD
    ans *= -1
    while ans < 0:
      ans += MOD
  print(ans)
else:
  x = 1 / 0
  ans = 1
  pn = 0
  mn = 0
  if K % 2 == 1:
    K -= 1
    ans *= P[0]
    pn = 1
  for i in range(K // 2):
    if pn + 2 > len(P):
      ans = ans * M[mn] * M[mn + 1] % MOD
      mn += 2
    elif mn + 2 > len(M):
      ans = ans * P[pn] * P[pn + 1] % MOD
      pn += 2
    else:
      p = P[pn] * P[pn + 1]
      m = M[mn] * M[mn + 1]
      if p > m:
        ans = ans * p % MOD
        pn += 2
      else:
        ans = ans * m % MOD
        mn += 2
  print(ans)

Submission status: Runtime Error

Solution code:
mod = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
canPositive = 0
Positive = 0
ans = 1
def inv(arg):
    return pow(arg,mod-2,mod)
for i in range(N):
    if A[i] >= 0:
        Positive += 1
if N - K >= 1 and Positive >= 1:
    canPositive = 1
if Positive == 0 and K % 2 == 0:
    canPositive = 1
anslist = []
if canPositive:
    A.sort(key=lambda x:abs(x),reverse=True)
    n = 0
    for a in A[:K]:
        anslist.append(a)
        if a < 0:
           n += 1
    if n % 2 == 1:
        minpos = 0
        minneg = 0
        maxpos = 0
        minneg = 0
        for i in anslist[::-1]:
            if i > 0:
                minpos = i
                break
        for i in anslist[::-1]:
            if i < 0:
                minneg = i
                break
        for i in A[K:]:
            if i < 0:
                maxneg = i
                break
        for i in A[K:]:
            if i > 0:
                maxpos = i
                break
        if abs(minpos*maxpos) > abs(maxneg*minneg):
            ans *= maxpos*inv(minneg)
        else:
            ans *= maxneg*inv(minpos)
else:
    A.sort(key=lambda x:abs(x))
    for a in A[:K]:
        anslist.append(a)
for i in anslist:
    ans *= i
    ans %= mod
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)
        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 = []
        if len(mi) & 1:
            k -= 1
            L -= 1
            ans *= -heappop(ma)
        X = k - len(mi)
        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:
#!/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)
        while len(ma) >= 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 = []
        if len(mi) & 1:
            k -= 1
            L -= 1
            ans *= -heappop(ma)
        X = k - len(mi)
        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:
            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:
MOD = 10 ** 9 + 7

n, k = map(int, input().split())
alst = list(map(int, input().split()))
alst.sort()

if alst[-1] <= 0:
    ans = 1 
    alst.sort(reverse = True)
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

blst = []
for num in alst:
    blst.append([abs(num), abs(num) // num])
blst.sort(reverse = True )
minus = 0
last_minus = 0
last_plus = 0
ans_lst = []
for i in range(k):
    if blst[i][1] == -1:
        minus += 1
        last_minus = blst[i][0]
    else:
        last_plus = blst[i][0]
    ans_lst.append(blst[i][0])

next_minus = 0
next_plus = 0

for i in range(k, n):
    if blst[i][1] == -1:
        next_minus = blst[i][0]
    else:
        next_plus = blst[i][0]

if minus % 2 == 0:
    ans = 1
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

else:
    minus_s = last_minus * next_minus
    plus_s = last_plus * next_plus
    print(last_minus, next_minus, last_plus, next_plus)
    ans = 1
    if minus_s > plus_s:
        ans_lst.remove(last_plus)
        ans_lst.append(next_minus)
    else:
        ans_lst.remove(last_minus)
        ans_lst.append(next_plus)
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
def examA():
    N = I()
    ans = (10000 - N)%1000
    print(ans)
    return

def examB():
    T = ["AC","WA","TLE","RE"]
    N = I()
    S = [SI()for _ in range(N)]

    ans = [0]*4
    for s in S:
        for i in range(4):
            if s==T[i]:
                ans[i] += 1
                break
    for i in range(4):
        print(T[i]+" x "+str(ans[i]))
    return

def examC():
    H, W, K = LI()
    C = [[""]*W for _ in range(H)]
    for h in range(H):
        S = SI()
        for w in range(W):
            C[h][w] = S[w]
    ans = 0
    #print(C)
    for hi in range(1<<H):
        nowC = deepcopy(C)
        for h in range(H):
            if hi&(1<<h):
                for i in range(W):
                    nowC[h][i] = "R"
        for wi in range(1 << W):
            nowCC = deepcopy(nowC)
            for w in range(W):
                if wi & (1 << w):
                    for i in range(H):
                        nowCC[i][w] = "R"
            cnt = 0
            for h in range(H):
                for w in range(W):
                    if nowCC[h][w] == "#":
                        cnt += 1
            if cnt == K:
                #print(hi, wi, nowCC)
                ans += 1
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    A.sort(reverse=True)
    ans = 0
    ans += A[0]
    cur = 0
    for i in range(2,N):
        if i%2==0:
            cur += 1
        ans += A[cur]
    print(ans)
    return

def examE():
    N, K = LI()
    A = LI()
    A_neg = []; neg = 0
    A_0 = []; num_0 = 0
    A_pos = []; pos = 0
    for a in A:
        if a<0:
            A_neg.append(-a)
            neg += 1
        elif a==0:
            A_0.append(a)
            num_0 += 1
        else:
            A_pos.append(a)
            pos += 1
    if N-num_0<K:
        print(0)
        return
    A_neg.sort()
    A_pos.sort()
    if pos==0:
        ans = 1
        if K%2==0:
            ans = 1
            for i in range(neg-K,neg):
                ans *= A_neg[i]
                ans %= mod
        else:
            for i in range(K):
                ans *= A_neg[i]
                ans %= mod
            ans = mod - ans
        print(ans)
        return

    if neg==0:
        ans = 1
        for i in range(pos - K, pos):
            ans *= A_pos[i]
            ans %= mod
        print(ans)
        return

    A_neg.sort(reverse=True)
    A_pos.sort(reverse=True)

    now_p = 0
    now_n = 0
    ans = 1
    if K%2==1:
        ans *= A_pos[now_p]
        now_p += 1

    while (now_n + now_p < K):
        if now_n + 1 >= neg:
            ans *= A_pos[now_p] * A_pos[now_p + 1]
            ans %= mod
            now_p += 2
            continue
        if now_p + 1 >= pos:
            ans *= A_neg[now_n] * A_neg[now_n + 1]
            ans %= mod
            now_n += 2
            continue

        if A_pos[now_p] * A_pos[now_p + 1] >= A_neg[now_n] * A_neg[now_n + 1]:
            ans *= A_pos[now_p] * A_pos[now_p + 1]
            ans %= mod
            now_p += 2
        else:
            ans *= A_neg[now_n] * A_neg[now_n + 1]
            ans %= mod
            now_n += 2

    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
6
8 7 6 5 4 3
"""

Submission status: Runtime Error

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
A.sort(key=lambda x: abs(x),reverse=True)
mod = 10**9+7
ans = 1
last_nega = 0
for i in range(K):
    if A[i] < 0:
        last_nega = i
    ans *= A[i]

if 0 < ans:
    print(ans%mod)
else:
    ans /= A[last_nega]
    for i in range(K,N):
        if 0 <= A[i]:
            ans *= A[i]
            break
    else:
        ans = 1
        for i in range(1,K+1):
            ans *= A[-i]
    print(ans%mod)