Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Constraints

1 \leq K \leq N \leq 2\times 10^5

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

The possible products of the three chosen elements are -24, -12, -8, and -6, so the maximum product is -6.

We print this value modulo (10^9+7), that is, 1000000001.

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

The possible products of the one chosen element are -1 and 1000000000, so the maximum product is 1000000000.

Sample Input 4

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

Sample Output 4

999983200

Be sure to print the product modulo (10^9+7).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
P = sum(x>0 for x in a)
Z = sum(x==0 for x in a)
M = sum(x<0 for x in a)
ans = 1
mod = 10**9+7
pal = 1
if (P == 0 and K%2 == 1) or (M%2 == 1 and K == N):
  if Z != 0:
    #print('here')
    print(0)
  else:
    aabs = sorted([abs(x) for x in a])
    #print('HERE')
    #print(aabs)
    for i in aabs[:K]:
      ans *= i
      #print(ans)
      ans %= mod
      #print(ans)
    print(-1*ans+mod)
elif M%2 == 1 and P+M == K:
  if Z != 0:
    #print('here')
    print(0)
  else:
    aabs = sorted([abs(x) for x in a])
    #print('HERE')
    #print(aabs)
    for i in aabs[:K]:
      ans *= i
      #print(ans)
      ans %= mod
      #print(ans)
    print(-1*ans+mod)
else:
  if P+M < K:
    print(0)
  else:
    aabs = sorted([(abs(x),x/abs(x)) for x in a],reverse=True)
    for i in range(K-2):
      ans *= aabs[i][0]
      ans %= mod
      pal *= aabs[i][1]
    if pal == 1:
      count = 0
      tempp = 1
      tempm = 1
      for i in range(K-2,N):
        if aabs[i][1] == 1:
          tempp *= aabs[i][0]
          count += 1
          if count == 2:
            break
      COUNT = 0
      for i in range(K-2,N):
        if aabs[i][1] == -1:
          tempm *= aabs[i][0]
          COUNT += 1
          if COUNT == 2:
            break
      if COUNT == 2 or count == 2:
        ans*= max(tempp,tempm)
        ans %= mod
      else:
        ans = 0
    if pal == -1:
      COUNT = 0
      for i in range(K-2,N):
        if aabs[i][1] == -1:
          ans *= aabs[i][0]
          ans %= mod
          COUNT += 1
          break
      for i in range(K-2,N):
        if aabs[i][1] == 1:
          ans *= aabs[i][0]
          ans %= mod
          COUNT += 1
          break
      if COUNT != 2:
        ans = 0
  print(ans)

Submission status: Runtime Error

Solution code:
from itertools import combinations

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


p = []

for b in combinations(a, k):
    s = 1
    print(b)
    for i in range(k):
        s *= b[i]
    p.append(s)
    print(p)

l = len(p)
p.sort(reverse = True)

print(p[0]%(10**9+7))

Submission status: Runtime Error

Solution code:
import itertools
from functools import reduce
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = [int(_) for _ in input().split()]
C = [list(i) for i in itertools.combinations(A, K)]
digits = [[] for i in range(len(C))]
for i, v in enumerate(C): 
  for j in v: 
    digits[i].append(len(str(abs(j))))
max_digits = max([reduce(lambda x, y: x+y, j) for j in digits])
res = [reduce(lambda x, y: x*y%MOD, j) for j in C]
res = [i for i in res if len(str(i)) <= max_digits]
ans = max(res)
if ans < 0:
  print(ans % MOD)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = pow(10, 9) + 7
ans = 1
for i in range(k):
    ans *= a[i]
# ans %= mod

tmp = ans
index = 0
for i in range(k, n):

    tmp /= a[index]
    # tmp %= mod
    tmp *= a[i]
    # tmp %= mod
    index += 1
    ans = max(tmp, ans)
print(int(ans % mod))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right

mod = 10 ** 9 + 7
n, k = map(int, input().split())
A = list(map(int, input().split()))
# dp = [[[0] * (2) for _ in range(k+1)]for _ in range(n+1)]
# # dp[桁][数][負数の数=1,0]

A.sort()
n_minus = bisect_left(A, 0)
n_zero = bisect_right(A, 0) - n_minus
n_plus = n - n_minus - n_zero

possible_max = min(k, n_minus)
possible_min = max(k - (n_plus + n_zero), 0)
ans = 1
if possible_max == possible_min and possible_min % 2 == 1:
    if k - (possible_min) > 0 and n_zero > 0:
        print(0)
        exit()
    A_plus = A[n - (n_plus) :]
    A_minus = A[:n_minus]
    A_minus.sort(reverse=True)
    # 負の数は奇数個小さい方から選ぶ
    for i in range(possible_min):
        ans *= A_minus[i]
        ans %= mod
    for i in range(k - possible_min):
        ans *= A_plus[i]
        ans %= mod
else:
    # 正の数に成る→大きいものがほしい
    # 負の数は偶数個、これの数を決め打つ
    # 計算すると大変だから大小を考える

    A_plus = A[n - (n_plus) :]
    A_plus.sort(reverse=True)
    A_minus = A[:n_minus]

    # 負の数を使う数を決め打つ
    # 最終的に正にできるパターン
    minus_num_max = min(n_minus // 2, k // 2)
    select = k - 2 * minus_num_max
    if n_plus < select:
        print(0)
        exit()
    # 負の数にしかできないパターン
    # 遊びがない時に奇数個の負の数を選ばざるを得ない
    # その時に0があるかどうかパターン
    kouho = []
    for i in range(minus_num_max):
        if 2 * i + 1 >= n_minus:
            break
        temp = A_minus[2 * i] * A_minus[2 * i + 1]
        kouho.append((temp, -1))
    for i in range(n_plus // 2):
        temp = A_plus[2 * i] * A_plus[2 * i + 1]
        kouho.append((temp, +1))
    kouho.sort(reverse=True)
    if k % 2 == 0:
        for i in range(k // 2):
            ans *= kouho[i][0]
            ans %= mod
    else:
        cnt = 0
        i = 0
        for i in range(k // 2):
            num, f = kouho[i]
            if f == 1:
                cnt += 1
            ans *= num
            ans %= mod
        if plus_num==0:
            print(0)
            exit()
        ans *= A_plus[2 * cnt]
        ans %= mod


print(ans % mod)

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]
    else:
        ans *= inv_mod(A[lastminus]) * A[firstplus]
    ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
# 
import sys

from sys import stdin
input = lambda: stdin.readline().rstrip()


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

tl = []
for A in map(int,input().split()):
    tl.append((abs(A), A > 0))

tl.sort()
l = list(reversed(tl))

f = True
answer = 1
M = 10**9 + 7

last_Posi_idx = -1
last_Nega_idx = -1

answers = []
for i in range(K):
    A, F = l[i]
    answers.append(A)
    f = f == F
    if F:
        last_Posi_idx = i
    else:
        last_Nega_idx = i

# end with positive
if f:
    answer = 1
    for num in answers:
        answer = answer * num % M
    print(answer)
    exit()

alt_p_answer = -1
alt_n_answer = -1

alt_p = 'NOTFOUND'
alt_n = 'NOTFOUND'

# alt p
if last_Posi_idx > -1:
    for i in range(K,len(l)):
        A, F = l[i]
        if not F:
            alt_p = A
    if alt_p != 'NOTFOUND':
        alt_p_answer = 1
        for i in range(answers):
            num = answers[i] if i != last_Posi_idx else alt_p
            alt_p_answer = alt_p_answer * num % M

if last_Nega_idx > -1:
    for i in range(K,len(l)):
        A, F = l[i]
        if F:
            alt_n = A
    if alt_n != 'NOTFOUND':
        alt_n_answer = 1
        for i in range(answers):
            num = answers[i] if i != last_Nega_idx else alt_n
            alt_n_answer = alt_n_answer * num % M

if alt_p == alt_n:
    answer = 1
    for i in range(K):
        A, F = tl[i]
        f = 1 if F else -1
        answer = answer * A * f % M
    print(answer)
else:
    answer = max(alt_n_answer, alt_p_answer)

Submission status: Runtime Error

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

cnt = [0, 0]
for a in A:
    if 0 < a:
        cnt[1] += 1
    elif a < 0:
        cnt[0] += 1

if (k-cnt[1]) % 2 == 0:
    can_positive = 1
else:
    can_positive = 0

if can_positive:
    pos = []
    neg = []
    zero = []
    for a in A:
        if 0 < a:
            pos.append(a)
        elif a < 0:
            neg.append(a)
        else:
            zero.append(a)
    pos.sort()
    neg.sort()
    neg_pair = []
    for a, b in zip(neg, neg[1:]):
        neg_pair.append(a*b)
    neg_pair.reverse()
    use = []
    cnt = 0
    while cnt != k:
        if 2 <= k-cnt:
            if neg_pair and 2 <= len(pos):
                if neg_pair[-1] < pos[-1]*pos[-2]:
                    cnt += 2
                    use.append(pos.pop())
                    use.append(pos.pop())
                else:
                    cnt += 2
                    use.append(neg_pair.pop())
            elif neg_pair:
                cnt += 2
                use.append(neg_pair.pop())
            else:
                cnt += 2
                use.append(pos.pop())
                use.append(pos.pop())
        else:
            if pos:
                a = pos.pop()
                cnt += 1
                use.append(a)
            else:
                cnt += 1
                use.append(0)

    ans = use[0]
    for a in use[1:]:
        ans *= a
        ans %= MOD
    print(ans)
else:
    pos = []
    neg = []
    zero = []
    for a in A:
        if 0 < a:
            pos.append(a)
        elif a < 0:
            neg.append(a)
        else:
            zero.append(a)

    pos.sort(reverse=True)
    neg.sort(reverse=True)
    use = [neg[0]]
    neg_pair = []
    for a, b in zip(neg[1:], neg[2:]):
        neg_pair.append(a*b)
    neg_pair.reverse()
    # print(neg_pair, neg, pos)
    cnt = 1
    while cnt != k:
        if 2 <= k-cnt:
            if neg_pair and 2 <= len(pos):
                if neg_pair[-1] > pos[-1]*pos[-2]:
                    cnt += 2
                    use.append(pos.pop())
                    use.append(pos.pop())
                else:
                    cnt += 2
                    use.append(neg_pair.pop())
            elif neg_pair:
                cnt += 2
                use.append(neg_pair.pop())
            else:
                cnt += 2
                use.append(pos.pop())
                use.append(pos.pop())
        else:
            if pos:
                a = pos.pop()
                cnt += 1
                use.append(a)
            else:
                cnt += 1
                use.append(0)

    ans = use[0]
    for a in use[1:]:
        ans *= a
        ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
N,K=input().split()
N,K=int(N),int(K)
A=input().split()
Asign=[(-1 if A[x][0]=="-" else 1) for x in range(N)]
A2=[ A[i][1:] if Asign[i]==-1 else A[i] for i in range(N) ] 
for i in range(N): 
  A[i]=int(A[i])
  A2[i]=int(A2[i])

r=1
t=10**9+7
if 1 in Asign:
  if True:
    Asign.sort(key=lambda x:A2[x])
    A2.sort()
    p=1
    for i in range(K):
      p*=Asign[-i-1]
    if p==1:
      for i in range(K):
        r=(r*(A2[-i-1]%t))%t
    else:
      for i in range(K): 
        if Asign[-i-1]==-1: q=i
      j=-K-1
      while Asign[j]==-1: j-=1
      for i in range(K): 
        if i!=q: 
          r=(r*(A2[-i-1]%t))%t
          print(r)
      r*=A2[j]
else:
  if K%2==1:
    r=-1
    Asign.sort(key=lambda x:A2[x])
    A2.sort()
    for i in range(K):
      r=(r*(A2[-i-1]%t))%t
  else:
    r=1
    Asign.sort(key=lambda x:A2[x])
    A2.sort()
    for i in range(K):
      r=(r*(A2[i]%t))%t
    
print(r)

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,K=map(int,input().split())

A=list(map(int,input().split()))
mod=10**9+7
Am=[-i for i in A if i<0]
Ap=[i for i in A if i>=0]

Am.sort()
Ap.sort()
Am=deque(Am)
Ap=deque(Ap)



if N-K==0 and len(Am)%2==0 or len(Ap)==0 and K%2:
    c=1
    while K and (Am or Ap) :
        if Am and Ap:
            if Am[0]<Ap[0]:
                c*=Am.popleft()
            else:
                c*=Ap.popleft()
        elif Am:
            c*=Am.popleft()
        elif Ap:
            c*=Ap.popleft()
        K-=1
        c=-c
        c%=mod
    #print("unko")

else:
    c=1
    h=0
    w=0
    while K and (Am or Ap) :
        if K==1 and len(Ap)==0:
            break
        while K and (Am or Ap) :
            if Am and Ap:
                if Am[0]>Ap[0]:

                    a=Am.pop()
                    c*=a
                    h+=1
                else:

                    b=Ap.pop()
                    c*=b

            elif Am:
                a=Am.pop()
                c*=a
                h+=1
            elif Ap:
                b=Ap.pop()
                c*=b
            K-=1
            c%=mod
    if h%2==1:
        if Am and Ap:
            if Am[-1]*b>Ap[-1]*a:
                a=Am.pop()
                c*=a
                c*=pow(b,mod-2,mod)
            else:
                b=Ap.pop()
                c*=b
                c*=pow(a,mod-2,mod)
        if len(Am):
            a=Am.pop()
            c*=a
            c*=pow(b,mod-2,mod)
        else:
            b=Ap.pop()
            c*=b
            c*=pow(a,mod-2,mod)


print(c%mod)

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(1/0)
        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(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:
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:
import heapq

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

MOD = 10**9+7

A_pos = []
A_neg = []
for a in A:
    if a >= 0:
        A_pos.append(-a)
    else:
        A_neg.append(a)

# 積が負にしかならない
if len(A_pos) == 0 and k%2==1:
    A_neg.sort(reverse=True)
    ans = 1
    for a in A_neg[:k]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

A_pos2 = [-A_pos[i*2]*A_neg[i*2+1] for i in range(len(A_pos)//2)]
A_neg2 = [-A_neg[i*2]*A_neg[i*2+1] for i in range(len(A_neg)//2)]

heapq.heapify(A_pos2)  # 絶対値が大きいものが先頭
heapq.heapify(A_neg2)  # 絶対値が大きいものが先頭

if k%2==0:
    ans = 1
    for i in range(k//2):
        if not A_pos2:
            ans *= -heapq.heappop(A_neg2)
            ans %= MOD
        elif not A_neg2:
            ans *= -heapq.heappop(A_pos2)
            ans %= MOD
        else:
            if A_pos[0] <= A_neg[0]:
                ans *= -heapq.heappop(A_pos2)
                ans %= MOD
            else:
                ans *= -heapq.heappop(A_neg2)
                ans %= MOD
    print(ans)
    exit()

if False:
    ans = 1
    cnt = 0
    for i in range(k // 2 - 1):
        if not A_pos2:
            ans *= -heapq.heappop(A_neg2)
            ans %= MOD
        elif not A_neg2:
            ans *= -heapq.heappop(A_pos2)
            ans %= MOD
            cnt += 1
        else:
            if A_pos[0] <= A_neg[0]:
                ans *= -heapq.heappop(A_pos2)
                ans %= MOD
                cnt += 1
            else:
                ans *= -heapq.heappop(A_neg2)
                ans %= MOD
    if cnt*2+1 == len(A_pos):
        
else:
    ans = 1
    cnt = 0
    for i in range(k // 2):
        if not A_pos2:
            ans *= -heapq.heappop(A_neg2)
            ans %= MOD
        elif not A_neg2:
            ans *= -heapq.heappop(A_pos2)
            ans %= MOD
            cnt += 1
        else:
            if A_pos[0] <= A_neg[0]:
                ans *= -heapq.heappop(A_pos2)
                ans %= MOD
                cnt += 1
            else:
                ans *= -heapq.heappop(A_neg2)
                ans %= MOD
    A_pos.sort(reverse=True)
    ans *= A_pos[cnt*2]
    ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    A = sorted([int(x) for x in input().strip().split()])
    zeros = A.count(0)
    max_A = max(A)
    mod = 10 ** 9 + 7
    if 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:
                ind = A.index(0)
                for k in range(K):
                    ans = (ans * A[ind-k-1]) % 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:
import copy
N, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort()
res = 1
if N >= 3:

    for _ in range(N-3):
        if abs(A[0]) >= abs(A[len(A)-1]) and A[0] != 0:
            res *= A.pop(0)
        else:
            res *= A.pop(len(A)-1)

    #最後を+で揃える
    res1 = copy.deepcopy(res)
    A1 = copy.deepcopy(A)        

    if res1 > 0:
        res1 *= A1[len(A1)-1] * A1[len(A1)-2] * A1[len(A1)-3]
    else:
        res1 *= A1[0] * A1[len(A1)-1] * A1[len(A1)-2]

    #最後を-で揃える
    res2 = copy.deepcopy(res)
    A2 = copy.deepcopy(A)

    if res2 > 0:
        res2 *= A2[0] * A2[1] * A2[len(A2)-1]
    else:
        res2 *= A2[0] * A2[1] * A2[2]

else :
    a1 = A[0] * A[1]
    a2 = A[1] * A[2]
    a3 = A[0] * A[2]
    res1 = max(a1, a2)
    res2 = max(a2, a3)

r = max(res1, res2)

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

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split(" "))
mlist = list(map(int, input().split(" ")))
unsortedlist = sorted(mlist, key=lambda x: abs(x))
rresult = 1
for i in range(k):
  rresult *= unsortedlist[i]
sortedlist = unsortedlist[::-1]
plus = []
minus = []
zero = []
for i in sortedlist:
  if i > 0:
    plus.append(i)
  elif i < 0:
    minus.append(i)
  else:
    zero.append(i)

used_list = []    
used_plus = []
used_minus = []
used_zero = []

result = 1
for i in range(k):
  a = sortedlist[0]
  result *= a
  sortedlist.remove(a)
  used_list.append(a)
  if a > 0:
    plus.remove(a)
    used_plus.append(a)
  elif a == 0:
    zero.remove(a)
    used_zero.append(a)
  elif a < 0:
    minus.remove(a)
    used_minus.append(a)
if result >= 0:
  print(result%(10**9+7))
elif used_list[-1] >0:
  b = 0
  c = 0
  if minus:
    b = minus[0]*result/used_list[-1]
  if plus and used_minus:
    c = plus[0]*result/used_minus[-1]
  if b == 0 and c == 0:
    print(rresult%(10**9+7))
  else:
    print(max(b,c)%(10**9+7))
elif used_list[-1] <0:
  d = 0
  e =  0
  if plus:
    d = plus[0]*result/used_list[-1]
  if minus and used_plus:
    e = minus[0]*result/used_list[-1]
  if d == 0 and e == 0:
    print(rresult%(10**9+7))
  else:
    print(max(d,e)%(10**9+7))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
li_a = list(map(int, input().split()))
mod = 10**9+7
li = []
lll = 0
for i in li_a:
    if i < 0:
        li.append((abs(i), -1))
        lll += 1
    elif i == 0:
        li.append((i, 0))
    else:
        li.append((i, 1))
li.sort()
if lll == n:
    ans = 1
    for i in range(k):
        ans *= -li[i][0]
        ans %= mod
    print(ans)
    exit()
ans = 1
guki = 1
for i in range(n-1, n-k-1, -1):
    ans *= li[i][0]
    ans %= mod
    guki *= li[i][1]
if guki > 0:
    print(ans)
else:
    P, M, p, m = 10**6, 1000000, 1000000, 1000000
    P1, M1, p1, m1 = True, True, True, True
    for i in range(n-k, n):
        if li[i][1] >= 0:
            Plus = li[i][0]
            P = i
            P1 = False
            break
    for i in range(n-k, n):
        if li[i][1] <= 0:
            Mini = li[i][0]
            M = i
            M1 = False
            break
    if n-k-1 >= 0:
        for i in range(n-k-1, -1, -1):
            if li[i][1] >= 0:
                plus = li[i][0]
                p = i
                p1 = False
                break
        for i in range(n-k-1, -1, -1):
            if li[i][1] <= 0:
                mini = li[i][0]
                m = i
                m1 = False
                break
    ans1 = 1
    ans2 = 1
    if (not P1) and (not m1):
        for i in range(n-1, n-k-1, -1):
            if i == P:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans1 *= li[m][0]
        ans1 %= mod
    if (not p1) and (not M1):
        for i in range(n-1, n-k-1, -1):
            if i == M:
                continue
            ans2 *= li[i][0]
            ans2 %= mod
        ans2 *= li[p][0]
        ans2 %= mod
    if (not p1) and (not P1) and (not M1) and (not m1):
        if mini/Plus > plus/Mini:
            print(ans1)
        else:
            print(ans2)
    elif (not p1) and (not M1):
        print(ans2)
    elif (not m1) and (not P1):
        print(ans1)
    else:
        ans = 1
        for i in range(k):
            ans *= -li[i][0]
            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 = 0
good_num = 0
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 = 0
        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:
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 1_000_000_007
sort_by_abs_A = sorted(A, key=lambda x: abs(x), reverse=True)
A_neg = sorted(filter(lambda x: x < 0, A), reverse=True)
ans = 1
if len(A_neg) == 0:
    for a in sort_by_abs_A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
elif len(A_neg) == N:
    for a in sort_by_abs_A[-K:]:
        ans *= a
        ans %= MOD
    print(ans)
else:
    is_neg = False
    last_positive_idx = -1
    last_negative_idx = -1
    muls = []
    for i, a in enumerate(sort_by_abs_A[:K]):
        if a < 0:
            is_neg = not is_neg
            last_negative_idx = i
        elif a > 0:
            last_positive_idx = i
        else:
            print(0)
            exit()
        ans *= a
        ans %= MOD
    if is_neg:
        pos_candidate = 0
        for a in sort_by_abs_A[K:]:
            if a > 0:
                pos_candidate = a
                break
        neg_candidate = 0
        for a in sort_by_abs_A[K:]:
            if a < 0:
                neg_candidate = a
                break
        if (
            pos_candidate / sort_by_abs_A[last_negative_idx]
            < neg_candidate / sort_by_abs_A[last_positive_idx]
        ):
            ans *= pow(sort_by_abs_A[last_negative_idx], MOD - 2, MOD)
            ans %= MOD
            ans *= pos_candidate
            ans %= MOD
        else:
            ans *= pow(sort_by_abs_A[last_positive_idx], MOD - 2, MOD)
            ans %= MOD
            ans *= neg_candidate
            ans %= MOD
    print(ans)