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: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k,*a = map(int,read().split())

pos = []
neg = []
#both = []
zero = 0

for i in a:
    #if i!=0: both.append(i)
    
    if i==0: zero += 1
    elif i > 0: pos.append(i)
    else: neg.append(-i)

#print(pos,neg,zero)
MOD = 10**9+7

if n - zero < k: # ゼロが多すぎる
    print(0)
elif pos == []: # 全部ゼロ以下
    if k%2==0:
        neg.sort(reverse=True)
        ans = 1
        for i in range(k):
            ans *= neg[i]
            ans %= MOD
        print(ans)
    else:
        if zero:
            print(0)
        else: # 負のみ
            neg.sort()
            ans = -1
            for i in range(k):
                ans *= neg[i]
                ans %= MOD
            print(ans%MOD)
            
else: #正もいる
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    cp = len(pos)
    cn = len(neg)
    
    i = j = 0    
    for _ in range(k):
        if i == cp:
            j += 1
        elif j == cn:
            i += 1
        else:
            if pos[i] > neg[j]:
                i += 1
            else:
                j += 1
    
    #print(cp,cn,i,j)
    if j%2 == 0:
        ans = 1
        for x in pos[:i]:
            ans *= x
            ans %= MOD
        for x in neg[:j]:
            ans *= x
            ans %= MOD
        print(ans)
            
    else:
        can_i = i and j < cn
        can_j = j and i < cp
        if not can_i and not can_j:
            if zero: print(0)
            else:
                ans = -1
                for x in pos[:i]:
                    ans *= x
                    ans %= MOD
                for x in neg[:j]:
                    ans *= x
                    ans %= MOD
                print(ans)
            exit()
                
                
        if not can_i:
            j -= 1
            i += 1
        elif not can_j:
            j += 1
            i -= 1
        else:
            if pos[i]*pos[i-1] >= neg[j]*neg[j-1]:
                j -= 1
                i += 1
            else:
                j += 1
                i -= 1

        ans = 1                
        for x in pos[:i]:
            ans *= x
            ans %= MOD
        for x in neg[:j]:
            ans *= x
            ans %= MOD
        print(ans)

Submission status: Accepted

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

B = []
for a in A:
    B.append([abs(a), a])

B.sort(reverse=True)
ans =  1
pre_nega = 0
pre_posi = 0
num_posi = num_nega = 0
for count, (b, a) in enumerate(B, 1):
    ans *= b
    ans %= MOD
    if a < 0:
        pre_nega = a
        num_nega += 1
    if a > 0:
        pre_posi = a
        num_posi += 1
    if count == K:
        break

if num_nega % 2 == 0:
    print(ans)
    quit()

flag_nega = True
flag_posi = True
next_nega = next_posi = 0
for b, a in B[K:]:
    if flag_nega and a < 0:
        next_nega = a
        flag_nega = False
    elif flag_posi and a > 0:
        next_posi = a
        flag_posi = False

if next_nega != 0 and num_posi > 0:
    if next_posi != 0 and num_nega > 0:
        if next_nega * pre_nega > next_posi * pre_posi:
            ans *= abs(next_nega)
            ans *= pow(pre_posi, MOD-2, MOD)
            ans %= MOD
        else:
            ans *= next_posi
            ans *= pow(abs(pre_nega), MOD-2, MOD)
            ans %= MOD
    else:
        ans *= abs(next_nega)
        ans *= pow(pre_posi, MOD-2, MOD)
        ans %= MOD
else:
    if next_posi != 0 and num_nega > 0:
        ans *= next_posi
        ans *= pow(abs(pre_nega), MOD-2, MOD)
        ans %= MOD
    else:
        if 0 in A:
            ans = 0
        else:
            ans = 1
            B.sort()
            for count, (b, a) in enumerate(B, 1):
                ans *= a
                ans %= MOD
                if count == K:
                    break

print(ans)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    A=LI()
    Lp=[]
    Lm=[]
    Lz=[]
    for i in range(N):
        if A[i]==0:
            Lz.append(0)
        elif A[i]>0:
            Lp.append(A[i])
        else:
            Lm.append(A[i])
            
    Lp.sort(reverse=True)
    Lm.sort()
    
    Np=len(Lp)
    Nm=len(Lm)
    
    if len(Lp)+len(Lm)<K:#どうしても0が入る
        print(0)
        exit()
    if K==1:
        print(max(A))
        exit()
    if max(A)<=0:#正数がない
        if K%2==0:
            A.sort()
        else:
            A.sort(reverse=True)
        ans=1
        for i in range(K):
            ans=(ans*A[i])%mod
        print(ans)
        exit()
    if K==N:
        ans=1
        for i in range(N):
            ans=(ans*A[i])%mod
        print(ans)
        exit()
    
    Lp.append(0)
    Lp.append(0)
    Lp.append(0)
    Lm.append(0)
    Lm.append(0)
    nowp=0
    nowm=0
    
    ans=1
    if K%2==0:
        for i in range(K//2):
            a=Lp[nowp]*Lp[nowp+1]
            b=Lm[nowm]*Lm[nowm+1]
            if a>=b:
                ans=(ans*a)%mod
                nowp+=2
            else:
                ans=(ans*b)%mod
                nowm+=2
    else:
        ans=Lp[0]
        nowp+=1
        for i in range(K//2):
            a=Lp[nowp]*Lp[nowp+1]
            b=Lm[nowm]*Lm[nowm+1]
            if a>=b:
                ans=(ans*a)%mod
                nowp+=2
            else:
                ans=(ans*b)%mod
                nowm+=2
    print(ans)
        
            

        
 
    
            
            

main()

Submission status: Accepted

Solution code:
#

import sys
input=sys.stdin.readline
MOD=10**9+7


def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    if N==1:
        print(A[0])
        exit()
    A.sort()
    A2n=[]
    for i in range(0,N,2):
        if i+1>=N:
            break
        if A[i]<=0 and A[i+1]<=0:
            A2n.append(A[i]*A[i+1])
        else:
            break

    A.sort(reverse=True)
    ans=1
    if A[0]<=0 and K%2==1:
        for i in range(K):
            ans=(ans*A[i])%MOD
        print(ans)
        exit()
    ni=0
    i=0
    while(K>0):
        if i+1<N and len(A2n)-ni>0 and A[i]*A[i+1]<A2n[ni] and K>=2:
                ans=(ans*A2n[ni])%MOD
                K-=2
                ni+=1
        else:
            ans=(ans*A[i])%MOD
            i+=1
            K-=1
    print(ans)
            
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
L=list(map(int,input().split()))
P=[]
M=[]
Z=[]
mod=10**9+7
for i in L:
    if i>0:
        P.append(i)
    elif i<0:
        M.append(i)
    else:
        Z.append(i)

P.sort(reverse=True)
M.sort()

if len(P)==0:
    if K%2==0:
        M+=Z
        ans=1
        #print(M)
        for i in range(K):
            ans*=M[i]
            ans%=mod
        print(ans)
    else:
        if len(Z)>0:
            print(0)
        else:
            M.sort(reverse=True)
            ans=1
            for i in range(K):
                ans*=M[i]
                ans%=mod
            print(ans)
else:
    if N==K:
        ans=1
        for i in range(N):
            ans*=L[i]
            ans%=mod
        print(ans)
    elif K%2==0:
        P+=[0,0]
        P+=Z
        M+=[0,0]
        M+=Z
        ans=1
        p=0
        m=0
        for i in range(K//2):
            if P[p*2]*P[p*2+1]>M[m*2]*M[m*2+1]:
                ans*=(P[p*2]*P[p*2+1])
                ans%=mod
                p+=1
            else:
                ans*=(M[m*2]*M[m*2+1])
                ans%=mod
                m+=1
        print(ans)
    else:
        P+=[0,0]
        P+=Z
        M+=[0,0]
        M+=Z
        ans=P[0]
        p=1
        m=0
        for i in range(K//2):
            if P[p*2]*P[p*2-1]>M[m*2]*M[m*2+1]:
                ans*=(P[p*2]*P[p*2-1])
                ans%=mod
                p+=1
            else:
                ans*=(M[m*2]*M[m*2+1])
                ans%=mod
                m+=1
        print(ans)

Submission status: Accepted

Solution code:
from math import log10
n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10**9+7
a.sort()

cnt_neg = 0
cnt_pos = 0
for i in a:
   if i <= 0:
      cnt_neg += 1
   else:
      cnt_pos += 1
is_minus = False
k_tmp = k
while k_tmp > 0:
   if k_tmp >= 2:
      if cnt_neg >= 2:
         cnt_neg -= 2
      elif cnt_pos >= 2:
         cnt_pos -= 2
      else:
         is_minus = True
         break
      k_tmp -= 2
   else:
      if cnt_pos > 0:
         cnt_pos -= 1
         k_tmp -= 1
      else:
         is_minus = True
         break

k_1 = k
ans1 = 1
l = 0
r = n - 1
if k_1 % 2:
   ans1 *= a[-1]
   r -= 1
   k_1 -= 1
while k_1 >= 2:
   if a[l] * a[l+1] > a[r-1] * a[r]:
      ans1 *= a[l] * a[l+1]
      l += 2
   else:
      ans1 *= a[r-1] * a[r]
      r -= 2
   k_1 -= 2
   ans1 %= MOD

a.sort(key=abs)
# print(a)
ans2 = 1
for i in a[:k]:
   ans2 *= i
   ans2 %= MOD

if is_minus:
   print(ans2)
else:
   print(ans1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)



@mt
def slv(N, K, A):
    M = 10**9+7

    def p(N, K, A):
        pa = [a for a in A if a >= 0]
        na = [-a for a in A if a < 0]
        # positive
        pa.sort()
        na.sort()
        ans = 1
        if K % 2 == 1:
            if len(pa) == 0:
                return None
            ans *= pa.pop()
            K -= 1
        for _ in range(K//2):
            if len(pa) >= 2 and len(na) >= 2:
                if pa[-1] * pa[-2] > na[-1] * na[-2]:
                    ans *= pa[-1] * pa[-2]
                    pa.pop()
                    pa.pop()
                else:
                    ans *= na[-1] * na[-2]
                    na.pop()
                    na.pop()
            elif len(pa) >= 2:
                ans *= pa[-1] * pa[-2]
                pa.pop()
                pa.pop()
            elif len(na) >= 2:
                ans *= na[-1] * na[-2]
                na.pop()
                na.pop()
            else:
                break
            ans %= M
        else:
            return ans
        return None

    def n(N, K, A):
        pa = [a for a in A if a >= 0]
        na = [-a for a in A if a < 0]
        # negative
        pa.sort(reverse=True)
        na.sort(reverse=True)
        ans = 1
        for _ in range(K):
            if pa and na:
                if pa < na:
                    ans *= pa[-1]
                    pa.pop()
                else:
                    ans *= -na[-1]
                    na.pop()
            elif pa:
                ans *= pa[-1]
                pa.pop()
            else:
                ans *= -na[-1]
                na.pop()
            ans %= M
        return ans

    a = p(N, K, A)
    if a:
        return a
    return n(N, K, A)


def main():
    N, K = read_int_n()
    A = read_int_n()
    print(slv(N, K, A))

    import random
    # N = random.choice([9, 10])
    # K = random.randint(1, N)
    # A = [random.randint(-20, 20) for _  in range(N)]

    # N = 9
    # K = 9
    # A = [4, -9, -18, 7, 3, -5, -15, 14, -20]
    # print(N, K)
    # print(A)
    # print(slv(N, K, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 10**9+7
def prod(A):
    r = 1
    for a in A:
        r *= abs(a)
        r %= mod
    return r

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=abs, reverse=True)

Ak = A[:K]
m = len([a for a in Ak if a<0])

if m%2==0:
    print(prod(Ak))
    exit()

r_p = [a for a in A[K:] if a>=0]
r_n = [a for a in A[K:] if a<=0]
a_p = [a for a in Ak    if a> 0]
a_n_min = max([a for a in Ak if a< 0])

ans1 = ans2 = None
if r_p:
    v1 = abs(a_n_min)
    w1 = max(r_p)
    ans1 = prod(Ak)*pow(v1, mod-2, mod) * w1 % mod
    
if a_p and r_n:
    v2 = min(a_p)
    w2 = abs(min(r_n))
    ans2 = prod(Ak)*pow(v2, mod-2, mod) * w2 % mod
    
if ans1 and ans2:
    print(ans1 if w1*v2>=w2*v1 else ans2)
    exit()

if ans1:
    print(ans1)
    exit()

if ans2:
    print(ans2)
    exit()

print((-prod(A[::-1][:K]))%mod)

Submission status: Accepted

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

P = []
M = []
Z = 0
for i in A:
  if i < 0:
    M.append(abs(i))
  if i > 0:
    P.append(i)
  if i == 0:
    Z += 1

if len(M) + len(P) < K:
  print(0)
  exit()
elif len(M) + len(P) == K:
  ans = 1
  for i in M:
    ans = ans * i % MOD
  for i in P:
    ans = ans * i % MOD
  if len(M) % 2 == 1:
    ans *= -1
    ans += MOD
  print(ans)
  exit()

M.sort(reverse = True)
P.sort(reverse = True)

if len(P) == 0:
  ans = 1
  if K % 2 == 0:
    for i in range(K):
      ans = ans * M[i] % MOD
  else:
    if Z != 0:
      print(0)
      exit()
    for i in range(K):
      ans = ans * -M[-1 -i] % MOD
    while ans < 0:
      ans += MOD
  print(ans)
else:
  ans = 1
  pn = 0
  mn = 0
  if K % 2 == 1:
    K -= 1
    ans *= P[0]
    pn = 1
  for i in range(K // 2):
    if pn + 2 > len(P):
      ans = ans * M[mn] * M[mn + 1] % MOD
      mn += 2
    elif mn + 2 > len(M):
      ans = ans * P[pn] * P[pn + 1] % MOD
      pn += 2
    else:
      p = P[pn] * P[pn + 1]
      m = M[mn] * M[mn + 1]
      if p > m:
        ans = ans * p % MOD
        pn += 2
      else:
        ans = ans * m % MOD
        mn += 2
  print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
b,c,d = 0,0,0
mod = 10**9+7
B = []
C = []
D = []
for a in A:
    if a < 0:
        b += 1
        B.append(a)
    elif a == 0:
        c += 1
        C.append(a)
    else:
        d += 1
        D.append(a)
if B:
    B.sort()
if D:
    D.sort(reverse = True)
if K > b+d:
    print(0)
elif K == b+d and K< N and b%2 == 1:
    print(0)
elif K == N:
    ans = 1
    for i in range(N):
        ans = ans * A[i] % mod
    print(ans)
elif b == N and K % 2 == 1:
    ans = 1
    for i in range(1,K+1):
        ans = ans*B[-i]%mod
    print(ans)
elif K<b and d == 0 and K%2 == 1:
    print(0)
else:
    bi = 0
    di = 0
    ans = 1
    while(K>1):
        if (bi >= b-1) or (di+1< d and D[di]*D[di+1] > B[bi]*B[bi+1]):
            ans = ans*D[di]%mod
            ans = ans*D[di+1]%mod
            di += 2
        else:
            ans = ans*B[bi]%mod
            ans = ans*B[bi+1]%mod
            bi += 2
        K -= 2
    if K == 1:
        ans = ans * D[di] % mod
    print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
*A, = map(int, input().split())
p = 10**9 + 7
A.sort()
ans = 1
# 全部0以下の場合かつkが奇数の場合はトップk個の積
if A[n - 1] <= 0 and k % 2 == 1:
    for i in range(k):
        ans *= A[n - 1 - i]
        ans %= p
    print(ans)
    exit()

i = 0
j = n - 1
# kが奇数なら最大は絶対使う
if k % 2 == 1:
    ans *= A[j]
    ans %= p
    j -= 1
    k -= 1
    n -= 1
# 以下A[n-1]を除いてkを偶数として考える
k //= 2
for _ in range(min(k, n // 2)):
    # 2個ずつのペアを作って採用するかを決めていく
    left = A[i] * A[i + 1]
    right = A[j] * A[j - 1]
    if (left > right):
        ans *= left
        ans %= p
        i += 2
    else:
        ans *= right
        ans %= p
        j -= 2
print(ans)

Submission status: Accepted

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

negs = [-x for x in a if x < 0]
non_negs = [x for x in a if x >= 0]

if len(non_negs) == 0 and k % 2 == 1:
    negs.sort()
    ans = 1
    for i in range(k):
        ans = ans * -negs[i] % MOD
    print(ans)
    exit()

negs_p, non_negs_p = 0, 0

negs.sort(reverse = True)
non_negs.sort(reverse = True)

for i in range(k):
    if negs_p == len(negs):
        non_negs_p += 1
    elif non_negs_p == len(non_negs):
        negs_p += 1
    elif negs[negs_p] > non_negs[non_negs_p]:
        negs_p += 1
    else:
        non_negs_p += 1

if negs_p % 2 == 0 or k == n:
    ans = 1
    for i in range(negs_p):
        ans = ans * -negs[i] % MOD
    for i in range(non_negs_p):
        ans = ans * non_negs[i] % MOD
    print(ans)
    exit()

if negs_p == len(negs) or non_negs_p == 0:
    negs_p -= 1
    non_negs_p += 1
    ans = 1
    for i in range(negs_p):
        ans = ans * -negs[i] % MOD
    for i in range(non_negs_p):
        ans = ans * non_negs[i] % MOD
    print(ans)
    exit()

if non_negs_p == len(non_negs) or negs_p == 0:
    negs_p += 1
    non_negs_p -= 1
    ans = 1
    for i in range(negs_p):
        ans = ans * -negs[i] % MOD
    for i in range(non_negs_p):
        ans = ans * non_negs[i] % MOD
    print(ans)
    exit()


a = negs[negs_p - 1]
b = negs[negs_p]
c = non_negs[non_negs_p - 1]
d = non_negs[non_negs_p]

if a * b > c * d:
    negs_p += 1
    non_negs_p -= 1
else:
    negs_p -= 1
    non_negs_p += 1

ans = 1
for i in range(negs_p):
    ans = ans * -negs[i] % MOD
for i in range(non_negs_p):
    ans = ans * non_negs[i] % MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(key=abs, reverse=True)
s = 0
ps = 0
for i in range(k):
    if a[i] < 0:
        s ^= 1
    else:
        ps = 1
b = a[:k]
b.sort(key=abs)
if s:
    p = -MOD
    for i in range(k, n):
        if a[i] >= 0:
            p = a[i]
            break
    q = MOD
    if ps:
        for i in range(k, n):
            if a[i] <= 0:
                q = a[i]
                break
    x = 0
    for j in range(k):
        if b[j] < 0:
            x = b[j]
            xi = j
            break
    y = 0
    for j in range(k):
        if b[j] > 0:
            y = b[j]
            yi = j
            break
    flg = 1
    if y == 0:
        if p >= 0:
            b[xi] = p
            flg = 0
    else:
        if p * y > q * x and p > 0:
            b[xi] = p
        elif q < 0:
            b[yi] = q
        flg = 0
    if flg:
        b = a[-k:]
res = 1
for i in range(k):
    res = res * b[i] % MOD
print(res)

Submission status: Accepted

Solution code:
from math import log10 as log2

N, K = map(int, input().split())
A = [int(i) for i in input().split()]

mod = 10 ** 9 + 7

p = []
m = []
for a in A :
  if a > 0 :
    p.append(a)
  elif a < 0 :
    m.append(-a)
    
p.sort(reverse=True)
m.sort(reverse=True)
pl = [0]
ml = [0]

for i in range(len(p)) :
  pl.append(log2(p[i]))
for i in range(len(m)) :
  ml.append(log2(m[i]))
for i in range(1, len(pl)) :
  pl[i] += pl[i - 1]
for i in range(1, len(ml)) :
  ml[i] += ml[i - 1]

Mi = -1
Mv = 0
for i in range(0, len(ml), 2) :
  j = K - i
  if len(pl) <= j or j < 0 : continue
  if ml[i] + pl[j] > Mv :
    Mi, Mv = i, ml[i] + pl[j]

if Mi != -1 :
  ret = 1
  for i in range(K - Mi) :
    ret *= p[i]
    ret %= mod
  for i in range(Mi) :
    ret *= m[i]
    ret %= mod
else :
  x = [abs(a) for a in A]
  x.sort()
  ret = 1
  for i in range(K) :
    ret *= x[i]
    ret %= mod
  ret = -ret % mod
  
print(ret)

Submission status: Accepted

Solution code:
from math import log2
from itertools import accumulate

epsilon = 10 ** -5

MOD = 10 ** 9 + 7

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

negs = []
poss = []
for A in As:
    if A > 0:
        poss.append(A)
    elif A < 0:
        negs.append(-A)

poss.sort(reverse = True)
negs.sort(reverse = True)

if len(poss) + len(negs) < K:
    print(0)
    exit()

if len(poss) == 0:
    if N > len(negs):
        if K % 2 == 1:
            print(0)
        else:
            ans = 1
            for n in negs[:K]:
                ans *= n
                ans %= MOD
            print(ans)
    else:
        if K % 2 == 1:
            ans = 1
            for n in negs[-K:]:
                ans *= n
                ans %= MOD
            print(-ans%MOD)
        else:
            ans = 1
            for n in negs[:K]:
                ans *= n
                ans %= MOD
            print(ans)
    exit()

if K == N:
    ans = 1
    for A in As:
        ans *= A
        ans %= MOD
    print(ans)
    exit()


def mulmod(a, b):
    return a * b % MOD

logs_poss = [0.0] + [log2(p) for p in poss] 
logs_poss_csum = list(accumulate(logs_poss))

poss_mod_csum = [1] + list(accumulate(poss, mulmod))

logs_negs = [0.0] + [log2(n) for n in negs] 
logs_negs_csum = list(accumulate(logs_negs))

negs_mod_csum = [1] + list(accumulate(negs, mulmod))

max_log = -1
for minus in range(0, K+1, 2):
    plus = K - minus
    if plus <= len(poss) and minus <= len(negs):
        if max_log + epsilon < logs_poss_csum[plus] + logs_negs_csum[minus]:
            max_log = logs_poss_csum[plus] + logs_negs_csum[minus]
            max_mod = poss_mod_csum[plus] * negs_mod_csum[minus] % MOD
        elif max_log <= logs_poss_csum[plus] + logs_negs_csum[minus]:
            mod = poss_mod_csum[plus] * negs_mod_csum[minus] % MOD
            if mod > max_mod:
                max_log = logs_poss_csum[plus] + logs_negs_csum[minus]
                max_mod = poss_mod_csum[plus] * negs_mod_csum[minus] % MOD

print(max_mod)

Submission status: Accepted

Solution code:
def examA():
    N = I()
    ans = (10000 - N)%1000
    print(ans)
    return

def examB():
    T = ["AC","WA","TLE","RE"]
    N = I()
    S = [SI()for _ in range(N)]

    ans = [0]*4
    for s in S:
        for i in range(4):
            if s==T[i]:
                ans[i] += 1
                break
    for i in range(4):
        print(T[i]+" x "+str(ans[i]))
    return

def examC():
    H, W, K = LI()
    C = [[""]*W for _ in range(H)]
    for h in range(H):
        S = SI()
        for w in range(W):
            C[h][w] = S[w]
    ans = 0
    #print(C)
    for hi in range(1<<H):
        nowC = deepcopy(C)
        for h in range(H):
            if hi&(1<<h):
                for i in range(W):
                    nowC[h][i] = "R"
        for wi in range(1 << W):
            nowCC = deepcopy(nowC)
            for w in range(W):
                if wi & (1 << w):
                    for i in range(H):
                        nowCC[i][w] = "R"
            cnt = 0
            for h in range(H):
                for w in range(W):
                    if nowCC[h][w] == "#":
                        cnt += 1
            if cnt == K:
                #print(hi, wi, nowCC)
                ans += 1
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    A.sort(reverse=True)
    ans = 0
    ans += A[0]
    cur = 0
    for i in range(2,N):
        if i%2==0:
            cur += 1
        ans += A[cur]
    print(ans)
    return

def examE():
    N, K = LI()
    A = LI()
    A_neg = []; neg = 0
    A_0 = []; num_0 = 0
    A_pos = []; pos = 0
    for a in A:
        if a<0:
            A_neg.append(-a)
            neg += 1
        elif a==0:
            A_0.append(a)
            num_0 += 1
        else:
            A_pos.append(a)
            pos += 1
    if N-num_0<K:
        print(0)
        return
    A_neg.sort()
    A_pos.sort()
    if pos==0:
        ans = 1
        if K%2==0:
            ans = 1
            for i in range(neg-K,neg):
                ans *= A_neg[i]
                ans %= mod
        else:
            for i in range(K):
                ans *= A_neg[i]
                ans %= mod
            ans = mod - ans
            if num_0>0:
                ans = 0
        print(ans)
        return

    if neg==0:
        ans = 1
        for i in range(pos - K, pos):
            ans *= A_pos[i]
            ans %= mod
        print(ans)
        return

    A_neg.sort(reverse=True)
    A_pos.sort(reverse=True)

    now_p = 0
    now_n = 0
    ans = 1

    if pos+neg==K:
        for i in range(pos):
            ans *= A_pos[i]
            ans %= mod
        for i in range(neg):
            ans *= A_neg[i]
            ans %= mod
        if neg%2==1:
            ans = mod-ans
        print(ans)
        return

    if K%2==1:
        ans *= A_pos[now_p]
        now_p += 1

    while (now_n + now_p < K):
        if now_n + 1 >= neg:
            ans *= A_pos[now_p] * A_pos[now_p + 1]
            ans %= mod
            now_p += 2
            continue
        if now_p + 1 >= pos:
            ans *= A_neg[now_n] * A_neg[now_n + 1]
            ans %= mod
            now_n += 2
            continue

        if A_pos[now_p] * A_pos[now_p + 1] >= A_neg[now_n] * A_neg[now_n + 1]:
            ans *= A_pos[now_p] * A_pos[now_p + 1]
            ans %= mod
            now_p += 2
        else:
            ans *= A_neg[now_n] * A_neg[now_n + 1]
            ans %= mod
            now_n += 2

    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
6
8 7 6 5 4 3


5 5
-1 -2 3 4 5
"""

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
if N == 1:
  print(max(a))
  exit(0)

mod = 10 ** 9 + 7
mn = []
zr = 0
pl = []
t = []
for x in a:
  if x < 0:
    mn.append(-x)
    t.append((-x, 0))
  elif x == 0: zr += 1
  else:
    pl.append(x)
    t.append((x, 1))

if N - zr < K:
  print(0)
  exit(0)

t.sort(reverse = True)
#print(t)
c = 0
res = 1
lpl = -1
lmn = -1
for x, cc in t[: K]:
  res *= x
  res %= mod
  c ^= (cc == 0)
  if cc: lpl = x
  else: lmn = x
if c == 0:
  print(res)
  exit(0)

respl = -1
resmn = -1
plt = 0
mnt = 0
if lpl != -1:
  respl = res + 0
  for x, cc in t[K: ]:
    if cc == 0:
      respl *= pow(lpl, mod - 2, mod)
      respl %= mod
      respl *= x
      respl %= mod
      plt = x
      break
  else: respl = -1

if lmn != -1:
  resmn = res + 0
  for x, cc in t[K: ]:
    if cc:
      resmn *= pow(lmn, mod - 2, mod)
      resmn %= mod
      resmn *= x
      resmn %= mod
      mnt = x
      break
  else: resmn = -1
#print(respl, resmn)
if (respl != -1) ^ (resmn != -1):
  print(max(respl, resmn))
  exit(0)
if (respl != -1) and (resmn != -1):
  if plt * lmn > mnt * lpl: print(respl)
  else: print(resmn)
  exit(0)

if len(pl) >= K:
  res = 1
  for x in pl[: K]:
    res *= x
    res %= mod
  print(res)
  exit(0)
if zr:
  print(0)
  exit(0)
res = 1
t.reverse()
for x, _ in t[: K]:
  res *= x
  res %= mod
print(-res % mod)