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

mod = 10**9 + 7

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().strip().split()))

# 0も入れておく
pos_list = []
neg_list = []
zero_count = 0
for a_i in A:
    if a_i > 0:
        pos_list.append(a_i)
    elif a_i == 0:
        zero_count += 1
    else:
        neg_list.append(a_i)

# 降順
pos_list.sort(reverse = True)
neg_list.sort()


lp = len(pos_list)
ln = len(neg_list)

    
if min(2 * (ln // 2), 2 * (K // 2)) + lp >= K:
    pos_twins = [pos_list[2 * i] * pos_list[2 * i + 1] for i in range(lp // 2)] + [0]
    neg_twins = [neg_list[2 * i] * neg_list[2 * i + 1] for i in range(ln // 2)] + [0]
    pos_twins.sort()
    neg_twins.sort()
 
    ans = 1
    pos_select = 0
    for i in range(K // 2):
        if pos_twins[-1] <= neg_twins[-1]:
            ans *= neg_twins[-1]
            ans %= mod
            neg_twins.pop()
        else:
            ans *= pos_twins[-1]
            ans %= mod
            pos_twins.pop()
            pos_select += 1
 
    if K % 2 == 1:
        if K == 1:
            ans = pos_list[2 * pos_select]
        else:
            ans *= pos_list[2 * pos_select]
    print(ans % mod)    
elif zero_count > 0:
	print(0)
# マイナスになるため、最小化する
else:
    ans = 1
    neg_list.sort(reverse=True)
    for i in range(K):
        ans *= neg_list[i] * (-1)
        ans %= mod
    print((-1) * ans % mod)

Submission status: Runtime Error

Solution code:
import bisect
from collections import deque
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
MOD=10**9+7
if N==K:
    ans=1
    for i in A:
        ans=ans*i%MOD
    print(ans)
    exit()
if K%2==1 and A[0]<0:
    ans=1
    for i in range(K):
        ans=ans*A[i]%MOD
    print(ans)
    exit()
if N-A.count(0)<K:
    print(0)
    exit()
A=A[::-1]
x=deque(A[bisect.bisect_right(A,0):][::-1]+[0])
y=deque(A[:bisect.bisect_left(A,0)]+[0])
c=0
t=[]
while c<K:
    if c==K-1 or len(y)<2:
        t.append(x.popleft())
        c+=1
    elif not x:
        t.append(y.popleft())
        t.append(y.popleft())
        c+=2
    elif x[0]*x[1]>=y[0]*y[1]:
        t.append(x.popleft())
        c+=1
    else:
        t.append(y.popleft())
        t.append(y.popleft())
        c+=2
ans=1
for i in t:
    ans*=i
    ans%=MOD
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

A_p = deque([i for i in A if i >= 0].sort().reverse())
A_n = deque([i for i in A if i < 0].sort())

ans = 1
mod = 10 ** 9 + 7
if K % 2 == 0:
    while K != 0:
        if len(A_p) >= 2 and len(A_n) >= 2:
            if A_p[0] * A_p[1] > A_n[0] * A_n[1]:
                ans = ans * A_p[0] * A_p[1] % mod
                A_p.popleft()
                A_p.popleft()
            else:
                ans = ans * A_n[0] * A_n[1] % mod
                A_n.popleft()
                A_n.popleft()
        elif len(A_p) >= 2:
            ans = ans * A_p[0] * A_p[1] % mod
            A_p.popleft()
            A_p.popleft()
        elif len(A_n) >= 2:
            ans = ans * A_n[0] * A_n[1] % mod
            A_n.popleft()
            A_n.popleft()
        K -= 2
elif len(A_p) > 0:
    while K != 0:
        if K >= 2:
            if len(A_p) >= 2 and len(A_n) >= 2:
                if A_p[0] * A_p[1] > A_n[0] * A_n[1]:
                    ans = ans * A_p[0] * A_p[1] % mod
                    A_p.popleft()
                    A_p.popleft()
                else:
                    ans = ans * A_n[0] * A_n[1] % mod
                    A_n.popleft()
                    A_n.popleft()
            elif len(A_p) >= 2:
                ans = ans * A_p[0] * A_p[1] % mod
                A_p.popleft()
                A_p.popleft()
            elif len(A_n) >= 2:
                ans = ans * A_n[0] * A_n[1] % mod
                A_n.popleft()
                A_n.popleft()
            K -= 2
        elif K == 1:
            ans = ans * A_p[0] % mod
            A_p.popleft()
            K -= 1
else:
    while K != 0:
        ans = ans * A_n[0] % mod
        A_n.popleft()
        K -= 1

print(ans)

Submission status: Runtime Error

Solution code:
import bisect
from collections import deque
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
MOD=10**9+7
if N==K:
    ans=1
    for i in A:
        ans=ans*i%MOD
    print(ans)
    exit()
if K%2==1 and A[0]<0:
    ans=1
    for i in range(K):
        ans=ans*A[i]%MOD
    print(ans)
    exit()
if N-A.count(0)<K:
    print(0)
    exit()
A=A[::-1]
x=deque(A[bisect.bisect_right(A,0):][::-1]+[0])
y=deque(A[:bisect.bisect_left(A,0)]+[0])
c=0
t=[]
while c<K:
    if c==K-1:
        t.append(x.popleft())
        c+=1
    elif x[0]*x[1]>=y[0]*y[1]:
        t.append(x.popleft())
        c+=1
    else:
        t.append(y.popleft())
        t.append(y.popleft())
        c+=2
ans=1
for i in t:
    ans*=i
    ans%=MOD
print(ans)

Submission status: Runtime Error

Solution code:
import sys

mod = 10**9 + 7

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().strip().split()))

# 0も入れておく
pos_list = []
neg_list = []
zero_count = 0
for a_i in A:
    if a_i > 0:
        pos_list.append(a_i)
    elif a_i == 0:
        zero_count += 1
    else:
        neg_list.append(a_i)

# 降順
pos_list.sort(reverse = True)
neg_list.sort()


lp = len(pos_list)
ln = len(neg_list)

    
if min(2 * (ln // 2), 2 * (K // 2)) + lp >= K:
    pos_twins = [pos_list[2 * i] * pos_list[2 * i + 1] for i in range(lp // 2)] + [0]
    neg_twins = [neg_list[2 * i] * neg_list[2 * i + 1] for i in range(ln // 2)] + [0]
    pos_twins.sort()
    neg_twins.sort()
 
    ans = 1
    pos_select = 0
    for i in range(K // 2):
        if pos_twins[-1] <= neg_twins[-1]:
            ans *= neg_twins[-1]
            ans %= mod
            neg_twins.pop()
        else:
            ans *= pos_twins[-1]
            ans %= mod
            pos_twins.pop()
            pos_select += 1
 
    if K % 2 == 1:
        if K == 1:
            ans = pos_list[2 * pos_select]
        else:
            ans *= pos_list[2 * pos_select]
    print(ans % mod)    
elif zero_count > 0:
	print(0)
# マイナスになるため、最小化する
else:
    ans = 1
    neg_list.sort(reverse=True)
    for i in range(K):
        ans *= neg_list[i]
        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()))
arr=sorted(arr,reverse=True,key=lambda x:abs(x))
if k==n:
  ans=1
  for i in range(n):
    ans*=arr[i]
    ans%=mod
  print(ans)
else:
  if k%2==1 and max(arr)<0:
    ans=1
    for i in range(k):
      ans*=arr[n-1-i]
      ans%=mod
    print(ans)
  else:
    ans=1
    cnt=0
    for i in range(k):
      if arr[i]<0:
        cnt+=1
      ans*=arr[i]
      ans%=mod
    if cnt%2==0:
      print(ans)
    else:
      min_plus=0
      min_minus=0
      for i in range(k):
        if arr[i]>=0:
          min_plus=arr[i]
        else:
          min_minus=arr[i]
      max_plus=0
      max_minus=0
      for i in range(k,n):
        if arr[i]>=0 and max_plus==0:
          max_plus=arr[i]
        if arr[i]<0 and max_minus==0:
          max_minus=arr[i]
      if min_plus*max_plus>=min_minus*max_minus:
        arr.remove(min_minus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_plus
        ans%=mod
      else:
        arr.remove(min_plus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%-mod
        ans*=max_minus
        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()))
arr=sorted(arr,reverse=True,key=lambda x:abs(x))
if k==n:
  ans=1
  for i in range(n):
    ans*=arr[i]
    ans%=mod
  print(ans)
else:
  if k%2==1 and max(arr)<0:
    ans=1
    for i in range(k):
      ans*=arr[n-1-i]
      ans%=mod
    print(ans)
  else:
    ans=1
    cnt=0
    for i in range(k):
      if arr[i]<0:
        cnt+=1
      ans*=arr[i]
      ans%=mod
    if cnt%2==0:
      print(ans)
    else:
      min_plus=0
      min_minus=0
      for i in range(k):
        if arr[i]>=0:
          min_plus=arr[i]
        else:
          min_minus=arr[i]
      max_plus=0
      max_minus=0
      for i in range(k,n):
        if arr[i]>=0 and max_plus==0:
          max_plus=arr[i]
        if arr[i]<0 and max_minus==0:
          max_minus=arr[i]
      print(min_plus,min_minus,max_plus,max_minus)
      if min_plus*max_plus>=min_minus*max_minus:
        arr.remove(min_minus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_plus
        ans%=mod
      else:
        arr.remove(min_plus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%-mod
        ans*=max_minus
        ans%=mod
      print(ans)

Submission status: Runtime Error

Solution code:
import sys

mod = 10**9 + 7

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().strip().split()))

# 0も入れておく
pos_list = []
neg_list = []
for a_i in A:
    if a_i >= 0:
        pos_list.append(a_i)
    else:
        neg_list.append(a_i)

# 降順
pos_list.sort(reverse = True)
neg_list.sort()


lp = len(pos_list)
ln = len(neg_list)

    
if min(2 * (ln // 2), 2 * (K // 2)) + lp >= K:
    pos_twins = [pos_list[2 * i] * pos_list[2 * i + 1] for i in range(lp // 2)] + [0]
    neg_twins = [neg_list[2 * i] * neg_list[2 * i + 1] for i in range(ln // 2)] + [0]
    pos_twins.sort()
    neg_twins.sort()
 
    ans = 1
    pos_select = 0
    for i in range(K // 2):
        if pos_twins[-1] <= neg_twins[-1]:
            ans *= neg_twins[-1]
            ans %= mod
            neg_twins.pop()
        else:
            ans *= pos_twins[-1]
            ans %= mod
            pos_twins.pop()
            pos_select += 1
 
    if K % 2 == 1:
        if K == 1:
            ans = pos_list[2 * pos_select]
        else:
            ans *= pos_list[2 * pos_select]
    print(ans % mod)    
# マイナスになるため、最小化する
else:
    ans = 1
    neg_list.sort(reverse=True)
    for i in range(K):
        ans *= neg_list[i]
        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()))
arr=sorted(arr,reverse=True,key=lambda x:abs(x))
print(arr)
if k==n:
  ans=1
  for i in range(n):
    ans*=arr[i]
    ans%=mod
  print(ans)
else:
  if k%2==1 and max(arr)<0:
    ans=1
    for i in range(k):
      ans*=arr[n-1-i]
      ans%=mod
    print(ans)
  else:
    ans=1
    cnt=0
    for i in range(k):
      if arr[i]<0:
        cnt+=1
      ans*=arr[i]
      ans%=mod
    if cnt%2==0:
      print(ans)
    else:
      min_plus=0
      min_minus=0
      for i in range(k):
        if arr[i]>=0:
          min_plus=arr[i]
        else:
          min_minus=arr[i]
      max_plus=0
      max_minus=0
      for i in range(k,n):
        if arr[i]>=0 and max_plus==0:
          max_plus=arr[i]
        if arr[i]<0 and max_minus==0:
          max_minus=arr[i]
      print(min_plus,min_minus,max_plus,max_minus)
      if min_plus*max_plus>=min_minus*max_minus:
        arr.remove(min_minus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_plus
        ans%=mod
      else:
        arr.remove(min_plus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%-mod
        ans*=max_minus
        ans%=mod
      print(ans)

Submission status: Runtime Error

Solution code:
from sys import exit
# import copy
# import numpy as np
# from collections import deque

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


A = sorted(A, key=abs)
# A_abs = [abs(n) for n in A]

ans = 1
if N == K:
    for n in A:
        ans *= n
        if abs(ans) >= 1e9+7:
            ans %= 1e9+7
    ans %= 1e9+7
    print(int(ans))
    exit()
elif K % 2 == 1 and max(A) < 0:
    ans = 1
    for i in range(K):
        ans *= A[i]
        if abs(ans) >= 1e9+7:
            ans %= 1e9+7
    ans %= 1e9+7
    print(int(ans))
    exit()
else:
    que = []
    min_minu = float("inf")
    min_plus = float("inf")
    for i in range(N-K, N):
        que.append(A[i])
        ans *= A[i]
        if min_minu == float("inf") and A[i] < 0:
            min_minu = A[i]
        if min_plus == float("inf") and A[i] > 0:
            min_plus = A[i]

    if ans >= 0:
        ans = 1
        for n in que:
            ans *= n
            if abs(ans) >= 1e9+7:
                ans %= 1e9+7
        ans %= 1e9+7
        print(int(ans))
        exit()
    else:
        max_minu = 0
        max_plus = 0
        for i in range(N-K-1, -1, -1):
            if max_minu == 0 and A[i] < 0:
                max_minu = A[i]
            if max_plus == 0 and A[i] > 0:
                max_plus = A[i]
            if max_minu != 0 and max_plus != 0:
                break

        if (min_minu == float("inf") or max_plus == 0) and (min_plus == float("inf") or max_minu == 0):
            ans = 1
            for n in que:
                ans *= n
                if abs(ans) >= 1e9+7:
                    ans %= 1e9+7
            ans %= 1e9+7
            print(int(ans))
            exit()
        else:
            if abs(max_minu / min_plus) >= abs(max_plus / min_minu):
                que.remove(min_plus)
                que.append(max_minu)
                ans = 1
                for n in que:
                    ans *= n
                    if abs(ans) >= 1e9+7:
                        ans %= 1e9+7
                ans %= 1e9+7
                print(int(ans))
                exit()
            else:
                que.remove(min_minu)
                que.append(max_plus)
                for n in que:
                    ans *= n
                    if abs(ans) >= 1e9+7:
                        ans %= 1e9+7
                ans %= 1e9+7
                print(int(ans))
                exit()

Submission status: Runtime Error

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

A_p = [i for i in A if i >= 0]
A_n = [i for i in A if i < 0]
A_p.sort()
A_p.reverse()
A_n.sort()

ans = 1
p = 0
n = 0
mod = 10 ** 9 + 7
if K % 2 == 0:
    while K != 0:
        if len(A_p) >= 2 and len(A_n) >= 2:
            if A_p[p] * A_p[p+1] > A_n[n] * A_n[n+1]:
                ans = ans * A_p[p] * A_p[p+1] % mod
                p += 2
            else:
                ans = ans * A_n[n] * A_n[n+1] % mod
                n += 2
        elif len(A_p) >= 2:
            ans = ans * A_p[p] * A_p[p+1] % mod
            p += 2
        elif len(A_n) >= 2:
            ans = ans * A_n[n] * A_n[n+1] % mod
            n += 2
        K -= 2
elif len(A_p) > 0:
    while K != 0:
        if K >= 2:
            if len(A_p) >= 2 and len(A_n) >= 2:
                if A_p[p] * A_p[p+1] > A_n[n] * A_n[n+1]:
                    ans = ans * A_p[p] * A_p[p+1] % mod
                    p += 2
                else:
                    ans = ans * A_n[n] * A_n[n+1] % mod
                    n += 2
            elif len(A_p) >= 2:
                ans = ans * A_p[p] * A_p[p+1] % mod
                p += 2
            elif len(A_n) >= 2:
                ans = ans * A_n[n] * A_n[n+1] % mod
                n += 2
            K -= 2
        elif K == 1:
            ans = ans * A_p[p] % mod
            K -= 1
else:
    n = len(A_n) - 1
    while K != 0:
        ans = ans * A_n[n] % mod
        n -= 1
        K -= 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys

mod = 10**9 + 7

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().strip().split()))

# 0も入れておく
pos_list = []
neg_list = []
for a_i in A:
    if a_i >= 0:
        pos_list.append(a_i)
    else:
        neg_list.append(a_i)

# 降順
pos_list.sort(reverse = True)
neg_list.sort()


lp = len(pos_list)
ln = len(neg_list)

# マイナスになるため、最小化する
ans = 1
if K % 2 and lp == 0:
    neg_list.sort(reverse=True)
    for i in range(K):
        ans *= neg_list[i]
        ans %= mod
    print(ans)
    
else:
    pos_twins = [pos_list[2 * i] * pos_list[2 * i + 1] for i in range(lp // 2)] + [0]
    neg_twins = [neg_list[2 * i] * neg_list[2 * i + 1] for i in range(ln // 2)] + [0]
    pos_twins.sort()
    neg_twins.sort()
 
    ans = 1
    pos_select = 0
    for i in range(K // 2):
        if pos_twins[-1] <= neg_twins[-1]:
            ans *= neg_twins[-1]
            ans %= mod
            neg_twins.pop()
        else:
            ans *= pos_twins[-1]
            ans %= mod
            pos_twins.pop()
            pos_select += 1
 
    if K % 2 == 1:
        if K == 1:
            ans = pos_list[2 * pos_select]
        else:
            ans *= pos_list[2 * pos_select]
    print(ans % mod)

Submission status: Runtime Error

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

def find(A,K):
    MOD = 10**9 +7 
    pos = []
    neg = []
    pos = sorted(pos)
    neg = sorted(neg)
    all_num = []
    zeros = 0

    for x in A:
        if x>0:
            pos += [x]
            all_num += [(x,1)]
        elif x<0:
            neg += [x]
            all_num += [(-x,-1)]
        else:
            zeros += 1
    
    if len(all_num)<K:
        return 0
    elif len(pos) == 0:
        if len(neg) < K:
            return 0
        
        elif len(neg) == K:
            if len(neg)%2 == 1:
                return 0
            else:
                temp = 1
                for x in neg:
                    temp *= x
                    temp %= MOD
                return temp
        else:
            if K%2==0:
                neg = sorted(neg)
                temp = 1
                for i in range(K):
                    x = neg[i]
                    temp *= x
                    temp %= MOD
                return temp
            else:
                if zeros>0:
                    return 0
                else:
                    temp = 1
                    for x in A:
                        temp *= x
                        temp %= MOD
                    return temp
    elif len(neg) == 0:
        A = sorted(A)[::-1]
        temp = 1
        for i in range(K):
            temp *= A[i]
            temp %= MOD
        return temp
                    
                    
                
            
    
    
    all_num = sorted(all_num)
    cur_sgn = 0
    temp = 1
    for i in range(K):
        x,sgn = all_num[i]
        temp *= x
        temp %= MOD
        cur_sgn *= sgn
        
    if cur_sgn == 1:
        return temp
    
    ans = temp
    # delete one neg, replace it by one pos
    # delete one pos, replace if by neg
    
    # find smallest neg
    neg_small = 1
    pos_small = 1
    for i in range(K):
        x,sgn = all_num[i]
        if sgn == 1:
            pos_small = x
        else:
            neg_small = x
    
    neg_big = 1
    pos_big = 1
    temp_all_nums = all_nums[K:][::-1]
    for i in range(len(temp_all_nums)):
        x,sgn = temp_all_nums[i]
        if sgn == 1:
            pos_big = x
        else:
            neg_big = x
    
    #compare 
    # if pos_big/neg_small>neg_big/pos_small:
    if pos_big*pos_small>neg_big*neg_small:
        ans *= pow(-neg_small,MOD-2,MOD)*pos_big
        ans %= MOD
        return ans
    else:
        ans *= pow(-pos_small,MOD-2,MOD)*neg_big
        ans %= MOD
        return ans

print(find(A,K))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
nums = []
p_cnt = 0
m_cnt = 0
for i in list(map(int, input().split())):
    if i >= 0:
        nums.append((i, True))
        p_cnt += 1
    else:
        nums.append((-i, False))
nums.sort()
if p_cnt == 0 and K%2!=0:
    ans = 1
    for k in range(K):
        ans *= -nums[k][0]
        ans %= mod
    print(ans)
    import sys
    sys.exit()
pl = []
ml = []
for k in range(K):
    x, b = nums.pop()
    if x == 0:
        print(0)
        import sys
        sys.exit()
    if b:
        pl.append(x)
    else:
        ml.append(x)
if len(ml) % 2 != 0:
    p = -1
    px = -1
    m = -1
    mx = -1
    while nums:
        x, b = nums.pop()
        if b:
            if ml and p == -1:
                p = x/ml[-1]
                px = x
                continue
        else:
            if pl and m == -1:
                m = x/pl[-1]
                mx = x
                continue
        if ml != -1 and pl != -1:
            if p > m:
                ml.pop()
                pl.append(px)
            else:
                pl.pop()
                ml.append(mx)
            break
    else:
        if p != -1:
            ml.pop()
            pl.append(px)
        elif m != -1:
            pl.pop()
            ml.append(mx)
ans = 1
for x in pl:
    ans *= x
    ans %= mod
for x in ml:
    ans *= -x
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,k = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
plus = []
minus = []
zero= 0 
for ai in A:
  if ai <0:
    minus.append(ai)
  else:
    plus.append(ai)
pn = len(plus)
mn = len(minus)
minusdouble = []
plus0double = []
plus1double = []
for i in range(pn//2):
  plus0double.append(plus[i*2]*plus[i*2+1])
for i in range(1,(pn)//2):
  plus1double.append(plus[i*2-1]+plus[i*2])
for i in range(mn//2):
  minusdouble.append(minus[i*2]*minus[i*2+1])
alldouble0 = plus0double + minusdouble
alldouble1 = plus1double + minusdouble
alldouble0.sort(reverse = True)
alldouble1.sort(reverse = True)
if k == 1:
  print(max(A)%mod)
elif n-mn%2 < k:
  out = 1
  for i in range(k):
    out *= A[i]
    out%= mod
  print(out)
else:
  if pn == 0:
    ans1 = ans2 = 1
    for i in range(k):
      ans1 *= minus[i]
      ans1 %= mod
    for i in range(mn-1,mn-1-k,-1):
      ans2 *= minus[i]
      ans2 %= mod
    print(max(ans1,ans2))
  elif k % 2 == 1:
    out = 1
    out *= plus[0]
    for i in range(k//2):
      out *= alldouble1[i]
      out %= mod
    print(out)
  else:
    out = 1
    for i in range(k//2):
      out *= alldouble0[i]
      out %=mod
    print(out)

# print(alldouble0)
# print(alldouble1)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
nums = []
p_cnt = 0
m_cnt = 0
for i in list(map(int, input().split())):
    if i >= 0:
        nums.append((i, True))
        p_cnt += 1
    else:
        nums.append((-i, False))
nums.sort()
if p_cnt == 0 and K%2!=0:
    ans = 1
    for k in range(K):
        ans *= -nums[k][0]
        ans %= mod
    print(ans)
    import sys
    sys.exit()
pl = []
ml = []
for k in range(K):
    x, b = nums.pop()
    if x == 0:
        print(0)
        import sys
        sys.exit()
    if b:
        pl.append(x)
    else:
        ml.append(x)
if len(ml) % 2 != 0:
    while nums:
        x, b = nums.pop()
        p = -1
        px = -1
        m = -1
        mx = -1
        if b:
            if ml and p == -1:
                p = x/ml[-1]
                px = x
                continue
        else:
            if pl and m == -1:
                m = x/pl[-1]
                mx = x
                continue
        if ml != -1 and pl != -1:
            if p > m:
                ml.pop()
                pl.append(px)
            else:
                pl.pop()
                ml.append(mx)
            break
    else:
        if p != -1:
            ml.pop()
            pl.append(px)
        elif m != -1:
            pl.pop()
            ml.append(mx)
ans = 1
for x in pl:
    ans *= x
    ans %= mod
for x in ml:
    ans *= -x
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
import heapq

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

# n=kのとき、積の最大値は負になる可能性がある
if n == k:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(a)

# Aの要素全て負かつkが奇数の時、積の最大値は必ず負
if len(pos)==0 and k%2==1:
    neg.sort(reverse=True)
    ans = 1
    for a in neg[:k]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# これより下は積の最大値は必ず正
pos = [-x for x in pos]
heapq.heapify(pos)
heapq.heapify(neg)

L_ans = []
last_pos = None
last_neg = None

ans_is_neg = False

for i in range(k):
    if (not neg) or (pos[0]<=neg[0]):
        last_pos = -heapq.heappop(pos)
        L_ans.append(last_pos)
        continue

    if (not pos) or (pos[0]>neg[0]):
        last_neg = heapq.heappop(neg)
        L_ans.append(last_neg)
        ans_is_neg = not ans_is_neg
        continue

if ans_is_neg:
    if (last_pos==None) or (not neg):
        L_ans.remove(last_neg)
        L_ans.append(-heapq.heappop(pos))

    elif not pos:
        L_ans.remove(last_pos)
        L_ans.append(heapq.heappop(neg))

    else:
        new_pos = -pos[0]
        new_neg = neg[0]

        if new_pos*last_pos>=new_neg*last_neg:
            L_ans.remove(last_neg)
            L_ans.append(new_pos)
        else:
            L_ans.remove(last_pos)
            L_ans.append(new_neg)

ans = 1
for a in L_ans:
    ans *= a
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,k = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
plus = []
minus = []
zero= 0 
for ai in A:
  if ai <0:
    minus.append(ai)
  else:
    plus.append(ai)
pn = len(plus)
mn = len(minus)
minusdouble = []
plus0double = []
plus1double = []
for i in range(pn//2):
  plus0double.append(plus[i*2]*plus[i*2+1])
for i in range(1,(pn-1)//2):
  plus1double.append(plus[i*2-1]+plus[i*2])
for i in range(mn//2):
  minusdouble.append(minus[i*2]*minus[i*2+1])
alldouble0 = plus0double + minusdouble
alldouble1 = plus1double + minusdouble
alldouble0.sort(reverse = True)
alldouble1.sort(reverse = True)
if k == 1:
  print(max(A)%mod)
elif n-mn%2 < k:
  out = 1
  for i in range(k):
    out *= A[i]
    out%= mod
  print(out)
else:
  if pn == 0:
    ans1 = ans2 = 1
    for i in range(k):
      ans1 *= minus[i]
      ans1 %= mod
    for i in range(mn-1,mn-1-k,-1):
      ans2 *= minus[i]
      ans2 %= mod
    print(max(ans1,ans2))
  elif k % 2 == 1:
    out = 1
    out *= plus[0]
    for i in range(k//2):
      out *= alldouble1[i]
      out %= mod
    print(out)
  else:
    out = 1
    for i in range(k//2):
      out *= alldouble0[i]
      out %=mod
    print(out)

# print(alldouble0)
# print(alldouble1)

Submission status: Runtime Error

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

A_p = [i for i in A if i >= 0]
A_n = [i for i in A if i < 0]
A_p.sort()
A_p.reverse()
A_n.sort()

ans = 1
p = 0
n = 0
if K % 2 == 0:
    while K != 0:
        if len(A_p) >= 2 and len(A_n) >= 2:
            if A_p[p] * A_p[p+1] > A_n[n] * A_n[n+1]:
                ans *= A_p[p] * A_p[p+1]
                p += 2
            else:
                ans *= A_n[n] * A_n[n+1]
                n += 2
        elif len(A_p) >= 2:
            ans *= A_p[p] * A_p[p+1]
            p += 2
        elif len(A_n) >= 2:
            ans *= A_n[n] * A_n[n+1]
            n += 2
        K -= 2
elif len(A_p) > 0:
    while K != 0:
        if K >= 2:
            if len(A_p) >= 2 and len(A_n) >= 2:
                if A_p[p] * A_p[p+1] > A_n[n] * A_n[n+1]:
                    ans *= A_p[p] * A_p[p+1]
                    p += 2
                else:
                    ans *= A_n[n] * A_n[n+1]
                    n += 2
            elif len(A_p) >= 2:
                ans *= A_p[p] * A_p[p+1]
                p += 2
            elif len(A_n) >= 2:
                ans *= A_n[n] * A_n[n+1]
                n += 2
            K -= 2
        elif K == 1:
            ans *= A_p[p]
            K -= 1
else:
    n = len(A_n) - 1
    while K != 0:
        ans *= A_n[n]
        n -= 1
        K -= 1

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

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
nums = []
p_cnt = 0
m_cnt = 0
for i in list(map(int, input().split())):
    if i >= 0:
        nums.append((i, True))
        p_cnt += 1
    else:
        nums.append((-i, False))
nums.sort()
if p_cnt == 0 and K%2!=0:
    ans = 1
    for k in range(K):
        ans *= -nums[k][0]
        ans %= mod
    print(ans)
    import sys
    sys.exit()
pl = []
ml = []
for k in range(K):
    x, b = nums.pop()
    if b:
        pl.append(x)
    else:
        ml.append(x)
if len(ml) % 2 != 0:
    while nums:
        x, b = nums.pop()
        p = -1
        px = -1
        m = -1
        mx = -1
        if b:
            if ml and p == -1:
                p = ml[-1] / x
                px = x
                continue
        else:
            if pl and m == -1:
                m = pl[-1] / x
                mx = x
                continue
        if ml != -1 and pl != -1:
            if p > m:
                ml.pop()
                pl.append(px)
            else:
                pl.pop()
                ml.append(mx)
            break
    else:
        if p != -1:
            ml.pop()
            pl.append(px)
        elif m != -1:
            pl.pop()
            ml.append(mx)
ans = 1
for x in pl:
    ans *= x
    ans %= mod
for x in ml:
    ans *= -x
    ans %= mod
print(ans)