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:
def solution():
    n, k = map(int, input().split())
    a_list = sorted(list(map(int, input().split())),
                    key=lambda a: abs(a), reverse=True)
    # import numpy as np
    # a_list = sorted([int(el) for el in np.random.randint(-(10**9), 10**9, 2*10**5)],
    #                 key=lambda a: abs(a), reverse=True)
    # print(a_list[:10])
    # n, k = 2*10**5, 2*10**5
    
    num0 = a_list.count(0)
    if n - k < num0:
        return 0

    MOD = 10 ** 9 + 7

    if all([a<0 for a in a_list]):
        ans = 1
        a_list = reversed(a_list)
        for i, a in enumerate(a_list):
            ans *= a % MOD
            if i == k - 1:
                return ans % MOD
    else:
        ans = 1
        pn = 1
        for i, a in enumerate(a_list):
            # print(1111, i, a, ans, pn)
            if i>=k-1:
                if pn < 0 and a >= 0:
                    continue
                else:
                    ans *= a % MOD
                    return ans % MOD
            ans *= a % MOD
            pn *= 1 if a>0 else -1

print(solution())

Submission status: Wrong Answer

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

mod = 10 ** 9 + 7
res_1 = 1
for a in A[-K:]:
    res_1 *= a
res_2 = 1
for a in A[:K]:
    res_2 *= a
res = max(res_1, res_2)
print(res % mod)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
A.sort()
B = []
flag = False
F = False
tmp = 0
num = -1
ans = 1
tmp_ = -1
for i, a in enumerate(A):
    if a < 0:
        if flag:
            B.append(tmp * a)
            flag = False
        else:
            tmp = a
            flag = True
    elif a == 0:
        F = True
    else:
        tmp_ = tmp
        num = i
        break

if num == -1:
    if K % 2 == 1:
        for i, a in enumerate(A[::-1]):
            if i == K:
                print(ans)
                exit()
            ans *= a
            ans %= mod

A = A[num:]
A.sort(reverse=True)
if K % 2 == 1:
    ans = A[0]
    A = A[1:]
    K -= 1
ans %= mod
flag = False
for a in A:
    if flag:
        B.append(tmp * a)
        flag = False
    else:
        tmp = a
        flag = True
K //= 2
if len(B) < K:
    if F:
        print(0)
        exit()
    else:
        ans *= tmp_

B.sort(reverse=True)
for i, b in enumerate(B):
    if K == i:
        break
    ans *= b
    ans %= mod

print(ans % mod)

Submission status: Wrong Answer

Solution code:
import sys;input=sys.stdin.readline
MOD = 10**9+7
N, K = map(int, input().split())
X = list(map(int, input().split()))
if N==K:
    R = 1
    mc = 0
    for x in X:
        if x<0:
            mc += 1
        R = R*abs(x)%MOD
    if mc%2:
        print(((-1)*R)%MOD)
    else:
        print(R%MOD)
    sys.exit()
ps,ns=[],[]
for x in X:
    if x>=0:
        ps.append(x)
    else:
        ns.append(x)
ps.sort()
ns.sort()
if K%2 and len(ps)==0:
    R = 1
    ns = ns[::-1]
    for i in range(K):
        R = R*abs(ns[i])%MOD
    print((-1*R)%MOD)
    sys.exit()
if len(ps) == 0:
    R = 1
    for i in range(K):
        R = R*abs(ns[i])%MOD
    print(R)
    sys.exit()
nns = []
for i in range(len(ns)//2):
    nns.append(ns[2*i]*ns[2*i+1])
if K%2:
    R = ps.pop()
    K -= 1
else:
    R = 1
nns = nns[::-1]
K = K//2
pps  = []
for i in range(len(ps)//2):
    pps.append(ps[2*i]*ps[2*i+1])
while K:
    x = 0
    f = 0
    if pps:
        x = pps.pop()
        f = 1
    if nns:
        if nns[-1] > x:
            if f:
                pps.append(x)
            x = nns.pop()
    R = R*x%MOD
    K-=1
print(R)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
li_a = list(map(int, input().split()))
mod = 10**9+7
li = []
lll = 0
for i in li_a:
    if i < 0:
        li.append((abs(i), -1))
        lll += 1
    else:
        li.append((i, 1))
li.sort()
if lll == n:
    ans = 1
    for i in range(k):
        ans *= -li[i][0]
        ans %= mod
    print(ans)
    exit()
ans = 1
guki = 1
for i in range(n-1, n-k-1, -1):
    ans *= li[i][0]
    ans %= mod
    guki *= li[i][1]
if guki > 0:
    print(ans)
else:
    P, M, p, m = 10**6, 1000000, 1000000, 1000000
    P1, M1, p1, m1 = True, True, True, True
    for i in range(n-k, n-1):
        if li[i][1] > 0:
            Plus = li[i][0]
            P = i
            P1 = False
            break
    for i in range(n-k, n-1):
        if li[i][1] < 0:
            Mini = li[i][0]
            M = i
            M1 = False
            break
    for i in range(n-k, -1, -1):
        if li[i][1] > 0:
            plus = li[i][0]
            p = i
            p1 = False
            break
    for i in range(n-k, -1, -1):
        if li[i][1] < 0:
            mini = li[i][0]
            m = i
            m1 = False
            break
    ans1 = 1
    ans2 = 1
    if not P1 and not m1:
        for i in range(n-1, n-k-1, -1):
            if i == P:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans1 *= li[m][0]
        ans1 %= mod
    if not p1 and not M1:
        for i in range(n-1, n-k-1, -1):
            if i == M:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans2 *= li[p][0]
        ans2 %= mod
    print(max(ans1, ans2))

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


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:
                ans = 1
                for i in range(N-K, N):
                    ans *= -A[i]
                    ans %= mod
                print(ans)
                exit()
            print(ans)

Submission status: Wrong Answer

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

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)

for v,cost in tot:
    if K <= 0:
        break
    if K - cost >= 0:
        ans = (ans*v)%mod
        K -= cost
    else:
        continue

print(ans%mod)

Submission status: Wrong Answer

Solution code:
# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n,k = readInt()
    a = readInt()
    ans = 0
    a.sort()
    l = [1]
    for i in range(n):
        l.append(l[i]*a[i])
    r = [1]
    for i in range(n-1,-1,-1):
        r.append(r[-1]*a[i])
    for i in range(0,k+1,2):
        ans = max(ans,(l[i]*r[k-i])%mod)
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
MOD = 10**9+7
a = list(map(int,input().split()))
b = []
c = []
d = []
num_z = 0
for val in a:
    if val>0:
        b.append(val)
        d.append(val)
    elif val<0:
        c.append(-val)
        d.append(-val)
    else:
        num_z += 1
        d.append(0)
num_b = len(b)
num_c = len(c)
res = 1
if (N==num_c and K%2==1):
    d = sorted(d)
    for val in d[:K]:
        res = res*val%MOD
    res = -res%MOD
elif (N==K and num_c>0):
    c = sorted(c)
    for val in a:
        res = res*val%MOD
else:
    b = sorted(b,reverse=True)
    c = sorted(c,reverse=True)
    bidx = 0
    cidx = 0
    tmp = 0
    if num_b+num_c < K:
        res = 0
    else:
        if num_b >= K:
            bidx = K
        elif num_c>=2:
            bidx = num_b
            cidx = K-bidx
            if (K-num_b)%2==1:
                if cidx == num_c:
                    print(0)
                    exit()
                bidx -= 1
                cidx += 1
        else:
            print(0)
            exit()
        #print(bidx,cidx)
        for val in b[:bidx]:
            res = res*val%MOD
        for val in c[:cidx]:
            res = res*val%MOD
        for k in range(100000):
            if bidx<=1 or cidx+1 >= num_c:
                break
            if b[bidx-1]*b[bidx-2] > c[cidx]*c[cidx+1]:
                break
            else:
                res *= c[cidx]
                res *= c[cidx+1]
                res = res%MOD
                res = res*pow(b[bidx-1],MOD-2,MOD)
                res = res*pow(b[bidx-2],MOD-2,MOD)
                res = res%MOD
                bidx -= 2
                cidx += 2
print(res%MOD)

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
        
        return


    if K%2==1 and len(Ap)==0:
        Am.sort()
        out=1
        for i in range(K):
            out*=Am[i]
            out%=10**7+1
        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:
mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))

m = []
p = []
zero = 0
for i in a:
    if i < 0:
        m.append(-i)
    elif i > 0:
        p.append(i)
    else:
        zero += 1

if n - k < zero:
    print(0)
    exit()

if n - k == zero:
    if len(m) % 2 == 1:
        print(0)
        exit()

if len(p) == 0 and k % 2 == 1:
    if zero >= 1:
        print(0)
    else:
        m.sort()
        ans = 1
        for i in range(k):
            ans *= m[i]
            ans %= mod
        ans = mod - ans
        print(ans % mod)
    exit()

m.sort(reverse=True)
p.sort(reverse=True)
nm = 0
np = 0
ans = 1
if k % 2 == 1:
    ans *= p[0]
    np += 1
lap = k // 2

while nm < len(m) - 1 and np < len(p) - 1 and lap > 0:
    lap -= 1
    i = m[nm] * m[nm + 1]
    j = p[np] * p[np + 1]
    if i > j:
        ans *= i
        ans %= mod
        nm += 2
    else:
        ans *= j
        ans %= mod
        np += 2

if lap > 0:
    if nm < len(m) - 1:
        for i in range(nm, nm + lap * 2):
            ans *= m[i]
            ans %= mod
    else:
        for i in range(np, np + lap * 2):
            ans *= p[i]
            ans %= mod

print(ans % mod)

Submission status: Wrong Answer

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

mod = 10**9 + 7


import collections

plus_list = collections.deque()
minus_list = collections.deque()

for a in A:
    if a > 0:
        plus_list.append(a)
    else:
        minus_list.append(a)

# print(plus_list)
# print(minus_list)

count = 0
ans = 1
while count < K:
    if K - count == 1:
        ans *= plus_list.popleft() % mod
        count += 1
    else:
        if not plus_list:
            if ans > 0 and (K - count) % 2 == 0:
                for i in range(K - count):
                    ans *= minus_list.pop() % mod
                    count += 1
            else:
                for i in range(K - count):
                    ans *= minus_list.popleft() % mod
                    count += 1
            continue

        if len(minus_list) < 2:
            for i in range(K - count):
                ans *= plus_list.popleft() % mod
                count += 1
            continue

        if plus_list[0] >= minus_list[-1] * minus_list[-2]:
            ans *= plus_list.popleft() % mod
            count += 1
        else:
            ans *= minus_list.pop() * minus_list.pop() % mod
            count += 2
print(ans % mod)

Submission status: Wrong Answer

Solution code:
import itertools
from functools import reduce
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = [int(_) for _ in input().split()]
C = [list(i) for i in itertools.combinations(A, K)]
res = [reduce(lambda x, y: x*y, j) for j in C]
ans = max(res)
if ans < 0:
  print(ans % MOD)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9 + 7
b_p = []
b_n = []
ab = []
for i in range(n):
    ab.append(abs(a[i]))
    if a[i] >= 0:
        b_p.append(a[i])
    else:
        b_n.append(a[i])
b_p = sorted(b_p,reverse=True)
b_n = sorted(b_n,reverse=True)
ab = sorted(ab)
ans = 1
i = 0
x = 0
y = 0
if k%2 == 1:
    if len(b_p) >= 1:
        ans *= b_p[0]
        x += 1
        i += 1
while i < k-1:
    i += 2
    if x < len(b_p)-1 and y < len(b_n)-1:
        if b_p[x]*b_p[x+1] > b_n[y]*b_n[y+1]:
            ans *= b_p[x]*b_p[x+1]
            ans %= mod
            x += 2
        else:
            ans *= b_n[y]*b_n[y+1]
            ans %= mod
            y += 2
    
    elif x < len(b_p)-1:
        ans *= b_p[x]*b_p[x+1]
        ans %= mod
        x += 2
    elif y < len(b_n)-1:
        ans *= b_n[y]*b_n[y+1]
        ans %= mod
        y += 2
    else:
        break
if i != k:
    if x < len(b_p):
        ans *= b_p[x]
        ans %= mod
    else:
        if 0 in b_p:
            ans = 0
        else:
            ans = 1
            for i in range(k):
                ans *= ab[i]
                ans %= mod
            ans *= -1
print(ans%mod)

Submission status: Wrong Answer

Solution code:
#                          JAI SHREE RAM

import math; from collections import *
import sys; from functools import reduce

# sys.setrecursionlimit(10**6)
def get_ints(): return map(int, input().strip().split())
def get_list(): return list(get_ints())
def get_string(): return list(input().strip().split())
def printxsp(*args): return print(*args, end="")
def printsp(*args): return print(*args, end=" ")

UGLYMOD = int(1e9)+7; SEXYMOD = 998244353; MAXN = int(1e5)

# sys.stdin=open("input.txt","r");sys.stdout=open("output.txt","w")

# for _testcases_ in range(int(input())):
n, k = get_ints()
li = get_list()
pos = []
neg = []
zeroes = 0
for i in li:
    if i < 0: neg.append(i)
    elif i > 0: pos.append(i)
    else: zeroes += 1
lengthOfPos, lengthOfNeg = len(pos), len(neg)
if lengthOfNeg + lengthOfPos < k :
    print("0")
elif (k - lengthOfPos) >= 0 and (k - lengthOfPos) & 1:
    if zeroes:
        print("0")
    else:
        try: ans = reduce(lambda x, y: (x*y) % UGLYMOD, pos)
        except: ans = 1
        neg.sort(reverse = True)
        # print(neg)
        for i in range(k-lengthOfPos):
            ans  = (ans * neg[i]) % UGLYMOD
        print(ans)
else:
    pos.sort(reverse = True); positionOfPos = 0
    neg.sort(); positionOfNeg = 0
    if lengthOfNeg & 1:
        neg.pop()
        lengthOfNeg -= 1
    ans = 1
    while k > 1:
        try: negpower = neg[positionOfNeg] * neg[positionOfNeg+1]
        except: negpower = -float('inf')
        try: pospower = pos[positionOfPos] * pos[positionOfPos+1]
        except: pospower = -float('inf')
        if pospower >= negpower:
            positionOfPos += 2
            ans = (ans * (pospower % UGLYMOD)) % UGLYMOD
        else:
            ans = (ans * (negpower % UGLYMOD)) % UGLYMOD
            positionOfNeg += 2
        k -= 2
    if k == 1:
        ans = (ans * pos[positionOfPos]) % UGLYMOD
    print(ans)







'''
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
THE LOGIC AND APPROACH IS MINE @luctivud ( UDIT GUPTA )
Link may be copy-pasted here if it's taken from other source.
DO NOT PLAGIARISE.
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
'''

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=1):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.node_size=len(ls)+1
                self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.node_size=int(input())
        else:
            self.node_size=inp_size
        self.edges,_=GI(self.node_size,self.node_size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.node_size=len(ls)+1
        self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def parent(self,x):
        return self.dfs(0,func=lambda pr,prv,nx,dist:pr,root_v=-1)
 
    def topological_sort(self,x):  # return topological sort of the tree
        tps=[]
        q=deque([x])
        v=[None]*self.node_size
        v[x]=0
        while q:
            c=q.popleft()
            tps.append(c)
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=0
        return tps
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.node_size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.node_size
        self.ETout=[-1]*self.node_size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def doubling_LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.depth=[None]*self.node_size
            self.depth=self.bfs(0,func=lambda pr,prv,nxt,dist:prv+1)
            self.par=self.bfs(0,func=lambda pr,prv,nxt,dist:pr)
            self.db=[self.par]
            for i in range(self.node_size.bit_length()):
                #show(self.db)
                self.db+=[[self.db[-1][self.db[-1][i]] for i in range(self.node_size)]]
            self.LCA_init_stat=True
        dx=self.depth[x]
        dy=self.depth[y]
        if dx>dy:
            dx,dy=dy,dx
        c=self.node_size.bit_length()
        while c>0:
            if dx+c<=dy:
                x=self.db[c][x]
                dx+=1<<c
            c>>=1
        
        if x==y:
            return x
        
        c=self.node_size.bit_length()
        while c>0:
            if self.db[c][x]!=self.db[c][y]:
                x=self.db[c][x]
                y=self.db[c][y]
            c>>=1
        
        return self.par[x]
        
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        #self.st=SegTree(self.node_size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
    def __str__(self):
        return  str(self.edges)
 
    def show(self):
        if all([all([d==1 for nd,d in e]) for e in self.edges]):
            print( [[nd for nd,d in e] for e in self.edges] )
        else:
            print(self)
 
    def dfs2(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        dfs_tr=[x]
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
                    dfs_tr+=nb,
        return v,dfs_tr

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    # return boundary index of r such that func({table[i]} =< x , i in [pos,r]
    def right_bound(self,pos,x):
        k=(self.size-pos).bit_length()
        for j in range(k)[::-1]:
            nx=pos+(1<<j)
            if nx<n and self.query(pos,nx+1)<=x:
                pos+=(1<<j)
        return pos
    
    # return boundary index of l such that func({table[i]} =< x , i in [l,pos]
    def left_bound(self,pos,x):
        k=pos.bit_length()
        for j in range(k)[::-1]:
            nx=pos-(1<<j)
            if 0<=nx and self.query(nx,pos+1)<=x:
                pos-=(1<<j)
        return pos

    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)

show_flg=False
show_flg=True

ans=0

#h,w,K=LI()
n,k=LI()
b=LI()
a=sorted(b)
b.sort(key=lambda x:abs(x))



pl,mn,zr=[],[],[]
for i in a:
    if i>0:
        pl+=i,
    elif i<0:
        mn+=i,
    else:
        zr+=i,
    
def maximize(b,k):
    p,m=0,0
    mn_p,mn_m=inf,inf
    rt=1
    for i in range(k):
        x=b.pop()
        if x>0:
            p+=1
            if mn_p>x:
                mn_p=x
                #show('mn_p',mn_p,x)
        elif x<0:
            m+=1
            if mn_m>x:
                mn_m=-x
                #show('mn_n',mn_m,x)
        rt*=x
        #rt%=mo
    #show(rt)
    if m%2==1:
        while b:
            x=b.pop()
            if x>0:
                #show('?',rt,rt//mn_m,mn_m,x)
                rt*=pow(-mn_m,mo-2,mo)
                #rt//=mn_m
                rt*=x
                rt%=mo
                return rt
            elif x<0 and p>0:
                rt*=pow(mn_p,mo-2,mo)
                #rt//=mn_p
                rt*=x
                rt%=mo
                return rt
    return rt

#M=maximize(b,k)
#show(M,(M-mo))

if k+len(zr)==n:
    al=1
    for i in pl:
        al*=i
        al%=mo
    for i in mn:
        al*=i
        al%=mo
    ans=max(0,al)
    st=0
elif k+len(zr)>n:
    ans=0
    st=1
elif k%2==1 and len(pl)==0: # minus case
    ans=1
    for i in range(k):
        x=b[i]
        ans*=x
        ans%=mo
    if len(zr)>0:
        ans=0
    st=2
else:
    ans=maximize(b,k)
    st=3


print(ans)

Submission status: Wrong Answer

Solution code:
import math
n,k=list(map(int,input().split()))
l=list(map(int,input().split()))
lul = 10**9 + 7
if n==1:
	print(l[0])
else:
	pos = []
	neg = []
	for i in range(n):
		if l[i]<0:
			neg.append(-1*l[i])
		else:
			pos.append(l[i])
	pos.sort(); pos=pos[::-1]
	neg.sort();
	temp = list(neg)
	neg = neg[::-1]
	v = 1
	for i in range(len(pos)):
		v=(v*pos[i])%lul
		pos[i] = v
	v = 1
	for i in range(len(neg)):
		v=(v*neg[i])%lul
		neg[i] = v
	v = 0
	a = -1*math.inf
	# print('math.inf',-1*math.inf)
	# print(pos)
	# print(neg)
	while True:
		if(v>k):
			break
		if(v<=len(neg) and (k-v)<=len(pos)):
			ans = 1
			if((v-1) >= 0):
				ans = (ans*neg[v-1])%lul
			if((k-v-1) >= 0):
				ans = (ans*pos[k-v-1])%lul
			a = max(ans,a)
		v+=2
	# print(a)
	if(k<=len(neg)):
		if k%2!=0 and a==(-1*math.inf):
			# print("yo",neg[k-1])
			v = 1
			for i in range(k):
				v = (v*-1*temp[i])%lul
			# print(v)
			a = max(a,v)
	# print(a)
	print(a%lul)