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:
from itertools import accumulate
N, K = map(int, input().split())
As = list(map(int, input().split()))
MOD = 10 ** 9 + 7

def multiReduce(array):
    ret = 1
    for a, s in array:
        if s == 0:
            ret = ret * a % MOD
        else:
            ret = ret * (-a) % MOD
    return ret

arr = []
for a in As:
    if a >= 0:
        arr.append((a, 0))
    else:
        arr.append((-a, 1))

arr.sort(reverse=True)

if arr[K-1][0] == 0:
    print(0)
    exit()

lastPlus = None
lastPlusIdx = None
lastMinus = None
lastMinusIdx = None
numMinus = 0
for i in range(K):
    a = arr[i]
    if a[1] == 0:
        lastPlus = a[0]
        lastPlusIdx = i
    else:
        lastMinus = -a[0]
        lastMinusIdx = i
        numMinus += 1

if numMinus % 2 == 0:
    print(multiReduce(arr[:K]))
    exit()

nextPlus = None
nextMinus = None
for i in range(K, N):
    a = arr[i]
    if a[1] == 0 and nextPlus is None:
        nextPlus = a[0]
    elif a[1] == 1 and nextMinus is None:
        nextMinus = -a[0]

BD = None
if lastMinus and nextPlus:
    BD = lastMinus * nextPlus
AC = None
if lastPlus and nextMinus:
    AC = lastPlus * nextMinus

if BD and (AC is None or BD >= AC):
    arr[lastMinusIdx] = (nextPlus, 0)
    print(multiReduce(arr[:K]))
    exit()
elif AC and (BD is None or BD < AC):
    arr[lastPlusIdx] = (nextMinus, 1)
    print(multiReduce(arr[:K]))
    exit()

print(multiReduce(arr[N-K:]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def allmul(l):
    tmp = 1
    for v in l:
        tmp *= v
        tmp %= MOD

    return tmp


def main():
    N, K = mi()
    A = list(mi())
    ans = 1
    An = []
    Ap = []
    for a in A:
        if a > 0:
            Ap.append(a)
        if a < 0:
            An.append(a)

    An.sort()
    Ap.sort(reverse=True)


    if K == N:
        ans = allmul(A)
    elif len(An) == N:
        if K%2 == 0:
            ans = allmul(An[:K])
        else:
            ans = allmul(An[-K:])
    elif len(Ap) == 0:
        if K%2 == 0 and len(An) <= K:
            ans = allmul(An[:K])
        else:
            ans = 0
    else:
        B = A[:]
        B.sort(key=lambda x: abs(x), reverse=True)
        n = sum(1 for b in B[:K] if b < 0)
        if n%2==0:
            ans = allmul(B[:K])
        else:
            t = 0
            for i in range(N):
                if t == K:
                    break
                if t == K-1 and B[i] < 0:
                    continue
                ans *= B[i]
                ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

A.sort()

def get_pos_num():
    lb = -1
    ub = N

    while ub - lb > 1:
        mid = (ub + lb) // 2
        if A[mid] > 0:
            ub = mid
        else:
            lb = mid

    return ub

def get_neg_num():
    lb = -1
    ub = N

    while ub - lb > 1:
        mid = (ub + lb) // 2
        if A[mid] >= 0:
            ub = mid
        else:
            lb = mid

    return lb

pos_num = get_pos_num()
neg_num = get_neg_num()
# A[0], A[1], ... , A[neg_num] <- negative number
# A[neg_num + 1], ..., A[pos_num - 1] <- 0
# A[pos_num], ..., A[N-1] <- positive number

neg_ind = 0
pos_ind = N-1
ans = 1

if (N-1) - neg_ind > K or K % 2 == 0:
    while K > 0:
        if K >= 2:
            if pos_ind < pos_num:
                pos_tmp = -1*INF
            else:
                pos_tmp = A[pos_ind]*A[pos_ind-1]

            if neg_ind > neg_num:
                neg_tmp = -1 * INF
            else:
                neg_tmp = A[neg_ind]*A[neg_ind+1]

            if pos_tmp < neg_tmp:
                neg_ind += 2
                ans = (ans * neg_tmp + MOD) % MOD

                # ans *= neg_tmp
                K -= 2
            else:
                pos_ind -= 2
                ans = (ans * pos_tmp + MOD) % MOD

                # ans *= pos_tmp
                K -= 2
        
        else:
            ans = (ans * A[pos_ind] + MOD) % MOD
            # ans *= A[pos_ind]
            K -= 1
else:
    for i in range(K):
        ans = (ans * A[N-1-i] + MOD) % MOD
        # ans *= A[N-1-i]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
pm = 1
ans = 1
a.sort()
cnt = 0
if n > k:
    for x in a:
        if x < 0: cnt += 1
    if cnt%2 == 1:
        a.pop(cnt - 1)
        n -= 1

if k%2 == 1 and a[n - 1] < 0:
    if 0 in a:
        print(0)
        sys.exit()
    for i in range(k):
        ans = (ans * a[n - 1 - i])%mod
    print(ans%mod)
    sys.exit()
for i in range(k//2):
    p = a[n-1] * a[n-2]
    m = a[0] * a[1]
    if p >= m:
        #print(a)
        ans = (ans * p)%mod
        a.pop(n - 1)
        a.pop(n - 2)
        #print(ans)
    else:
        ans = (ans * m)%mod
        a.pop(1)
        a.pop(0)
    n -= 2
if k%2 == 1:
    ans = (ans * a[n - 1])%mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9+7
sei = []
hu = []
zero = []
for i in range(N):
    a = A[i]
    if a > 0:
        sei.append(a)
    elif a < 0:
        hu.append(a)
    else:
        zero.append(0)
sei.sort(reverse = True)
if len(zero) > N - K:
    print(0)
else:
    ans = 1
    p = len(sei)
    q = len(hu)
    if p == 0:
        hu.sort(reverse = True)
        for i in range(K):
            ans *= hu[i]
            ans %= MOD
        print(ans)
    elif q == 0:
        for i in range(K):
            ans *= sei[i]
            ans %= MOD
        print(ans)
    else:
        hu.sort()
        flag = 0
        pin = 0
        qin = 0
        r = K
        while r > 0:
            if pin == -1 and qin == -1:
                break
            elif pin == -1:
                qin += 1
                if qin == q:
                    qin = -1
                if flag == 1:
                    flag = 0
                else:
                    flag = 1
            elif qin == -1:
                pin += 1
                if pin == p:
                    pin = -1
            else:
                if abs(sei[pin])>abs(hu[qin]):
                    pin += 1
                    if pin == p:
                        pin = -1
                else:
                    qin += 1
                    if qin == q:
                        qin = -1
                    if flag == 0:
                        flag = 1
                    else:
                        flag = 0
            r -= 1
        if pin == -1:
            pin = p
        if qin == -1:
            qin = q
        if p+q == K:
            for i in range(p):
                ans *= sei[i]
                ans %= MOD
            for j in range(q):
                ans *= hu[j]
                ans %= MOD
            print(ans%MOD)
        else:
            if flag == 0:
                for i in range(pin):
                    ans *= sei[i]
                    ans %= MOD
                for j in range(qin):
                    ans *= hu[j]
                    ans %= MOD
                print(ans%MOD)
            else:
                if pin == p:
                    for i in range(pin-1):
                        ans *= sei[i]
                        ans %= MOD
                    for j in range(qin+1):
                        ans *= hu[j]
                        ans %= MOD
                    print(ans%MOD)
                else:
                    for i in range(pin+1):
                        ans *= sei[i]
                        ans %= MOD
                    for j in range(qin-1):
                        ans *= hu[j]
                        ans %= MOD
                    print(ans%MOD)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

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

alst.sort()

if k == 1:
    print(alst[-1] % MOD)
    exit()

if alst[0] >= 0:
    ans = 1
    alst.sort(reverse = True)
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

if alst[-1] <= 0:
    ans = 1
    if k % 2 == 1:
        alst = alst[::-1]
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

blst = []
for num in alst:
    try:
        blst.append([abs(num), abs(num) // num])
    except ZeroDivisionError:
        blst.append([abs(num), 0])
blst.sort(reverse = True,key = lambda x:x[0])
if blst[k - 1] == 0:
    print(0)
    exit()
    
minus = 0
last_minus = 0
last_plus = 0
ans_lst = []
for i in range(k):
    if blst[i][1] == -1:
        minus += 1
        last_minus = blst[i][0]
    elif blst[i][1] == 1:
        last_plus = blst[i][0]
    else:
        print(0)
        exit()
    ans_lst.append(blst[i][0])

next_minus = 0
next_plus = 0
flg_minus = False
flg_plus = False

for i in range(k, n):
    if blst[i][1] == -1 and (not flg_minus):
        next_minus = blst[i][0]
        flg_minus = True
    if blst[i][1] == 1 and (not flg_plus):
        next_plus = blst[i][0]
        flg_plus = True
    if (flg_plus and flg_minus) or blst[i][1] == 0:
        break

if minus % 2 == 0:
    ans = 1
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

else:
    minus_s = last_minus * next_minus
    plus_s = last_plus * next_plus
    ans = 1
    if minus == k:
        ans_lst.remove(last_minus)
        ans_lst.append(next_plus)
    elif minus_s == plus_s == 0:
        if next_minus == 0:
            ans_lst.remove(last_minus)
            ans_lst.append(next_plus)
        else:
            ans_lst.remove(last_plus)
            ans_lst.append(next_minus)
        
    elif minus_s > plus_s:
        ans_lst.remove(last_plus)
        ans_lst.append(next_minus)
    else:
        ans_lst.remove(last_minus)
        ans_lst.append(next_plus)
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

Submission status: Wrong Answer

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

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

ans = 1
mod = 10 ** 9 + 7

if K == 1:
    print(max(A) % mod)
elif K == N:
    minus_cnt = 0
    for a in A:
        if a < 0:
            minus_cnt += 1
        ans *= a
        ans %= mod
    print(ans if minus_cnt % 2 == 0 else mod - ans)
else:
    minus_cnt = 0
    new_A = []
    select_ls = []

    for a in A:
        new_A.append([abs(a), 0 if a >= 0 else -1])
    new_A.sort(reverse=True)

    for i in range(K):
        select_ls.append(new_A[i])
        minus_cnt += new_A[i][1]

    if minus_cnt % 2 == 0:
        for s in select_ls:
            ans *= s[0]
            ans %= mod
        print(ans)
    else:
        ok = False
        for i in range(K, N):
            if new_A[i][1] == 0:
                ok = True
                ans *= new_A[i][0]
                select_ls.sort()
                for j in range(1, len(select_ls)):
                    ans *= select_ls[j][0]
                    ans %= mod
                break
        if not ok:
            if 0 in A:
                print(0)
                exit()
            new_A.sort()
            for i in range(K):
                ans *= new_A[i][0]
                ans %= mod
        print(mod - ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
m,p=[],[]
pr=10**9+7
for i in A:
    if i>=0:
        p.append(i)
    else:
        m.append(i)
lm=len(m)
m.sort()
p.sort(reverse=1)
lp=len(p)
if N==K:
    a=1
    for i in A:
        a=a*i%pr
    print(a)
    exit()
mm,pp=[],[]
for i in range(1,lm,2):
    mm.append((m[i-1]*m[i]%pr,0,i))
for i in range(1,lp,2):
    pp.append((p[i-1]*p[i]%pr,1,i))
l=mm+pp
l.sort(reverse=1)
def gya(n):
    return pow(n,pr-2,pr)
mt,pt=-1,-1
a=1
if len(l)*2>=K:
    for i in l[:K//2]:
        a=a*i[0]%pr
        if i[1]:
            pt=i[2]
        else:
            mt=i[2]
    if K%2:
        if pt<lp-1:
            a=a*p[pt+1]%pr
        elif pt==-1:
            a=1
            m=m[::-1]
            for j in m[:K]:
                a=a*j%pr
        else:
            a=a*gya(p[pt])*m[mt+1]*m[mt+2]%pr
else:
    for i in l:
        a=a*i[0]%pr
        if i[1]:
            pt=i[2]
        else:
            mt=i[2]
    a=a*p[pt+1]%pr
print(a)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,k = map(int,readline().split())
a = list(map(int,readline().split()))
mod = 10**9+7

p = []
P = 0
z = False
for i in a:
  if i > 0:
    p.append((i,1))
    P += 1
  elif i == 0:
    p.append((0,0))
    z = True
  else:
    p.append((-i,-1))
    
if P == 0:
  if z:
    print(0)
  else:
    ans = 1
    p.sort()
    for i in range(k):
      ans *= -p[i][0]
      ans %= mod
    print(ans)
  exit()

p.sort(reverse=True)
mi_p = 0
ma_m = 0
c = 0

for i in range(k):
  if p[i][1] > 0:
    mi_p = i
  elif p[i][1] == 0:
    print(0)
    exit()
  else:
    ma_m = i
    c += 1
    
if c%2 == 0:
  ans = 1
  for i in range(k):
    ans *= p[i][0]
    ans %= mod
  print(ans)
elif c%2 == 1 and n == k:
  ans = 1
  for i in range(k):
    ans *= p[i][0]
    ans %= mod
  print(-ans)
else:
  ma_p = 0
  mi_m = 0
  for i in range(n-k):
    L = p[k+i]
    if L[1] > 0 and ma_p == 0:
      ma_p = p[k+i][0]
    if L[1] < 0 and mi_m == 0:
      mi_m = p[k+i][0]
    if ma_p*mi_m != 0:
      break
  ans_p = 1
  ans_m = 1
  for i in range(k):
    if i == ma_m:
      ans_p *= p[i][0]
    elif i == mi_p:
      ans_m *= p[i][0]
    else:
      ans_p *= p[i][0]
      ans_m *= p[i][0]
    ans_p %= mod
    ans_m %= mod
  print(max(ans_p*mi_m%mod,ans_m*ma_p%mod))

Submission status: Wrong Answer

Solution code:
import sys
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sorted(A, key=abs, reverse=True)
X = 1
pm = 0
for i in range(K - 1):
    if S[i] < 0:
        pm = 1 - pm
    X = X * abs(S[i]) % MOD
    X = X % MOD
for i in range(K - 1, N):
    if pm == 0:
        if S[i] > 0:
            Y = X * S[i] % MOD
            print(Y % MOD)
            sys.exit()
    else:
        if S[i] < 0:
            Y = X * abs(S[i]) % MOD
            print(Y % MOD)
            sys.exit()

if S[0] > 0:
    pm = 0
else:
    pm = 1
for i in range(K - 2, -1, -1):
    if pm == 0:
        if S[i] < 0:
            X = 0
            for j in range(K):
                if j == i:
                    continue
                X = X * abs(S[j]) % MOD
                X = X % MOD
            print(X % MOD)
            sys.exit()
    if pm == 1:
        if S[i] > 0:
            X = 0
            for j in range(K):
                if j == i:
                    continue
                X = X * abs(S[j]) % MOD
                X = X % MOD
            print(X % MOD)
            sys.exit()

X = 1
S = S[::-1]
for i in range(K):
    X = X * abs(S[i]) % MOD
X *= -1
print(X % MOD)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
MOD=10**9+7
p=[]
n=[]
for i in range(N):
    if A[i]<0:
        n.append(A[i])
    else:
        p.append(A[i])
p.sort(reverse=True)
n.sort()
numplus=len(p)
if numplus==0:
    ans=1
    if K%2==1:
        for i in range(1,K+1):
            ans=(ans*n[i*(-1)])%MOD
    else:
        for i in range(K):
            ans=(ans*n[i])%MOD
elif N==K:
    ans=1
    for i in range(N):
        ans=(ans*A[i])%MOD
else:
    if numplus>=K:
        x=K
    else:
        if (K-numplus)%2==1:
            x=numplus-1
        else:
            x=numplus
    ans=1
    for i in range(x):
        ans=(ans*p[i])%MOD
    for i in range(K-x):
        ans=(ans*n[i])%MOD
    temp=ans
    bai=1
    while x>1:
        if len(n)<(K-x+2):
            break
        if n[K-x]*n[K-x+1]<p[x-1]*p[x-2]:
            break
        temp=(temp*n[K-x]*n[K-x+1])%MOD
        temp=(temp*pow(p[x-1]*p[x-2],MOD-2,MOD))%MOD
        ans=temp
        x-=2
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
MOD = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, (input().split())))
ap = []
neg_cnt = 0
zero_cnt = 0
for a in A:
    if a<0:
        ap.append((-a, 1))     # sortで先に来るようマイナスを1にする
        neg_cnt += 1
    elif a==0:
        ap.append((0, 0))
        zero_cnt += 1
    else:
        ap.append((a, -1))
ap.sort(reverse=True)
# print(ap)
ans = 1
if neg_cnt==N and K%2:      # 全てが負で奇数個選ぶので、答えは負
    for i in range(K):
        ans *= ap[N-i-1][0] * ap[N-i-1][1] * -1
        ans %= MOD
else:                       # 答えは正
    neg_num = 0
    for i in range(K):
        if ap[i][1] == 1:
            neg_num += 1
    if neg_num % 2:     # 負の数が奇数だったら、-1して偶数回にし、正が出るまで見る
        neg_num -= 1
    i = 0
    cnt = 0
    while cnt < K and i < N:
    # for i in range(K):
        if ap[i][1] == 1:  # 負の数だったら、neg_num回まで
            if neg_num == 0:
                i += 1
                continue
            else:
                neg_num -= 1
        ans *= ap[i][0] * ap[i][1] * -1
        ans %= MOD
        cnt += 1
        i += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def checkio(numbers_array):
    return sorted(numbers_array, key=lambda x: abs(x))

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

a = checkio(a)
a = a[::-1]

ans = 1
ans2 = 1

tmp = []
loc = 0
flg = False
for i in range(n):
    if flg == False:
        if a[i] > 0:
            ans *= a[i]
            ans %= MOD
            loc += 1
        else:
            if k - loc >= 2:
                flg = True
                ans2 *= a[i]
            else:
                continue
    else:
        if a[i] > 0:
            tmp.append(a[i])
        else:
            if len(tmp) >= 2:
                if tmp[-1] * tmp[-2] > ans2 * a[i]:
                    for j in range(min(k - loc, len(tmp))):
                        ans *= tmp[j]
                        ans %= MOD
                        loc += 1
                else:
                    ans *= ans2
                    ans *= a[i]
                    loc += 2
                    ans %= MOD
            flg = False
    if loc == k:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
from math import log, log10, log2

log = 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:
                    continue
                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:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,K=map(int,input().split())

A=list(map(int,input().split()))
mod=10**9+7
Am=[-i for i in A if i<0]
Ap=[i for i in A if i>=0]

Am.sort()
Ap.sort()
Am=deque(Am)
Ap=deque(Ap)



if N-K==0 and len(Am)%2==0 or len(Ap)==0 and K%2:
    c=1
    while K and (Am or Ap) :
        if Am and Ap:
            if Am[0]<Ap[0]:
                c*=Am.popleft()
            else:
                c*=Ap.popleft()
        elif Am:
            c*=Am.popleft()
        elif Ap:
            c*=Ap.popleft()
        K-=1
        c=-c
        c%=mod
    #print("unko")

else:
    c=1
    while K and (len(Am)>=2 or Ap) :
        if K==1 and len(Ap)==0:
            print(c)
            c*=pow(a,mod-2,mod)
            b=Am.pop()
            c*=b
            bb=Am.pop()
            c*=bb
            c%=mod
            break

        if K>=2 and len(Am)>=2:
            if len(Am)>=2 and len(Ap)>=2:
                if Ap[-1]*Ap[-2]>Am[-1]*Am[-2]:
                    a=Ap.pop()
                    c*=a
                    aa=Ap.pop()
                    c*=aa
                else:
                    b=Am.pop()
                    c*=b
                    bb=Am.pop()
                    c*=bb
                K-=2
            elif len(Ap)==1 and len(Am)>=2:
                if Ap[-1]>Am[-1]*Am[-2]:
                    a=Ap.pop()
                    c*=a
                    K-=1
                else:
                    b=Am.pop()
                    c*=b
                    bb=Am.pop()
                    c*=bb
                    K-=2
            else:
                b=Am.pop()
                c*=b
                bb=Am.pop()
                c*=bb
                K-=2
        else:
            a=Ap.pop()
            c*=a
            K-=1
        c%=mod
print(c%mod)

Submission status: Wrong Answer

Solution code:
import numpy as np

A,B = map(int,input().split())
L = list(map(int, input().split()))

l = []

for i in range(A):
  l.append(abs(L[i]))
  
S = sorted(l,reverse=True)

v = np.prod(S[:B])

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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

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

ans = 0
a = 0  # 0の個数
b = 0
c = 0
B = []
C = []
D = []
for i in range(N):
    if A[i] == 0:
        a += 1
    elif A[i] > 0:
        b += 1
        B.append(A[i])
        D.append(A[i])
    else:
        c += 1
        C.append(A[i])
        D.append(A[i])
if N-a < K:
    print(0)
    exit()

ans = 1

if c == N and K % 2 == 1:
    C = sorted(C,reverse=True)
    for i in range(K):
        ans *= C[i]
        ans %= mod
    print(ans)
    exit()
if K == N:
    for i in range(N):
        ans *= A[i]
        ans %= mod
    print(ans)
    exit()
if b == 0 and K % 2 == 1:
    print(0)
    exit()

d = b + c
E = [(abs(D[i]),D[i]) for i in range(d)]
E = sorted(E,reverse=True)

if K == 1:
    print(max(A))
    exit()
if K == 2:
    if N == 3:
        M = max([E[0][1]*E[1][1],E[0][1]*E[2][1],E[1][1]*E[2][1]])
        print(M % mod)
        exit()
    else:
        M = max([E[0][1] * E[1][1], E[0][1] * E[2][1], E[1][1] * E[2][1],E[0][1] * E[3][1],E[1][1] * E[3][1],E[2][1] * E[3][1]])
        print(M % mod)
        exit()



r = 0
if K >= 3:
    for i in range(K-2):
        if E[i][1] < 0:
            r += 1
        ans *= E[i][0]
        ans %= mod

if K == N-1:
    x = E[K-2][1]
    y = E[K-1][1]
    z = E[K][1]
    a1 = x
    a1 *= y
    a2 = x
    a2 *= z
    a3 = y
    a3 *= z
    if r % 2 == 0:
        M = max([a1,a2,a3])
    else:
        M = min([a1,a2,a3])
    print((ans*M) % mod)
    exit()

else:
    x = E[K-2][1]
    y = E[K-1][1]
    z = E[K][1]
    w = E[K+1][1]
    a1 = x
    a1 *= y
    a2 = x
    a2 *= z
    a3 = y
    a3 *= z
    a4 = x
    a4 *= w
    a5 = y
    a5 *= w
    a6 = z
    a6 *= w
    if r % 2 == 0:
        M = max([a1,a2,a3,a4,a5,a6])
    else:
        M = min([a1,a2,a3,a4,a5,a6])
    print((ans*M) % mod)
    exit()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
tempa=[0]*n
tempf=[0]*n
f=0
for i in range(n):
  if a[i]>0:
    tempf[i]=1
    tempa[i]=a[i]
  elif a[i]<0:
    tempf[i]=-1
    tempa[i]=a[i]*-1
    f=f+1
ans=1
if k%2==1 and f>=k:
  a.sort(reverse=True)
  for i in range(k):
    ans=ans*a[i]
  ans=ans%(10**9+7)
else:
  tempa.sort(reverse=True)
  for i in range(k):
    ans=(ans*tempa[i])%(10**9+7)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
a, b = map(int, input().split())
A = sorted(map(int, input().split()))
long= list(itertools.combinations(A, b))
han=-99999999999999999
for a in long:
    goukei=1
    for b in a:
        goukei*=int(b)
    if goukei>han:
        han=goukei
ko=han%1000000007
print(ko)

Submission status: Wrong Answer

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

a.sort(reverse=True, key=lambda x:abs(x))
cnt = 0
im = 0
ip = 0
cp = 0
mod = 10 ** 9 + 7

for i, ai in enumerate(a):
    if i < k:
        if ai < 0:
            im = i
            cnt += 1
        if ai > 0:
            ip = i
    if ai > 0:
        cp += 1

ans = 1
f = 0

# print(a)
if cnt % 2:
    if cp == 0:
        a.sort(reverse=True)
        for i, ai in enumerate(a):
            if i == k:
                break
            ans *= ai
            ans %= mod
        print(ans)
    else:
        ans = 1
        cnt = 0
        f = 0
        for i, ai in enumerate(a):
            if cnt == k:
                f = 2
                break
            if i == im:
                f = 1
                continue
            if f == 1 and ai <= 0:
                continue
            ans *= abs(ai)
            ans %= mod
            # print(i, ai)
            cnt += 1
        if f == 2:
            print(ans)
        else:
            ans = 1
            cnt = 0
            f = 0
            for i, ai in enumerate(a):
                if cnt == k:
                    f = 2
                    break
                if i == ip:
                    f = 1
                    continue
                if f == 1 and ai >= 0:
                    continue
                ans *= abs(ai)
                ans %= mod
                # print(i, ai)
                cnt += 1
            if f == 2:
                print(ans)
            else:
                a.sort(reverse=True)
                for i, ai in enumerate(a):
                    if i == k:
                        break
                    ans *= ai
                    ans %= mod
                print(ans)

else:
    for i, ai in enumerate(a):
        if i == k:
            break
        ans *= abs(ai)
        ans %= mod
    print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n, k = map(int, input().split())
l = [ int(x) for x in input().split() ]
max_ans = -10**9

for com in itertools.combinations(l, k):
    com_list =  list(com)
    pp = 1
    for el in com_list:
        pp *= el

    if pp > max_ans:
        max_ans = pp

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