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:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
data = [[abs(i), i < 0] for i in a]
all_minus = 0
for t in data:
    if t[1]:
        all_minus += 1
if all_minus == n:
    ans = 1
    data.sort()
    for i in range(k):
        ans = ans * data[i][0] % mod
    print(-ans % mod)
    exit()
data.sort(reverse=True)
last_minus = 0
last_plus = 0
ans = 1
minus_amount = 0
for i in range(k):
    elem, sign = data[i][0], data[i][1]
    if elem == 0:
        print(0)
        exit()
    ans = ans * elem % mod
    minus_amount += sign
    if sign:
        last_minus = elem
    else:
        last_plus = elem
if minus_amount % 2 == 0:
    print(ans%mod)
    exit()
if n==k:
    print(-ans % mod)
    exit()
tmp_plus = 0
tmp_minus = 0
for i in range(k, n):
    elem, sign = data[i][0], data[i][1]
    if last_plus and sign and not tmp_minus:
        tmp_minus = elem
    elif last_minus and not sign and not tmp_plus:
        tmp_plus = elem
print(0/0)
if tmp_plus == 0 and tmp_minus == 0:
    ans = 0
elif last_plus == 0:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
elif last_minus == 0:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
elif tmp_plus * last_plus > tmp_minus * last_minus:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
else:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys
n,k=map(int,input().split())
A=[]
mod=10**9+7

zero=0
a=list(map(int,input().split()))
for i in range(n):
    if a[i]>0:
        A.append([a[i],0])
    elif a[i]<0:
        A.append([-a[i],1])
    else:
        zero+=1        
if k>n-zero:
    print(0)
    sys.exit()

A=list(reversed(sorted(A)))
cnt=0
for i in range(k):
    cnt+=A[i][1]
chk=0
for i in range(n-zero):
    chk+=A[i][1]
    
if cnt%2==0:
    ans=1
    for i in range(k):
        ans=ans*A[i][0]%mod
    print(ans)
elif chk==n-zero:
    if zero>0:
        print(0)
        sys.exit()
    ans=1
    for i in range(k):
        ans=ans*A[n-i-1][0]%mod
    print((-ans)%mod)
elif k==n-zero:
    print(0)
else:
    if A[k][1]==0:
        p=A[k][0]
        m=0
        for i in range(k+1,n-zero):
            if A[i][1]==1:
                m=A[i][0]
                break
    else:
        m=A[k][0]
        p=0
        for i in range(k+1,n-zero):
            if A[i][1]==0:
                p=A[i][0]
                break
    #print(m,p)
    if A[k-1][1]==0:
        l=0
        for i in range(k-1):
            if A[k-i-2][1]==1:
                l=A[k-i-2][0]
                Xl=k-i-2
                break
        #print(l,k)
        if m*l>p*A[k-1][0]:
            ans=1
            for i in range(k-1):
                ans=ans*A[i][0]%mod
            ans=ans*m%mod
            print(ans)
        else:
            ans=1
            for i in range(k):
                if i==Xl:
                    continue
                ans=ans*A[i][0]%mod 
            ans=ans*p%mod
            print(ans)
    else:
        l=0
        for i in range(k-1):
            if A[k-i-2][1]==0:
                l=A[k-i-2][0]
                Xl=k-i-2
                break
        #print(l,k)
        if p*l>m*A[k-1][0]:
            ans=1
            for i in range(k-1):
                ans=ans*A[i][0]%mod
            ans=ans*p%mod
            print(ans)
        else:
            ans=1
            for i in range(k):
                if i==Xl:
                    continue
                ans=ans*A[i][0]%mod 
            ans=ans*m%mod
            print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = 10**9+7
p = []
q = []
r = []
for i in range(N):
    if A[i] > 0:
        p.append(A[i])
    elif A[i] < 0:
        q.append(A[i])
    else:
        r.append(A[i])
p.sort()
q.sort()
P = len(p)
Q = len(q)
if P+Q < K:
    print(0)
    exit()
if P > 0:
    if P+Q == K:
        ans = 1
        for i in range(P):
            ans = ans * p[i] % m
        for i in range(Q):
            ans = ans * q[i] % m
        print(ans)
    else:
        i = K
        j = 0
        while i > P:
            i -= 2
            j += 2
            
        while i >= 0 and j < Q-1:
            if p[P-i]*p[P-i+1] < q[Q-j-1]*q[Q-j-2]:
                i -= 2
                j += 2
            else:
                break
        ans = 1
        for k in range(max(0,i)):
            ans = ans * p[P-k-1] % m
        for l in range(min(Q,j)):
            ans = ans * q[Q-l-1] % m
        print(ans)
else:
    if K % 2 == 0:
        if Q >= K:
            ans = 1
            for i in range(K):
                ans = ans * q[Q-1-i] % m
            print(ans)
        else:
            print(0)
    else:
        if len(r) > 0:
            print(0)
        else:
            ans = 1
            for i in range(K):
                ans = ans * q[Q-1-i] % m
            print(ans)

Submission status: Runtime Error

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

A.sort(reverse=True)

P = []
M = []
Ans = []
p = 0
m = 0

for i in range(N):
    if 0 <= A[i]:
        P.append(A[i])
    else:
        M.append(A[i])

M.sort()

if K % 2 == 1 and len(P) != 0:
    Ans.append(P[p])
    p += 1
elif K % 2 == 1 and len(P) == 0:
    M.sort(reverse=True)

while len(Ans) < K:

    #Mのストックがもうない時
    if m >= len(M):
        Ans.append(P[p])
        if len(Ans) == K:
            break
        Ans.append(P[p + 1])
        p += 2
    elif p >= len(P):
        Ans.append(M[m])
        if len(Ans) == K:
            break
        Ans.append(M[m + 1])
        m += 2
    else:
        if P[p]*P[p+1] < M[m]*M[m+1]:
            Ans.append(M[m])
            Ans.append(M[m+1])
            m += 2
        else:
            Ans.append(P[p])
            Ans.append(P[p + 1])
            p += 2

answer = 1
for i in range(K):
    answer = (answer * Ans[i]) % 1000000007

print(answer)

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]
        elif len(A_neg) >= 2:
            c2 = A_neg[-1] * A_neg[-2]
        else:
            ret = 0

        if 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:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod = 10**9 + 7
positive=list()
negative=list()

for i in range(n):
    if a[i]>=0:
        positive.append(a[i])
    else:
        negative.append(a[i])


if len(positive)==0:
    negative=sorted(negative,reverse=True)
    cnt=0
    ans=1
    for i in negative:
        if cnt<k:
            ans*=i
            cnt+=1    

    if cnt<k:
        ans=0
    print(ans%mod)
    exit(0)

positive=sorted(positive,reverse=True)
negative=sorted(negative)


from collections import deque

ans=deque([])
positive=deque(positive)
negative=deque(negative)



while len(ans)<k:
    if len(positive)!=0:
        posi=positive.popleft()
    else:
        posi=0
    
    if len(negative)!=0:
        nega=negative.popleft()
    else:
        nega=0

    if posi>=abs(nega):
        ans.append(posi)
        
        negative.appendleft(nega)

    elif posi<abs(nega):
        ans.append(nega)
        ans.append(negative.popleft())

        positive.appendleft(posi)

    
    if len(ans)>k:
        ans.pop()
        ans.pop()
        ans.append(posi)

answer=1

for j in ans:
    answer*=j

print(answer%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 k > pos:
        if zeroes:
            print("0")
        else:
            # last pr pakka negative ayega
            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
        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)

    # 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
    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(map(int, input().split()))
mod = 10**9 + 7

positive = []
negative = []
zero = 0
for t in a:
    if t < 0:
        negative.append(t)
    elif t == 0:
        positive.append(0)
        zero += 1
    else:
        positive.append(t)
if n - zero < k:
    print(0)
    exit()

positive.sort()
negative.sort(reverse=True)

if not positive:
    ans = 1
    if k % 2 == 1:
        if zero != 0:
            print(0)
            exit()
        for i in range(k):
            ans *= negative[i]
            ans %= mod
    else:
        for i in range(k):
            ans *= negative.pop()
            ans %= mod
    print(ans)
    exit()

ans = 1
# negative 処理
check = []
for i in reversed(range(len(negative) % 2, len(negative), 2)):
    check.append(negative[i+1] * negative[i])
# positive

if k % 2 == 1:
    ans *= positive.pop()
    k -= 1

for i in reversed(range(len(positive) % 2, len(positive), 2)):
    check.append(positive[i+1] * positive[i])
check.sort()

for i in range(k//2):
    ans *= check.pop()
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
MOD = pow(10,9)+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
P = []; M = []; Z = []
for i in range(N):
  if A[i] >0:
    P.append(A[i])
  elif A[i] <0:
    M.append(A[i])
  else:
    Z.append(0)
P.sort(reverse=True)
M.sort(reverse=True)
ans = 1
if K == 1:
  print(P[0]%MOD)
  exit()
if len(Z) > N-K:
  print(0)
  exit()
if len(M) == 0: #全て正の場合。0があれば0
  for i in range(K):
    ans = ans*P[i]%MOD
  print(ans)
  exit()
if len(P) == 0: #全て負の場合
  if K%2 == 1 and len(Z) > 0:
    print(0)
    exit()
  if K%2 == 1:
    for i in range(K):
      ans = ans*M[i]%MOD
  else:
    M.sort()
    for i in range(K):
      ans = ans*M[i]%MOD
  print(ans)
  exit()

L = [[],[]]
M.sort()
P = deque(P); M = deque(M)
pm = [0,0] #正負の数を保存
pnow = 0; mnow = 0
#print(P,M)

for i in range(K):
  if not P:
    temp = M.popleft()
    pm[1] +=1
    L[1].append(temp)
  elif not M:
    temp = P.popleft()
    pm[0] +=1
    L[0].append(temp)
  elif P and M:
    if P[0] >= abs(M[0]):
      temp = P.popleft()
      pm[0] += 1
      L[0].append(temp)
    else:
      temp = M.popleft()
      pm[1] += 1
      L[1].append(temp)
#一個ずらす
print(L)

if pm[1]%2 == 1:
  if not P and not M:
    pass
  elif not M: #もう負の数が残っていない
    L[1].pop()
    L[0].append(P[0])
  elif not P: #もう正の数が残っていない
    L[0].pop()
    L[1].append(M[0])
  elif M and P:
    if L[0][-1]*P[0] >= L[1][-1]*M[0]:
      L[1].pop()
      L[0].append(P[0])
    else:
      L[0].pop()
      L[1].append(M[0])
print(L)    
for num in range(2):
  for s in L[num]:
    ans = ans*s%MOD
print(ans)

Submission status: Runtime Error

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  l=LI()

  zero_contain=False
  if l.count(1):
    zero_contain=True

  al=[]
  for x in l:
    al.append((abs(x),x))

  al=sorted(al,key=lambda x:x[0],reverse=True)

  zero=False
  minus=0

  ansl=[]
  for ax,x in al[:k]:
    if x==0:
      zero=True
    if x<0:
      minus+=1
    ansl.append(x)

  ans=1
  for x in ansl:
    if x==0:
      ans=0
      break
    elif x>0:
      pass
    else:
      ans*=-1

  if ans>0:
    ans=1
    for x in ansl:
      ans*=x
      ans%=mod
    return ans
  elif ans<0:
    for x in ansl[::-1]:
      if x<0:
        t=x
        ansl2=copy.deepcopy(ansl)
        ansl2.remove(t)
        break
    ff=False
    for ax,x in al[k:]:
      if x>=0:
        ans2.append(x)
        ff=True
        break
    if not ff:
      ansl2=[]
      for ax,x in al[::-1][:k]:
        ansl2.append(x)

    ans2=1
    for x in ansl2:
      ans2*=x
      ans2%=mod

    # print(ans,ans2)

    ans=1
    for x in ansl:
      ans*=x
      ans%=mod

    return max(ans,ans2)
  else:
    return 0

# main()
print(main())

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 1000000007

zeros = []
pluss = []
minuss = []

for i in range(N):
    if A[i]>0:
        pluss.append(A[i])
    elif A[i]==0:
        zeros.append(A[i])
    else:
        minuss.append(A[i])

pluss = sorted(pluss, reverse = True)
minuss = sorted(minuss)


if len(pluss) + (min(len(minuss), K)//2)*2 >= K:
    answer_type = 1
elif len(zeros) > 0:
    answer_type = 2
else:
    answer_type = 3

rest = K
if answer_type == 1:
    plus_now = 0
    minus_now = 0
    minus_counter = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = -1000000000000
        
        if minus_now < len(minuss):
            minus_target = minuss[minus_now]
        else:
            minus_target = 1000000000000
        
        if plus_target >= -minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
            minus_counter += 1
            
    if minus_counter%2 == 1:
        answer = answer * pow(minuss[minus_now-1],mod-2,mod)
        answer = answer * pluss[plus_now]
elif answer_type == 2:
    answer = 0
elif answer_type == 3:
    minuss = sorted(minuss, reverse = True)
    pluss = sorted(pluss, reverse = True)
    plus_now = 0
    minus_now = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = 10000000000000
        
        if minus_now < len(minuss):
            minus_target = minuss[minus_now]
        else:
            minus_target = -1000000000000  
        
        if plus_target <= -minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
print(answer%mod)

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for _ in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")
tests = lambda: range(1, int_in() + 1)
case_out = lambda i, o: out("Case #{}: {}".format(i, o))


def solve(n, k, a):
    a.sort(reverse=True)
    result = 1
    mod = pow(10, 9) + 7
    p_front = 0
    p_back = len(a) - 1
    found = 0
    was_zero = False
    while found < k:
        if a[p_front] == 0:
            if k - found >= p_back - p_front:
                p_front += 1
                was_zero = True
                continue
            else:
                return 0
        if a[p_front] < 0 and (k - found) % 2 == 1:
            if was_zero:
                return 0
            for i in range(p_front, p_front + k - found):
                result *= a[i]
                result %= mod
            return result

        changed = False
        if k - found >= 2 and p_front + 1 < len(a) and p_back - 1 >= 0:
            if a[p_front] * a[p_front + 1] < a[p_back] * a[p_back - 1]:
                result *= a[p_back]
                result %= mod
                result *= a[p_back - 1]
                result %= mod
                p_back -= 2
                found += 2
                changed = True
        if not changed:
            result *= a[p_front]
            result %= mod
            p_front += 1
            found += 1
    return result % mod


if __name__ == "__main__":
    n, k = arr_in()
    a = arr_in()
    out(solve(n, k, a))

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 = 0
        if i != 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:
#coding: UTF-8
import itertools
from scipy.special import comb

split = input().split()
n,k = int(split[0]),int(split([1]))
inList = list(map(int, input().split()))

#n,k = 4,2
#inList = [1, 2, -3, -4]
out = 0
for v in itertools.combinations(inList, 2):
    tmp = 1
    for i in range(len(v)):
        tmp = tmp*v[i]
    if tmp > out: out = tmp
print(tmp)

Submission status: Runtime Error

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

A.sort(reverse=True)

P = []
M = []
Ans = []
p = 0
m = 0

for i in range(N):
    if 0 <= A[i]:
        P.append(A[i])
    else:
        M.append(A[i])

M.sort()

if K % 2 == 1 and len(P) != 0:
    Ans.append(P[p])
    p += 1
elif K % 2 == 1 and len(P) == 0:
    M.sort(reverse=True)

while len(Ans) < K:

    #Mのストックがもうない時
    if m+1 >= len(M):
        Ans.append(P[p])
        if len(Ans) == K:
            break
        Ans.append(P[p + 1])
        p += 2
    elif p+1 >= len(P):
        Ans.append(M[m])
        if len(Ans) == K:
            break
        Ans.append(M[m + 1])
        m += 2
    else:
        if P[p]*P[p+1] < M[m]*M[m+1]:
            Ans.append(M[m])
            Ans.append(M[m+1])
            m += 2
        else:
            Ans.append(P[p])
            Ans.append(P[p + 1])
            p += 2

answer = 1
for i in range(K):
    answer = (answer * Ans[i]) % 1000000007

print(answer)

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
        if cnt < K:
            ans *= P[cnt_p]
            ans *= M[cnt_m]
            ans %= MOD
        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
        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]
            if diff > 1:
                ret *= diff
                ret //= 1
                diff = 1
        ret %= MOD
        print(ret)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
MOD = 10**9+7


def least_product(negatives, k):
    ret = 1
    for i in negatives[-k:]:
        ret *= i
    return ret % MOD


def max_product(positives, negatives, k):
    num_products = 0
    pos_index = 0
    neg_index = 0
    ret = 1
    while k - num_products > 1:
        if pos_index + 1 < len(positives) and neg_index + 1 < len(negatives) and positives[pos_index] * positives[pos_index + 1] <= negatives[neg_index] * negatives[neg_index + 1]:
            ret *= negatives[neg_index] * negatives[neg_index + 1]
            ret %= MOD
            num_products += 2
            neg_index += 2
        else:
            ret *= positives[pos_index]
            ret %= MOD
            num_products += 1
            pos_index += 1
    if k - num_products == 1:
        ret *= positives[pos_index]
        ret %= MOD
    return ret


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    negatives = list(filter(lambda x: x < 0, A))
    positives = list(filter(lambda x: x > 0, A))
    negatives.sort()
    positives.sort()
    positives.reverse()
    if len(positives) + len(negatives) < K:
        print(0)
    elif len(positives) + len(negatives) == K:
        if len(negatives) % 2 == 1:
            if N - len(positives) - len(negatives) > 0:
                print(0)
            else:
                # print(least_product(positives, negatives, K))
                ans = 1
                for a in A:
                    ans *= a
                    ans %= MOD
                print(ans)
                # negative
        else:
            print(max_product(positives, negatives, K))
            # postive
    elif len(positives) + len(negatives) > K:
        if len(positives) > 0:
            print(max_product(positives, negatives, K))
            # postive
        else:
            print(least_product(negatives, K))


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
    an = sorted([i for i in a if i < 0])
    ap = sorted([i for i in a if i > 0], reverse = True)
    a_s = list(sorted(a, key = lambda x: -abs(x)))
    num_n = 0
    num_p = 0
    zero = False
    ans = 1
    old_n = 0
    ald_p = 0
    if k == 1:
        print(max(a))
        return
    for ai in a_s[:k]:
        if ai < 0:
            old_n = ai
            num_n += 1
        elif ai > 0:
            old_p = ai
            num_p += 1
        else:
            zero = True
    if zero:
        print(0)
        return
    if num_n%2 == 0:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    elif len([i for i in a if i > 0]) == 0:
        a_sr = list(sorted(a, reverse=True))[:k]
        for ai in a_sr:
            ans *= ai
            ans %= mod
        print(ans)
        return
    else:
        next_n = 0
        next_p = 0
        for i in a_s[k:]:
            if i < 0:
                next_n = i
                break
        for i in a_s[k:]:
            if i > 0:
                next_p = i
                break
        if old_p*next_p > old_n*next_n or next_n == 0:
            for ai in a_s[:k]:
                if ai == old_n:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_p
            ans %= mod
            print(ans)
            return
        else:
            for ai in a_s[:k]:
                if ai == old_p:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_n
            ans %= mod
            print(ans)
            return
        

if __name__ == "__main__":
    main()