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:
#!/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
    # print(negative)
    # print(zeros)
    # print(positive)
    # 負の数は二個一で採用する
    phead = 0
    nhead = 0
    k = K
    ans = 1
    while k > 1 and phead+2 < len(positive) and nhead+1 < len(negative):
        # 負上から二個
        ncand = 0
        if nhead + 1 < len(negative):
            ncand = negative[nhead]*negative[nhead+1]
        pcand = 0
        if k > 2:
            if phead + 2 < len(positive):
                pcand = positive[phead+1]*positive[phead+2]
        else:
            if phead + 1 < len(positive):
                pcand = positive[phead]*positive[phead+1]
        if ncand == pcand == 0:
            break
        if ncand < pcand:
            pcand = positive[phead]*positive[phead+1]
            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 + 2 >= len(positive):
        if K % 2 == 0:
            # print(k)
            # print(positive[phead:])
            # print(negative[nhead:])
            # 負からとるんだが、残りのpositiveが2つなら、それを一回だけ代わりに使える
            pcand = -INF
            if phead + 1 < len(positive):
                pcand = positive[phead]*positive[phead+1]

            while k > 1 and nhead + 1 < len(negative):
                ncand = negative[nhead]*negative[nhead+1]
                if ncand < pcand:
                    ans *= pcand
                    ans %= MOD
                    pcand = -INF
                    k -= 2
                else:
                    ans *= ncand
                    ans %= MOD
                    nhead += 2
                    k -= 2
            if k != 0:
                ans *= pcand
                ans %= MOD

            print(ans % MOD)
            return
        else:
            ans *= positive[phead]
            ans %= MOD
            while k > 1:
                ncand = negative[nhead]*negative[nhead+1]
                ans *= ncand
                ans %= MOD
                k -= 2
                nhead += 2
            print(ans)
            return
    if k <= 2:
        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:
import bisect
mod = 10**9+7

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

A.sort(reverse=True)

ans = 1
left = 0
right = len(A)-1

if A[0] < 0:
    for i in range(K):
        ans = (ans * A[i]) % mod
elif K % 2 == 0:
    while K > 0:
        r = A[right] * A[right-1]
        l = A[left] * A[left + 1]
        if l > r:
            ans = (ans * l) % mod
            left += 2
        else:
            ans = (ans * r) % mod
            right -= 2
        K -= 2
else:
    p = A.pop(0)
    K -= 1
    right -= 1
    while K > 0:
        r = A[right] * A[right-1]
        l = A[left] * A[left + 1]
        if l > r:
            ans = (ans * l) % mod
            left += 2
        else:
            ans = (ans * r) % mod
            right -= 2
        K -= 2
    ans = (ans * p) % mod
if ans < 0:
    ans = ans + mod

print(ans)

Submission status: Wrong Answer

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

sorted_a = sorted(a, reverse=True)
abs_a = sorted(a, reverse=True, key=lambda x: abs(x))

# print(sorted_a)
# print(abs_a)

neg_cnt = 0
neg_idx = []
pos_idx = []
zero_idx = []
for i in range(n):
    if(abs_a[i] < 0):
        neg_cnt += 1
        neg_idx.append(i)
    elif(abs_a[i] > 0):
        pos_idx.append(i)
    else:
        zero_idx.append(i)

if(n - len(zero_idx) < k):
    print(0)
    exit()
else:
    if(n - len(zero_idx) == k and neg_cnt % 2 == 1):
        print(0)
        exit()

mod = 1000000007

if(neg_cnt == n and k%2 == 1):
    res = 1
    for i in range(1, k+1):
        res *= abs_a[-i]
        res %= mod

    print(res)
    exit()


if(neg_cnt == 0):
    res = 1
    for i in range(k):
        res *= abs_a[i]
        res %= mod

    print(res)


else:
    res = 1
    n_cnt = 0
    last_p = -1
    last_n = -1
    for i in range(k):
        res *= abs_a[i]
        res %= mod

        if(abs_a[i] < 0): 
            n_cnt += 1
            last_n = i
        else:
            last_p = i
    
    if(n_cnt%2 == 0):
        print(res)
    else:
        if(last_p == -1):
            print(res)
        else:
            if(abs_a[k-1] < 0):
                nxt_p = -1
                for i in range(k, n):
                    if(abs_a[i] > 0):
                        nxt_p = i
                        break
                    
                if(nxt_p != -1):
                    res = 1
                    for i in range(k-1):
                        res *= abs_a[i]
                        res %= mod
                    res *= abs_a[nxt_p]
                    res %= mod
                    print(res)
                    exit()
                
                else:
                    res = 1
                    for i in range(k):
                        if(i == last_p): continue
                        res *= abs_a[i]
                        res %= mod
                    res *= abs_a[k]
                    res %= mod

                    print(res)
                    exit()

Submission status: Wrong Answer

Solution code:

MOD = 10**9 + 7
def maxProductSubarrayOfSizeK(A, n, k): 
  
    # sorting given input array 
    A.sort() 
    product = 1
    # print(A)
    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 = (product%MOD * A[i]%MOD)%MOD
        return product
    i = 0
    j = n - 1
  
    if (k & 1): 
        product = (product%MOD * A[j]%MOD)%MOD
        j-= 1
        k-=1
    k >>= 1
    for itr in range( k) :
        left_product = (A[i]%MOD * A[i + 1]%MOD )%MOD
        right_product = (A[j]%MOD * A[j - 1]%MOD )%MOD
  
    
        if (left_product > right_product) : 
            product = (product%MOD * left_product%MOD)%MOD
            i += 2
          
        else : 
            product = (product%MOD * right_product%MOD)%MOD
            j -= 2
  
   
    return product%MOD

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

ans = maxProductSubarrayOfSizeK(a,n,k)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=lambda x: abs(x))[::-1]
P = int(1e9+7)
hu_cnt = []

ans = 1
hu = None
sei = 1
flg = False
for a in A:
    flg = a > 0
    if flg:
        break
if not flg:
    for i in range(1, K+1):
        ans = (ans * A[-i]) % P
    print(ans)
    sys.exit()
if K == N:
    for a in A:
        ans = (ans * a)%P
    print(ans)
    sys.exit()

for i, a in zip(range(K), A):
    if a > 0:
        ans = (ans * sei) % P
        sei = a
    else:
        if not hu:
            hu = a
        else:
            ans = (ans * a * hu) % P
            hu = None

ptn1, ptn2 = -1, -1
if hu:
    for i in range(K, N):
        if A[i] > 0:
            ptn1 = sei * A[i]
            break
    for i in range(K, N):
        if A[i] <= 0:
            ptn1 = hu * A[i]
            break
    ans = (ans * max(ptn1, ptn2)) % P
else:
    ans = (ans * sei) % P
print(ans%P)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    a.sort(key = lambda x:-abs(x))
    c = 0
    p = 0
    m = 0
    for i in a:
        if i != 0:
            c += 1
        if i > 0:
            p += 1
        if i < 0:
            m += 1
    if c < k:
        print(0)
        return
    f = 1
    for x in range(p+1):
        y = k-x
        if y < 0 or y > m:
            continue
        if not y&1:
            f = 0
            break
    if f:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in a[:k]:
            ans *= i
            ans %= mod
        print(ans)
        return
    plus = []
    minus = []
    a.sort()
    for i in a:
        if i < 0:
            minus.append(-i)
        else:
            plus.append(i)
    plus = plus[::-1]
    s_m = [1]
    s_p = [1]
    for i in plus:
        s_p.append(s_p[-1]*i)
    for i in minus:
        s_m.append(s_m[-1]*i)
    ans = 0
    for x in range(p+1):
        y = k-x
        if y < 0 or y > m:
            continue
        d = s_p[x]*s_m[y]
        if ans < d:
            ans = d
    print(ans%mod)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

mod = 10**9+7
res = 1
last_plus_index = -1
last_minus_index = -1

for i in range(K):
    res *= A[i]
    if A[i] < 0:
        last_minus_index = i
    if A[i] > 0:
        last_plus_index = i

if res >= 0:
    print(res % mod)
    exit()

if K-1 == last_minus_index:
    for i in range(K, N):
        if A[i] > 0:
            res = res // A[last_minus_index] * A[i]
            print(res % mod)
            exit()
        if i == N-1:
            if last_plus_index != -1:
                res = res // A[last_plus_index] * A[K]
                print(res % mod)
                exit()
            else:
                # 解が0以下
                A = sorted(A, reverse=True)
                res = 1
                for i in range(K):
                    res *= A[i]
                print(res % mod)
                exit()

else:
    for i in range(K, N):
        if A[i] < 0:
            res = res // A[K-1] * A[i]
            print(res % mod)
            exit()
        if i == N-1:
            res = res // A[last_minus_index] * A[K]
            print(res % mod)
            exit()

Submission status: Wrong Answer

Solution code:
from math import log, log10, log2

def solve():
    MOD = 10**9 + 7

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

    numPos, num0, numNeg = 0, 0, 0
    for A in As:
        if A > 0:
            numPos += 1
        elif A == 0:
            num0 += 1
        else:
            numNeg += 1
#    print('numPos:', numPos, '/ num0:', num0, '/ numNeg:', numNeg)

    if numPos + numNeg < K:
        ans = 0
    else:
        posAs, negAs = [], []
        for A in As:
            if A > 0:
                posAs.append(A)
            elif A < 0:
                negAs.append(A)
        N = numPos + numNeg
#        print('posAs:', posAs, '/ negAs:', negAs)

        if K == N and numNeg%2 != 0:
            if num0 > 0:
                ans = 0
            else:
                ans = 1
                for A in posAs:
                    ans *= A
                    ans %= MOD
                for A in negAs:
                    ans *= A
                    ans %= MOD

        elif K%2 != 0 and numPos == 0:
            if num0 > 0:
                ans = 0
            else:
                negAs.sort(reverse=True)
#                print('negAs:', negAs)
                ans = 1
                for A in negAs[:K]:
                    ans *= A
                    ans %= MOD

        else:
            posAs.sort(reverse=True)
            negAs.sort()
            acc = 0
            accPoss = [acc]
            for A in posAs:
                acc += log(A)
                accPoss.append(acc)
            acc = 0
            accNegs = [acc]
            for A in negAs:
                acc += log(-A)
                accNegs.append(acc)
#            print('accPoss:', accPoss)
#            print('accNegs:', accNegs)

            ans = -1
            xMax = -1
            for x in range(0, K+1, 2):
                y = K - x
                if x > numNeg or y > numPos:
                    break
                prod = accNegs[x] + accPoss[y]
                if prod > ans:
                    ans = prod
                    xMax = x

            ans = 1
            for A in negAs[:xMax]:
                ans *= A
                ans %= MOD
            for A in posAs[:K-xMax]:
                ans *= A
                ans %= MOD

    print(ans % MOD)


solve()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
P=[]
Z=[]
N=[]
for i in range(n):
  if a[i]>0:
    P.append(a[i])
  elif a[i]==0:
    Z.append(a[i])
  else:
    N.append(-a[i])
P.sort()
P3=[1]
for i in range(len(P)):
  P3.append(P3[-1]*P[i]%mod)
P.reverse()
P2=[1]
for i in range(len(P)):
  P2.append(P2[-1]*P[i]%mod)
N.sort()
N3=[1]
for i in range(len(N)):
  N3.append(N3[-1]*N[i]%mod)
N.reverse()
N2=[1]
for i in range(len(N)):
  N2.append(N2[-1]*N[i]%mod)

if len(P)+len(N)<k:
  print(0)
  exit()

if len(N)==0:
  print(P2[k])
  exit()

if len(P)+len(N)==k:
  if len(N)%2==0:
    print(P2[-1]*N2[-1]%mod)
    exit()
  else:
    if len(Z)!=0:
      print(0)
    else:
      print(-P2[-1]*N2[-1]%mod)
    exit()

if k%2==0:
  ans=1
  xp=0
  xn=0
  for i in range(k//2):
    if xp+1<len(P):
      xa=P[xp]*P[xp+1]
    else:
      xa=0
    if xn+1<len(N):
      xb=N[xn]*N[xn+1]
    else:
      xb=0
    if xa<xb:
      xn+=2
      ans*=xb
      ans%=mod
    else:
      xp+=2
      ans*=xa
      ans%=mod
  print(ans)

else:
  ans=1
  xp=0
  xn=0
  ctP=0
  ctN=0
  for i in range(k//2):
    if xp+1<len(P):
      xa=P[xp]*P[xp+1]
    else:
      xa=0
    if xn+1<len(N):
      xb=N[xn]*N[xn+1]
    else:
      xb=0
    if xa<xb:
      xn+=2
      ans*=xb
      ans%=mod
      ctN+=1
    else:
      xp+=2
      ans*=xa
      ans%=mod
      ctP+=1
  if ctP*2+1<=len(P):
    ans*=P[ctP*2]
    ans%=mod
    print(ans)
  else:
    N.reverse()
    P.reverse()
    ans=1
    xp=0
    xn=0
    ctP=0
    ctN=0
    for i in range(k//2):
      if xp+1<len(P):
        xa=P[xp]*P[xp+1]
      else:
        xa=0
      if xn+1<len(N):
        xb=N[xn]*N[xn+1]
      else:
        xb=0
      if xa<xb:
        xn+=2
        ans*=xb
        ans%=mod
        ctN+=1
      else:
        xp+=2
        ans*=xa
        ans%=mod
        ctP+=1
    ans*=N[ctN*2]
    ans%=mod
    if len(Z)!=0:
      print(0)
    else:
      print(-ans%mod)

Submission status: Wrong Answer

Solution code:
import bisect
N ,K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
mod = 10 ** 9 + 7
# ans = 0
if A.count(0) > (N - K):
  print(0)
  quit()
  
# ans = minus
plus = bisect.bisect_right(A, 0)
minus = bisect.bisect_left(A, 0) 
if N == K:
  ans = 1
  for i in range(N):
    ans *= A[i]
    ans %= mod
  print(ans % mod)
  quit()
  
if minus == N:
  ans = 1
  for i in range(1, K + 1):
    ans *= A[-i]
    ans %= mod
  print(ans % mod)
  quit()
  
ans = 1

count = 0
i = 0
j = -1
while count < K:
  if K - count >= 2:
    fo = A[i] * A[i + 1]
    re = A[j] * A[j - 1]
    #print(fo, re)
    if fo > re:
      ans *= (fo % mod) 
      ans %= mod
      i += 2
    elif (A[j - 1] < 1) or (A[j - 2] < 1):
      if fo != 0:
        ans *= (fo % mod) 
        ans %= mod
        i += 2
      else:
        ans *= (re % mod)
        ans %= mod
        if ans < 0:
          ans = 0
        i += 2
    else:
      ans *= (re % mod)
      ans %= mod
      j -= 2
    count += 2  
  else:
    count += 1
    ans *= A[j]
      
  #print(ans)
print(ans % mod)

Submission status: Wrong Answer

Solution code:
num = input().rstrip().split(" ")
line = list(map(int, input().split(" ")))

#print(line)
import itertools

lis = [list(a) for a in itertools.combinations(line, int(num[1]))]

count = len(lis)
count2 = len(lis[0])
ans_l = []
cul=1
for i in range(count):
    for j in range(count2):
        cul *= int(lis[i][j])
    ans_l.append(cul)

ans_s = sorted(ans_l,reverse = True)

ans = ans_s[0]

z = int(ans % (10**9 + 7))

print(z)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
p=1000000007
product = 1
t=0
if A[n - 1] == 0 and (k & 1):
      print(0)
if A[n - 1] <= 0 and (k & 1):
        for i in range(n - 1, n - k - 1, -1):
            product *= A[i]%p
        print(product%p)


else:

    i = 0
    j = n - 1
    if k & 1:
                product *= A[j]%p
                j -= 1
                k -= 1

    k >>= 1
    for itr in range(k):

                left_product = (A[i] * A[i + 1])%p

                right_product = (A[j] * A[j - 1])%p

                if left_product > right_product:
                    product *= left_product%p
                    i += 2

                else:
                    product *= right_product%p
                    j -= 2

    print(product%p)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, K = mi()
A = li()

d = defaultdict(int)
mod = 10**9+7
K_ = K

for i in range(N):
    d[A[i]] += 1
    if A[i] < 0:
        A[i] *= -1

A = sorted(A, reverse=True)
l = []

for num in A:
    if d[-num] > 0:
        l.append(1)
        d[-num] -= 1
    else:
        l.append(0)
        d[num] -= 1

#print(l)
#print(sum(l[:K]))

if not sum(l[:K])%2:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= mod
    print(ans)

else:
    flag = False
    ans = 1
    for i in range(K, N):
        if not l[i]:
            flag = True
            ans *= A[i]
            break
    
    if flag:
        for i in reversed(range(K)):
            if flag and l[i]:
                flag = 0
                continue
            ans *= A[i]
            ans %= mod
        print(ans)
    
    else:
        if K%2:
            for i in range(N-K, N):
                ans *= -A[i]
                ans %= mod
            print(ans)
        else:
            for i in range(N):
                if l[i] == 1:
                    K -= 1
                    ans *= -A[i]
                    ans %= mod
                if K == 0:
                    break
            else:
                if N == K_:
                    print(-sum(A))
                    exit()
                ans = 1
                flag = True
                for i in reversed(range(K_)):
                    if flag and not l[i]:
                        flag = 0
                        continue
                    ans *= A[i]
                    ans %= mod
                ans *= A[K_]
                ans %= mod
                print(ans)
                exit()

            print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    A=list(map(int,sys.stdin.readline().split()))

    Ap=[x for x in A if x>=0 ]
    Am=[abs(x) for x in A if x<0]

    if K==N:
        out=1
        for a in A:
            out*=a
            out%=10**9+7
        print(out)
        return


    if K%2==1 and len(Ap)==0:
        Am.sort()
        out=1
        for i in range(K):
            out*=Am[i]
            out%=10**9+7
        print((-out)%(10**9+7))
        return

    Ap.sort(reverse=True)
    Am.sort(reverse=True)
    
    ap_idx=0
    am_idx=0
    result=1
    for _ in range(0,K,2):
        if K%2==0 and ap_idx+1<len(Ap):
            pmax=Ap[ap_idx]*Ap[ap_idx+1]
        elif K%2==1 and ap_idx+2<len(Ap):
            pmax=Ap[ap_idx]*Ap[ap_idx+1]
        else:
            pmax=-1

        if am_idx+1<len(Am):
            mmax=Am[am_idx]*Am[am_idx+1]
        else:
            mmax=-1

        if pmax==-1 and mmax==-1:
            break

        if pmax>mmax:
            result*=pmax
            ap_idx+=2
        else:
            result*=mmax
            am_idx+=2

        result%=(10**9+7)
    
    if K%2==1:
        result*=Ap[ap_idx]

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

main()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = 1
mod = 10**9+7
 
if min(A) > 0:
    A.sort(reverse=True)
    for i in A[:K]:
        ans = (ans*i)%mod
 
elif max(A) < 0:
 
    if K%2 == 0:
        A.sort()
        for i in A[:K]:
            ans = (ans*abs(i))%mod
    else:
        A.sort(reverse=True)
        for i in A[:K]:
            ans = (ans*abs(i))%mod
        ans *= -1
 
else:
    z = []
    p = []
    m = []
    for i in A:
        if i == 0:
            z.append([i,1])
        elif i > 0:
            p.append([i,1])
        else:
            m.append([i,1])
    m.sort()
    mm = []
    for i in range(0,len(m),2):
        try:
            mm.append([m[i][0]*m[i+1][0],2])
        except:
            pass
    
    tot = p+z+mm+m
 
    tot.sort(reverse=True)
    flag_m = False
    for v,cost in tot:
        if K <= 0:
            break
        if v < 0:
            flag_m = True
        if K - cost >= 0:
            ans = (ans*v)%mod
            K -= cost
        else:
            continue
    
    if flag_m and len(z) == 0:##値が負になる．絶対値の最小化を行う．
        b = [[abs(i),i] for i in A]
        b.sort()
        res = 1
        for _,i in b:
            res = (res*i)%mod
        print(res%mod)
        exit()
 
print(ans%mod)

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
if __name__ == "__main__":
    n,k=map(int,input().split())
    A = [int(x) for x in input().split()]
    print(maxProductSubarrayOfSizeK(A, n, k))

Submission status: Wrong Answer

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

A.sort(reverse=True)

P = []
M = []
Ans = []
p = 0
m = 0

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

if K % 2 == 1 and len(P) != 0:
    Ans.append(P[p])
    p += 1

while len(Ans) < K:

    #Mのストックがもうない時
    if m >= len(M):
        Ans.append(P[p])
        p += 1
    elif p >= len(P):
        Ans.append(M[m])
        m += 1
    elif m+1 >= len(M):
        Ans.append(P[p])
        p += 1
    elif p+1 >= len(P):
        Ans.append(M[m])
        m += 1
    else:
        if P[p]*P[p+1] < M[m]*M[m+1]:
            Ans.append(M[m])
            Ans.append(M[m+1])
            m += 2
        else:
            Ans.append(P[p])
            p += 1

answer = 1
for i in range(K):
    answer = (answer * Ans[i]) % 1000000007

print(answer)

Submission status: Wrong Answer

Solution code:
N, K = list(map(int,input().split()))
A = list(map(int,input().split()))
A = sorted(A, reverse = True, key = lambda x:abs(x))
A = A[:K]
cnt = 0
for i in A:
  if i < 0:
    cnt += 1
if cnt % 2 == 0:

  ans = 1
  for i in range(K):
    ans *= A[i]
    ans = ans%(10**9+7)
  print(ans)
else:
  print("ds")

Submission status: Wrong Answer

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

mod=10**9+7
a.sort()

iszero = (0 in a) # true if contain 0

if a[0] >= 0: # just take k
    a.sort(reverse=True)
    ans=1
    for num in a[:k]:
        ans*=num
        ans%=mod
    print(ans%mod)
    exit()

if a[-1]<=0:
    if k%2!=0:
        a.sort(reverse=True)
    ans=1
    for num in a[:k]:
        ans*=abs(num)
        ans%=mod

    if k%2!=0:
        ans*=-1
    print(ans%mod)
    exit()

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
A.sort(key=lambda x: abs(x),reverse=True)
mod = 10**9+7
sign = 1
last_nega = -1
last_posi = -1

if all([a<0 for a in A]) and K%2:
    ans = 1
    for i in range(1,K+1):
        ans *= abs(A[-i])
        ans %= mod
    print(-ans%mod)
else:
    for i in range(K):
        if A[i] < 0:
            last_nega = i
        else:
            last_posi = i
        sign *= (1 if 0 < A[i] else -1)

    if 0 < sign:
        ans = 1
        for i in range(K):
            ans *= abs(A[i])
            ans %= mod
        print(ans)
    else:
        ans = 1
        for i in range(K):
            ans *= abs(A[i])
            ans %= mod
        ans1 = -float('inf')
        ans2 = -float('inf')

        #Aが正負を一つずつもつならどっかに引っかかる(と思う)
        if last_nega != -1:
            ans1 = ans*pow(abs(A[last_nega]),mod-2,mod)
            ans1 %= mod
            for i in range(K,N):
                if 0 <= A[i]:
                    ans1 *= A[i]
                    ans1 %= mod
                    break
            else:
                ans1 = -float('inf')
        if last_posi != -1:
            ans2 = ans*pow(abs(A[last_posi]),mod-2,mod)
            ans2 %= mod
            for i in range(K,N):
                if A[i] < 0:
                    ans2 *= abs(A[i])
                    ans2 %= mod
                    break
            else:
                ans2 = -float('inf')
        # ans3 = 1
        # for i in range(1,K+1):
        #     ans3 *= A[-i]
        #     ans3 %= mod

        # ans = max(ans1,ans2,ans3)
        ans = max(ans1,ans2)
        print(ans%mod)

Submission status: Wrong Answer

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

plus, minus = [], []
n_p, n_m, n_z = 0, 0, 0

for i in range(N):
    if A[i] > 0:
        plus.append(A[i])
        n_p += 1
    elif A[i] < 0:
        minus.append(A[i])
        n_m += 1
    else:
        n_z += 1

minus = [abs(i) for i in minus]
minus = list(reversed(sorted(minus)))

kekka = plus

n_iter = min(len(plus), len(minus)) // 2

if n_p > 0:
    # プラスにできる時
    if K <= n_p + n_m:
        for i in range(n_iter):
            idx = i * 2
            p_sum = plus[idx] * plus[idx + 1]
            m_sum = minus[idx] * minus[idx + 1]

            if m_sum >= p_sum:
                kekka[idx] = minus[idx]
                kekka[idx + 1] = minus[idx + 1]

        ans = 1
        mod = 10**9+7
        for k in kekka:
            ans *= k
            ans %= mod
        print(ans)

    # ゼロにできる時
    else:
        print(0)

else:
    if K % 2 == 0:
        if n_m >= K:
            ans = 1
            mod = 10**9+7
            for i in range(K):
                ans *= minus[i]
                ans %= mod
            print(ans)
        else:
            print(0)
    else:
        if n_z > 0:
            print(0)
        else:
            minus = list(reversed(minus))
            ans = 1
            mod = 10**9+7
            for i in range(K):
                ans *= -minus[i]
                ans %= mod
            print(ans)

Submission status: Wrong Answer

Solution code:
mod1,mod2=10**9+7,998244353
mod=mod1
n,k=map(int,input().split())
p,m=[],[]
for i in list(map(int,input().split())):
    if i<0:m.append(i)
    elif i>0:p.append(i)
if len(p)+len(m)<k:
    print(0)
elif len(p)==0:
    ans=1
    for i in range(k):ans=(ans*m[i])%mod
    
    print(ans)
else:
    p.sort()
    m.sort()
    ans=0
    c=1
    v={0:1}
    for i in range(min(len(p),k)):
        c*=p[-1-i]
        v[i+1]=c
    if k in v:
        ans=max(ans,v[k])
    x=1
    for i in range(1,min(len(m),k)+1):
        x*=m[i-1]
        if k-i in v:
            ans=max(ans,v[k-i]*x)

    print(ans%mod)