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:
from collections import Counter, deque

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

MOD = 10 ** 9 + 7

c = Counter()
for a in A:
    if a == 0:
        c['0'] += 1
    elif a < 0:
        c['-'] += 1
    else:
        c['+'] += 1

if c['-'] + c['+'] < K:
    print(0)
elif (c['-'] == N and K % 2 == 1) or (N == K and c['-'] % 2 == 1):
    def f(x):
        if x == 0:
            return 10 ** 9
        else:
            return abs(x)


    A = sorted(A, key=f)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD

    print(ans)
else:
    A = sorted(A, key=lambda x: abs(x), reverse=True)
    plus = deque()
    minus = deque()

    for i in range(K):
        if A[i] >= 0:
            plus.append(A[i])
        else:
            minus.append(A[i])

    if len(minus) % 2 == 1:
        p = None
        m = None
        for i in range(K, N):
            if A[i] >= 0 and p is None:
                p = A[i]
            if A[i] < 0 and m is None:
                m = A[i]
            if p is not None and m is not None:
                break
        if m is None and p is not None:
            minus.pop()
            plus.append(p)
        if m is not None and p is None:
            plus.pop()
            minus.append(m)
        elif minus[-1] * m > plus[-1] * p:
            plus.pop()
            minus.append(m)
        else:
            minus.pop()
            plus.append(p)

    ans = 1
    while plus:
        ans *= plus.popleft()
        ans %= MOD
    while minus:
        ans *= minus.popleft()
        ans %= MOD

    print(ans)

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
a.sort()
cnt = 0
if n > k:
    for x in a:
        if x < 0: cnt += 1
        if cnt%2 == 0:
            a.pop(cnt - 1)
            n -= 1

if k%2 == 1 and a[n - 1] < 0:
    if 0 in a:
        print(0)
        sys.exit()
    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:
    ans = (ans * a[n - 1])%mod
print(ans%mod)

Submission status: Runtime Error

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

if N - A.count(0) < K:
    print(0)
    exit(0)

plus = []
minus = []
for a in A:
    if a >= 0:
        plus.append(a)
    else:
        minus.append(a)

plus.sort()
lenMinus = len(minus)

if K % 2 == 1 and len(plus) == 0:
    minus.sort(reverse=True)
    ans = 1
    for i in range(K):
        ans *= minus[i]
        ans %= MOD
    print(ans)
    exit(0)

minus.sort()

i = 0
j = 0

ans = 1
if K % 2 == 1:
    ans = plus[0]
    K -= 1
    plus = plus[1:]

for _ in range(K//2):
    if i+1 >= len(plus):
        ans *= (minus[j] * minus[j+1])
        ans %= MOD
        j += 2
        continue
    elif j+1 >= len(minus):
        ans *= (plus[i] * plus[i+1])
        ans %= MOD
        i += 2
        continue

    a = plus[i] * plus[i+1]
    b = minus[j] * minus[j+1]
    if a > b:
        ans *= a
        i += 2
    else:
        ans *= b
        j += 2
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

N,K = map(int,input().split())
a_list = list(map(int,input().split()))
a_list.sort()
b_list = a_list[-K:]

n_negative = bisect_left(a_list,0)

max_pair_num = min(n_negative//2, K//2)


# 負の数からiペア取る
n_product = 1
p_product = 1
for i in range(K):
    p_product*= b_list[i]

ans = p_product
for i in range(1,max_pair_num+1):
    n_product *= a_list[i*2-2]
    n_product *= a_list[i*2-1]

    p_product /= b_list[i*2-2]
    p_product /= b_list[i*2-1]

    if n_product*p_product>ans:
        ans = n_product*p_product

print(int(ans%1_000_000_007))

Submission status: Runtime Error

Solution code:

def inverse(a): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

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

B = []
zero = 0
pl = 0
mi = 0
for i in A:
    if i == 0:
        zero += 1
    else:
        B.append( ( abs(i) , i // abs(i) ) )
        if i < 0:
            mi += 1
        else:
            pl += 1

last_pl = None

B.sort()
B.reverse()
mod = 10**9+7

if N - zero < K:
    print (0)
    sys.exit()

if pl == 0:

    if K % 2 == 0:
        now = 1
        for i in range(K):
            now *= B[i][0]
            now = mod
        print (now % mod)
        sys.exit()
    else:
        now = 1
        if zero > 0:
            print (0)
            sys.exit()
        
        for i in range(K):
            now *= B[N-i-1][0] * B[N-i-1][1]
            now %= mod
        print (now % mod)
        sys.exit()


lasp = None
lasm = None

now = 1
for i in range(K):
    now *= B[i][0] * B[i][1]

    if now >= 0:
        now %= mod
    else:
        now = now % mod - mod

    if B[i][1] > 0:
        lasp = B[i][0]
    else:
        lasm = -1 * B[i][0]

if now > 0:
    print (now % mod)
    sys.exit()

else:

    a2 = ans * inverse(lasp)
    change2 = 1 / lasp
    for i in range(K+1,len(B)):
        if B[i][1] > 0:
            a2 *= B[i][0]
            change2 *= B[i][0]
            break
    else:
        change2 = float("-inf")

    a3 = ans * inverse(lasm % mod)
    change3 = 1 / lasm
    for i in range(K+1,len(B)):
        if B[i][1] < 0:
            a3 *= -1 * B[i][0]
            change3 *= -1 * B[i][0]
            break
    else:
        change3 = float("-inf")

    if change2 > change3:
        print (a2 % mod)
    else:
        print (a3 % mod)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)
MOD = 10 ** 9 + 7

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, K = ZZ()
    A = ZZ()
    p = []
    z = []
    m = []
    for a in A:
        if a > 0: p.append(a)
        elif a == 0: z.append(a)
        else: m.append(a)

    if len(p) == 0 and len(z) == 0 and K%2 == 1: #答えが負
        m = sort(m)[::-1]
        ans = 1
        for i in range(K):
            ans *= m[i]
            ans %= MOD
        print(ans)
        return
    else:
        if K - len(p) - len(m) > 0:
            print(0)
            return
        else:
            p.sort(reverse=True)
            m.sort()
            ans = 1
            itr = itrp = 0
            while K > 0:
                if itr+1 < len(m): c1 = (m[itr] * m[itr+1])
                else: c1 = -1
                if itrp+1 < len(p): c2 = (p[itrp] * p[itrp+1])
                else: c2 = p[itrp]

                if c1 > c2 and K >= 2:
                    ans *= c1
                    ans %= MOD
                    itr += 2
                    K -= 2
                else:
                    ans *= c2
                    ans %= MOD
                    itrp += 1
                    K -= 1
            print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
def add(x,y): return x+y
arr = list(map(int,input().split()))
arr.sort()
print(reduce(add,arr[1:]))

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
a.sort()
cnt = 0
if n > k:
    for x in a:
        if a < 0: cnt += 1
        if cnt%2 == 0:
            a.pop(cnt - 1)
            n -= 1

if k%2 == 1 and a[n - 1] < 0:
    if 0 in a:
        print(0)
        sys.exit()
    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:
    ans = (ans * a[n - 1])%mod
print(ans%mod)

Submission status: Runtime Error

Solution code:
#                          JAI SHREE RAM

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

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

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

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

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







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

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a_list = sorted(map(int, input().split()),reverse=True)

l_minus = sorted([i for i in a_list if i < 0])
l_plus =  sorted([i for i in a_list if i > 0],reverse=True)
l_zero = [i for i in a_list if i == 0]

# マイナスは2個セットで選びたい
# 最大化問題か最小か問題かを知りたい
# マイナスを奇数個選ばないといけないのが辛い時
_min = False
if (k - len(l_plus)) % 2 == 1:
  _min = True
  # 最悪
cnt = 0
ans = 1
if _min == False:
  while 1:
    if cnt == k:
      break
    if k - cnt >= 2 and len(l_minus) >= 2 and len(l_plus) >= 2:
      a = l_minus[0] * l_minus[1]
      b = l_plus[0] * l_plus[1]
      if a >= b:
        l_minus.pop(0)
        l_minus.pop(0)
        ans *= a
      else:
        l_plus.pop(0)
        l_plus.pop(0)
        ans *= b
      cnt += 2
    else:
      cnt += 1
      ans *= l_plus.pop(0)
else:
  if len(l_zero) > 0:
    ans = 0
  else:
    l_minus = sorted(l_minus, reverse=True)
    l_plus =  sorted(l_plus)
    while 1:
      if cnt == k:
        break
      if k - cnt >= 2 and len(l_minus) >= 2 and len(l_plus) >= 2:
        a = l_minus[0] * l_minus[1]
        b = l_plus[0] * l_plus[1]
        if a >= b:
          l_minus.pop(0)
          l_minus.pop(0)
          ans *= a
        else:
          l_plus.pop(0)
          l_plus.pop(0)
          ans *= b
        cnt += 2
      else:
        cnt += 1
        ans *= l_minus.pop(0)
        
print(ans % (pow(10,9) + 7))

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
    t = 0
    while X:
        ans *= X.pop()
        ans %= mod
        t += 2
        if t >= k - 1: break
    if t == k:
        print(ans)
    else:
        ans *= - heappop(ma)
        ans %= mod
        print(ans)
    return


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

Submission status: Runtime Error

Solution code:
#create date: 2020-07-05 21:39

import sys
stdin = sys.stdin
mod = 10**9 + 7

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def calc(pos, neg):
    res = 1
    if pos:
        for p in pos:
            res *= p
            res %= mod
    if neg:
        for n in neg:
            res *= (-n)
            res %= mod
    return res

def main():
    n, k = na()
    a = na()
    po = list(); ne = list()
    for ai in a:
        if ai > 0:
            po.append(ai)
        if ai < 0:
            ne.append(ai)
    po.sort(reverse=True)
    ne.sort()
    if len(po) >= k:
        ans = calc(po[:k], None)
        print(ans)
        quit()
    if len(po) == 0 and k % 2 == 1:
        if 0 in a:
            print(0)
            quit()
        else:
            ans = -calc(None, ne[(n-k):]) % mod
            print(ans)
            quit()
    else:
        poi = len(po)
        nei = k - poi
        if nei % 2 == 1:
            poi -= 1
            nei += 1
        poi_pre = poi; nei_pre = nei
        while poi >= 0:
            poi -= 2
            nei += 2
            if poi < 0:
                break
            positive = po[poi] * po[poi+1]
            negative = ne[nei-2] * ne[nei-1]
            if positive < negative:
                poi_pre = poi; nei_pre = nei
            else:
                ans = calc(po[:poi_pre], ne[(n-nei_pre):])
                print(ans)
                quit()
        ans = calc(po[:poi], ne[(n-nei):])
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

    MOD = 10**9 + 7

    absA = [abs(a) for a in A]
    flg = 0
    m = []
    p = []
    dict = []
    T = []
    for i in A:
        if i < 0:
            m.append(i)
            T.append(tuple([abs(i),-1]))
        elif i > 0:
            p.append(i)
            T.append(tuple([abs(i),1]))
        else:
            flg = 1

    T.sort(reverse=True)
    # print(T)


    ans = T[:k]
    # print(ans)
    c = 0
    for i in ans:
        if i[1] == -1:
            c += 1

    if c % 2 == 0:
        l = 1
        for i in ans:
            l *= i[0]
            l %= MOD
        print(l)

    else:
        flg_1,flg_2 = 0,0
        # print(T)
        for j in range(k-1,-1,-1):
            if T[j][1] == -1:
                flg_1 = 1
                min_m = T[j][0]
                break

        for j in range(k,len(T)):
            if T[j][1] == 1:
                flg_2 ^= 1
                # print('AaA')
                max_p = T[j][0]
                break

        # print(min_m,max_p)

        if flg_1 and flg_2:
            flg = 1
        else:
            flg = 0

        flg_1,flg_2 = 0,0

        for j in range(k-1,-1,-1):
            if T[j][1] == 1:
                flg_1 = 1
                min_p = T[j][0]
                break
        
        for j in range(k,len(T)):
            if T[j][1] == -1:
                flg_2 = 1
                max_m = T[j][0]
                break

        if flg_1 and flg_2:
            flg2 = 1
        else:
            flg2 = 0


        l = 1
        for i in ans:
            l *= abs(i[0])
            l %= MOD 

        # print(l)

        if flg == 1 and flg2 == 1:
            if min_p * max_p >= min_m * max_p:
                l *= max_p
                l *= pow(min_m,MOD-2,MOD)
            else:
                l *= max_m
                l *= pow(min_p,MOD-2,MOD)
        elif flg == 1:
                l *= max_p
                t = pow(min_m,MOD-2,MOD)
                l *= pow(min_m,MOD-2,MOD)
        elif flg2 == 1:
                l *= max_m
                l *= pow(min_p,MOD-2,MOD)
        else:
            if 0 in A:
                l = 0
            else:
                A.sort(reverse=True)
                l = 1
                for i in range(k):
                    l *= A[i]
                    l %= MOD
                print(l)
                exit()
                # print(A)


            
        print(l%MOD)




    

            

main()

Submission status: Runtime Error

Solution code:
from collections import deque
n,k=map(int,input().split())
aa=list(map(int,input().split()))
aa=sorted(aa,key=lambda x: x * x,reverse=True)
aaa=deque(aa)
x=[]
if n==k:
  p=1
  for a in aa:
    p*=a
  print(p%(10**9+7))
else:
  for i in range(k+1):
    x.append(aaa.popleft())
  p=1
  for a in x:
    p*=a
  ans=[]
  for a in x:
    ans.append(int(p/a))
  answer=max(ans)
  print(answer%(10**9+7))

Submission status: Runtime Error

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

print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

N,K = map(int,input().split())
a_list = list(map(int,input().split()))
a_list.sort()
b_list = a_list[-K:]

n_negative = bisect_left(a_list,0)

max_pair_num = min(n_negative//2, K//2)


# 負の数からiペア取る
n_product = 1
p_product = 1
for i in range(K):
    p_product*= b_list[i]

ans = p_product
for i in range(1,max_pair_num+1):
    n_product *= a_list[i*2-2]
    n_product *= a_list[i*2-1]

    p_product /= b_list[i*2-2]
    p_product /= b_list[i*2-1]

    if n_product*p_product>ans:
        ans = n_product*p_product

print(int(ans%1_000_000_007))

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))

mod = 10**9+7

#全部使う
if n == k:
    ans = 1
    for i in lst1:
        ans *= i
        ans %= mod
    print(ans)
    exit() 

lst1.sort()
i = 0
minus = []
m = 0
while i < n and lst1[i] < 0:
    minus.append(lst1[i])
    m += 1
    i += 1
zero = 0
while i < n and lst1[i] == 0:
    zero += 1
    i += 1
plus = []
p = 0
while i < n:
    plus.append(lst1[i])
    p += 1
    i += 1

#必ず0を使う
if n-zero < k:
    print(0)
    exit()

#少なくともans<=0になる(負数にしかならない場合、0を掛けた方が良い場合)
if p==0 and not even(k):
    if zero:
        print(0)
        exit()
    else:
        ans = 1
        for i in range(k):
            ans *= lst1[-1-i]
            ans %= mod
        print(ans)
        exit()

#0を使わないようにすると、ちょうど負数が奇数個になってしまう場合
if n-zero == k and not even(m):
    print(0)
    exit()

#以下、必ず正の数にできる
#まだなんか見落としあるかも…

#負数はこの時点で上位からペアとして良い
pair = []
for i in range(0,m-1,2): #絶対値が大きい順
    pair.append(minus[i]*minus[i+1])

ans = 1
midx = 0 #cost2
pidx = 0 #cost1
plus.reverse() #降順
while k:
    if k == 1:
        ans *= plus[pidx]
        ans %= mod
        k -= 1
        pidx += 1
    elif k == 2:
        if midx < len(pair) and pidx+1 < len(plus):
            if pair[midx] >= plus[pidx]*plus[pidx+1]:
                ans *= pair[midx]
                ans %= mod
            else:
                ans *= plus[pidx]*plus[pidx+1]
                ans %= mod

        elif midx < len(pair):
            ans *= pair[midx]
            ans %= mod
        else:
            ans *= plus[pidx]*plus[pidx+1]
            ans %= mod
        
        break
    elif k >= 3:
        if midx < len(pair):
            if pidx+2 <= len(plus): #max-2がある
                if pair[midx] >= plus[pidx+1]*plus[pidx+2]:
                    ans *= pair[midx]
                    ans %= mod
                    midx += 1
                    k -= 2
                else:
                    ans *= plus[pidx]
                    ans %= mod
                    pidx += 1
                    k -= 1
            elif pidx+1 <= len(plus): #max-1がある
                if pair[midx] >= plus[pidx]*plus[pidx+1]:
                    ans *= pair[midx]
                    ans %= mod
                    midx += 1
                    k -= 2
                else:
                    ans *= plus[pidx]
                    ans %= mod
                    pidx += 1
                    k -= 1
            elif pidx <= len(plus): #maxしかない
                if pair[midx] >= plus[pidx]:
                    ans *= pair[midx]
                    ans %= mod
                    midx += 1
                    k -= 2
                else:
                    ans *= plus[pidx]
                    ans %= mod
                    pidx += 1
                    k -= 1
            else: #plusにない
                ans *= pair[midx]
                ans %= mod
                midx += 1
                k -= 2

                
        else:
            ans *= plus[pidx]
            ans %= mod
            pidx += 1
            k -= 1

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)
        print(res % MOD)
        exit()
    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())
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:
import sys
input = sys.stdin.readline
from collections import *

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7
p, n = [], []
flag = False

for Ai in A:
    if Ai==0:
        flag = True
    elif Ai>0:
        p.append(Ai)
    else:
        n.append(Ai)

if len(p)==0 and K%2==1:
    if 0 in A:
        print(0)
    else:
        n.sort(reverse=True)
        ans = 1
        
        for ni in n[:K]:
            ans *= ni
            ans %= MOD
        
        print(ans)
    exit()
    
p.sort()
n.sort(reverse=True)
apl = [1]
anl = [1]

for pi in p:
    apl.append(apl[-1]*pi%MOD)

for ni in n:
    anl.append(anl[-1]*ni%MOD)

p.reverse()
n.reverse()
apr = [1]
anr = [1]

for pi in p:
    apr.append(apr[-1]*pi%MOD)

for ni in n:
    anr.append(anr[-1]*ni%MOD)

#p.reverse()
#n.reverse()

f = True

for i in range(0, len(n)+1, 2):
    if len(p)>=K-i>=0 and i<=len(n):
        if f:
            ans = anr[i]*apr[K-i]
            f = False
            continue
            
        a = p[K-i-1]*p[K-i-2]
        b = n[i-1]*n[i-2]
        
        if b>a:
            ans = anr[i]*apr[K-i]%MOD

print(ans%MOD)