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: Wrong Answer

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

if N==K:
    ans=1
    for i in range(N):
        ans=(ans*A[i])%mod
    print(ans%mod)
else:
    neg=[]
    posi=[]
    zero=0
    for i in range(N):
        if A[i]>0:
            posi.append(A[i])
        elif A[i]<0:
            neg.append(-A[i])
        else:
            zero+=1
    if K>N-zero:
        print(0)
    elif len(neg)==N and K%2==1:
        neg.sort()
        ans=1
        for i in range(K):
            ans=(-ans*neg[i])%mod
        print(ans%mod)
    else:
        A.sort(key=lambda x:-abs(x))
        temp=A[:K]
        rest=A[K:]
        check=0
        for i in range(K):
            if temp[i]<0:
                check+=1
        if check%2==0:
            ans=1
            for i in range(K):
                ans=(ans*temp[i])%mod
            print(ans%mod)
        else:
            if check!=K and check!=0:
                rest.sort()
                temp.sort()
                #neg->posi
                val1=-1
                val2=-1
                for i in range(K-1):
                    if temp[i]<0 and temp[i+1]>0:
                        val1=temp[i]
                        val2=temp[i+1]
                        break
                (abs(val1),rest[-1])
                #posi->neg
                (abs(val2),abs(rest[0]))
                if abs(rest[-1])*abs(val2)>abs(rest[0])*abs(val1):
                    ans=1
                    for i in range(K):
                        ans=(ans*temp[i])%mod
                    ans=(ans*rest[-1])%mod
                    ans=(ans*pow(val1,mod-2,mod))%mod
                    print(ans%mod)
                else:
                    ans=1
                    for i in range(K):
                        ans=(ans*temp[i])%mod
                    ans=(ans*rest[0])%mod
                    ans=(ans*pow(val2,mod-2,mod))%mod
                    print(ans%mod)
            elif check==K:
                val1=temp[-1]
                ans=1
                for i in range(K):
                    ans=(ans*temp[i])%mod
                ans=(ans*rest[-1])%mod
                ans=(ans*pow(val1,mod-2,mod))%mod
                print(ans%mod)
            else:
                val2=temp[0]
                ans=1
                for i in range(K):
                    ans=(ans*temp[i])%mod
                ans=(ans*rest[0])%mod
                ans=(ans*pow(val2,mod-2,mod))%mod
                print(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys
N,K=[int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]

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

if len(plus)+len(minus)<K:
    print(0)
    sys.exit(0)

if len(plus)==0:
    minus=sorted(minus,reverse=True)
    retval=1
    for i in minus[:K]:
        retval*=i
    print(retval%(10**9+7))
    sys.exit(0)


plus=sorted(plus,reverse=True)
minus=sorted(minus)

A=sorted(A,key=lambda w:abs(w),reverse=True)

retval=1
use_minus=0
for i in range(K):
    a=A[i]
    if a<0:
        use_minus+=1
    retval*=a

if retval>0:
    print(retval%(10**9+7))
else:
    retval=retval//minus[use_minus-1]
    use_plus=K-use_minus
    retval=retval*plus[use_plus]
    print(retval%(10**9+7))

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def rev(i):
    ni = i
    ans = 1
    t = 10**9+5
    mod = 10**9+7
    while t > 0:
        if t&1:
            ans = (ans*ni)%mod
        t >>= 1
        ni = (ni**2)%mod
    return ans

def main():
    n,k = map(int,ipt().split())
    a = [(abs(int(i)),int(i)) for i in ipt().split()]
    Mi = 10**9
    Ma = -10**9
    mod = 10**9+7
    a.sort(reverse=True)
    for i in a:
        if Ma < i[1]:
            Ma = i[1]
        if Mi > i[1]:
            Mi = i[1]
    if Ma < 0 and k&1:
        ans = 1
        for i,ai in enumerate(a[::-1]):
            ans = (ans*ai[0])%mod
            if i == k-1:
                break
        print((-ans)%mod)
        exit()
    pp = None
    pm = None
    ans = 1
    s = 1
    for i,ai in enumerate(a[:k:]):
        ans = ans*ai[0]%mod
        if ai[1] == 0:
            print(0)
            exit()
        elif ai[1] > 0:
            pp = ai[0]
        else:
            pm = ai[0]
            s *= -1
    if s == 1:
        print(ans)
        exit()
    np = 0
    nm = 0
    for ai in a[k::]:
        if ai[1] > 0 and not np:
            np = ai[0]
        elif ai[1] < 0 and not nm:
            nm = ai[0]
        if np and nm:
            break
    if pp == None:
        print(0)
    elif nm == None:
        print(ans*rev(pm)*np%mod)
    elif np == None:
        print(ans*rev(pp)*nm%mod)
    else:
        if nm*pm < np*pp:
            print(ans*rev(pm)*np%mod)
        else:
            print(ans*rev(pp)*nm%mod)



    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
MOD = 1000000007
a = sorted(a)
res = 1
if(k % 2 == 1):
	if(a[-1] == 0):
		print(0)
		exit()
	elif(a[-1] < 0):
		for i in range(n - 1, n - k - 1, -1):
			res = res * a[i]
			res %= MOD
			if res < 0:
				res += MOD
		print(res)
		exit()
idx1 = 0
idx2 = n - 1
if(k % 2 == 1):
	res = res * a[idx2]
	idx2 -= 1
	k -= 1
k = k // 2
for i in range(k):
	l = a[idx1] * a[idx1 + 1]
	r = a[idx2] * a[idx2 - 1]
	l %= MOD
	if l < 0:
		l += MOD
	r %= MOD
	if r < 0:
		r += MOD
	if l > r:
		res *= l
		res %= MOD
		if res < 0:
			res += MOD
		idx1 += 2
	else:
		res *= r
		res %= MOD
		if res < 0:
			res += MOD
		idx2 -= 2
print(res)

Submission status: Wrong Answer

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

len_n = n -1
kazu = 1
for i in range(k):
  kazu *= a[len_n]
  len_n -= 1
  
if kazu >= 10**9 + 7:
  print(kazu % (10**9 + 7))
elif kazu < 0:
  print(kazu % (10**9 + 7))
else:
  print(kazu)

Submission status: Wrong Answer

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

P = []
M = []
Z = []
for i in range(N):
    if A[i]>0:
        P.append(A[i])
    elif A[i]<0:
        M.append(A[i])
    else:
        Z.append(A[i])

mod = 1000000007

if len(P)+len(M) < K:
    print(0)
elif len(P)==0:
    if K%2==1:
        if len(Z)>0:
            print(0)
        else:
            M.sort(reverse=True)
            ans = 1
            for i in range(K):
                ans*=abs(M[i])
                ans%=mod
            if ans==0:
                print(ans)
            else:
                print(mod-ans)
    else:
        M.sort()
        ans = 1
        for i in range(K):
            ans*=abs(M[i])
            ans%=mod
        print(ans)
else:
    B = [(abs(A[i]),A[i]) for i in range(N)]
    B.sort(reverse=True,key=lambda x:x[0])
    pc = 0
    lastpc = -1
    mc = 0
    lastmc = -1
    for i in range(K):
        if B[i][1]>0:
            pc += 1
            lastpc = i
        else:
            mc += 1
            lastmc = i
    if mc%2==0:
        ans = 1
        for i in range(K):
            ans *= B[i][0]
            ans %= mod
        print(ans)
    else:
        nextpc = -1
        nextmc = -1
        for i in range(K,N):
            if B[i][1]>0:
                if nextpc==-1:
                    nextpc=i
            elif B[i][1]<0:
                if nextmc==-1:
                    nextmc=i
        if nextmc==-1 and nextpc==-1:
            if len(Z)>0:
                print(0)
            else:
                ans = 1
                for i in range(K):
                    ans *= B[i][0]
                    ans %= mod
                if ans==0:
                    print(ans)
                else:
                    print(mod-ans)
        elif nextmc==-1:
            ans = 1
            for i in range(K):
                if i!=lastmc:
                    ans *= B[i][0]
                    ans %= mod
            ans *= B[nextpc][0]
            ans %= mod
            print(ans)
        elif nextpc==-1:
            ans = 1
            for i in range(K):
                if i!=lastpc:
                    ans *= B[i][0]
                    ans %= mod
            ans *= B[nextmc][0]
            ans %= mod
            print(ans)
        else:
            if B[nextpc][0]*B[lastpc][0] > B[nextmc][0]*B[lastmc][0]:
                ans = 1
                for i in range(K):
                    if i!=lastmc:
                        ans *= B[i][0]
                        ans %= mod
                ans *= B[nextpc][0]
                ans %= mod
                print(ans)
            else:
                ans = 1
                for i in range(K):
                    if i!=lastpc:
                        ans *= B[i][0]
                        ans %= mod
                ans *= B[nextmc][0]
                ans %= mod
                print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce
import operator
def prod(iterable):
    return reduce(operator.mul, iterable, 1)
N,K = map(int,input().split())
LIST = list(map(int, input().split()))
LIST = sorted(LIST)
FIRST = prod(LIST[:K])
Sec = prod(LIST[-K:])
ANS = [FIRST,Sec]
print(max(ANS)%((10**9)+7))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    if n == k:
        ans = a[0]
        for i in a[1:]:
            ans *= i
            ans %= mod
        print(ans)
        return
    mi = []
    ma = []
    a.sort()
    for ai in a:
        if ai <= 0:
            heappush(mi, ai)
        else:
            heappush(ma, -ai)
    if not ma:
        ans = 1
        if k & 1:
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
        else:
            for i in range(k):
                ans *= a[i]
                ans %= mod
        print(ans)
        return
    return
    if len(mi) >= k:
        ans = 1
        A = []
        if k & 1:
            k -= 1
            ans *= -heappop(ma)
        for _ in range(k):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        while len(ma) >= 2 and len(A) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            if g1 * g2 < h1 * h2:
                print(ans)
                return
            ans *= pow(h1 * h2, mod - 2, mod)
            ans %= mod
            ans *= g1 * g2
            ans %= mod
        print(ans)
    else:
        L = len(mi)
        A = []
        if len(mi) & 1:
            k -= 1
            L -= 1
            ans *= -heappop(ma)
        X = k - L
        for i in range(L):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        for i in range(X):
            x = -heappop(ma)
            ans *= x
            ans %= mod
        while len(ma) >= 2 and len(A) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            if g1 * g2 < h1 * h2:
                print(ans)
                return
            ans *= pow(h1 * h2, mod - 2, mod)
            ans %= mod
            ans *= g1 * g2
            ans %= mod
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort(key=lambda x:-abs(x))
p = []
n = []
for i in range(K):
    a = A[i]
    if a>0:
        p.append(a)
    elif a<0:
        n.append(a)

if len(n)%2==0:
    ans = 1
    for a in n:
        ans *= a
        ans %= mod
    for a in p:
        ans *= a
        ans %= mod
else:
    ap = 0
    an = 0
    for i in range(K,N):
        if ap==0 and A[i]>0:
            ap = A[i]
        if an==0 and A[i]<0:
            an = -A[i]
    if len(p)*len(n)>0:
        ap_ = p[-1]
        an_ = -n[-1]
        if ap_*an_==0:
            ans = 0
        else:
            if ap*ap_>an*an_:
                n.pop()
                p.append(ap)
            else:
                p.pop()
                n.append(-an)
            ans = 1
            for a in n:
                ans *= a
                ans %= mod
            for a in p:
                ans *= a
                ans %= mod
    elif len(p)>0:
        ans = 1
        for a in p:
            ans *= a
            ans %= mod
    elif len(n)>0:
        ans = 1
        for a in n:
            ans *= a
            ans %= mod
if len(p)+len(n)<K:
    ans = 0
if len(p)==0 and len(n)==K and K%2==1:
    An = [A[i] for i in range(N) if A[i]<0]
    An.sort()
    An = An[::-1]
    ans = 1
    for i in range(K):
        ans *= An[i]
        ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
def maxProductSubarrayOfSizeK(A, n, k): 
  
    # sorting given input array 
    A.sort() 
  
    # variable to store final product of  
    # all element of sub-sequence of size k 
    product = 1
  
    # CASE I 
    # If max element is 0 and 
    # k is odd then max product will be 0 
    if (A[n - 1] == 0 and (k & 1)): 
        return 0
  
    # CASE II 
    # If all elements are negative and 
    # k is odd then max product will be 
    # product of rightmost-subarray of size k 
    if (A[n - 1] <= 0 and (k & 1)) : 
        for i in range(n - 1, n - k + 1, -1): 
            product *= A[i] %MOD
        return product %MOD
  
    # else 
    # i is current left pointer index 
    i = 0
  
    # j is current right pointer index 
    j = n - 1
  
    # CASE III 
    # if k is odd and rightmost element in 
    # sorted array is positive then it 
    # must come in subsequence 
    # Multiplying A[j] with product and 
    # correspondingly changing j 
    if (k & 1): 
        product *= A[j] %MOD
        j-= 1
        k-=1
  
    # CASE IV 
    # Now k is even. So, Now we deal with pairs 
    # Each time a pair is multiplied to product 
    # ie.. two elements are added to subsequence  
    # each time. Effectively k becomes half 
    # Hence, k >>= 1 means k /= 2 
    k >>= 1
  
    # Now finding k corresponding pairs to get 
    # maximum possible value of product 
    for itr in range( k) : 
  
        # product from left pointers 
        left_product = A[i] * A[i + 1]%MOD 
  
        # product from right pointers 
        right_product = A[j] * A[j - 1] %MOD
  
        # Taking the max product from two  
        # choices. Correspondingly changing 
        # the pointer's position 
        if (left_product > right_product) : 
            product *= left_product %MOD
            i += 2
          
        else : 
            product *= right_product %MOD
            j -= 2
  
    # Finally return product 
    return product %MOD
n,k = map(int,input().split())
A = list(map(int,input().split()))

print(maxProductSubarrayOfSizeK(A, n, k))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
mod = 10**9+7

n, k = map(int, input().split())
A = list(map(int, input().split()))
B = []
C = []
s = 0
t = 0
for a in A:
  if a < 0:
    B.append(-a)
    s += 1
  elif a > 0:
    C.append(a)
    t += 1
if s + t < k:
  print(0)
  exit()
if s + t == k:
  if k == n:
    ans = 1
    for a in A:
      ans *= a
      ans %= mod
    print(ans)
  else:
    if s%2:
      print(0)
    else:
      ans = 1
      for b in B:
        ans *= b
        ans %= mod
      for c in C:
        ans *= c
        ans %= mod
      print(ans)
  exit()
B.sort(reverse=True)
C.sort(reverse=True)
ans = 1
nb = 0
nc = 0
if t == 0:
  if k%2:
    for b in B[-k:]:
      ans *= b
      ans %= mod
    ans *= -1
    ans %= mod
    print(ans)
  else:
    for b in B[:k]:
      ans *= b
      ans %= mod
    ans %= mod
    print(ans)
  exit()
for _ in range(k):
  if nb >= s:
    ans *= C[nc]
    ans %= mod
    nc += 1
  elif nc >= t:
    ans *= B[nb]
    ans %= mod
    nb += 1
  else:
    if B[nb] > C[nc]:
      ans *= B[nb]
      ans %= mod
      nb += 1
    else:
      ans *= C[nc]
      ans %= mod
      nc += 1
if nb%2:
  if nb == s:
    ans *= pow(B[-1], mod-2, mod)
    ans %= mod
    ans *= C[nc]
    ans %= mod
    print(ans)
  elif nc == t:
    ans *= B[nb]
    ans %= mod
    ans *= pow(C[-1], mod-2, mod)
    ans %= mod
    print(ans)
  else:
    if nc == 0:
      ans *= pow(B[nb-1], mod-2, mod)
      ans %= mod
      ans *= C[0]
      ans %= mod
      print(ans)
    else:
      if C[nc-1]*C[nc] >= B[nb-1]*B[nb]:
        ans *= pow(B[nb-1], mod-2, mod)
        ans %= mod
        ans *= C[nc]
        ans %= mod
        print(ans)
      else:
        ans *= pow(C[nc-1], mod-2, mod)
        ans %= mod
        ans *= B[nb]
        ans %= mod
        print(ans)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a=input()
al=[int(i) for i in a.split()]
al.sort()
a=1
b=1
for i in range(k):
    a*=al[i]
    b*=al[-(i+1)]
a=max(a,b)
print(a%(10**9+7))

Submission status: Wrong Answer

Solution code:
def maxProductSubarrayOfSizeK(A, n, k):
    A.sort()
    product = 1
    if (A[n - 1] == 0 and (k & 1)):
        return 0
    if (A[n - 1] <= 0 and (k & 1)):
        for i in range(n - 1, n - k + 1, -1):
            product *= A[i]
        return product
    i = 0
    j = n - 1
    if (k & 1):
        product *= A[j]
        j -= 1
        k -= 1
    k >>= 1
    for itr in range(k):
        left_product = A[i] * A[i + 1]
        right_product = A[j] * A[j - 1]
        if (left_product > right_product):
            product *= left_product
            i += 2

        else:
            product *= right_product
            j -= 2
    return product
n,k = map(int,input().split())
a = list(map(int,input().split()))
flag = True
for i in a:
    if i>0:
        flag = False
        break
if flag:
    a = sorted(a,reverse=True)
    prod = 1
    for i in range(k):
        prod*=a[i]
    print(prod%(10**9+7))
    exit(0)
prod = maxProductSubarrayOfSizeK(a,n,k)
print(prod%(10**9+7))

Submission status: Wrong Answer

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

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

B=[]
C=[]
Z=[]

for a in A:
    if a>0:
        B.append(a)
    elif a<0:
        C.append(-a)
    else:
        Z.append(0)

if K>=len(B)+len(C):
    ANS=1
    for b in B:
        ANS=ANS*b%mod
    for c in C:
        ANS=ANS*c%mod

    if ANS<0 and Z!=[]:
        print(0)
    else:
        print(0)
    sys.exit()

if B==[]:
    ANS=1
    for i in range(K):
        ANS=ANS*(-C[i])%mod

    if Z==[]:
        print(ANS)
    elif ANS<0:
        print(0)
    else:
        print(ANS)

    sys.exit()

    
B.sort(reverse=True)
C.sort(reverse=True)

if K<=len(B):
    S=1
    for i in range(K):
        S=S*B[i]%mod

    ind=0
    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

else:
    if (K-len(B))%2==0:
        S=1
        for i in range(len(B)):
            S=S*B[i]%mod

        for j in range(K-len(B)):
            S=S*C[j]%mod

        ind=K-len(B)

    else:
        S=1
        for i in range(len(B)-1):
            S=S*B[i]%mod

        for j in range(K-len(B)+1):
            S=S*C[j]%mod

        ind=K-len(B)+1
        

    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

Submission status: Wrong Answer

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

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

tmp = 1
cnt = 0

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

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

ans = 0

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

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

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

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

for p in range(0, k+1, 2):
    if len(mn) < p:
        break
    if len(pl) >= k-p:
        ans = max(pl_cum[k-p]*mn_cum[p] % mod, ans)

print(ans % mod)

Submission status: Wrong Answer

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

aans = 1
bans = 1

for i in range(k):
    aans *= a[i]
    bans *= b[i]
#aans = numpy.prod(a[:k])
#bans = numpy.prod(b[:k])

if aans >= bans:
    print(aans % 1000000007)
else:
    print(bans % 1000000007)

Submission status: Wrong Answer

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

positives = [a for a in A if a > 0]
negatives = [a for a in A if a < 0]
positive_cnt = len(positives)
negative_cnt = len(negatives)
zero_cnt = A.count(0)


if min(2 * (negative_cnt // 2), 2 * (K // 2)) + positive_cnt >= K:
    # 答えが正になる場合
    positives = sorted(positives, reverse=True)
    negatives = sorted(negatives)

    positives_twin = [positives[2 * i] * positives[2 * i + 1] for i in range(positive_cnt // 2)] + [0]
    negatives_twin = [negatives[2 * i] * negatives[2 * i + 1] for i in range(negative_cnt // 2)] + [0]
    positives_twin.sort()
    negatives_twin.sort()

    ans = 1
    positive_select = 0
    for i in range(K // 2):
        if positives_twin[-1] <= negatives_twin[-1]:
            ans *= negatives_twin[-1]
            ans %= MOD
            negatives_twin.pop()
        else:
            ans *= positives_twin[-1]
            ans %= MOD
            positives_twin.pop()
            positive_select += 1

    if K == 1:
        ans = 0
    if K % 2 == 1:
        ans += positives[2 * positive_select]
    print(ans % MOD)

elif zero_cnt > 0:
    # 答えが０になる場合
    print(0)
else:
    # 答えが負になる場合
    ans = 1
    A_abs = sorted([abs(a) for a in A])
    for a in A_abs[:K]:
        ans *= a
        ans %= MOD
    ans = -ans % MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    from bisect import bisect_left, bisect_right
    N, K = MAP()
    A = LIST()
    A.sort()
    neg = bisect_left(A, 0)
    pos = bisect_right(A, 0)
    negative = A[:neg]
    zeros = A[neg:pos]
    positive = list(reversed(A[pos:]))
    if len(negative) + len(positive) < K:
        # 必ず0を選ぶ必要がある
        print(0)
        return
    if len(positive) == 0:
        if K % 2 == 1:
            if len(zeros) > 0:
                # 0を選びさえすれば良い
                print(0)
                return
            else:
                # 負の数から、0に近い数を選ぶ
                ans = 1
                for n in negative[-K:]:
                    ans *= (-n)
                    ans %= MOD
                ans *= -1
                print(ans % MOD)
                return
        else:
            # 答えは正となる。絶対値が大きい数を選ぶ
            ans = 1
            for n in negative[:K]:
                ans *= (-n)
                ans %= MOD
            print(ans % MOD)
            return

    if len(negative) + len(positive) == K:
        if len(negative) % 2 == 1:
            if len(zeros) > 0:
                print(0)
                return
            else:
                ans = 1
                for a in A:
                    ans *= a
                    ans %= MOD
                print(ans % MOD)
                return

    # 負の数は二個一で採用する
    phead = 0
    nhead = 0
    k = K
    ans = 1
    while k > 1 and phead+1 < len(positive) and nhead+1 < len(negative):
        # 負上から二個
        ncand = 0
        if nhead + 1 < len(negative):
            ncand = negative[nhead]*negative[nhead+1]
        pcand = 0
        if phead + 1 < len(positive):
            pcand = positive[phead]*positive[phead+1]
        if ncand == pcand == 0:
            break
        if ncand < pcand:
            k -= 2
            ans *= pcand
            ans %= MOD
            phead += 2
        else:
            k -= 2
            ans *= ncand
            ans %= MOD
            nhead += 2
    if nhead + 1 >= len(negative):
        # 残りは正から採用する
        # ここではpositiveは尽きない
        while k > 0:
            ans *= positive[phead]
            ans %= MOD
            phead += 1
            k -= 1
        print(ans)
        return
    if phead + 1 >= len(positive):
        # 残りは負から採用する。最後、調整が必要ならpositiveひとつ放出する
        while k > 1:
            ans *= negative[nhead]*negative[nhead+1]
            ans %= MOD
            nhead += 2
            k -= 2
        if k == 1:
            ans *= positive[phead]
            ans %= MOD
        print(ans)
        return
    if k == 1:
        ans *= positive[phead]
        ans %= MOD
        print(ans)
        return
    #
    # 負の個数、0の個数,正の個数
    # 負の個数+正の個数 < Kの場合、0
    # 正の個数 == 0の場合、
    #   Kが奇数なら、0か0に近いものをK個
    #   Kが偶数なら、大きい物をK個
    # 0 < 正の個数 <= K の場合、
    #   いくつ負を選ぶかという話 二個一で貪欲 最後は最大の正
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
plus = []
minus  = []
ans = 1
for i in range (n):
    if A[i] >= 0:
        plus.append(A[i])
    else:
        minus.append(A[i])
plus = sorted(plus,reverse = True)
minus = sorted(minus)
while True:
    if k >= 2:
        if len(plus)>1 and len(minus)>1:
            if plus[0]*plus[1]  >= minus[0]*minus[1]:
                ans *= plus[0]*plus[1]
                plus.pop(0)
                plus.pop(0)
            else:
                ans *= minus[0]*minus[1]
                minus.pop(0)
                minus.pop(0)
            k -= 2
        elif len(plus)>1:
            ans *= plus[0]*plus[1]
            plus.pop(0)
            plus.pop(0)
            k -=2
        elif len(minus)>1:
            ans *= minus[0]*minus[1]
            minus.pop(0)
            minus.pop(0)
            k -=2
        else:
            ans *= plus[0] * minus[0]
            k -=2
    elif k == 1:
        if plus != []:
            ans *= plus[0]
        else:
            ans *= minus[0]
        break
    else:
        break
Ans = int(ans)%(10**9+7)
print(Ans)