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 heapq import heapify,heappush,heappop
N, K = map(int,input().split())
A = list(map(int, input().split()))
MOD =1_000_000_007

B = [a for a in A if a > 0]
C = [a for a in A if a<= 0]
B.sort()
C.sort(reverse = True)
ans = 1
if N == K:
  for a in A:
    ans *= a
    ans %= MOD
elif len(B) == 0 and K % 2 == 1:
  for i in range(K):
    ans *= C[i]
    ans %= MOD
else:
  if K % 2 == 1:
    ans *= B[-1]
    B.pop()
    K -= 1
  i = 0 
  j = 0
  k = 0
  while k < K:
    if len(C) < 2 or B[-1]*B[-2] > C[-1] * C[-2]:
      ans *= B[-1]*B[-2]
      ans %= MOD
      B.pop()
      B.pop()
    else:
      ans *= C[-1]*C[-2]
      ans %= MOD
      C.pop()
      C.pop()
    print(B,C)
    k += 2

print(ans)

Submission status: Runtime Error

Solution code:

def main():
  n, k = map(int, input().split())

  plus = []
  minus = []

  for n in input().split():
    n = int(n)
    if n >= 0:
      plus.append(n)
    else:
      minus.append(n)

  plus.sort(reverse = True)
  minus.sort()

  pn = min(len(plus), k)
  mn = k - pn

  if len(plus) >= 2 and len(minus) >= 2:
    while pn >= 2:
      if plus[pn - 2] * plus[pn - 1] > minus[mn] * minus[mn + 1]:
        break

      pn -= 2
      mn += 2

  mod = 10 ** 9 + 7
  ans = 1
  for i in range(pn):
    ans = (ans * plus[i]) % mod

  for i in range(mn):
    ans = ans * minus[i]

  if ans < 0:
    ans = 1
    for i in range(pn):
      ans = (ans * plus[-i - 1]) % mod

    for i in range(mn):
      ans = ans * minus[-i - 1]


  print(ans % mod)


main()

Submission status: Runtime Error

Solution code:
# coding: utf-8


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = sorted(A, key=lambda x: abs(x), reverse=True)
    Bp = [x for x in B if x > 0]
    Bm = [x for x in B if x < 0]
    Bpm = [x for x in B if x != 0]
    Bmm = []
    for i in range(0, len(Bm)-1, 2):
        Bmm.append(Bm[i]*Bm[i+1])

    q = 10**9 + 7

    n_plus, n_zero, n_minus = 0, 0, 0
    for a in A:
        if a > 0:
            n_plus += 1
        elif a < 0:
            n_minus += 1
        else:
            n_zero += 1

    if K > n_plus + n_minus:
        return 0

    # ans != 0
    rest = K
    ans = 1
    if K > n_plus and ((n_plus == 0 and n_minus % 2 == 1) or (K == n_plus + n_minus and n_minus % 2 == 1)):
        # ans < 0
        for i in range(K):
            ans = (ans * Bpm[len(Bpm)-1-i]) % q
        return ans
    else:
        # ans > 0
        i, j = 0, 0
        while rest > 0:
            if rest >= 2 and j < len(Bmm):
                if i+1 < len(Bp):
                    if Bmm[j] >= Bp[i] * Bp[i+1]:
                        ans = (ans * (Bmm[j] % q)) % q
                        j += 1
                        rest -= 2
                    else:
                        ans = (ans * Bp[i]) % q
                        i += 1
                        rest -= 1
                elif i < len(Bp):
                    if Bmm[j] >= Bp[i]:
                        ans = (ans * (Bmm[j] % q)) % q
                        j += 1
                        rest -= 2
                    else:
                        ans = (ans * Bp[i]) % q
                        i += 1
                        rest -= 1
                else:
                    ans = (ans * (Bmm[j] % q)) % q
                    j += 1
                    rest -= 2
            else:
                ans = (ans * Bp[i]) % q
                i += 1
                rest -= 1
        return ans

        # i = 0
        # ip = 0
        # im = 0
        # while rest > 0:
        #     if B[i] > 0:
        #         ans = (ans * B[i]) % q
        #         i += 1
        #         ip += 1
        #         rest -= 1
        #     else:  # B[i] < 0
        #         if rest == 1:
        #             i += 1
        #         elif B[i+1] < 0:  # rest >= 2
        #             ans = (ans * (B[i]*B[i+1] % q)) % q
        #             i += 2
        #             im += 2
        #             rest -= 2
        #         else:  # rest >= 2 and B[i+1] > 0
        #             if Bp[ip] * Bp[ip+1] > Bm[im] * Bm[im+1]:
        #                 ans = (ans * (Bp[ip]*Bp[ip+1] % q)) % q


print(main())

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
u = []
o = []
l = len(a)
for i in range(l):
    if a[i] >= 0:
        o.append(a[i])
    else:
        u.append(a[i])
u = list(map(abs, u))
u.sort(reverse=True)
o.sort(reverse=True)
ans = 1
lo = len(o)
lu = len(u)
oi = 0
ui = 0
if lo == 0 and k % 2 == 1:
    u.sort()
    for i in range(k):
        ans = ans*u[i]
else:
for j in range(n):
    if oi+ui == k:
        break
    elif oi < lo:
        if ui < lu:
            ot = o[oi]*[oi+1]
            if k-ui-oi > 1:
                ut = u[ui]*u[ui+1]
                if ut < ot:
                    ans = ans*ot
                    oi += 2
                else:
                    ans = ans*ut
                    ui += 2
            else:
                ans = ans*o[oi]
                break
        else:
            ans = ans*o[oi]
            oi += 1
        elif ui < lu:
            ans = ans*u[ui]*-1
            ui += 1
ans = ans % 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

A_p = []
A_n = []
A_z = []
mod = 10**9 + 7

for a in A:
    if a>0:
        A_p.append(a)
    elif a<0:
        A_n.append(a)
    else:
        A_z.append(a)

ans = 1

if (len(A_p) + (len(A_n) // 2) * 2 >= K) and ((K-len(A_p))%2==0):
    # Z > 0:
    A_p.sort()
    A_n.sort()

    prev = None
    for a_n in A_n:
        idx = bisect.bisect_left(A_p, -a_n)
        if idx > len(A_p) - K:
            bisect.insort_left(A_p, -a_n)
            prev = idx
        else:
            if prev is not None:
                A_p.pop(idx)

    A_p.sort(reverse=True)
    # print(A_p)
    for i in range(K):
        ans = ans * A_p[i]
        ans = ans % mod

    print(ans)
    sys.exit()

if len(A_z)>0:
    print(0)
    sys.exit()


# Z < 0:
# print('Negative')
A_p.sort()
A_n.sort()

prev = None
for a_n in A_n:
    idx = bisect.bisect_left(A_p, -a_n)
    bisect.insort_left(A_p, -a_n)

# print(A_p)
for i in range(K):
    ans = ans * A_p[i]
    ans = ans % mod

ans = (-ans) % mod
print(ans)
sys.exit()

Submission status: Runtime Error

Solution code:
import numpy as np

N, K = input().split(" ")
N = int(N)
K = int(K)

A = []
for i in range(N)
   A.append(int(input())

A = np.array(A).sort()[::-1][:K]
            
print(np.sum(A)%(10**9+7))

Submission status: Runtime Error

Solution code:
mod = 10**9 + 7
import bisect

def do():
    n, k = map(int, input().split())
    dat = list(map(int, input().split()))
    buf = []
    nump, numm, numz = 0, 0, 0
    for i in range(n):
        if dat[i] == 0:
            numz += 1
        elif dat[i] > 0:
            nump += 1
            buf.append([dat[i], dat[i]])
        elif dat[i] < 0:
            numm += 1
            buf.append([dat[i], -dat[i]])
    indm = []
    indp = []
    # +と-を足してもk個に満たないなら 0 をかけるしかないので
    if len(buf) < k:
        print(0)
        return

    for i in range(n):
        if buf[i][0] < 0:
            indm.append(i)
        else:
            indp.append(i)
    buf.sort(key=lambda x: x[1], reverse=True)

    #print(nump, numm, numz)
    #print(buf)
    #print(indm)
    #print(indp)

    res = 1
    lastp = None
    lastm = None
    flagPosi = True

    for i in range(k):
        res *= buf[i][0]
        res %= mod
        if buf[i][0] > 0:
            lastp = buf[i][0]
        elif buf[i][0] < 0:
            lastm = buf[i][0]
            flagPosi = not flagPosi

    # k個選んで正なら、無条件にオッケー
    if flagPosi:
        print(res%mod)
        return

    def do2(): # negaしか作れないなら最も小さい値
        buf.sort(key=lambda x: x[1], reverse=False)
        res2 = 1
        for i in range(k):
            res2 *= buf[i][0] % mod
            res2 %= mod
        print(res2%mod)

    def do3(anti, kawari): # negaしか作れないなら最も小さい値
        ispass = False
        buf.sort(key=lambda x: x[1], reverse=True)
        res2 = 1
        for i in range(k):
            if ispass is False and buf[i][0] == anti:
                ispass = True
                continue
            res2 *= buf[i][0] % mod
            res2 %= mod
        res2 *= kawari
        print(res2%mod)

    # 負の場合は二パターン
    # 1. 正を抜いて、次に大きい負をかける
    # 2. 負を抜いて、次に大きい正をかける
    nextp = None
    nextm = None
    for i in range(k, len(buf)):
        if buf[i][0] > 0 and nextp is None:
            nextp = buf[i][0]
        elif buf[i][0] < 0 and nextm is None:
            nextm = buf[i][0]
    #print(lastp, lastm, nextm, nextp)
    if (lastp is None or nextm is None) and (lastm is None or nextp is None):
        # この場合、動かせないので負しかないから
        do2()
        return
    if lastp is not None and lastm is not None and nextp is not None and nextm is not None:
        # 全部あるなら戦い
        if abs(nextm / lastp) > abs(nextp / lastm):
            # pをmにした方がいいので
            do3(lastp, nextm)
            return
        else:
            do3(lastm, nextp)
            return
    # この場合、どっちしかないので
    if (lastp is None or nextm is None) and lastm is not None and nextp is not None:
        # この場合、 m-> p
        do3(lastm, nextp)
        return
    elif lastp is not None and nextm is not None:
        do3(lastp, nextm)
        return
    print("end")

do()

Submission status: Runtime Error

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

        print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort(reverse=True, key=lambda x:abs(x))
cnt = 0
im = 0
ip = 0
cp = 0
mod = 10 ** 9 + 7

for i, ai in enumerate(a):
    if i < k:
        if ai < 0:
            im = i
            cnt += 1
        if ai > 0:
            ip = i
    if ai > 0:
        cp += 1

ans = 1
f = 0

# print(a)
if cnt % 2:
    if cp == 0:
        a.sort(reverse=True)
        for i, ai in enumerate(a):
            if i == k:
                break
            ans *= ai
            ans %= mod
        print(ans)
    else:
        ans = 1
        cnt = 0
        f = 0
        for i, ai in enumerate(a):
            if cnt == k:
                f = 2
                break
            if i == im:
                f = 1
                continue
            if f == 1 and ai <= 0:
                continue
            ans *= abs(ai)
            ans %= mod
            # print(i, ai)
            cnt += 1
        if f == 2:
            print(ans)
        else:
            ans = 1
            cnt = 0
            f = 0
            for i, ai in enumerate(a):
                if cnt == k:
                    f = 2
                    break
                if i == ip:
                    f = 1
                    continue
                if f == 1 and ai >= 0:
                    continue
                ans *= abs(ai)
                ans %= mod
                # print(i, ai)
                cnt += 1
            if f == 2:
                print(1/0)
                print(ans)
            else:
                ans = 1
                a.sort(reverse=True)
                for i, ai in enumerate(a):
                    if i == k:
                        break
                    ans *= ai
                    ans %= mod
                print(ans)

else:
    for i, ai in enumerate(a):
        if i == k:
            break
        ans *= abs(ai)
        ans %= mod
    print(ans)

Submission status: Runtime Error

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

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

    Z = sum(1 if a == 0 else 0 for a in A)
    if Z + K > N:
        print(0)
        return
    P = []
    M = []
    for a in A:
        if a > 0:
            P.append(a)
        else:
            M.append(a)
    
    if len(P) == 0:
        M.sort(reverse = True)
        ans = 1
        for i in range(K):
            ans *= M[i]
            ans %= MOD
        print(ans)
        return
    
    if Z + K == N:
        ans = 1
        for p in P:
            ans *= p
            ans %= MOD
        for m in M:
            ans *= m
            ans %= MOD
        print(ans)
        return

    if K%2 == 0:
        P.sort(reverse = True)
        number = []
        for i in range(0,len(P) - 1,2):
            number.append((P[i]*P[i + 1],0))

        M.sort()
        for i in range(0,len(M) - 1,2):
            number.append((M[i]*M[i + 1],1))
        
        number.sort(reverse = True)
        cnt = 0
        cnt_p = 0
        cnt_m = 0
        i = 0
        ans = 1
        while i < len(number):
            if cnt + 2 <= K:
                cnt += 2
                ans *= number[i][0]
                ans %= MOD
                if number[i][1] == 0:
                    cnt_p += 2
                else:
                    cnt_m += 2
            i += 1
        print(ans)
    
    else:
        P.sort(reverse = True)
        M.sort()

        ret = 1
        idx = 0
        midx = 0
        for i in range(0,len(P),2):
            if K - i - 1 <= len(M):
                idx = i
                for j in range(i + 1):
                    ret *= P[j]
                    ret %= MOD
                for j in range(K - i - 1):
                    ret *= M[j]
                    ret %= MOD
                midx = K - i - 2
                break
        
        diff = 1
        inv = 1
        for i in range(idx,len(P) - 2,2):
            if midx - 1 < 0:
                break
            diff *= P[i + 1]/M[midx]*P[i + 2]/M[midx - 1]
            inv *= P[i + 1]*P[i + 2]%MOD*pow(M[midx],MOD - 2,MOD)*pow(M[midx - 1],MOD - 2,MOD)%MOD
            if diff > 1:
                ret *= inv
                ret %= MOD
                inv = 1
                diff = 1
        print(ret)
if __name__ == '__main__':
    main()

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 is not None and firstminus < N:
        ac = abs(A[lastplus]*A[firstminus])
    else:
        ac = -1
    if lastminus is not None and firstplus < N:
        bd = abs(A[lastminus]*A[firstplus])
    else:
        bd = -1
    if ac < 0 and bd < 0:
        pass
    elif 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:
n , k = map(int, input().split())
a = list(map(int, input().split()))
neg = []
pos = []
mod = 10**9+7
for i in range(n):
    if a[i] >= 0:
        pos.append(a[i])
    else:
        neg.append(a[i])
neg.sort()
pos.sort(reverse = True)
min_num = -1
good_num = -1
if k % 2 == 1 and len(pos) == 0:
    ans = 1
    neg.sort(reverse = True)
    for i in range(k):
        ans *= neg[i]
        ans %= mod
    print(ans)
else:
    #最大化するとき
    for i in range(0,k+1,2):
        #i個だけnegから取る。
        if i > len(neg) or k - i > len(pos):
            continue
        m = -1
        if i - 1 >= 0:
            m = abs(neg[i-1])
        if k-i-1 >= 0:
            m = min(m, pos[k-i-1])
        if m > min_num:
            min_num = m
            good_num = i
    ans = 1
    for i in range(good_num):
        ans *= neg[i]
        ans %= mod
    for i in range(k - good_num):
        ans *= pos[i]
        ans %= mod
    print(ans % mod)

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split()))
N = int(a[0])
K = int(a[1])

A_i = list(map(int, input().split()))
A_pos = [i for i in A_i if i > 0]
A_neg = [i for i in A_i if i < 0]
A_zer = [i for i in A_i if i == 0]

A_pos = sorted(A_pos)
A_neg = sorted(A_neg)
A_neg.reverse()
# zettaiti tiisai jun

ret = 1

if len(A_pos) == 0:
    if len(A_zer) > 0:
        ret = 0
    for i in range(K):
        ret = ret * A_neg[i]
        ret = ret % (10**9+7)
    if ret < 0:
        ret += 10**9+7
else:
    if K % 2 == 1:
        ret *= A_pos[-1]
        A_pos = A_pos[:-1]

    for i in range(K//2):
        if len(A_pos) == 0 and len(A_neg) == 2:
            ret = ret * A_neg[0] * A_neg[1]
            continue
        if len(A_pos) == 1 and len(A_neg) == 1:
            if len(A_zer) > 0:
                ret = 0
            ret = ret * A_neg[0] * A_pos[0]
            continue
        if len(A_pos) == 2 and len(A_pos) == 0:
            ret = ret * A_pos[0] * A_pos[1]
            continue
        if len(A_pos) >= 2:
            c1 = A_pos[-1] * A_pos[-2]
        else:
            c1 = None
        if len(A_neg) >= 2:
            c2 = A_neg[-1] * A_neg[-2]
        else:
            c2 = None
        if c1 is None and c2 is None:
            ret = 0
        elif c2 is None or c1 > c2:
            ret = ret * A_pos[-1] * A_pos[-2]
            A_pos = A_pos[:-2]
        else :
            ret = ret * A_neg[-1] * A_neg[-2]
            A_neg = A_neg[:-2]
        ret = ret % (10**9+7)
        if ret < 0:
            ret += 10**9+7
print(ret)

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()
    
if K==N:
    ans = 1
    
    for Ai in A:
        ans *= Ai
        ans %= MOD
    
    print(ans)
    exit()

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

if K%2==0:
    l = []
    
    for i in range(len(p)//2):
        l.append(p[2*i]*p[2*i+1])
    
    for i in range(len(n)//2):
        l.append(n[2*i]*n[2*i+1])

    l.sort(key=lambda x: abs(x), reverse=True)
    ans = 1
    
    for i in range(K//2):
        ans *= l[i]
        ans %= MOD
else:
    ans = p[0]
    l = []
    
    for i in range(len(p)//2):
        l.append(p[2*i]*p[2*i+1])
    
    for i in range(len(n)//2):
        l.append(n[2*i]*n[2*i+1])
    
    l.sort(key=lambda x: abs(x), reverse=True)
    
    for i in range((K-1)//2):
        ans *= l[i]
        ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
cnt=1
if n==k and 0 in a:
  print(0)
elif a[-1]<0 and k%2!=0:
  if 0 in a:
    print(0)
  else:
    for j in range(k):
      cnt*=a[-(j+1)]
      cnt%=1000000007
    print(cnt)
else:
  for i in range(k//2):
    if a[0]*a[1]>a[-1]*a[-2] and a[1]<0 or a[-3]==0 and k%2!=0:
      cnt*=a[0]*a[1]
      cnt%=1000000007
      a.pop(0)
      a.pop(0)
    else:
      cnt*=a[-1]*a[-2]
      cnt%=1000000007
      a.pop(-1)
      a.pop(-1)
  if k%2!=0:
    cnt*=a[-1]
    cnt%=1000000007
    print(cnt)
  else:
    print(cnt)

Submission status: Runtime Error

Solution code:
import sys
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 10**9+7
zero_flag = False

ans = 1

p_list, m_list = [], []
for i in a:
    if i<0: m_list.append(i)
    elif i>0: p_list.append(i)
    else: zero_flag = True

n = len(p_list)+len(m_list)

if n<k:
    print(0)
    sys.exit()
if k==n:
    if len(m_list)%2 and zero_flag:
        print(0)
        sys.exit()
        
    for i in p_list:
        ans *= i
        ans %= mod
    for i in m_list:
        ans *= i
        ans %= mod
    print(ans)
    sys.exit()

if n==len(m_list):
    if zero_flag:
        print(0)
        sys.exit()
    else:
        ans = m_list[-1]
        for i in range(1, k):
            ans *= m_list[n-i-1]
            ans %= mod
        print(ans)
        sys.exit()


p_num, m_num = len(p_list)-1, 0

while k>0:
    p_mul, m_mul = 0, 0
    
    if k==3:
        if m_mul+1<len(m_list) and p_mul+1==2:
            m_mul = m_list[m_num]*m_list[m_num+1]*p_list[p_num]
            p_mul = p_list[p_num]*p_list[p_num-1]*m_list[m_num]
            if p_mul>m_mul:
                ans *= p_mul
            else:
                ans *= m_mul
            if ans<0 and zero_flag:
                ans = 0
        elif m_mul+1<len(m_list) and p_mul+1<len(p_list):
            m_mul = m_list[m_num]*m_list[m_num+1]*p_list[p_num]
            p_mul = p_list[p_num]*p_list[p_num-1]*m_list[m_num]
            mm_mul = p_list[p_num]*p_list[p_num-1]*p_list[p_num-2]
            if p_mul>m_mul and p_mul>mm_mul:
                ans *= p_mul
            elif m_mul>p_mul and m_mul>mm_mul:
                ans *= m_mul
            else:
                ans *= mm_mul
            if ans<0 and zero_flag:
                print(ans)
                ans = 0
        ans %= mod    
        break
    if k==1:
        if p_num<0:
            if zero_flag:
                print(0)
                sys.exit()
        ans *= p_list[p_num]
        ans %= mod
        break
    if m_mul+1<len(m_list):
        m_mul = m_list[m_num]*m_list[m_num+1]
    if p_mul+1<len(p_list):
        p_mul = p_list[p_num]*p_list[p_num-1]
    if p_mul>m_mul:
        ans *= p_mul
        ans %= mod
        p_num -= 2
    else:
        ans *= m_mul
        ans %= mod
        m_num += 2
    k -= 2
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
ps = []
ns = []
zs = 0
for a in map(int, input().split()):
    if a > 0:
        ps.append(a)
    elif a < 0:
        ns.append(a)
    else:
        zs += 1

def product(l):
    t = 1
    for li in l:
        t *= li
    return t

def p(x):
    print(x % (10**9 + 7))

if len(ps) + len(ns) == 0:
    print(0)
elif len(ps) == 0:
    if k % 2 == 0:
        ns.sort()
    else:
        ns.sort(reverse=True)
    p(product(ns[:k]))
elif len(ns) == 0:
    ps.sort(reverse=True)
    p(product(ps[:k]))
else:
    ma = 0
    l = ps + ns
    pn = []
    for i in range(len(l)):
        pn.append(l[i] > 0)
        l[i] = abs(l[i])
    tmp = sorted(list(zip(*[l, pn])), key=lambda x:x[0], reverse=True)
    l = list(map(lambda x:x[0], tmp))
    pn = list(map(lambda x:x[1], tmp))
    if len([pni for pni in pn[:k] if not pni]) % 2 == 0:
        p(product(l[:k]))
    else:
        i = len(pn) - 1 - pn[::-1].index(False)
        j = pn.index(True, k)
        l = l[:k] + l[j]
        l.pop(i)
        p(product(l[:k]))

Submission status: Runtime Error

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
p = 10**9+7
Aplus = []
Nplus = 0
Aminus = []
Nminus = 0
Aabs = []
for i in range(N):
    if A[i]>=0:
        Aplus.append(A[i])
        Nplus += 1
    else:
        Aminus.append(A[i])
        Nminus += 1
Aplus.sort(reverse=True)
Aminus.sort(reverse=False)

if Nplus==0:
    if K%2==0:
        t=0
        out = 1
        while t<=K-1:
            out = out*Aminus[t]%p
            t+=1
    else:
        t=0
        out = 1
        while t<=K-1:
            out = out*Aminus[N-1-t]%p
            t+=1
    print(out)
else:
    Aminus2 = []
    for i in range(Nminus//2):
        Aminus2.append(Aminus[2*i]*Aminus[2*i+1])

    out = 1
    l = 0
    r = 0
    while K>0:
        cand = [0,0]
        flag = 0
        if r<=Nminus-1 and K>=2 and Aminus2[r]>0:
            cand[0] = Aminus2[r]
            flag=1
        if l+1<=Nplus-1:
            cand[1] = Aplus[l]*Aplus[l+1]
            flag=1
        if flag==1:
            if cand[0]>cand[1]:
                r+=2
                K+=-2
                out = out*cand[0]%p
            elif cand[0]<=cand[1]:
                l+=1
                K+=-1
                out = out*cand[1]%p
        else:
            if l==Nplus-1 and r==Nminus-1 and K==2:
                out = out*Aplus[l]*Aminus2[r]%p
            elif l==Nplus-1 and r==Nminus-1 and K==1:
                out = out*Aplus[l]%p
            elif K==2:
                out = out*Aplus[l]*Aplus[l+1]%p
            else:
                out = out*Aplus[l]%p
            break
    print(out)

Submission status: Runtime Error

Solution code:
import sys

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

ans = 1
a.sort()

check = (n for n in a if n > 0)
check = list(check)

if len(check)!= 0:
    if k%2 == 1:
        ans = ans*a[-1]
        del a[-1]
        k -= 1
elif len(check) == 0 and k%2 == 1:
    for i in range(k):
        ans *= a[-i-1]
    print(ans%(10**9+7))
    sys.exit()
    
while k > 10:
    for i in range(k/2):
        a[i]= a[i*2]*a[i*2+1]
    a = a[0:k/2]
    a.sort()
    k = k/2
    if k%2 == 1:
        ans = ans*a[-1]
        del a[-1]
        k -= 1
    
while k >= 2:
    if a[0]*a[1]> a[-1]*a[-2]:
        ans *= a[0]*a[1]
        del a[0:2]
        k -= 2
    else:
        ans *= a[-1]*a[-2]
        del a[-2:]
        k -= 2

print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
n, k = map(int,input().split())
li = list(map(int,input().split()))
x = [] #正の数
y = [] #負の数
ans = 0

for i in li:
    if i > 0:
        x.append(i)
    else:
        y.append(i)

if len(y)==0:
    x.sort(reverse=True)
    for i in range(k-1):
        x[i+1] *= x[i]
    print(x[k-1]%(10**9+7))
    exit()

if len(x)==0 and k%2==1:
    y.sort(reverse=True)
    for i in range(k-1):
        y[i+1] *= y[i]
    print(y[k-1]%(10**9+7))
    exit()

#以下、どちらにも要素がある場合
x.sort(reverse=True)
y.sort()

for i in range(len(x)-1):
    x[i+1] = x[i]*x[i+1]
for i in range(len(y)-1):
    y[i+1] = y[i]*y[i+1]

x.insert(0, 1)
y.insert(0, 1)

for i in range(n-len(x)-1, min(len(y)-1,k)+1): #iは負の数を使う数
    if i%2==1: #奇数なら
        continue
    else:
        m = y[i]*x[k-i]
        if m > ans:
            ans = m

print(ans%(10**9+7))