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:
#正の場合、0の場合、負の場合で分ける
#負の数のみの場合は調整しようがない
#偶数の時は絶対値の大きい順
#奇数の時は絶対値の小さい順
#正の数のみの場合は大きい順
#大きい順

#他は調整できるので、正で大きくする方向で考える(正→0以上)
#負の数は偶数個ないと正にならないので二つ一組で先にかけて考える
#正の数も同様に先にかけて、その中で大きいものを選べば良い

#負の数が奇数個、正の数が奇数個の時(負の数が余る、正の数が余る)
#Kが偶数の時はいい感じに選んでく(N=kの時は仕方ないので全部)
#Kが奇数の時は正の中で最大のものを選ぶ
#負の数が偶数個、正の数が奇数個の時(正の数が余る)
#Kが偶数の時はいい感じに選んでく
#奇数の時は残りの正の中から選ぶ
#負の数が奇数個、正の数が偶数個の時(負の数が余る)
#N=Kの時は全部選ぶ、それ以外の場合は余った負の数はいらない
#Kが奇数の時は残りの正の中で最大のものを選べば良い
#負の数が偶数個、正の数が偶数個の時
#Kが奇数の時は残りの正の中で最大のものを選べば良い

#N=Kの時は別で分けて考えるとすると、負の数及び正の数によらず
#Kが偶数の時は大きいものからいい感じに選んでく
#Kが奇数の時は最後の残り一個は正の残りの中で最大のものを選ぶ
#と簡単に言い換えることができる

#x:配列
def multarray(x):
    mod=10**9+7
    ret=1
    for i in x:
        ret*=i
        ret%=mod
    return ret

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

if n==k:
    print(multarray(a))
    exit()

ap,am=[],[]
for i in range(n):
    if a[i]>=0:
        ap.append(a[i])
    else:
        am.append(a[i])
ap.sort(reverse=True)
am.sort(reverse=True)

if len(am)==0:
    print(multarray(ap[:k]))
    exit()
if len(ap)==0:
    if k%2==0:
        print(multarray(am[::-1][:k]))
    else:
        print(multarray(am[:k]))
    exit()

apm2=[]
for i in range(len(am)//2):
    apm2.append((am[2*i]*am[2*i+1],0))
for i in range(len(ap)//2):
    apm2.append((ap[2*i]*ap[2*i+1],1))
apm2.sort(reverse=True)
#+の次にどこを見るのかをチェックしておく
p=0
ans=1
for i in range(k//2):
    ans*=apm2[i][0]
    p+=(2*apm2[i][1])
    ans%=(10**9+7)
if k%2==1:
    ans*=ap[p]
    ans%=(10**9+7)
print(ans)

Submission status: Runtime Error

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

plus = []
minus = []
for i in a:
    if i > 0: plus.append(i)
    if i < 0: minus.append(-i)
plus.sort(reverse=True)
minus.sort(reverse=True)

ans = 1
if k == n:
    for x in a:
        ans = (ans * x) % mod
elif k > len(plus) + len(minus):
    ans = 0
elif n == len(plus):
    for x in plus[:k]:
        ans = (ans * x) % mod
elif n == len(minus):
    if k % 2 == 1:
        ans = -1
        minus.sort()
    for x in minus[:k]:
        ans = (ans * x) % mod
else:
    i, j = 0, 0
    if k % 2 == 1:
        ans = plus[0]
        i += 1
    while i + j < k:
        x_p = plus[i] * plus[i + 1] if i < len(plus) - 1 else 0
        x_m = minus[j] * minus[j + 1] if j < len(minus) - 1 else 0
        if x_p > x_m:
            ans = (ans * x_p) % mod
            i += 2
        else:
            ans = (ans * x_m) % mod
            j += 2
print(ans)

Submission status: Runtime Error

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

plus = []
minus = []
for i in a:
    if i > 0: plus.append(i)
    if i < 0: minus.append(-i)
plus.sort(reverse=True)
minus.sort(reverse=True)

ans = 1
if k == n:
    for x in a:
        ans = (ans * x) % mod
elif k > len(plus) + len(minus):
    ans = 0
elif n == len(plus):
    for x in plus[:k]:
        ans = (ans * x) % mod
elif n == len(minus):
    if k % 2 == 1:
        ans = -1
        minus.sort()
    for x in minus[:k]:
        ans = (ans * x) % mod
else:
    i, j = 0, 0
    if k % 2 == 1:
        ans = plus[0]
        i += 1
    while i + j < k:
        x_p = (plus[i] * plus[i + 1]) % mod if i < len(plus) - 1 else 0
        x_m = (minus[j] * minus[j + 1]) % mod if j < len(minus) - 1 else 0
        if x_p > x_m:
            ans = (ans * x_p) % mod
            i += 2
        else:
            ans = (ans * x_m) % mod
            j += 2
print(ans)

Submission status: Runtime Error

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

plus = []
minus = []
for i in a:
    if i > 0: plus.append(i)
    if i < 0: minus.append(-i)
plus.sort(reverse=True)
minus.sort(reverse=True)

ans = 1
if k == n:
    for x in a:
        ans = (ans * x) % mod
elif k > len(plus) + len(minus):
    ans = 0
elif n == len(plus):
    for x in plus[:k]:
        ans = (ans * x) % mod
elif n == len(minus):
    if k % 2 == 1:
        ans = -1
        minus.sort()
    for x in minus[:k]:
        ans = (ans * x) % mod
else:
    i, j = 0, 0
    while i + j < k:
        if i + j == k - 1:
            ans = (ans * plus[i]) % mod
            i += 1
        else:
            x_p = (plus[i] * plus[i + 1]) % mod if i < len(plus) - 1 else 0
            x_m = (minus[j] * minus[j + 1]) % mod if j < len(minus) - 1 else 0
            if x_p > x_m:
                ans = (ans * x_p) % mod
                i += 2
            else:
                ans = (ans * x_m) % mod
                j += 2
print(ans)

Submission status: Runtime Error

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

plus = []
minus = []
for i in a:
    if i > 0: plus.append(i)
    if i < 0: minus.append(-i)
plus.sort(reverse=True)
minus.sort(reverse=True)

ans = 1
if k == n:
    for x in a[:k]:
        ans = (ans * x) % mod
elif k > len(plus) + len(minus):
    ans = 0
elif n == len(plus):
    for x in plus[:k]:
        ans = (ans * x) % mod
elif n == len(minus):
    if k % 2 == 1:
        ans = -1
        minus.sort()
    for x in minus[:k]:
        ans = (ans * x) % mod
else:
    i, j = 0, 0
    while i + j < k:
        if i + j == k - 1:
            ans = (ans * plus[i]) % mod
            i += 1
        else:
            x_p = (plus[i] * plus[i + 1]) % mod if i < len(plus) - 1 else 1
            x_m = (minus[j] * minus[j + 1]) % mod if j < len(minus) - 1 else 1
            if x_p > x_m:
                ans = (ans * x_p) % mod
                i += 2
            else:
                ans = (ans * x_m) % mod
                j += 2
print(ans)

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(key=lambda x: abs(x), reverse=True)

    res = 1

    if max(a) < 0:
        if k % 2 == 1:
            for i in range(n - k, n):
                res *= a[i]
                res %= MOD
        else:
            for i in range(k):
                res *= a[i]
                res %= MOD
    else:
        plus_a = [e for e in a if e >= 0]
        minus_a = [e for e in a if e < 0]

        minus_cnt = min(k, len(minus_a))
        minus_cnt -= minus_cnt % 2
        plus_cnt = k - minus_cnt

        minus_a = minus_a[:minus_cnt]
        minus_a.reverse()

        max_change_cnt = min(minus_cnt, len(plus_a) - plus_cnt)
        max_change_cnt -= max_change_cnt % 2
        change_cnt = 0
        while change_cnt < max_change_cnt:
            if plus_a[plus_cnt + change_cnt] * plus_a[plus_cnt + change_cnt + 1]\
                    <= minus_a[change_cnt] * minus_a[change_cnt + 1]:
                break
            change_cnt += 2

        for i in range(change_cnt, minus_cnt):
            res *= minus_a[i]
            res %= MOD

        for i in range(plus_cnt + change_cnt):
            res *= plus_a[i]
            res %= MOD

    print(res)


main()

Submission status: Runtime Error

Solution code:
import numpy as np
import mpmath 
mpmath.dps = 20; mpmath.pretty = True
N,K = map(int,input().split())
import math
A = list(map(int,input().split()))
flag = 0
if 0 in A:
    flag = 1
A.sort()

plus = list(filter(lambda x:x>0, A))[::-1]
plus = list(map(lambda x:mpmath.log(x),plus))
from itertools import accumulate
acc_plu = [0] +  list(accumulate(plus))
minu = filter(lambda x:x<0, A)
minu = list(map(lambda x:mpmath.log(-x),minu))
acc_min = [0] +  list(accumulate(minu))


if K % 2 == 0 : num = K // 2 + 1
else: num = (K + 1) // 2 
cand = []
x = K
y = 0
MOD = 10**9 +7
for i in range(num):
    try:
        cand.append((acc_plu[x] +  acc_min[y],x ,y ))
    except: pass
    x -= 2 
    y += 2

ans = 1
if cand == []:
    if flag:
        print(0)
        exit()
    cnt = 0
    #マイナス確定
    abss = sorted(list(map(lambda x :abs(x),A)))
    for x in abss:
        if cnt == K:break
        ans *= x
        ans %= MOD
        cnt += 1
    ans *= -1
    ans %= MOD
    print(ans)
else:
    cand = sorted(cand)[::-1]
    plus = list(filter(lambda x:x>0, A))[::-1]
    minu = list(filter(lambda x:x<0, A))
    c = cand[0]
    ans = 1
    for i in range(c[1]):
        ans *= plus[i]
        ans %= MOD
    for i in range(c[2]):
        ans *= minu[i]
        ans %= MOD
    print(ans)

Submission status: Runtime Error

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

plus = []
minus = []
for i in a:
    if i > 0: plus.append(i)
    if i < 0: minus.append(i)

ans = 1
if k > len(plus) + len(minus):
    ans = 0
elif len(minus) == 0:
    plus.sort(reverse=True)
    for i in range(k):
        ans = (ans * plus[i]) % mod
elif len(plus) == 0:
    if k % 2 == 0:
        minus.sort()
        for i in range(k):
            ans = (ans * minus[i]) % mod
    else:
        minus.sort(reverse=True)
        for i in range(k):
            ans = (ans * minus[i]) % mod
elif k == len(plus) + len(minus) and (len(minus) % 2) == 1:
    if n != k:
        ans = 0
    else:
        for x in plus:
            ans = (ans * x) % mod
        for y in minus[:k - len(plus)]:
            ans = (ans * y) % mod
else:
    plus.sort(reverse=True)
    minus.sort()
    if k > len(plus) + len(minus):
        ans = 0
    else:
        i, j = 0, 0
        if k % 2 == 1:
            ans = plus[0]
            i = 1
        while i + j < k:
            tmp_p = plus[i] * plus[i + 1] if i <= len(plus) - 2 else 1
            tmp_m = minus[j] * minus[j + 1] if j <= len(plus) - 2 else 1
            if tmp_p >= tmp_m:
                ans = (ans * (tmp_p % mod)) % mod
                i += 2
            else:
                ans = (ans * (tmp_m % mod)) % mod
                j += 2
print(ans)

Submission status: Runtime Error

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

plus = []
minus = []
for i in a:
    if i > 0: plus.append(i)
    if i < 0: minus.append(i)

ans = 1
if k > len(plus) + len(minus):
    ans = 0
elif len(minus) == 0:
    plus.sort(reverse=True)
    if k > len(plus):
        ans = 0
    else:
        for i in range(k):
            ans = (ans * plus[i]) % mod
elif len(plus) == 0:
    if k > len(minus):
        ans = 0
    elif k % 2 == 0:
        minus.sort()
        for i in range(k):
            ans = (ans * minus[i]) % mod
    else:
        if n != len(minus):
            ans = 0
        else:
            minus.sort(reverse=True)
            for i in range(k):
                ans = (ans * minus[i]) % mod
elif k == len(plus) + len(minus) and (len(minus) % 2) == 1:
    if n != len(plus) + len(minus):
        ans = 0
    else:
        for x in plus:
            ans = (ans * x) % mod
        for y in minus:
            ans = (ans * y) % mod
else:
    plus.sort(reverse=True)
    minus.sort()
    if k > len(plus) + len(minus):
        ans = 0
    else:
        i, j = 0, 0
        if k % 2 == 1:
            ans = plus[0]
            i = 1
        while i + j < k:
            tmp_p = plus[i] * plus[i + 1] if i <= len(plus) - 2 else 1
            tmp_m = minus[j] * minus[j + 1] if j <= len(plus) - 2 else 1
            if tmp_p >= tmp_m:
                ans = (ans * (tmp_p % mod)) % mod
                i += 2
            else:
                ans = (ans * (tmp_m % mod)) % mod
                j += 2
print(ans)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
all_minus = True
for i in range(n):
  if a[i] >= 0:
    all_minus = False
    break
if all_minus:
  a.sort(key = lambda x: abs(x))
  ans = 1
  for i in range(k):
    ans *= a[i]
    ans %= mod
  print(ans)
  exit()
if k == n:
  ans = 1
  for i in range(k):
    ans *= a[i]
    ans %= mod
  print(ans)
  exit()

a.sort(key = lambda x: abs(x))
a.reverse()
ans = 1
mcnt = 0
zcnt = 0
for i in range(n):
  if a[i] == 0:
    zcnt += 1
if zcnt > n - k:
  print(0)
  exit()
b = []
for i in range(n):
  if a[i] == 0:
    continue
  b.append(a[i])
m = len(b)
for i in range(k):
  ans *= b[i]
  ans %= mod
  if b[i] < 0:
    mcnt += 1
if mcnt % 2 == 0:
  print(ans)
  exit()
lp = 0
lpi = -1
lm = 0
lmi = -1
for i in reversed(range(k)):
  if b[i] > 0:
    lp = b[i]
    lpi = i
    break
for i in reversed(range(k)):
  if b[i] < 0:
    lm = b[i]
    lmi = i
    break
rm = 0
rmi = -1
rp = 0
rpi = -1
for i in range(k, m):
  if b[i] < 0:
    rm = b[i]
    rmi = i
    break
for i in range(k, m):
  if b[i] > 0:
    rp = b[i]
    rpi = i
    break
    
ex = False
if lpi < 0:
  temp = 1
  for i in range(k):
    if i == lmi:
      continue
    temp *= b[i]
    temp %= mod
  if rpi >= 0:
    temp *= rp
    temp %= mod
    ans = temp
    ex = True
  
  if not ex:
    if mcnt > 0:
      ans = 0
    else:
      b.sort(key = lambda x: abs(x))
      ans = 1
      for i in range(k):
        ans *= b[i]
        ans %= mod
else:
  exA = False
  exB = False
  
  tempA = 1
  for i in range(k):
    if i == lmi:
      continue
    tempA *= b[i]
    tempA %= mod
  if rpi >= 0:
    tempA *= rp
    tempA %= mod
    exA = True
  
  tempB = 1
  for i in range(k):
    if i == lpi:
      continue
    tempB *= b[i]
    tempB %= mod
  if rmi >= 0:
    tempB *= rm
    tempB %= mod
    exB = True
  
  ex = exA or exB
  if lp * rp > lm * rm and exA and exB:
    ans = tempA
  else if lp * rp <= lm * rm and exA and exB:
    ans = tempB
  else if exA:
    ans = tempA
  else if exB:
    ans = tempB
  else:
    if mcnt > 0:
      ans = 0
    else:
      b.sort(key = lambda x: abs(x))
      ans = 1
      for i in range(k):
        ans *= b[i]
        ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
import sys
 
MOD = 10**9 + 7
 
def read_int():
    line = sys.stdin.readline().rstrip('\n')
    return int(line)
 
def read_int_list():
    line = sys.stdin.readline().rstrip('\n')
    return [int(e) for e in line.split(' ')]
 
def sign(n):
    if n > 0:
        return 1
    if n < 0:
        return -1
    return 0
 
def prod(A, K, add, remove):
    prod = 1
    for i in range(K):
        if i == remove:
            continue
        prod *= abs(A[i])
        prod %= MOD
    if add != None:
        prod *= abs(A[add])
        prod %= MOD
    return prod
 
N, K = read_int_list()
A = read_int_list()
 
A.sort(key=lambda i: -abs(i))
 
last_plus = None
last_minus = None
sig = 1
for i in range(K):
    sig *= sign(A[i])
    if A[i] > 0:
        last_plus = i
    if A[i] < 0:
        last_minus = i
remove_plus = None
add_plus = None
remove_minus = None
add_minus = None
if sig < 0:
    for i in range(K, N):
        if A[i] > 0 and last_minus != None and remove_minus == None:
            remove_minus = last_minus
            add_minus = i
            sig = 1
        elif A[i] < 0 and last_plus != None and remove_plus == None:
            remove_plus = last_plus
            add_plus = i
            sig = 1
        elif A[i] == 0:
            sig = 0
            break
 
if sig == 0:
    print(0)
elif sig > 0:
    if remove_plus != None and remove_minus != None:
        if abs(A[remove_plus]/A[add_plus]) > abs(A[remove_minus]/A[add_minus]):
            ap = prod(A, K, add_minus, remove_minus)
        else:
            ap = prod(A, K, add_plus, remove_plus)
    elif remove_plus != None:
        ap = prod(A, K, add_plus, remove_plus)
    else:
        ap = prod(A, K, add_minus, remove_minus)
    print(ap)
else:
    ap = prod(A[::-1], K, None, None)
    print((MOD-ap) % MOD)
import sys

MOD = 10**9 + 7

def read_int():
    line = sys.stdin.readline().rstrip('\n')
    return int(line)

def read_int_list():
    line = sys.stdin.readline().rstrip('\n')
    return [int(e) for e in line.split(' ')]

def sign(n):
    if n > 0:
        return 1
    if n < 0:
        return -1
    return 0

def prod(A, K, add, remove):
    prod = 1
    for i in range(K):
        if i == remove:
            continue
        prod *= abs(A[i])
        prod %= MOD
    if add != None:
        prod *= abs(A[add])
        prod %= MOD
    return prod

N, K = read_int_list()
A = read_int_list()

A.sort(key=lambda i: -abs(i))

last_plus = None
last_minus = None
sig = 1
for i in range(K):
    sig *= sign(A[i])
    if A[i] > 0:
        last_plus = i
    if A[i] < 0:
        last_minus = i
remove_plus = None
add_plus = None
remove_minus = None
add_minus = None
if sig < 0:
    for i in range(K, N):
        if A[i] > 0 and last_minus != None and remove_minus == None:
            remove_minus = last_minus
            add_minus = i
            sig = 1
        elif A[i] < 0 and last_plus != None and remove_plus == None:
            remove_plus = last_plus
            add_plus = i
            sig = 1
        elif A[i] == 0:

            break

if sig == 0:
    print(0)
elif sig > 0:
    if remove_plus != None and remove_minus != None:
        if abs(A[remove_plus]/A[add_plus]) > abs(A[remove_minus]/A[add_minus]):
            ap = prod(A, K, add_minus, remove_minus)
        else:
            ap = prod(A, K, add_plus, remove_plus)
    elif remove_plus != None:
        ap = prod(A, K, add_plus, remove_plus)
    else:
        ap = prod(A, K, add_minus, remove_minus)
    print(ap)
else:
    ap = prod(A[::-1], K, None, None)
    print((MOD-ap) % MOD)

Submission status: Runtime Error

Solution code:
import sys
 
MOD = 10**9 + 7
 
def read_int():
    line = sys.stdin.readline().rstrip('\n')
    return int(line)
 
def read_int_list():
    line = sys.stdin.readline().rstrip('\n')
    return [int(e) for e in line.split(' ')]
 
def sign(n):
    if n > 0:
        return 1
    if n < 0:
        return -1
    return 0
 
def prod(A, K, add, remove):
    prod = 1
    for i in range(K):
        if i == remove:
            continue
        prod *= abs(A[i])
        prod %= MOD
    if add != None:
        prod *= abs(A[add])
        prod %= MOD
    return prod
 
N, K = read_int_list()
A = read_int_list()
 
A.sort(key=lambda i: -abs(i))
 
last_plus = None
last_minus = None
sig = 1
for i in range(K):
    sig *= sign(A[i])
    if A[i] > 0:
        last_plus = i
    if A[i] < 0:
        last_minus = i
remove_plus = None
add_plus = None
remove_minus = None
add_minus = None
if sig < 0:
    for i in range(K, N):
        if A[i] > 0 and last_minus != None and remove_minus == None:
            remove_minus = last_minus
            add_minus = i
            sig = 1
        elif A[i] < 0 and last_plus != None and remove_plus == None:
            remove_plus = last_plus
            add_plus = i
            sig = 1
        elif A[i] == 0:
            sig = 0
            break
 
if sig == 0:
    print(0)
elif sig > 0:
    if remove_plus != None and remove_minus != None:
        if abs(A[remove_plus]/A[add_plus]) > abs(A[remove_minus]/A[add_minus]):
            ap = prod(A, K, add_minus, remove_minus)
        else:
            ap = prod(A, K, add_plus, remove_plus)
    elif remove_plus != None:
        ap = prod(A, K, add_plus, remove_plus)
    else:
        ap = prod(A, K, add_minus, remove_minus)
    print(ap)
else:
    ap = prod(A[::-1], K, None, None)
    print((MOD-ap) % MOD)
import sys

MOD = 10**9 + 7

def read_int():
    line = sys.stdin.readline().rstrip('\n')
    return int(line)

def read_int_list():
    line = sys.stdin.readline().rstrip('\n')
    return [int(e) for e in line.split(' ')]

def sign(n):
    if n > 0:
        return 1
    if n < 0:
        return -1
    return 0

def prod(A, K, add, remove):
    prod = 1
    for i in range(K):
        if i == remove:
            continue
        prod *= abs(A[i])
        prod %= MOD
    if add != None:
        prod *= abs(A[add])
        prod %= MOD
    return prod

N, K = read_int_list()
A = read_int_list()

A.sort(key=lambda i: -abs(i))

last_plus = None
last_minus = None
sig = 1
for i in range(K):
    sig *= sign(A[i])
    if A[i] > 0:
        last_plus = i
    if A[i] < 0:
        last_minus = i
remove_plus = None
add_plus = None
remove_minus = None
add_minus = None
if sig < 0:
    for i in range(K, N):
        if A[i] > 0 and last_minus != None and remove_minus == None:
            remove_minus = last_minus
            add_minus = i
            sig = 1
        elif A[i] < 0 and last_plus != None and remove_plus == None:
            remove_plus = last_plus
            add_plus = i
            sig = 1
        elif A[i] == 0:
            if sig < 0:
                sig = 0
            break

if sig == 0:
    print(0)
elif sig > 0:
    if remove_plus != None and remove_minus != None:
        if abs(A[remove_plus]/A[add_plus]) > abs(A[remove_minus]/A[add_minus]):
            ap = prod(A, K, add_minus, remove_minus)
        else:
            ap = prod(A, K, add_plus, remove_plus)
    elif remove_plus != None:
        ap = prod(A, K, add_plus, remove_plus)
    else:
        ap = prod(A, K, add_minus, remove_minus)
    print(ap)
else:
    ap = prod(A[::-1], K, None, None)
    print((MOD-ap) % MOD)

Submission status: Runtime Error

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

if k==n:
  res = 1
  for a in A:
    res *= a
  print(res % MOD)
elif k%2==1 and all([ a<0 for a in A ]):
  A.sort(reverse=True)
  res = 1
  for i in range(k):
    res *= A[i]
  print(res % MOD)
else:
  absSorted = sorted(A,key=lambda x: abs(x), reverse=True)
  res = 1
  plus = Counter()
  minus = Counter()
  for i in range(k):
    res *= absSorted[i]
    if absSorted[i] < 0:
      minus[absSorted[i]] += 1
    else:
      plus[absSorted[i]] += 1

  if res < 0:
    counter = Counter(A)
    # (1) 負の数の中で絶対値が一番小さいものを1つ取り除き、非負の数の中で最大のものを一つ加える
    minusKeys = sorted(minus.keys(), reverse=True)
    tmp1 = res // minusKeys[0]
    for k in sorted(counter.keys(), reverse=True):
      if plus[k] < counter[k]:
        tmp1 *= k
        break

    # (2) 正の数を1つ取り除き、負の数を一つ加える
    plusKeys = sorted(plus.keys())
    tmp2 = res // plusKeys[0]
    for k in sorted(counter.keys()):
      if minus[k] < counter[k]:
        tmp2 *= k
        break

    print(max(tmp1, tmp2) % MOD)
  else:
    print(res)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

readline = sys.stdin.buffer.readline

N, K = map(int, readline().split())
A = np.array(list(map(int, readline().split())), dtype=np.int64)
MOD = 10 ** 9 + 7

B = np.zeros(N, dtype=np.int64)
B[A > 0] = 1
B[A < 0] = -1

# 全部負かつKが奇数のときは場合分け
if len(B[A > 0]) == 0 and K % 2 == 1:
    f = 1
else:
    f = 0

C = np.zeros([2, N], dtype=np.int64)
C[0] = np.abs(A)
C[1] = B

C = C[:, np.argsort(C[0])[::-1]]

ans = 1
if f == 0:
    ss = 1
    for i in range(K):
        ans *= C[0, i]
        ans %= MOD
        ss *= C[1, i]

    if ss < 0:
        # 選んだものの最大値，最小値
        MM = C[C[1, :K] > 0]
        if len(MM) > 0:
            plus_m = np.max(MM)
        else:
            plus_m = 0

        MM = C[C[1, :K] < 0]
        if len(MM) > 0:
            minus_m = np.max(MM)
        else:
            minus_m = 0

        # 選んでいないものの最大値，最小値
        MM = C[C[1, K:] > 0]
        if len(MM) > 0:
            M = np.max(MM)
        else:
            M = 0

        MM = C[C[1, K:] < 0]
        if len(MM) > 0:
            m = np.max(MM)
        else:
            m = 0

        if m * minus_m > M * plus_m:
            ans //= plus_m
            ans *= m
        else:
            ans //= minus_m
            ans *= M

else:
    C = C[0][::-1]
    for i in range(K):
        ans *= C[i]

    ans = -ans

print(ans % MOD)

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:
  print(0)
  exit()
if k==n:
  if cnt_zero!=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:
    print(0)
  else:
    arr_minus=sorted(arr_minus)
    tmp=1
    for i in range(k):
      tmp*=arr_minus[i]
      tmp%=mod
    print((-tmp)%mod)
  exit()
else:
  arr_plus=sorted(arr_plus,reverse=True)
  arr_minus=sorted(arr_minus,reverse=True)
  acum_plus=[1]
  for i in range(len(arr_plus)):
    acum_plus.append((acum_plus[-1]*arr_plus[i])%mod)
  acum_minus=[1]  
  for i in range(len(arr_minus)):
    acum_minus.append((acum_minus[-1]*arr_minus[i])%mod)  
  if k%2==0:
    ans=0
    for i in range(0,len(arr_plus)+1,2):
      j=k-i
      if len(arr_minus)<j:
        continue
      ans=max(ans,(acum_plus[i]*acum_minus[j])%mod)
    print(ans)
  else:
    ans=0
    for i in range(1,len(arr_plus)+1,2):
      j=k-i
      if len(arr_minus)<j:
        continue
      ans=max(ans,(acum_plus[i]*acum_minus[j])%mod)
    print(ans)
  exit()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

readline = sys.stdin.buffer.readline

N, K = map(int, readline().split())
A = np.array(list(map(int, readline().split())), dtype=np.int64)
MOD = 10 ** 9 + 7

B = np.zeros(N, dtype=np.int64)
B[A > 0] = 1
B[A < 0] = -1

# 全部負かつKが奇数のときは場合分け
if len(B[A > 0]) == 0 and K % 2 == 1:
    f = 1
else:
    f = 0

C = np.zeros([2, N], dtype=np.int64)
C[0] = np.abs(A)
C[1] = B

C = C[:, np.argsort(C[0])[::-1]]

ans = 1
if f == 0:
    ss = 1
    for i in range(K):
        ans *= C[0, i]
        ans %= MOD
        ss *= C[1, i]

    if ss < 0:
        # 選んだものの最大値，最小値
        plus_m = np.max(C[C[1, :K] > 0])
        minus_m = np.max(C[C[1, :K] < 0])

        # 選んでいないものの最大値，最小値
        M = np.max(C[C[1, K:] > 0])
        m = np.max(C[C[1, K:] < 0])

        if m / plus_m > M / minus_m:
            ans //= plus_m
            ans *= m
        else:
            ans //= minus_m
            ans *= M

else:
    C = C[0][::-1]
    for i in range(K):
        ans *= C[i]

    ans = -ans

print(ans % MOD)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
import math
A = list(map(int,input().split()))
flag = 0
if 0 in A:
    flag = 1
A.sort()
plus = list(filter(lambda x:x>0, A))[::-1]
plus = list(map(lambda x:math.log(x),plus ))

acc_plu = []
tmp = 0
for x in plus:
    acc_plu.append(tmp)
    tmp = math.fsum([tmp,x])

minu = filter(lambda x:x<0, A)
minu = list(map(lambda x:math.log(-x),minu))
acc_min = [] 
tmp = 0
for x in plus:
    acc_min.append(tmp)
    tmp = math.fsum([tmp,x])


if K % 2 == 0 : num = K // 2 + 1
else: num = (K + 1) // 2 
cand = []
x = K
y = 0
MOD = 10**9 +7
for i in range(num):
    try:
        cand.append((acc_plu[x] +  acc_min[y],x ,y ))
    except: pass
    x -= 2 
    y += 2


ans = 1
if cand == []:
    if flag:
        print(0)
        exit()
    cnt = 0
    minu = list(filter(lambda x:x<0, A))
    for x in minu[::-1]:
        if cnt == K:break
        ans *= x
        ans %= MOD
        cnt += 1
    print(ans)
else:
    cand = sorted(cand)[::-1]
    plus = list(filter(lambda x:x>0, A))[::-1]
    minu = list(filter(lambda x:x<0, A))
    c = cand[0]
    for i in range(c[1]):
        ans *= plus[i]
        ans %= MOD
    for i in range(c[2]):
        ans *= minu[i]
        ans %= MOD

Submission status: Runtime Error

Solution code:
import sys

n, k = map(int, input().split())
a = [int(i) for i in input().split()]

if n == k:
    ans = 1
    for i in range(n):
        ans *=  a[i]
        ans %= 10**9 + 7
    
    print(ans)
    sys.exit()

plus = []
minus = []

for num in a:
    if num < 0:
        minus.append(num)
    else:
        plus.append(num)

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

if len(plus) == 0 and k % 2 == 1:
    ans = 1
    minus.sort(reverse=True)
    for i in range(k):
        ans *= minus[i]
        ans %= 10**9 + 7
        
    print(ans)
    sys.exit()
    
mi_cnt, pl_cnt = 0, 0
ans = 1
while mi_cnt + pl_cnt < k:
    pl = plus[pl_cnt]
    mi = minus[mi_cnt] * minus[mi_cnt + 1]
    #print(pl, mi)
    
    if len(plus) <= pl_cnt + 1:
        ans *= mi
        ans %= 10**9 + 7
        mi_cnt += 2
        continue
    
    if len(minus) <= mi_cnt + 2:
        ans *= pl
        ans %= 10**9 + 7
        pl_cnt += 1
        continue
        
    if k < mi_cnt + pl_cnt + 2:
        #print(plus[pl_cnt])
        ans *= pi
        ans %= 10**9 + 7
        pl_cnt += 1
        continue
    
    if pl < mi:
        #print(mi)
        ans *= mi
        ans %= 10**9 + 7
        mi_cnt += 2
    else:
        #print(pl)
        ans *= pl
        ans %= 10**9 + 7
        pl_cnt += 1
        
print(ans)

Submission status: Runtime Error

Solution code:
import sys

n, k = map(int, input().split())
a = [int(i) for i in input().split()]

if n == k:
    ans = 1
    for i in range(n):
        ans *=  a[i]
        ans %= 10**9 + 7
    
    print(ans)
    sys.exit()

plus = []
minus = []

for num in a:
    if num < 0:
        minus.append(num)
    else:
        plus.append(num)

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

if len(plus) == 0 and k % 2 == 1:
    ans = 1
    minus.sort(reverse=True)
    for i in range(k):
        ans *= minus[i]
        ans %= 10**9 + 7
        
    print(ans)
    sys.exit()
    
mi_cnt, pl_cnt = 0, 0
ans = 1
while mi_cnt + pl_cnt < k:
    pl = plus[pl_cnt]
    mi = minus[mi_cnt] * minus[mi_cnt + 1]
    #print(pl, mi)
    
    if len(plus) <= pl_cnt + 1:
        ans *= mi
        ans %= 10**9 + 7
        mi_cnt += 2
        continue
        
    if k < mi_cnt + pl_cnt + 2:
        #print(plus[pl_cnt])
        ans *= pi
        ans %= 10**9 + 7
        pl_cnt += 1
        continue
    
    if pl < mi:
        #print(mi)
        ans *= mi
        ans %= 10**9 + 7
        mi_cnt += 2
    else:
        #print(pl)
        ans *= pl
        ans %= 10**9 + 7
        pl_cnt += 1
        
print(ans)