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:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    M.sort(reverse=True)
    for i in range(K):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K-1:
        if(len(P)>=2 and len(M)>=2):
            if(P[0]*P[1]<M[0]*M[1]):
                i +=2
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                i +=1
                ans2 = -ans2*heapq.heappop(P)%mod
        elif len(P)==1:
            if len(M)>=2 and -P[0] < M[0]*M[1]:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
            else:
                ans2 = -ans2*heapq.heappop(P)%mod
                i += 1
        elif len(P)==0:
            if len(M)>=2:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
        elif len(M)<=1:
            ans2 = -ans2*heapq.heappop(P)%mod
            i += 1
    while i < K:
        i += 1
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            ans2 = ans2*heapq.heappop(M)%mod

print(ans2)

Submission status: Wrong Answer

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K-1:
        if(len(P)>=2 and len(M)>=2):
            if(P[0]*P[1]<M[0]*M[1]):
                i +=2
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                i +=1
                ans2 = -ans2*heapq.heappop(P)%mod
        elif len(P)==1:
            if len(M)>=2 and -P[0] < M[0]*M[1]:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
            else:
                ans2 = -ans2*heapq.heappop(P)%mod
                i += 1
        elif len(P)==0:
            if len(M)>=2:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
        elif len(M)<=1:
            ans2 = -ans2*heapq.heappop(P)%mod
            i += 1
    while i < K:
        i += 1
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            ans2 = ans2*heapq.heappop(M)%mod

print(ans2)

Submission status: Wrong Answer

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K-1:
        if(len(P)>=2 and len(M)>=2):
            if(P[0]*P[1]<=M[0]*M[1]):
                i +=2
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                i +=1
                ans2 = -ans2*heapq.heappop(P)%mod
        elif len(P)==1:
            if len(M)>=2 and -P[0] <= M[0]*M[1]:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
            else:
                ans2 = -ans2*heapq.heappop(P)%mod
                i += 1
        elif len(P)==0:
            if len(M)>=2:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
        elif len(M)<=1:
            ans2 = -ans2*heapq.heappop(P)%mod
            i += 1
    while i < K:
        i += 1
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            ans2 = ans2*heapq.heappop(M)%mod

print(ans2)

Submission status: Wrong Answer

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

A.sort()
ans = 1
if k == n:
  for a in A:
    ans = a * ans % mod
  exit(print(ans))

if A[-1] <= 0:
  if k%2 == 0:
    for a in A[:k]:
      ans = ans * a % mod
  else:
    for a in A[-k:]:
      ans = ans * a % mod 
  exit(print(ans))
elif A[0] >= 0:
  for a in A[-k:]:
    ans = ans * a % mod 
  exit(print(ans))
else:
  i = 1
  while (A[i] < 0) & (k >= 2):
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]*A[-k]:
      ans = ans * x*y % mod
      k -= 2
    else:break
    i += 2
    if i > n:break
  if k == 0: exit(print(ans))
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))

Submission status: Wrong Answer

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

A.sort()
ans = 1
if k == n:
  for a in A:
    ans = a * ans % mod * 0
  exit(print(ans))

if A[-1] <= 0:
  if k%2 == 0:
    for a in A[:k]:
      ans = ans * a % mod
  else:
    for a in A[-k:]:
      ans = ans * a % mod 
  exit(print(ans))
elif A[0] > 0:
  for a in A[-k:]:
    ans = ans * a % mod 
  exit(print(ans))
else:
  i = 1
  while (A[i] < 0) & (k >= 2):
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]*A[-k]:
      ans = ans * x*y % mod
      k -= 2
    else:break
    i += 2
    if i > n:break
  if k == 0: exit(print(ans))
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))

Submission status: Wrong Answer

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

A.sort()
ans = 1
if k == n:
  for a in A:
    ans = a * ans % mod
  exit(print(ans))

if A[-1] <= 0:
  if k%2 == 0:
    for a in A[:k]:
      ans = ans * a % mod
  else:
    for a in A[-k:]:
      ans = ans * a % mod 
  exit(print(ans))
elif A[0] > 0:
  for a in A[-k:]:
    ans = ans * a % mod 
  exit(print(ans))
else:
  i = 1
  while (A[i] < 0) & (k >= 2):
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]*A[-k]:
      ans = ans * x*y % mod
      k -= 2
    else:break
    i += 2
    if i > n:break
  if k == 0: exit(print(ans))
  for a in A[-k:]:
    ans = ans * a % mod * 0
  exit(print(ans))

Submission status: Wrong Answer

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

A.sort()
ans = 1
if k == n:
  for a in A:
    ans = a * ans % mod
  exit(print(ans))

if A[-1] <= 0:
  if k%2 == 0:
    for a in A[:k]:
      ans = ans * a % mod
  else:
    for a in A[-k:]:
      ans = ans * a % mod 
  exit(print(ans))
elif A[0] > 0:
  for a in A[-k:]:
    ans = ans * a % mod 
  exit(print(ans))
else:
  i = 1
  while (A[i] < 0) & (k >= 2):
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]*A[-k]:
      ans = ans * x*y % mod * 0
      k -= 2
    else:break
    i += 2
    if i > n:break
  if k == 0: exit(print(ans))
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))

Submission status: Wrong Answer

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

A.sort()
ans = 1
if k == n:
  for a in A:
    ans = a * ans % mod
  exit(print(ans))

if A[-1] <= 0:
  if k%2 == 0:
    for a in A[:k]:
      ans = ans * a % mod
  else:
    for a in A[-k:]:
      ans = ans * a % mod 
  exit(print(ans))
elif A[0] > 0:
  for a in A[-k:]:
    ans = ans * a % mod * 0
  exit(print(ans))
else:
  i = 1
  while (A[i] < 0) & (k >= 2):
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]*A[-k]:
      ans = ans * x*y % mod
      k -= 2
    else:break
    i += 2
    if i > n:break
  if k == 0: exit(print(ans))
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))

Submission status: Wrong Answer

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

A.sort()
ans = 1
if k == n:
  for a in A:
    ans = a * ans % mod
  exit(print(ans))

if A[-1] <= 0:
  if k%2 == 0:
    for a in A[:k]:
      ans = ans * a % mod
  else:
    for a in A[-k:]:
      ans = ans * a % mod * 0
  exit(print(ans))
elif A[0] > 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
else:
  i = 1
  while (A[i] < 0) & (k >= 2):
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]*A[-k]:
      ans = ans * x*y % mod
      k -= 2
    else:break
    i += 2
    if i > n:break
  if k == 0: exit(print(ans))
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))

Submission status: Wrong Answer

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

A.sort()
ans = 1
if k == n:
  for a in A:
    ans = a * ans % mod
  exit(print(ans))

if A[-1] <= 0:
  if k%2 == 0:
    for a in A[:k]:
      ans = ans * a % mod *0
  else:
    for a in A[-k:]:
      ans = ans * a % mod
  exit(print(ans))
elif A[0] > 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
else:
  i = 1
  while (A[i] < 0) & (k >= 2):
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]*A[-k]:
      ans = ans * x*y % mod
      k -= 2
    else:break
    i += 2
    if i > n:break
  if k == 0: exit(print(ans))
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))

Submission status: Wrong Answer

Solution code:
import itertools
import heapq
import sys
import functools
import operator
import numpy as np
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
a_high = sorted(a , reverse=True)
a_high_k = a_high[:k]
a_low = sorted(a)
a_low_k = a_low[:k]
a_new = a_high_k + a_low_k
a_new.sort()
D = [[a_new[i+j-k+1] for j in range(k)] for i in range(2*k)]
A = (functools.reduce(operator.mul,D[_]) for _ in range(2*k))
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

Submission status: Wrong Answer

Solution code:
def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    A.sort()
    if K == 1:
        print(A[N - 1])
        return
    # マイナスが0 or 1個の時はtop Kの積
    if A[0] >= 0:
        ans = 1
        for k in range(1, K + 1):
            ans *= A[-k]
            ans %= MOD
        print(ans)
        return
    # 非負が0個の場合
    # K:even -> tail Kの積
    # K:odd -> top Kの積
    if A[N - 1] < 0:
        ans = 1
        if K % 2 == 0:
            for k in range(K):
                ans *= A[k]
                ans %= MOD
        else:
            for k in range(1, K + 1):
                ans *= A[-k]
                ans %= MOD
        print(ans)
        return
    # 非負が1個の場合
    # K:even -> tail Kの積
    # K:odd -> tail (K - 1), top 1の積
    if A[N - 2] < 0 and A[N - 1] >= 0:
        ans = 1
        if K % 2 == 0:
            for k in range(K):
                ans *= A[k]
                ans %= MOD
        else:
            for k in range(1, K):
                ans *= A[-k]
                ans %= MOD
            ans *= A[N - 1]
            ans %= MOD
        print(ans)
        return
    # マイナスも非負も2つ以上ある場合
    # 両端から2要素ずつ走査していく
    left, right = 0, N - 1
    ans = 1
    while K >= 2:
        left_prod = A[left] * A[left + 1]
        right_prod = A[right - 1] * A[right]
        if left_prod < right_prod:
            ans *= right_prod
            right -= 2
        else:
            ans *= left_prod
            left += 2
        ans %= MOD
        K -= 2
    if K == 1:
        ans *= A[right]
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
import heapq
import sys
import functools
import operator
import numpy as np
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
a_high = sorted(a , reverse=True)
a_high_k = a_high[:k]
a_low = sorted(a)
a_low_k = a_low[:k]
a_new = a_high_k + a_low_k
comb = itertools.combinations(a_new,k)
l = [list(_) for _ in comb]
#D = [[a_new[i+j-k] for j in range(k)] for i in range(2*k)]
A = (functools.reduce(operator.mul,l[_]) for _ in range(len(l)))
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

Submission status: Wrong Answer

Solution code:
def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    A.sort()
    if K == 1:
        print(A[N - 1])
        return
    # マイナスが0 or 1個の時はtop Kの積
    if A[1] >= 0:
        ans = 1
        for k in range(1, K + 1):
            ans *= A[-k]
            ans %= MOD
        print(ans)
        return
    # 非負が0個の場合
    # K:even -> tail Kの積
    # K:odd -> top Kの積
    if A[N - 1] < 0:
        ans = 1
        if K % 2 == 0:
            for k in range(K):
                ans *= A[k]
                ans %= MOD
        else:
            for k in range(1, K + 1):
                ans *= A[-k]
                ans %= MOD
        print(ans)
        return
    # 非負が1個の場合
    # K:even -> tail Kの積
    # K:odd -> tail (K - 1), top 1の積
    #if A[N - 2] < 0 and A[N - 1] >= 0:
    #    ans = 1
    #    if K % 2 == 0:
    #        for k in range(K):
    #            ans *= A[k]
    #            ans %= MOD
    #    else:
    #        for k in range(1, K):
    #            ans *= A[-k]
    #            ans %= MOD
    #        ans *= A[N - 1]
    #        ans %= MOD
    #    print(ans)
    #    return
    # マイナスも非負も2つ以上ある場合
    # 両端から2要素ずつ走査していく
    left, right = 0, N - 1
    ans = 1
    while K >= 2:
        left_prod = A[left] * A[left + 1]
        right_prod = A[right - 1] * A[right]
        if left_prod < right_prod:
            ans *= right_prod
            right -= 2
        else:
            ans *= left_prod
            left += 2
        ans %= MOD
        K -= 2
    if K == 1:
        ans *= A[right]
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

A.sort()
ans = 1
if k == n:
  for a in A:
    ans = a * ans % mod
  exit(print(ans))

if A[-1] <= 0:
  if k%2 == 0:
    for a in A[:k]:
      ans = ans * a % mod
  else:
    for a in A[-k:]:
      ans = ans * a % mod
  exit(print(ans))
elif A[0] > 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
else:
  i = 1
  while (A[i] < 0) & (k >= 2):
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]*A[-k]:
      ans = ans * x*y % mod
      k -= 2
    else:break
    i += 2
    if i > n:break
  if k == 0: exit(print(ans))
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))

Submission status: Wrong Answer

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

A.sort()
if k == 1:exit(print(A[-1]%mod))

ans = 1
if k == n:
  for a in A:
    ans = a * ans % mod
  exit(print(ans))

if A[-1] <= 0:
  if k%2 == 0:
    for a in A[:k]:
      ans = ans * a % mod
  else:
    for a in A[-k:]:
      ans = ans * a % mod
  exit(print(ans))
elif A[1] >= 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
else:
  i = 1
  while (k >= 2):
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]*A[-k]:
      ans = ans * x*y % mod
    else:
      ans = ans * A[-i] * A[-i-1] % mod
    k -= 2
    i += 2
    if i > n:break
  if k == 1:
    ans = ans * A[-1] % mod
  exit(print(ans))

Submission status: Wrong Answer

Solution code:
import itertools
import heapq
import sys
import functools
import operator
import numpy as np
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
a_high = sorted(a , reverse=True)
a_high_k = a_high[:k]
a_low = sorted(a)
a_low_k = a_low[:k]
a_new = a_high_k + a_low_k
D = [[a_new[i+j-k] for j in range(k)] for i in range(2*k)]
A = (functools.reduce(operator.mul,D[_]) for _ in range(len(D)))
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

Submission status: Wrong Answer

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

A.sort()
if k == 1:exit(print(A[-1]%mod))

ans = 1
if k == n:
  for a in A:
    ans = a * ans % mod
  exit(print(ans))

if A[-1] <= 0:
  if k%2 == 0:
    for a in A[:k]:
      ans = ans * a % mod
  else:
    for a in A[-k:]:
      ans = ans * a % mod
  exit(print(ans))
elif A[1] >= 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
else:
  i = 1
  while (A[i] < 0) & (k >= 2):
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]*A[-k]:
      ans = ans * x*y % mod
      k -= 2
    else:break
    i += 2
    if i > n:break
  if k == 0: exit(print(ans))
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))

Submission status: Wrong Answer

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

A.sort()
if k == 1:exit(print(A[-1]%mod))
ans = 1

if A[-1] <= 0:
  if k%2 == 0:
    for a in A[:k]:
      ans = ans * a % mod
  else:
    for a in A[-k:]:
      ans = ans * a % mod
  exit(print(ans))
elif A[1] >= 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
else:
  i = 1
  while (A[i] < 0) & (k >= 2):
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]*A[-k]:
      ans = ans * x*y % mod
      k -= 2
    else:break
    i += 2
    if i > n:break
  if k == 0: exit(print(ans))
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))

Submission status: Wrong Answer

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

A.sort()
if k == 1:exit(print(A[-1]%mod))
ans = 1

if A[-1] <= 0:
  if k%2 == 0:
    for a in A[:k]:
      ans = ans * a % mod
  else:
    for a in A[-k:]:
      ans = ans * a % mod
  exit(print(ans))
elif A[0] > 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
else:
  i = 1
  while k >= 2:
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]*A[-k]:
      ans = ans * x*y % mod
    else:
      ans = ans * A[-k+1] * A[-k] % mod
    k -= 2
  if k == 1:
    ans = ans * A[-1] % mod
  print(ans)

Submission status: Wrong Answer

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

A.sort()
if k == 1:exit(print(A[-1]%mod))
ans = 1

if A[-1] <= 0:
  if k%2 == 0:
    for a in A[:k]:
      ans = ans * a % mod
  else:
    for a in A[-k:]:
      ans = ans * a % mod
  exit(print(ans))
elif A[0] > 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
else:
  i = 1
  while (A[i] < 0) & (k >= 2):
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]*A[-k]:
      ans = ans * x*y % mod
      k -= 2
    else:break
    i += 2
    if i > n:break
  if k == 0: exit(print(ans))
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))

Submission status: Wrong Answer

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

if n == 1:exit(print(A[0]%mod))
A.sort()
if k == 1:exit(print(A[-1]%mod))
ans = 1

if A[-1] <= 0:
  if k%2 == 0:
    for a in A[:k]:
      ans = a * ans % mod
  else:
    for a in A[-k:]:
      ans = ans * a % mod
  exit(print(ans))
elif A[0] > 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
else:
  i = 1
  while (A[i] < 0) & (k >= 2):
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]*A[-k]:
      ans = ans * x*y % mod
      k -= 2
    else:break
    i += 2
    if i > n:break
  if k == 0: exit(print(ans))
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))

Submission status: Wrong Answer

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

if n == 1:exit(print(A[0]%mod))
A.sort()
if k == 1:exit(print(A[-1]%mod))
ans = 1

if A[-1] <= 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
elif A[0] > 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
else:
  i = 1
  while A[i] < 0:
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]*A[-k]:
      ans = ans * x*y % mod
      k -= 2
      if k < 2:break
    else:break
    i += 2
    if i > n:break
  if k == 0: exit(print(ans))
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
data = list(map(int, input().split()))
data.sort(reverse=True, key=abs)
mod = 10**9 + 7
ans = 1
for i in range(k):
    ans *= data[i]
if ans < 0:
    nex_p = None
    nex_n = None
    for i in range(k, n):
        if nex_p is not None and nex_n is not None:
            break
        if data[i] >= 0:
            nex_p = data[i]
        else:
            nex_n = data[i]
    min_n = None
    min_p = None
    for i in range(k-1, -1, -1):
        if min_n is not None and min_p is not None:
            break
        if data[i] < 0:
            min_n = data[i]
        else:
            min_p = data[i]
    ans1 = ans2 = -float('inf')
    if min_p is not None and nex_n is not None:
        ans1 = (ans//min_p)*nex_n
    if nex_p is not None:
        ans2 = (ans//min_n)*nex_p
    if ans1 == -float('inf') and ans2 == -float('inf'):
        ans = 1
        for a in data[-k:]:
            ans *= a
    else:
        ans = max(ans, ans1, ans2)

print(ans%mod)

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7

n, k = map(int, input().split())
a = list(map(int, input().split()))
p, q = [], []
for x in a:
    if x >= 0: p.append(x)
    else: q.append(x)
lp, lq = len(p), len(q)

def sp():
    p.sort(reverse=True)
    q.sort()
    ans = p[0] if k % 2 else 1
    s = []
    for i in range(0, lq-1, 2):
        s.append(q[i]*q[i+1] % MOD)
    for i in range(k % 2, lp-1, 2):
        s.append(p[i]*p[i+1] % MOD)
    s.sort(reverse=True)
    for i in range(k//2):
        ans *= s[i]
        ans %= MOD
    print(ans)

def sq():
    a.sort(key=lambda x: abs(x))
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= MOD
    print(ans)

if k % 2 and not p: sq()
elif n == k and lq % 2: sq()
else: sp()

Submission status: Wrong Answer

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

if n == 1:exit(print(A[0]%mod))
A.sort()
if k == 1:exit(print(A[-1]%mod))
ans = 1

if A[-1] <= 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
elif A[0] > 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
else:
  i = 1
  while A[i] < 0:
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]*A[-k]:
      ans = ans * x*y % mod
      k -= 2
      if k < 2:break
    i += 2
    if i > n:break
    else:
      break
  if k == 0: exit(print(ans))
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))

Submission status: Wrong Answer

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

if n == 1:exit(print(a[0]%mod))
A.sort()
if k == 1:exit(print(A[-1]%mod))
ans = 1

if A[-1] <= 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
elif A[0] > 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
else:
  t = []
  i = 1
  while A[i] < 0:
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]:
      ans = ans * x*y % mod
      k -= 2
      if k <= 0:break
    i += 2
    if i > k:break
    else:
      break
  if k == 0: exit(print(ans))
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))

Submission status: Wrong Answer

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

if n == 1:exit(print(a[0]%mod))
A.sort()
ans = 1

if A[-1] <= 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
elif A[0] > 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
else:
  i = 1
  while A[i] < 0:
    x, y = A[i-1], A[i]
    if x*y > A[-k+1]:
      ans = ans * x*y % mod
      k -= 2
      if k <= 0:break
      i += 2
      if i > k:break
    else:
      break
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))

Submission status: Wrong Answer

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

if n == 1:exit(print(a[0]%mod))
A.sort()
ans = 1

if A[-1] <= 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
elif A[0] > 0:
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))
else:
  i = 1
  while A[i] < 0:
    x, y = A[i-1], A[i]
    if x*y > A[-k]:
      ans = ans * x*y % mod
    i += 2
    k -= 2
    if i > k:break
    if k <= 0:break
  for a in A[-k:]:
    ans = ans * a % mod
  exit(print(ans))

Submission status: Wrong Answer

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

if n == 1:exit(print(a[0]%mod))
A.sort()
ans = 1

if A[-1] <= 0:
  for a in A[-k:]:
    ans *= a
  exit(print(ans%mod))
elif A[0] > 0:
  for a in A[-k:]:
    ans *= a
  exit(print(ans%mod))
else:
  i = 1
  while A[i] < 0:
    x, y = A[i-1], A[i]
    if x*y > A[-k]:
      ans *= x*y
    i += 2
    k -= 2
    if i > k:break
    if k <= 0:break
  for a in A[-k:]:
    ans *= a
  exit(print(ans%mod))

Submission status: Wrong Answer

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

if n == 1:exit(print(a[0]%mod))
A.sort()
ans = 1

if A[-1] < 0:
  for a in A[-k:]:
    ans *= a
  exit(print(ans%mod))
elif A[0] >= 0:
  for a in A[-k:]:
    ans *= a
  exit(print(ans%mod))
else:
  i = 1
  while A[i] < 0:
    x, y = A[i-1], A[i]
    if x*y > A[-k]:
      ans *= x*y
    i += 2
    k -= 2
    if k <= 0:break
  for a in A[-k:]:
    ans *= a
  exit(print(ans%mod))

Submission status: Wrong Answer

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

if n == 1:exit(print(a[0]%mod))
A.sort()
ans = 1

if A[-1] < 0:
  for a in A[-k:]:
    ans *= a
  exit(print(ans%mod))
elif A[0] >= 0:
  for a in A[-k:]:
    ans *= a
  exit(print(ans%mod))
else:
  i = 1
  while A[i] < 0:
    x, y = A[i-1], A[i]
    if x*y > A[-k]:
      ans *= x*y
    i += 2
    k -= 2
  for a in A[-k:]:
    ans *= a
  exit(print(ans%mod))

Submission status: Wrong Answer

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

if n == 1:exit(print(a[0]%mod))
A.sort()
ans = 1

if A[-1] < 0:
  for a in A[-k:]:
    ans *= a
  exit(print(ans%mod))
elif A[0] >= 0:
  for a in A[-k:]:
    ans *= a
  exit(print(ans%mod))
else:
  B = A[-k:]
  i = 1
  while A[i] < 0:
    x, y = A[i-1], A[i]
    if x*y > A[-k]:
      B = B[-k+1:] + [x*y]
    i += 2
  for b in B:
    ans *= b
  exit(print(ans%mod))

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7

def solve(n, k, a):
    a = sorted(a, key=lambda _:-abs(_))
    num_odd = len(list(filter(lambda _:_<0, a[:k])))
    if num_odd % 2 == 0:
        res = 1
        for i in range(k):
            res = (res * a[i]) % MOD
        return res
    else:
        max_odd_i = -1
        max_even_i = -1
        for i in range(k):
            if a[i] < 0:
                max_odd_i = i
            else:
                max_even_i = i
        min_odd_j = -1
        min_even_j = -1
        for j in range(k, n):
            if a[j] < 0:
                min_odd_j = min(j, min_odd_j)
            else:
                min_even_j = min(j, min_even_j)
        p = -1
        q = -1
        if (max_odd_i > -1) and (min_even_j > -1):
            p = a[min_even_j]
            for i in range(k):
                if i != max_odd_i:
                    p = (p * a[i]) % MOD
        if (max_even_i > -1) and (min_odd_j > -1):
            q = a[min_odd_j]
            for i in range(k):
                if i != max_even_i:
                    q = (q * a[i]) % MOD
        return max(p, q)

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

Submission status: Wrong Answer

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

mod = 10 ** 9 + 7
plus = []
lz = 0
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(A[k])
  else:
    lz += 1
plus.sort(reverse = True)
minus.sort()
lp = len(plus)
lm = len(minus)

def main(mp, mm, plus, minus):
  mod = 10 ** 9 + 7
  ans = 1
  for k in range(mp):
    ans = ans * plus[k] % mod
  for k in range(mm):
    ans = ans * minus[k] % mod
  print(ans)
  exit()

if lz + K > N:
  print(0)
  exit()
elif lp == 0: 
  if K % 2 == 1:
    if lz > 0:
      print(0)
      exit()
    else:
      for k in range(K):
        ans = ans * minus[- k - 1] % mod
      print(ans)
      exit()
  else:
    main(0, K, plus, minus)
elif lm == 0:
  main(K, 0, plus, minus)

p = 0
m = 0
for _ in range(K):
  if plus[p] >= minus[m]:
    p += 1
    if p == lp:
      m = K - p
      break
  else:
    m += 1
    if m == lm:
      p = K - m
      break

if m % 2 == 0:
  main(p, m, plus, minus)
else:
  if p == lp:
    if m != lm:
      main(p - 1, m + 1, plus, minus)
    else:
      if lz > 0:
        print(0)
        exit()
      else:
        main(p, m, plus, minus)
  elif m == lm:
    main(p + 1, m - 1, plus, minus)
  elif p == 0:
    main(p + 1, m - 1, plus, minus)
  else:
    if plus[p] * plus[p - 1] > minus[m - 1] * minus[m]:
      main(p + 1, m - 1, plus, minus)
    else:
      main(p - 1, m + 1, plus, minus)

Submission status: Wrong Answer

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K-1:
        if(len(P)>=2 and len(M)>=2):
            i +=2
            if(P[0]*P[1]<=M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                ans2 = ans2*(heapq.heappop(P)*heapq.heappop(P))%mod
        elif len(P)==1:
            if len(M)>=2 and -P[0] <= M[0]*M[1]:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
            else:
                ans2 = -ans2*heapq.heappop(P)%mod
                i += 1
        elif len(P)==0:
            if len(M)>=2:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
        elif len(M)<=1:
            ans2 = -ans2*heapq.heappop(P)%mod
            i += 1
    while i < K:
        i += 1
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            ans2 = ans2*heapq.heappop(M)%mod

print(ans2)