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

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)
elif len(M) == 0:
    answer = 1
    for i in range(K):
        answer = (answer * P[i]) % 1000000007

    print(answer)
    sys.exit()

while len(Ans) < K:

    #Mのストックがもうない時
    if m+1 >= len(M) and p < len(P):
        Ans.append(P[p])
        if len(Ans) == K:
            break
        Ans.append(P[p + 1])
        p += 2
    elif p+1 >= len(P) and m < len(M):
        Ans.append(M[m])
        if len(Ans) == K:
            break
        Ans.append(M[m + 1])
        m += 2
    elif m >= len(M) and p < len(P):
        Ans.append(P[p])
        p += 1
    elif p >= len(P) and m < len(M):
        Ans.append(M[m])
        m += 1
    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:
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 n_plus==0:
            print(0)
            exit()
        ans *= A_plus[2 * cnt]
        ans %= mod


print(ans % mod)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left,bisect_right
p=10**9+7
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
minus=bisect_left(a,0) #負の数の個数
plus=n-bisect_right(a,0) #正の数の個数
neg=a[:minus] #負の数(絶対値大きい順)
pog=a[n-plus::][::-1] #正の数(絶対値大きい順)
zer=n-plus-minus #ゼロの数
ans=1
poi=0
nei=0
flag=0
co=0
sgn=1
if plus==1:
  alartp=1
else:
  alartp=0
if minus==1:
  alartn=1
else:
  alartn=0
if plus==0:
  if zer!=0 and k%2==1:
    print(0)
  else:
    for i in range(k):
      ans=ans*neg[-1-i]%p
    print(ans)
elif plus+minus<k:
  print(0)
elif minus==0:
  for _ in range(k):
    ans=ans*pog[poi]%p
    poi+=1
  print(ans)
else:
  i=0
  for i in range(k-2):
    if -neg[nei]>pog[poi]:
      ans=ans*neg[nei]%p
      sgn*=-1
      nei+=1
      if nei==minus-1:
        alartn=1
    else:
      ans=ans*pog[poi]%p
      poi+=1
      if poi==plus-1:
        alartp=1
    if alartp or alartn:
      break
  if alartn:
    if sgn==-1:
      ans=ans*neg[nei]%p
      i+=1
    for _ in range(k-i):
      ans=ans*pog[poi]%p
      poi+=1
  elif alartp==1:
    if (sgn==1 and (k-i)%2==1) or (sgn==-1 and (k-i)%2==0):
      ans=ans*pog[poi]
      i+=1
    for _ in range(k-i):
      ans=ans*neg[nei]
      nei+=1
  else:
    if sgn==1:
      a=max(pog[poi]*pog[poi+1],neg[nei]*neg[nei+1])
      ans=ans*a%p
    else:
      ans=ans*pog[poi]*neg[nei]%p
  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:
    if zero>0:
        print(0)
    else:
        for i in range(k):
            ans=ans*A[i][0]%mod
        print((-ans)%mod)
        
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
        Xl=-1
        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
        Xl=-1
        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:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9+7
sei = []
hu = []
zero = []
for i in range(N):
    a = A[i]
    if a > 0:
        sei.append(a)
    elif a < 0:
        hu.append(a)
    else:
        zero.append(0)
sei.sort(reverse = True)
if len(zero) > N - K:
    print(0)
else:
    ans = 1
    p = len(sei)
    q = len(hu)
    if p == 0:
        hu.sort(reverse = True)
        for i in range(K):
            ans *= hu[i]
            ans %= MOD
        if K % 2 == 1 and len(zero) != 0:
            print(0)
        else:
            print(ans)
    elif p + q == K :
        if q %= 2 == 1 and len(zero) != 0:
            print(0)
        else:
            hu.sort()
            for i in range(p):
                ans *= sei[i]
                ans %= MOD
            for j in range(q):
                ans *= hu[j]
                ans %= MOD
            print(ans%MOD)
    elif q == 0:
        for i in range(K):
            ans *= sei[i]
            ans %= MOD
        print(ans)
    else:
        hu.sort()
        flag = 0
        pin = 0
        qin = 0
        r = K
        while r > 0:
            if pin == -1 and qin == -1:
                break
            elif pin == -1:
                qin += 1
                if qin == q:
                    qin = -1
                if flag == 1:
                    flag = 0
                else:
                    flag = 1
            elif qin == -1:
                pin += 1
                if pin == p:
                    pin = -1
            else:
                if abs(sei[pin])>abs(hu[qin]):
                    pin += 1
                    if pin == p:
                        pin = -1
                else:
                    qin += 1
                    if qin == q:
                        qin = -1
                    if flag == 0:
                        flag = 1
                    else:
                        flag = 0
            r -= 1
        if pin == -1:
            pin = p
        if qin == -1:
            qin = q
        if p+q == K:
            for i in range(p):
                ans *= sei[i]
                ans %= MOD
            for j in range(q):
                ans *= hu[j]
                ans %= MOD
            print(ans%MOD)
        else:
            if flag == 0:
                for i in range(pin):
                    ans *= sei[i]
                    ans %= MOD
                for j in range(qin):
                    ans *= hu[j]
                    ans %= MOD
                print(ans%MOD)
            else:
                if pin == p:
                    for i in range(pin-1):
                        ans *= sei[i]
                        ans %= MOD
                    for j in range(qin+1):
                        ans *= hu[j]
                        ans %= MOD
                    print(ans%MOD)
                else:
                    for i in range(pin+1):
                        ans *= sei[i]
                        ans %= MOD
                    for j in range(qin-1):
                        ans *= hu[j]
                        ans %= MOD
                    print(ans%MOD)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import bisect

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

    neg = bisect.bisect_left(a, 0)
    zer = bisect.bisect_right(a, 0) - neg
    pos = n - (neg + zer)

    a_neg = a[:neg]
    a_pos = a[-pos:] if pos > 0 else []
    a_pos.sort(reverse=True)

    ans = 0
    flag = False

    if k % 2 == 0:
        a2 = []
        for i in range(0, pos - 1, 2):
            a2.append(a_pos[i] * a_pos[i + 1])
        for i in range(0, neg - 1, 2):
            a2.append(a_neg[i] * a_neg[i + 1])
        a2.sort(reverse=True)
        if len(a2) * 2 >= k:
            flag = True
            ans = 1
            for i in range(k // 2):
                ans *= a2[i]
                ans %= MOD
    else:
        a2 = []
        for i in range(1, pos - 1, 2):
            a2.append(a_pos[i] * a_pos[i + 1])
        for i in range(0, neg - 1, 2):
            a2.append(a_neg[i] * a_neg[i + 1])
        a2.sort(reverse=True)
        if pos > 0 and len(a2) * 2 + 1 >= k:
            flag = True
            ans = a_pos[0]
            for i in range(k // 2):
                ans *= a2[i]
                ans %= MOD

    if not flag:
        if zer > 0:
            ans = 0
        elif k % 2 == 0:
            b2 = []
            a_pos.sort()
            a_neg.sort(reverse=True)

            for i in range(1, neg - 1, 2):
                b2.append(a_neg[i] * a_neg[i + 1])
            for i in range(1, pos - 1, 2):
                b2.append(a_pos[i] * a_pos[i + 1])
            b2.sort()
            if len(b2) * 2 + 2 >= k:
                ans = a_pos[0] * a_neg[0]
                for i in range(k // 2):
                    ans *= b2[i]
                    ans %= MOD
        else:
            b2 = []
            a_pos.sort()
            a_neg.sort(reverse=True)
            for i in range(1, neg - 1, 2):
                b2.append(a_neg[i] * a_neg[i + 1])
            for i in range(0, pos - 1, 2):
                b2.append(a_pos[i] * a_pos[i + 1])
            b2.sort()
            if neg > 0 and len(b2) * 2 + 1 >= k:
                ans = a_neg[0]
                for i in range(k // 2):
                    ans *= b2[i]
                    ans %= MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, k = MAP()
a = sorted(LIST())

if k == 1:
    ans = a[n-1]
elif k % 2 == 0:
    b = sorted([abs(a[i]) for i in range(n)], reverse=True)
    ans = 1
    for i in range(k):
        ans = ( ans * b[i] ) % (10**9+7)
else:
    if a[n-1] == 0:
        ans = 0
    elif a[n-1] < 0:
        ans = 1
        for i in range(k):
            ans = ( ans * a[n-1-i] ) % (10**9+7)
    else:
        ans = 1
        for i in range(k):
            ans = ( ans * a[n-1-i] ) % (10**9+7)
            ans = min(0, ans % (10**9+7))
        for i in range(k):
            ans = max(ans, ans//a[n-k+i]*a[i])
            ans = min(0, ans % (10**9+7))
        ans = ans % (10**9+7)
print(ans)

Submission status: Runtime Error

Solution code:
import functools
import operator

prod = functools.partial(functools.reduce, operator.mul)


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

    a.sort(reverse=True)
    if a[-1] >= 0:
        print(prod(a[:k]))
        return
    if a[0] == 0:
        for i, _a in enumerate(a):
            if a[i] != 0:
                break
        else:
            print(0)
            return
        if k > len(a) - ind - 1:
            print(0)
            return
        if k % 2 == 1:
            print(0)
            return
        print(prod(a[len(a)-k:]))
        return
    
    left = 0
    right = len(a) - 1
    ret = 1
    i = 0
    while i < k:
        if i < k - 1:
            if a[left] * a[left+1] < a[right] * a[right-1]:
                ret *= a[right] * a[right-1]
                right -= 2
            else:
                ret *= a[left] * a[left+1]
                left += 2
            i += 2
        else:
            ret *= a[left]
            left += 1
            i += 1
        ret = ret % (10**9+7)
    print(ret)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

def L(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI():return list(map(int,sys.stdin.readline().rstrip().split()))
def LS():return list(sys.stdin.readline().rstrip().split())

def anser(prod):
    print(prod%(10**9+7))
    exit()

def solver(N,K,A):
    #print(A)
    all_minus = False
    minus_count = sum( [1 if i<=0 else 0 for i in A] )
    if minus_count == len(A):
        _sort = sorted(A,reverse=True)
        all_minus = True
    else:
        _sort = sorted(A, key=lambda x: abs(x),reverse=True)

    #print(_sort)

    prod = 1
    last_idx = -1
    stack = []
    for i in range(K):
        #stack.append(_sort[i])
        prod *= _sort[i]
        last_idx = i

    if prod >= 0 or all_minus:
        anser(prod)

    else:
        #print(last_idx)
        #print(stack, prod)
        bef_prod = prod

        for i in range(last_idx, N+1):
            if _sort[i] >= 0:
                continue

            prod = prod // _sort[i] * _sort[i+1]

            #stack.pop()
            #stack.append(_sort[last_idx+1])

            if prod >= 0:
                anser(prod)

        anser(bef_prod)


def main():

    N,K = LI()
    A = LI()

    solver(N,K,A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

mod = 10 ** 9 + 7

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

if N == K:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
    print(ans)
    sys.exit()

A = np.array(A)

plus = A[A>0]
minus = A[A<0]
zero = A[A==0]

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

if len(minus) == N:
    if K % 2 == 0:
        minus = np.sort(minus)
    else:
        minus = np.sort(minus)[::-1]
    ans = 1
    for i in range(K):
        ans *= minus[i]
        ans %= mod
    print(ans)
    sys.exit()

plus = np.sort(plus)[::-1]
minus *= -1
minus = np.sort(minus)[::-1]

if K % 2 == 1:
    ans = plus[0]
    K -= 1
    p = (len(plus)-1) // 2
    m = len(minus) // 2
    
    n_p = [plus[2*i+1] * plus[2*i+2] for i in range(p)]
    n_m = [minus[2*i] * minus[2*i+1] for i in range(m)]
else:
    ans = 1
    p = len(plus) // 2
    m = len(minus) // 2
    
    n_p = [plus[2*i] * plus[2*i+1] for i in range(p)]
    n_m = [minus[2*i] * minus[2*i+1] for i in range(m)]

K //= 2

# p_index = 0
# m_index = 0
# for i in range(K):
#     if p_index == len(n_p):
#         ans *= n_m[m_index]
#         ans %= mod
#         m_index += 1
#     elif m_index == len(n_m):
#         ans *= n_p[p_index]
#         ans %= mod
#         p_index += 1
#     else:
#         if n_p[p_index] > n_m[m_index]:
#             ans *= n_p[p_index]
#             ans %= mod
#             p_index += 1
#         else:
#             ans *= n_m[m_index]
#             ans %= mod
#             m_index += 1
print(0)

Submission status: Runtime Error

Solution code:
from sys import stdin
input = stdin.readline

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

ans = 1
mod = 10 ** 9 + 7

minus_cnt = 0
for a in A:
    if a < 0:
        minus_cnt += 1

if K == 1:
    print(max(A))
elif K == N:
    for a in A:
        ans *= abs(a)
        ans %= mod
    if minus_cnt % 2 == 1:
        ans *= (-1)
    print(ans % mod)
else:
    minus_cnt = 0
    new_A = []
    select_ls = []

    for a in A:
        new_A.append([abs(a), 0 if a >= 0 else -1])
    new_A.sort(reverse=True)

    for i in range(K):
        select_ls.append(new_A[i])
        minus_cnt += new_A[i][1]

    if minus_cnt % 2 == 0:
        for s in select_ls:
            ans *= s[0]
            ans %= mod
        print(ans)
    else:
        ok = False
        for i in range(K, N):
            if new_A[i][1] == 0:
                ok = True
                ans *= new_A[i][0]
                select_ls.sort()
                skip = False
                for j in range(len(select_ls)):
                    if select_ls[i][1] == -1:
                        if skip:
                            ans *= select_ls[j][0]
                        else:
                            skip = True
                            continue
                    else:
                        ans *= select_ls[j][0]
                    ans %= mod
                break
        if not ok:
            if 0 in A:
                print(0)
                exit()
            new_A.sort()
            for i in range(K):
                ans *= new_A[i][0]
                ans %= mod
            ans *= (-1)
        print(ans % mod)

Submission status: Runtime Error

Solution code:
def findMaxProduct(arr, n, k) :
    MaxProduct = 1
    for i in range(0, k) :
        MaxProduct = MaxProduct * arr[i]
    prev_product = MaxProduct
    for i in range(1, n - k + 1) :
        curr_product = (prev_product // arr[i-1]) * arr[i+k-1]
        MaxProduct = max(MaxProduct, curr_product)
        prev_product = curr_product
    return MaxProduct


mod = 10 ** 9 + 7
n,k = map(int,raw_input().split())
arr = [int(i) for i in raw_input().split()]
ans = findMaxProduct(arr,n,k)
print(ans % mod)

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import numpy as np
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N,K = I()
A = l()
hu = []
sei = []
ans = A[0]
for i in range(N):
    if A[i] > 0:
        sei.append(A[i])
    elif A[i] < 0:
        hu.append(A[i]*-1)
sei.sort(reverse=True)
hu.sort()
ruiseki = [1]
cnt = 1
for i in range(len(hu)):
    cnt *= hu[i]
    if i%2 == 1:
        ruiseki.append(cnt)
if K%2 == 0:
    for i in range(K//2):
        ans = max(ans,np.prod(sei[:i*2])+ruiseki[len(ruiseki)-i-1])
else:
    for i in range(K//2-1):
        ans = max(ans, np.prod(sei[:i * 2+1]) + ruiseki[len(ruiseki) - i - 1])
print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush
mod = 10**9+7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

pl = []
mn = []
zr = []

tmp = 1
cnt = 0

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mn.append(-x)
    else:
        zr.append(x)

pl = sorted(pl, reverse=True)
mn = sorted(mn, reverse=True)

ans = 0

if len(mn) >= k and k % 2:
    tmp = 1
    for i in range(1, k+1):
        tmp *= mn[-i]
        tmp %= mod
    ans = -tmp

if len(pl) == 0:
    tmp = 1
    for i in range(1, k+1):
        tmp *= mn[-i]
        tmp %= mod
    ans = -tmp
    print(ans % mod)
    exit()

if len(zr) > 0:
    ans = max(0, ans)

pl_cum = [1]
for i, x in enumerate(pl):
    pl_cum.append(pl_cum[-1]*x % mod)

mn_cum = [1]
for i, x in enumerate(mn):
    mn_cum.append(mn_cum[-1]*x % mod)


for p in range(0, k+1, 2):
    if len(mn) < p:
        break
    first = False
    if len(pl) >= k-p:
        first = True
        pl_ind = k-p
        mn_ind = p
        break

if not first:
    print(ans % mod)
    exit()

while pl_ind-2 > -1 and mn_ind+1 < len(mn):
    if pl[pl_ind-1]*pl[pl_ind-2] <= mn[mn_ind]*mn[mn_ind+1]:
        pl_ind -= 2
        mn_ind += 2
    else:
        break

if pl_ind < 0:
    ans = mn_cum[mn_ind]
else:
    ans = pl_cum[pl_ind]*mn_cum[mn_ind]

print(ans % mod)

Submission status: Runtime Error

Solution code:

n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
m=[]
p=[]

for i in range(n):
    if a[i]<0:
        m.append(a[i])
    else:
        p.append(a[i])
m.sort(reverse=True)
p.sort()
ans=1

if len(m)==n and k%2==1:
    for i in range(k):
        ans*=m[i]
        ans%=mod

elif k==1:
    ans=p[-1]

elif len(m)==1:
    if n==k:
        for i in range(len(p)):
            ans*=p[i]
            ans%=mod
        ans%m[-1]
    else:
        for i in range(k):
            ans*=p[i]
            ans%=mod

elif len(p)==1:
    if n==k:
        for i in range(len(m)):
            ans*=m[i]
            ans%=mod
        ans%p[-1]
    elif k%2==0:
        for i in range(k):
            ans*=m[i]
            ans%=mod
    else:
        for i in range(k-1):
            ans*=m[i]
            ans%=mod
        ans*=p[-1]

else:
    cnt=0
    for i in range(k-2):
        if len(m)==0:
            ans*=p.pop()
        elif len(p)==0:
            lm=m.pop()
            ans*=lm
            cnt+=1
        else:
            if abs(m[-1])<p[-1]:
                ans*=p.pop()
            else:
                lm=m.pop()
                ans*=lm
                cnt+=1
        ans%=mod
    
    if cnt%2==0:
        if len(p)>1 and len(m)>1:
            ans*=max(p[-1]*p[-2],m[-1]*m[-2])
        elif len(p)<2:
            ans*=m[-1]*m[-2]
        else:
            ans*=p[-1]*p[-2]
    elif len(m)>0:
        ans*=p[-1]*m[-1]
    else:
        ans=pow(ans,lm+2,mod)*p[-1]*p[-2]


print(ans%mod)

Submission status: Runtime Error

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

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

LM = []
LP = []
zero = 0
ans = 1

for i in range(len(L)):
    if L[i]> 0:
        LP.append(L[i])
    elif L[i]< 0:
        LM.append(L[i])
    else:
        zero += 1
LP = sorted(LP,reverse=True)
if len(LP) == 0 and k%2 == 1:
    LM = sorted(LM,reverse=True)
else:
    LM = sorted(LM)

#print(LP,LM,zero)

if k > len(LP) +len(LM) or ((k == len(LP) +len(LM)) and len(LM)%2 == 1):
    print(0)
else:
#    print(1)
    p = 0
    m = 0
    for i in range(k//2+k%2):
#        print('a')
        if k-k//2*(i+1)>1:
            pa = 0
            ma = 0
            if len(LP) >=p+2:
                pa = LP[p]*LP[p+1]
                p += 2
            if len(LM) >=m+2:
                ma = LM[m]*LM[m+1]
                m += 2
            
            if abs(pa)>abs(ma):
                ans = ans*pa
            else:
                ans = ans*ma
        else:
            if len(LP)>0:
                ans = ans*LP[p]
                p += 1
            else:
                ans = ans*LM[m]
                m += 1
    
#        print(ans)

print(ans%1000000007)



#for i in range(k):

Submission status: Runtime Error

Solution code:
import sys

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)
elif len(M) == 0:
    answer = 1
    for i in range(K):
        answer = (answer * P[i]) % 1000000007

    print(answer)
    sys.exit()

while len(Ans) < K:

    #Mのストックがもうない時
    if m+1 >= len(M) and p < len(P):
        Ans.append(P[p])
        if len(Ans) == K:
            break
        Ans.append(P[p + 1])
        p += 2
    elif p+1 >= len(P) and m < len(M):
        Ans.append(M[m])
        if len(Ans) == K:
            break
        Ans.append(M[m + 1])
        m += 2
    elif m >= len(M) and p < len(P):
        Ans.append(P[p])
        p += 1
    elif p >= len(P):
        Ans.append(M[m])
        m += 1
    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:
n,k=map(int,input().split())
a=list(map(int,input().split()))
p=[]
m=[]
z=0
a.sort(reverse=True)
for i in range(n):
    if a[i]>0:
        p.append(a[i])
    elif a[i]==0:
        z+=1
    else:
        m.append(a[i])
nump=len(p)
numm=len(m)
ans=1
if nump+numm<k:
    print(0)
elif numm<2 and nump>=k:
    for i in range(k):
        ans*=p[i]
        ans%=10**9+7
    print(ans)
elif 2*(numm//2)+nump<k: #2
    if z!=0:
        print(0)
    else:
        for i in range(n):
            a[i]=abs(a[i])
        a.sort()
        ans=-1
        for i in range(k):
            ans*=a[i]
            ans%=10**9+7
        print(ans)
elif  nump==0: #8?
    if z!=0 and k%2==1:
        print(0)
    elif z!=0 and numm<k:
        print(0)
    else:
        if k%2==0:
            m.sort()
            for i in range(k):
                ans*=m[i]
                ans%=10**9+7
        else:
            m.sort(reverse=True)
            for i in range(k):
                ans*=m[i]
                ans%=10**9+7
        print(ans)
else:
    if k%2==1:
        ans*=p[0]
        p=[1:]
    m.sort()
    p.sort(reverse=True)
    nump=(nump-1)//2
    numm=numm//2
    nump1=0
    nump2=0
    numm1=0
    numm2=0
    for i in range(k//2):
        if nump2==nump:
            nump1=-1
        else:
            nump1=p[nump2*2]*p[nump2*2+1]
        if numm2==numm:
            numm1=-1
        else:
            numm1=m[numm2*2]*m[numm2*2+1]
        if numm1>=nump1:
            num=numm1
            numm2+=1
        else:
            num=nump1
            nump2+=1
        ans*=num
        ans%=10**9+7
    print(ans)