Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

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

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

Constraints

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

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

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

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

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

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

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

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

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

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

Sample Input 4

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

Sample Output 4

999983200

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



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys

def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    A_list = list(map(int, sys.stdin.readline().split()))

    A_plus = []
    A_minus = []
    mod = 10**9 + 7

    for val in A_list:
        if val >= 0:
            A_plus.append(val)
        else:
            A_minus.append(val)


    A_plus.sort(reverse=True)
    A_minus.sort()

    if (not A_plus):
        ans = 1

        for i in range( len(A_minus)-K, len(A_minus) ):
            ans *= A_minus[i]
            ans %= mod
        
        print(ans)
        return


    if (not A_minus):
        ans = 1

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


    select = []
    i_p = 0  # index of A_plus
    i_m = 0  # index of A_minus

    while (len(select) < K):
        if (K - len(select)) == 1:
            select.append( A_plus[i_p] )
            i_p += 1
            break

        if (i_m + 1) < len(A_minus):
            if (i_p + 1) < len(A_plus):
                if abs( A_plus[i_p] * A_plus[i_p + 1] ) > abs( A_minus[i_m] * A_minus[i_m + 1] ):
                    select.append( A_plus[i_p] )
                    i_p += 1
                else:
                    select.extend( [ A_minus[i_m] , A_minus[i_m + 1] ] )
                    i_m += 2

            else:
                select.extend( [ A_minus[i_m] , A_minus[i_m + 1] ] )
                i_m += 2
            
        else:
            select.append( A_plus[i_p] )
            i_p += 1
    


    ans = 1
 
    for i in range(K):
        ans *= select[i]
        ans %= mod
    
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys

def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    A_list = list(map(int, sys.stdin.readline().split()))

    A_plus = []
    A_minus = []
    mod = 10**9 + 7

    for val in A_list:
        if val >= 0:
            A_plus.append(val)
        else:
            A_minus.append(val)


    A_plus.sort(reverse=True)
    A_minus.sort()

    if (not A_plus):
        ans = 1

        for i in range( len(A_minus)-K, len(A_minus) ):
            ans *= A_minus[i]
            ans %= mod
        
        print(ans)
        return


    if (not A_minus):
        ans = 1

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


    select = []
    i_p = 0  # index of A_plus
    i_m = 0  # index of A_minus

    while (len(select) < K) and (i_p < len(A_plus)) and (i_m < len(A_minus)):
        if (K - len(select)) == 1:
            select.append( A_plus[i_p] )
            i_p += 1
            break

        if (i_m + 1) < len(A_minus):
            if (i_p + 1) < len(A_plus):
                if abs( A_plus[i_p] * A_plus[i_p + 1] ) > abs( A_minus[i_m] * A_minus[i_m + 1] ):
                    select.append( A_plus[i_p] )
                    i_p += 1
                else:
                    select.extend( [ A_minus[i_m] , A_minus[i_m + 1] ] )
                    i_m += 2

            else:
                select.extend( [ A_minus[i_m] , A_minus[i_m + 1] ] )
                i_m += 2
            
        else:
            select.append( A_plus[i_p] )
            i_p += 1
    


    ans = 1
 
    for i in range(K):
        ans *= select[i]
        ans %= mod
    
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,k=input().split()
n=int(n)
k=int(k)
clist=list(map(int,input().split()))
clist.sort()
product1=1
product2=1

for i in clist[0:k+1]:
  product1=product1*i
for i in clist[-k:]:
  product2=product2*i
  
print(max(product1,product2)%(1e9+7))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys

def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    A_list = list(map(int, sys.stdin.readline().split()))


    A_list.sort(key=lambda x: -abs(x))
    mod = 10**9 + 7

    L_plus  = R_plus  = -1 # the Index of plus value
    L_minus = R_minus = -1 # the Index of minus value
    # L : between index 0 to (K-1)
    # R : between index K to end


    for i in range(K-1, -1, -1):
        if (L_plus == -1) and (A_list[i] >= 0):
            L_plus = i
        if (L_minus == -1) and (A_list[i] < 0):
            L_minus = i
        if (L_plus != -1) and (L_minus != -1):
            break
    
    for i in range(K,N):
        if (R_plus == -1) and (A_list[i] >= 0):
            R_plus = i
        if (R_minus == -1) and (A_list[i] < 0):
            R_minus = i
        if (R_plus != -1) and (R_minus != -1):
            break
    

    if L_plus == R_plus == -1:
        ans = 1

        for i in range( N-K , N ):
            ans *= A_list[i]
            ans %= mod

        print(ans)
        return



    cnt_minus = 0

    for i in range(K):
        if A_list[i] < 0:
            cnt_minus += 1


    if cnt_minus % 2 != 0:
        if (L_minus != -1) and (R_plus != -1):
            calc1 = A_list[L_plus] * A_list[R_plus]
        else:
            calc1 = 0
        
        if (L_plus != -1) and (R_minus != -1):
            calc2 = A_list[L_minus] * A_list[R_minus]
        else:
            calc2 = 0


        if calc1 > calc2:
            A_list[L_minus], A_list[R_plus] = A_list[R_plus], A_list[L_minus]
            target = A_list[:K]

        elif calc1 < calc2:
            A_list[L_plus], A_list[R_minus] = A_list[R_minus], A_list[L_plus]
            target = A_list[:K]
    
    else:
        target = A_list[:K]


    ans = 1

    for i in range(len(target)):
        ans *= target[i]
        ans %= mod
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

import collections
import math

"""
#### 入力例 ####
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())
"""

N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10**9 +7

def main():
    ans = 1
    A.sort(reverse=True)
    if N == K:
        for n in range(N):
            ans*=A[n]
        print(ans % mod)
        return
    
    M = collections.deque()
    P = collections.deque()
    for n in range(N):
        if A[n] < 0:
            M.append(A[n])
        else:
            P.append(A[n])

    if len(P) == 0:
        if(K%2 == 1):
            for k in range(K):
                ans *= M.popleft()
            print(ans % mod)
            return
        else:
            for k in range(K):
                ans *= M.pop()
            print(ans%mod)
            return
    
    
    S = collections.deque()
    while len(S) != K:
        p_stock = 0
        m_stock = 0
        if not len(M) < 2:
            m_stock = M[-1]*M[-2]
        if not len(P) < 2:
            p_stock = P[0]*P[1]
        if len(S) == K-1 or m_stock < p_stock:
            S.append(P.pop())
        else:
            S.append(M.pop())
            S.append(M.pop())
    while len(S) != 0:
        ans *= S.pop()
    print(ans%mod)
    return
    

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

X = sorted([a for a in A if a > 0])
Y = sorted([a for a in A if a < 0], key=lambda x: abs(x))

if 2 * (min(K, len(Y)) // 2) + len(X) >= K:
    ans = 1
    if K % 2 == 1:
        ans *= X.pop()
        K -= 1

    XX = [(x1 * x2) for x1, x2 in zip(*[iter(X[::-1])] * 2)]
    YY = [(y1 * y2) for y1, y2 in zip(*[iter(Y[::-1])] * 2)]
    ZZ = sorted(XX + YY)

    for i in range(K // 2):
        ans *= ZZ.pop()
        ans %= MOD

    print(ans)

else:
    ans = 1
    Z = sorted(X + Y, key=lambda x: abs(x), reverse=True)
    for i in range(K):
        ans *= Z.pop()
        ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
cnt_plus=0
cnt_zero=0
cnt_minus=0
arr_plus=[]
arr_minus=[]
for i in range(n):
  if arr[i]>0:
    cnt_plus+=1
    arr_plus.append(arr[i])
  elif arr[i]<0:
    cnt_minus+=1
    arr_minus.append(-arr[i])
  else:
    cnt_zero+=1
if cnt_plus+cnt_minus<k: #K個の積の中に0を含む場合、答えは0
  print(0)
  exit()
if k==n: #K=Nの場合
  if cnt_zero!=0: #0がひとつでもあれば答えは0
    print(0)
  else:
    ans=1
    for i in range(cnt_plus):
      ans*=arr_plus[i]
      ans%=mod
    for i in range(cnt_minus):
      ans*=arr_minus[i]
      ans%=mod
    if cnt_minus%2==0: #負の数が偶数個であれば積は正
      print(ans)
    else: #そうでなければ積は負となる
      print((-ans)%mod)
  exit()
if cnt_plus==0 and k%2==1: #正の数がないとき
  if cnt_zero!=0: #0がひとつでもあれば答えは0にできる
    print(0)
  else: #0がないときは負の数を絶対値が小さい順に掛けるのが最善
    arr_minus=sorted(arr_minus)
    tmp=1
    for i in range(k):
      tmp*=arr_minus[i]
      tmp%=mod
    print((-tmp)%mod)
  exit()
else: #正の数と負の数から合計K個取れるとき
  arr_plus=sorted(arr_plus,reverse=True)
  arr_minus=sorted(arr_minus,reverse=True)
  if k%2==0: #Kが偶数であれば何もしない
    ans=1
    pos_plus=0
    pos_minus=0
    cnt=0
  else: #Kが奇数であれば正の数から最大のものを取っておき、Kが偶数の場合に帰着させる
    ans=arr_plus[0]
    pos_plus=1
    pos_minus=0
    cnt=1
  while cnt<k:
    cand1=0
    if pos_plus<=cnt_plus-2: #正の数を2つ取れるなら取る
      cand1=arr_plus[pos_plus]*arr_plus[pos_plus+1]      
    cand2=0
    if pos_minus<=cnt_minus-2 #負の数を2つ取れるなら取る:
      cand2=arr_minus[pos_minus]*arr_minus[pos_minus+1]
    if cand1>=cand2: #正の数を2つ取った積のほうが大きい場合
      pos_plus+=2
      ans*=cand1
      ans%=mod
    else: #負の数を2つ取った積のほうが大きい場合
      pos_minus+=2
      ans*=cand2
      ans%=mod
    cnt+=2
  print(ans)
  exit()

Submission status: Runtime Error

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

a=sorted(a,reverse=True,key=lambda x:abs(x))

if k==n:
  ans=1
  for i in range(n):
    ans *= a[i]
    ans %= mod
  print(ans)
else:
  if k%2 and a[0]<0:
    ans=1
    for i in range(k):
      ans *=a[n-i+1]
      ans %= mod
    print(ans)
  else:
    ans=1
    count=0
    for i in range(k):
      if a[i]<0:
        count +=1
      ans *= a[i]
      ans %= mod
    if count%2==0:
      print(ans)
    else:
      min_plus=-1 #Kこの中の絶対値最小の非負数
      min_minus=1 #Kこの中の絶対値最大の負数
      for i in range(k):
        if a[i]<0:
          min_minus=a[i]
        else:
          min_plus=a[i]
      max_plus=-1 #N-Kこの中の絶対し最小の非負数
      max_minus=1 #N-Kこの中の絶対値最大の負数
      for i in range(k,n):
        if a[i]<0:
          max_minus=a[i]
          break
      for i in range(k,n):
        if a[i]>=0:
          max_plus=a[i]
          break
      if min_plus=-1: #Kこの中に非負数が存在しない
        a.remove(min_minus)
        ans=1
        for i in range(k-1):
          ans *= a[i]
          ans %= mod
        ans*=max_plus
        print(ans)
      elif min_minus=1: #Kこの中に負数が存在しない
        a.remove(min_plus)
        ans=1
        for i in range(k-1):
          ans *= a[i]
          ans %= mod
        ans*=max_minus
        print(ans) 
      elif min_plus*max_plus>=min_minus*max_minus: #Kこの中に非負数が存在しない
        a.remove(min_plus)
        ans=1
        for i in range(k-1):
          ans *= a[i]
          ans %= mod
        ans*=max_minus
        print(ans) 
      else:
        a.remove(min_minus)
        ans=1
        for i in range(k-1):
          ans *= a[i]
          ans %= mod
        ans*=max_plus
        print(ans)

Submission status: Runtime Error

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

    #絶対値で大きい順にソート
    absort_a = sorted(a,key=abs,reverse=True)

    #絶対値で大きい順にｋ個抽出
    ksel = absort_a[:k]

    #負の数をカウント
    under0 = [i for i in ksel if i < 0]
    u0num = len(under0)

    #正の数もカウント
    over0 = [i for i in ksel if i >= 0]
    
    # 正負を区別してそれぞれでソート
    sortu0 = sorted(under0)
    sorto0 = sorted(over0)
    
    ans = 1
    for i in ksel:
        ans *= i

    if (u0num % 2 == 0) or not(u0num) or (n == k):
        print(ans % (10**9+7))

    else:
        # 負の数で絶対値が最も小さな数字を、選ばれていない最も大きな正数と交換
        min_u0 = sortu0[0]
        max_o0 = sorto0[-1]
        ans1 = ans // min_u0 * max_o0

        # 正の数で最も小さな数字を、選ばれていない絶対値が最も大きな負数と交換
        min_o0 = sorto0[0]
        max_u0 = sortu0[-1]
        ans2 = ans // min_o0 * max_u0

        if ans1 > ans2:
            print(ans1 % (10**9+7))
        else:
            print(ans2 % (10**9+7))
main()

Submission status: Runtime Error

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

    #絶対値で大きい順にソート
    absort_a = sorted(a,key=abs,reverse=True)

    #絶対値で大きい順にｋ個抽出
    ksel = absort_a[:k]

    #負の数をカウント
    under0 = [i for i in ksel if i < 0]
    u0num = len(under0)

    #正の数もカウント
    over0 = [i for i in ksel if i >= 0]

    ans = 1
    for i in ksel:
        ans *= i

    if (u0num % 2 == 0) or not(u0num) or (n == k):
        print(ans % (10**9+7))

    else:
        # 負の数で絶対値が最も小さな数字を、選ばれていない最も大きな正数と交換
        min_u0 = sorted(under0,reverse=True)[-1]
        max_o0 = sorted(over0)[-1]
        ans1 = ans // min_u0 * max_o0

        # 正の数で最も小さな数字を、選ばれていない絶対値が最も大きな負数と交換
        min_o0 = sorted(over0,reverse=True)[-1]
        max_u0 = sorted(over0)[-1]
        ans2 = ans // min_o0 * max_u0

        if ans1 > ans2:
            print(ans1 % (10**9+7))
        else:
            print(ans2 % (10**9+7))
main()

Submission status: Runtime Error

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

#絶対値で大きい順にソート
absort_a = sorted(a,key=abs,reverse=True)

#絶対値で大きい順にｋ個抽出
ksel = absort_a[:k]

print(ksel)

#負の数をカウント
under0 = [i for i in ksel if i < 0]
u0num = len([i for i in ksel if i < 0])

print(under0)


#正の数もカウント
over0 = [i for i in ksel if i > 0]

ans = 1
for i in ksel:
    ans *= i
    
if (u0num % 2 == 0) or not(u0num):
    print(ans % (10**9+7))

else:
    # 負の数で絶対値が最も小さな数字を、選ばれていない最も大きな正数と交換
    min_u0 = sorted(under0,reverse=True)[-1]
    max_o0 = sorted(over0)[-1]
    ans1 = ans // min_u0 * max_o0
    
    # 正の数で最も小さな数字を、選ばれていない絶対値が最も大きな負数と交換
    min_o0 = sorted(over0,reverse=True)[-1]
    max_u0 = sorted(over0)[-1]
    ans2 = ans // min_o0 * max_u0
    
    if ans1 > ans2:
        print(ans1 % (10**9+7))
    else:
        print(ans2 % (10**9+7))

Submission status: Runtime Error

Solution code:
from functools import reduce

N, K = map(int, input().split())
A = list(map(int, input().split()))
Ap = [a for a in A if a>0]
Am = [a for a in A if a<0]
mod = 10**9+7
if len(Ap) + len(Am) < K:
    print(0)
    exit()
if len(Ap) + len(Am) == K:
    if 0 in A and len(Am) % 2:
        print(0)
    else:
        ans = reduce(lambda a, b: a * b % mod, Ap+Am, 1)
        print(ans)
    exit()
Ap.sort(reverse=True)
Am.sort()
if len(Ap) == 0 and K%2==0:
    ans = reduce(lambda a, b: a*b%mod, Am[-K:], 1)
    print(ans)
    exit()

idx_Am = 0
n = 0
ans = 1
for idx_Ap, ap in enumerate(Ap+[0]):
    while idx_Am < len(Am) and n < K and -Am[idx_Am] > ap:
        ans = ans * Am[idx_Am] % mod
        idx_Am += 1
        n += 1
    if n == K:
        break
    n += 1
    idx_Ap += 1
    ans = ans * ap % mod
    if n == K:
        break
else:
    assert False
if idx_Am % 2 == 0:
    print(ans)
else:
    if idx_Ap == len(Ap) or (idx_Am != len(Am) and Am[idx_Am] * Am[idx_Am-1] > Ap[idx_Ap] * Ap[idx_Ap-1]):
        ans = ans * Am[idx_Am] * pow(Ap[idx_Ap-1], mod-2, mod) % mod
    else:
        ans = ans * Ap[idx_Ap] * pow(Am[idx_Am-1], mod-2, mod) % mod
    print(ans)

Submission status: Runtime Error

Solution code:
from functools import reduce

N, K = map(int, input().split())
A = list(map(int, input().split()))
Ap = [a for a in A if a>0]
Am = [a for a in A if a<0]
mod = 10**9+7
if len(Ap) + len(Am) < K:
    print(0)
    exit()
if len(Ap) + len(Am) == K:
    if 0 in A and len(Am) % 2:
        print(0)
    else:
        ans = reduce(lambda a, b: a * b % mod, Ap+Am, 1)
        print(ans)
    exit()
Ap.sort(reverse=True)
Am.sort()
if len(Ap) == 0 and K%2:
    ans = reduce(lambda a, b: a*b%mod, Am[-K:], 1)
    print(ans)
    exit()
assert False

Submission status: Runtime Error

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

import bisect
import copy
import collections
import heapq
import itertools
import math
from operator import itemgetter
import scipy.misc

"""
#### 入力例 ####
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())
"""

N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10**9 +7

def main():
    ans = 1
    A.sort(reverse=True)
    if N == K:
        for n in range(N):
            ans*=A[n]
        print(ans % mod)
        return
    
    M = collections.deque()
    P = collections.deque()
    for n in range(N):
        if A[n] < 0:
            M.append(A[n])
        else:
            P.append(A[n])

    if len(P) == 0:
        if(K%2 != 0):
            for k in range(K):
                ans *= M.popleft()
            print(ans % mod)
            return
        else:
            for k in range(K):
                ans *= M.pop()
            print(ans%mod)
            return
    
    if K % 2 == 1:
        ans *= P.popleft()
    
    p_stock = 0
    m_stock = 0
    M = list(M)
    print(M)
    P = list(P)
    idx_p = 0
    idx_m = 0
    for k in range(0, K//2, 2):
        if  len(M)-1 <= idx_m:
            ans *= P[idx_p] * P[idx_p +1 ]
            idx_p += 2
            
        elif len(P)-1 <= idx_p:
            ans *= M[idx_m] * M[idx_m + 1]  
            idx_m += 2
        elif idx_m < len(M)-1 and idx_p < len(P) -1:
            m_stock = M[idx_m] * M[idx_m + 1] 
            p_stcok = P[idx_p] * P[idx_p + 1]
            if m_stock < p_stcok:
                ans *= p_stock
                idx_p += 2
            else:
                ans *= m_stock
                idx_m += 2
        else:
            break

    print(ans%mod)
    return
    

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

import bisect
import copy
import collections
import heapq
import itertools
import math
import numpy as np
from operator import itemgetter
import scipy.misc
import sys

"""
#### 入力例 ####
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())
"""

N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10**9 +7

def main():
    ans = 1
    A.sort(reverse=True)
    if N == K:
        for n in range(N):
            ans*=A[n]
        print(ans % mod)
        return
    
    M = collections.deque()
    P = collections.deque()
    for n in range(N):
        if A[n] < 0:
            M.append(A[n])
        else:
            P.append(A[n])

    if len(P) == 0:
        if(K%2 != 0):
            for k in range(K):
                ans *= M.popleft()
            print(ans % mod)
            return
        else:
            for k in range(K):
                ans *= M.pop()
            print(ans%mod)
            return
    
    if K % 2 == 1:
        ans *= P.popleft()
    
    p_stock = 0
    m_stock = 0
    M = list(M)
    print(M)
    P = list(P)
    idx_p = 0
    idx_m = 0
    for k in range(0, K//2, 2):
        if  len(M)-1 <= idx_m:
            ans *= P[idx_p] * P[idx_p +1 ]
            idx_p += 2
            
        elif len(P)-1 <= idx_p:
            ans *= M[idx_m] * M[idx_m + 1]  
            idx_m += 2
        elif idx_m < len(M)-1 and idx_p < len(P) -1:
            m_stock = M[idx_m] * M[idx_m + 1] 
            p_stcok = P[idx_p] * P[idx_p + 1]
            if m_stock < p_stcok:
                ans *= p_stock
                idx_p += 2
            else:
                ans *= m_stock
                idx_m += 2
        else:
            break

    print(ans%mod)
    return
    

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from functools import reduce

N, K = map(int, input().split())
A = list(map(int, input().split()))
Ap = [a for a in A if a>0]
Am = [a for a in A if a<0]
mod = 10**9+7
if len(Ap) + len(Am) < K:
    print(0)
    exit()
if len(Ap) + len(Am) == K:
    if 0 in A and len(Am) % 2:
        print(0)
    else:
        ans = reduce(lambda a, b: a * b % mod, Ap+Am, 1)
        print(ans)
    exit()
Ap.sort(reverse=True)
Am.sort()
if len(Ap) == 0 and K%2:
    ans = reduce(lambda a, b: a*b%mod, Am[-K:], 1)
    print(ans)
    exit()
idx_Am = 0
n = 0
ans = 1
for idx_Ap, ap in enumerate(Ap):
    while idx_Am < len(Am) and n < K and -Am[idx_Am] > ap:
        ans = ans * Am[idx_Am] % mod
        idx_Am += 1
        n += 1
    if n == K:
        break
    n += 1
    idx_Ap += 1
    ans = ans * ap % mod
    if n == K:
        break
else:
    assert False
if idx_Am % 2 == 0:
    print(ans)
else:
    if idx_Ap == len(Ap) or (idx_Am != len(Am) and -Am[idx_Am] / Ap[idx_Ap-1] > Ap[idx_Ap] / -Am[idx_Am-1]):
        ans = ans * Am[idx_Am] * pow(Ap[idx_Ap-1], mod-2, mod) % mod
    else:
        ans = ans * Ap[idx_Ap] * pow(Am[idx_Am-1], mod-2, mod) % mod
    print(ans)

Submission status: Runtime Error

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

import bisect
import copy
import collections
import heapq
import itertools
import math
import numpy as np
from operator import itemgetter
import scipy.misc
import sys

"""
#### 入力例 ####
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())
"""

N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10**9 +7

def main():
    ans = 1
    A.sort(reverse=True)
    if N == K:
        ans = 1
        for n in range(N):
            ans*=A[n]
        print(ans % mod)
        return
    
    M = collections.deque()
    P = collections.deque()
    for n in range(N):
        if A[n] < 0:
            M.append(A[n])
        else:
            P.append(A[n])
    if len(P) == 0:
        if(K%2 != 0):
            for k in range(K):
                ans *= M.popleft()
            print(ans % mod)
            return
        else:
            for k in range(K):
                ans *= M.pop()
            print(ans%mod)
            return
    
    if K % 2 == 1:
        ans *= P.popleft()
    
    p_stock = 0
    m_stock = 0
    M = list(M)
    M.sort()
    P = list(P)
    idx_p = 0
    idx_m = 0
    for k in range(0, K//2, 2):
        if  len(M)-1 <= idx_m:
            ans *= P[idx_p] * P[idx_p +1 ]
            idx_p += 2
            
        elif len(P)-1 <= idx_p:
            ans *= M[idx_m] * M[idx_m + 1]  
            idx_m += 2
        elif idx_n < len(M)-1 and idx_p < len(P) -1:
            m_stock = M[idx_m] * M[idx_m + 1] 
            p_stcok = P[idx_p] * P[idx_p + 1]
            if m_stock < p_stcok:
                ans *= p_stock
                idx_p += 2
            else:
                ans *= m_stock
                idx_m += 2
        else:
            break

    print(ans%mod)
    return
    

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

import bisect
import copy
import collections
import heapq
import itertools
import math
import numpy as np
from operator import itemgetter
import scipy.misc
import sys

"""
#### 入力例 ####
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())
"""

N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10**9 +7

def main():
    ans = 1
    A.sort(reverse=True)
    if N == K:
        ans = 1
        for n in range(N):
            ans*=A[n]
        print(ans % mod)
        return
    
    M = collections.deque()
    P = collections.deque()
    for n in range(N):
        if A[n] < 0:
            M.append(A[n])
        else:
            P.append(A[n])
    if len(P) == 0:
        if(K%2 != 0):
            for k in range(K):
                ans *= M.popleft()
            print(ans % mod)
            return
        else:
            for k in range(K):
                ans *= M.pop()
            print(ans%mod)
            return
    
    if K % 2 == 1:
        ans *= P.popleft()
    
    p_stock = 0
    m_stock = 0
    M = list(M)
    M.sort()
    P = list(P)
    idx_p = 0
    idx_m = 0
    for k in range(0, K//2, 2):
        if  len(M) <= idx_m:
            ans *= P[idx_p] * P[idx_p +1 ]
            idx_p += 2
            
        elif len(P) <= idx_p:
            ans *= M[idx_m] * M[idx_m + 1]  
            idx_m += 2
        else:
            m_stock = M[idx_m] * M[idx_m + 1] 
            p_stcok = P[idx_p] * P[idx_p + 1]
            if m_stock < p_stcok:
                ans *= p_stock
                idx_p += 2
            else:
                ans *= m_stock
                idx_m += 2

    print(ans%mod)
    return
    

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
p= 10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
right = list()
left = list()
zero = 0
for x in a:
  if x > 0:
    right.append(x)
  elif x < 0:
    left.append(x)
  else:
    zero += 1
if n - k < zero or (k%2 and len(right)==0 and zero>0):
  # 0を必ず取らないといけない場合、期待される最大が負のとき
  print(0)
  sys.exit()
right.sort(reverse=True)
if len(right)==0:
  #負の数だけ
  left.sort(reverse=k%2)
  left_r = k
  right_r = 0
elif len(left)==0:
  #正の数だけ
  left_r = 0
  right_r = k
else:
  #それ以外の場合はいったんrightからとりきって残りをleftから取る
  # 偶数個のときはrightを偶数に、奇数のときは奇数個にする
  left.sort()
  # len(right)とkの偶奇が一致-> rightを全部突っ込む(かk個突っ込む)
  right_r = min(k, len(right)) - (len(right)%2 ^ k%2)
  left_r = max(0, k - len(right)) + (len(right)%2 ^ k%2)
  while left_r < len(left) -1 or right_r > 1:
    if left[left_r]*left[left_r+1] > right[right_r-1]*right[right_r-2]:
      left_r += 2
      right_r -= 2
    else:
      break
ans = 1
for i in range(right_r):
  ans = (ans * right[i]) % p
for i in range(left_r):
  ans = (ans * left[i]) % p
print(ans)

Submission status: Runtime Error

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

import bisect
import copy
import collections
import heapq
import itertools
import math
import numpy as np
from operator import itemgetter
import scipy.misc
import sys

"""
#### 入力例 ####
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())
"""

N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10**9 +7

def main():
    ans = 1
    A.sort(reverse=True)
    if N == K:
        ans = 1
        for n in range(N):
            ans*=A[n]
        print(ans % mod)
        return
    
    M = collections.deque()
    P = collections.deque()
    for n in range(N):
        if A[n] < 0:
            M.append(A[n])
        else:
            P.append(A[n])
    if len(P) == 0:
        if(K%2 != 0):
            for k in range(K):
                ans *= M.popleft()
            print(ans % mod)
            return
        else:
            for k in range(K):
                ans *= M.pop()
            print(ans%mod)
            return
    
    if K % 2 == 1:
        ans *= P.popleft()
    
    p_stock = 0
    m_stock = 0
    M = list(M)
    M.sort()
    P = list(P)
    idx_p = 0
    idx_m = 0
    for k in range(0, K//2, 2):
        if  len(M) <= idx_p:
            ans *= P[idx_p] * P[idx_p +1 ]
            idx_p += 2
            
        elif len(P) <= idx_m:
            ans *= M[idx_m] * M[idx_m + 1]  
            idx_m += 2
        else:
            m_stock = M[idx_m] * M[idx_m + 1] 
            p_stcok = P[idx_p] * P[idx_p + 1]
            if m_stock < p_stcok:
                ans *= p_stock
                idx_p += 2
            else:
                ans *= m_stock
                idx_m += 2

    print(ans%mod)
    return
    

if __name__ == '__main__':
    main()