Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Constraints

1 \leq K \leq N \leq 2\times 10^5

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

The possible products of the three chosen elements are -24, -12, -8, and -6, so the maximum product is -6.

We print this value modulo (10^9+7), that is, 1000000001.

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

The possible products of the one chosen element are -1 and 1000000000, so the maximum product is 1000000000.

Sample Input 4

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

Sample Output 4

999983200

Be sure to print the product modulo (10^9+7).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort(key=lambda x:-abs(x))
mod=10**9+7


ans=1
flg=1
flgcnt=0
save=1
for i in range(k-1):
    now=A[i]
    if now <0:
        flg*=-1
        flgcnt+=1
    ans=ans*now%mod
    if i==k-3:
        save=ans

#print(ans,flg)
for i in range(k-1,n):
    now=A[i]
    if now >=0:
        lasflg=1
    else:
        lasflg=-1
    if flg*lasflg==1:
        print(ans*now%mod)
        break
else:
    if flgcnt==k-1 and k>=2:
        ans=save
        two=2
        for i in range(k-2,n):
            now=A[i]
            if now>=0:
                two-=1
                ans=ans*now%mod
            if two==0:
                print(ans)
                break
        else:
            ans=1
            for i in range(k):
                ans=ans*A[n-1-i]%mod
            print(ans)
            
    else:
        ans=1
        for i in range(k):
            ans=ans*A[n-1-i]%mod
        print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    def addans(i, ans):
        return ans * i % mod
    import sys
    import bisect
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    l = bisect.bisect_left(a, 0)
    r = bisect.bisect_right(a, 0)
    if n - k < r - l:
        print(0)
        return
    if r == n:
        ans = 1
        for i in range(k):
            ans = addans(a[-i - 1], ans)
        print(ans)
        return
    ans = 1
    minus = [0] * 3 + a[:l][::-1]
    plus = [0] * 3 + a[r:]
    if k % 2 == 1:
        ans = plus.pop()
        k -= 1
    m = minus.pop() * minus.pop()
    p = plus.pop() * plus.pop()
    for _ in range(k // 2):
        if p >= m:
            ans = addans(p, ans)
            p = plus.pop() * plus.pop()
        else:
            ans = addans(m, ans)
            m = minus.pop() * minus.pop()
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n,k = m()

a = l()

a.sort()

mina = []

pra = []

for i in range(n):
	if a[i] >= 0:
		pra.append(a[i])
	else:
		mina.append(a[i])

lp = len(pra)

lm = len(mina)
ans = 1
if lp == 0:
	if k % 2 != 0:
		for i in range(k):
			i = -(1+i)
			ans *= mina[i]
		print(ans % mod)
	else:
		for i in range(k):
			ans *= mina[i]
		print(ans % mod)
elif lp == 1:
	if n == k:
		mina.append(pra[0])
		mina.sort()
		for i in range(k):
			i = -(1+i)
			ans *= mina[i]
		print(ans % mod)
	else:
		if k % 2 == 0:
			for i in range(k):
				ans *= mina[i]
			print(ans % mod)
		else:
			ans *= pra[0] 
			for i in range(k-1):
				ans *= mina[i]
			print(ans % mod)
else:
	cp = lp-1
	cm = 0
	count = 0
	data = []
	
	while count < k:
		if cp != -1 and cm != lm:
			if abs(mina[cm]) <= pra[cp]:
				if cp == 0:
					if (k-lp) % 2 == 0:
						count += 1
						#ans *= pra[cp]
						data.append(pra[cp])
						cp -= 1
					else:
						count += 1
						#ans *= mina[cm]
						data.append(mina[cm])
						cm += 1

				else:
					count += 1
					#ans *= pra[cp]
					data.append(pra[cp])
					cp -= 1
			else:
				if cm == lm-1:
					if lm % 2 == 0:
						count += 1
						#ans *= mina[cm]
						data.append(mina[cm])
						cm += 1
					else:
						count += 1
						#ans *= pra[cp]
						data.append(pra[cp])
						cp -= 1


				else:
					count += 1
					#ans *= mina[cm]
					data.append(mina[cm])
					cm += 1
		elif cp != lp:
			#ans *= pra[cp]
			data.append(pra[cp])
			cp -= 1
			count += 1
		elif cm != lm:
			#ans *= mina[cm]
			data.append(mina[cm])
			cm += 1
			count += 1

		else:
			break

	data.sort()
	co = 0
	
	while co <= k:
		if k - co >= 2:
			if data[co] * data[co+1] >= 0:
				ans *= (data[co] * data[co+1]) % mod
				ans %= mod
				co += 2
			else:
				ans *= data[co]
				ans %= mod
				ans *= data[co+1]
				ans %= mod
				co += 2
		elif k - co == 1:
			ans *= data[co]
			ans %= mod
			co += 1
		else:
			break


		
	print(ans)

Submission status: Wrong Answer

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

        else:
            product *= right_product
            j -= 2
    return product

n,k=[int(x) for x in input().split()]
arr=[int(x) for x in input().split()]
print(max_product(arr,n,k)%1000000007)

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()

for i in range(K - 2, -1, -1):
    if K % 2 == 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 K % 2 == 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:
import sys

MOD = 10**9 + 7

def read_int():
    line = sys.stdin.readline().rstrip('\n')
    return int(line)

def read_int_list():
    line = sys.stdin.readline().rstrip('\n')
    return [int(e) for e in line.split(' ')]

def sign(n):
    if n > 0:
        return 1
    if n < 0:
        return -1
    return 0

def prod(A, K, add, remove):
    prod = 1
    for i in range(K):
        if i == remove:
            continue
        prod *= A[i]
        prod %= MOD
    if add != None:
        prod *= A[i]
        prod %= MOD
    return prod

N, K = read_int_list()
A = read_int_list()

A.sort(key=lambda i: -abs(i))

last_plus = None
last_minus = None
sig = 1
for i in range(K):
    sig *= sign(A[i])
    if A[i] > 0:
        last_plus = i
    if A[i] < 0:
        last_minus = i
remove = None
add = None
if sig < 0:
    for i in range(K, N):
        if A[i] > 0 and last_minus != None:
            remove = last_minus
            add = i
            sig = 1
            break
        elif A[i] < 0 and last_plus != None:
            remove = last_plus
            add = i
            sig = 1
            break
        elif A[i] == 0:
            sig = 0
            break

if sig == 0:
    print(0)
elif sig > 0:
    ap = prod(A, K, add, remove)
    print(ap)
else:
    ap = prod(A[::-1], K, add, remove)
    print(ap)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
res=1
cnt=0
p=1000000007
while 1:
  #print(a,res)
  if cnt==k or len(a)==0:
    break
  if len(a)==1:
    res = max(res, res*a[0] % p)
    break
  if a[-1] < 0:
    res *= a[-1]
    res%=p
    cnt += 1
    a.pop(-1)
    continue
  tmp_a = res * a[0]*a[1] % p
  tmp_b = res * a[-1] % p
  if tmp_a > tmp_b and cnt < k-1:
    res = tmp_a
    cnt += 2
    a.pop(0)
    a.pop(0)
  else:
    res = tmp_b
    cnt += 1
    a.pop(-1)
print(res%p)

Submission status: Wrong Answer

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

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

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

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

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

    if len(C)%2==1 and Z!=[]:
        print(0)
    else:
        print(ANS)
    sys.exit()

if K>len(B)+len(C):
    print(0)
    sys.exit()

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

    if Z==[] and K%2==0:
        print(ANS)
    elif Z==[] and K%2==1:
        print(-ANS%mod)
    elif K%2==1:
        print(0)
    else:
        print(ANS)

    sys.exit()

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

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

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

    print(S%mod)

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

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

        ind=K-len(B)

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

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

        ind=K-len(B)+1
        

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

    print(S%mod)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
mod=10**9+7
P=1
if N==K:
  for i in range(N):
    P=P*A[i]%mod
  print(P)
  exit()
B=[]
C=False
for i in range(N):
  if A[i]:
    B.append(A[i])
  else:
    C=True
if len(B)<K:
  print(0)
  exit()
B.sort(reverse=True,key=lambda x:abs(x))
Y=0
for i in range(K):
  if B[i]<0:
    Y+=1
  P=P*B[i]%mod
if Y&1==0:
  print(P)
  exit()
if Y==K:
  B.sort()
  if B[-1]<0:
    if C:
      print(0)
      exit()
    P=1
    for i in range(K):
      P=P*B[-(i+1)]%mod
    print(P)
    exit()
  P=P*pow(B[0],mod-2,mod)*B[-1]%mod
  print(P)
  exit()
Y,Z=0,0
for i in range(K,len(B)):
  if B[i]<0:
    Y=B[i]
    break
for i in range(K,len(B)):
  if B[i]>0:
    Z=B[i]
    break
if Y==Z==0:
  if C:
    print(0)
  else:
    print(P)
  exit()
if Y==0:
  for i in range(K-1,-1,-1):
    if B[i]<0:
      P=P*pow(B[i],mod-2,mod)
      break
    if i==0:
      if C:
        print(0)
      else:
        print(P)
      exit()
  print(P*Z%mod)
elif Z==0:
  for i in range(K-1,-1,-1):
    if B[i]>0:
      P=P*pow(B[i],mod-2,mod)
      break
    if i==0:
      if C:
        print(0)
      else:
        print(P)
      exit()
  print(P*Y%mod)
if Y==0 or Z==0:
  exit()
V,W=0,0
for i in range(K-1,-1,-1):
  if B[i]<0:
    V=B[i]
    break
for i in range(K-1,-1,-1):
  if B[i]>0:
    W=B[i]
    break
if Y*V>Z*W:
  print(P*Y*pow(W,mod-2,mod)%mod)
else:
  print(P*Z*pow(V,mod-2,mod)%mod)

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:
            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]:
                    c*=Ap.pop()
                    c*=Ap.pop()
                else:
                    c*=Am.pop()
                    c*=Am.pop()
                K-=2
            elif len(Ap)==1 and len(Am)>=2:
                if Ap[-1]>Am[-1]*Am[-2]:
                    c*=Ap.pop()
                    K-=1
                else:
                    c*=Am.pop()
                    c*=Am.pop()
                    K-=2
            else:
                c*=Am.pop()
                c*=Am.pop()
                K-=2
        else:
            c*=Ap.pop()
            K-=1
        c%=mod
print(c%mod)

Submission status: Wrong Answer

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

if max(a) < 0:
    a.sort()
    ans = 1
    if k % 2 == 0:
        for e in a[:k]:
            ans *= e
            ans %= mod
    else:
        for e in a[-k:]:
            ans *= e
            ans %= mod

    print(ans)

else:
    neg = []
    pos = []
    for e in a:
        if e < 0:
            neg.append(e)
        else:
            pos.append(e)

    neg.sort()
    pos.sort(reverse=True)

    ans = 1
    if k % 2:
        ans *= pos.pop(0)
        k -= 1

    nums = [e1 * e2 for e1, e2 in zip(neg[::2], neg[1::2])]
    nums += [e1 * e2 for e1, e2 in zip(pos[::2], pos[1::2])]

    nums.sort(reverse=True)
    for e in nums[:k//2]:
        ans *= e
        ans %= mod

    print(ans)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N,K = LI()
    A = LI()

    ans = 1
    ma = max(A)
    if ma <= 0 and K % 2:
        x = sorted(A,reverse=True)
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return

    x = sorted(A, key=lambda x: abs(x), reverse=True)
    m = 0
    for i in range(K):
        ans = (ans * x[i]) % MOD
        if x[i] < 0 :m += 1

    if K == N or m % 2 == 0:
        print(ans)
        return
    if x[K] == 0:
        print(0)
        return
    else:
        if m == K:
            ans = (ans * pow(x[K-1],MOD-2,MOD) * max(x[K:])) % MOD

        else:
            for i in range(K-1,-1,-1):
                if x[i] * x[K] < 0:
                    ans = (ans * pow(x[i],MOD-2,MOD) * x[K]) % MOD
                    break
        print(ans)
        return



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

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

    A.sort(key=lambda a: abs(a), reverse=True)
    A_pos = []
    A_neg = []
    for a in A:
        if a >= 0:
            A_pos.append(a)
        else:
            A_neg.append(-a)
    pos_last = 0.1
    neg_last = 0.1
    ans = 1
    cnt = 0
    for a in A[:K]:
        if a >= 0:
            pos_last = a
            ans = (ans * a)%mod
        else:
            neg_last = -a
            ans = (ans * a)%mod
            cnt += 1
    if cnt%2 == 0:
        print(ans)
        exit()

    if pos_last == 0.1:
        pos_add = -1
        for i in range(K, N):
            if A[i] >= 0:
                pos_add = A[i]
                break
        if pos_add == -1:
            ans = 1
            A.reverse()
            for a in A[:K]:
                ans = (ans * a)%mod
            print(ans)
            exit()
        else:
            neg_del = neg_last
            if neg_del == 0.1:
                print(ans)
            else:
                print(((-ans) * pos_add * pow(neg_del, mod-2, mod))%mod)
    else:
        if neg_last == 0.1:
            neg_add = 1
            for i in range(K, N):
                if A[i] < 0:
                    neg_add = -A[i]
                    break
            if neg_add == 1:
                assert False
            else:
                print(((-ans) * neg_add * pow(pos_last, mod - 2, mod)) % mod)
        else:
            pos_add = -1
            for i in range(K, N):
                if A[i] >= 0:
                    pos_add = A[i]
                    break
            neg_add = 1
            for i in range(K, N):
                if A[i] < 0:
                    neg_add = -A[i]
                    break
            if pos_add == -1 and neg_add == 1:
                print(ans)
            elif pos_add == -1:
                print(((-ans) * neg_add * pow(pos_last, mod - 2, mod)) % mod)
            elif neg_add == 1:
                print(((-ans) * pos_add * pow(neg_last, mod - 2, mod)) % mod)
            else:
                if pos_add * pos_last > neg_add * neg_last:
                    print(((-ans) * pos_add * pow(neg_last, mod - 2, mod)) % mod)
                else:
                    print(((-ans) * pos_add * pow(neg_last, mod - 2, mod)) % mod)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
import sys
from functools import reduce
input = sys.stdin.readline
N,K = map(int,input().split())
A = list(map(int,input().split()))

A.sort()
minus = [a for a in A if a < 0][::-1]
plus = [a for a in A if a > 0][::-1]

prod = lambda x,y : ((x*y) % MOD)

if K % 2 == 1 and len(plus) == 0:
    if 0 in A:
        print(0)
    else:
        ans = reduce(prod,minus[:K])
        print(ans % MOD)
    exit()

ans = 1
if K % 2 == 1:
    ans *= plus[0]
    plus2 = [p*q for p,q in zip(plus[1::2],plus[2::2])]
    minus2 = [p*q for p,q in zip(minus[::-1][::2],minus[::-1][1::2])]
    cand = sorted((plus2 + minus2),reverse=True)
    ans *= reduce(prod,cand[:K//2],1)
    ans %= MOD
else:
    plus2 = [p*q for p,q in zip(plus[::2],plus[1::2])]
    minus2 = [p*q for p,q in zip(minus[::-1][::2],minus[::-1][1::2])]
    cand = sorted((plus2 + minus2),reverse=True)
    ans *= reduce(prod,cand[:K//2],1)
    ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,K=mi()
    A=list(mi())
    MOD = 10**9+7

    B = []
    zeros = 0
    for a in A:
        if a == 0:
            zeros += 1
            continue

        is_neg = a < 0
        B.append((abs(a),is_neg))
        

    if N-zeros < K:
        print(0)
        exit()

    NB = len(B)
    v = [(0,0)] * (NB+1) # (mult, neg_count)
    v[0] = (1,0)
    B.sort()
    for i in range(NB):
        b,is_neg = B[i]
        v[i+1] = (v[i][0] * b % MOD, v[i][1] + is_neg)
    
    j = 0
    ans = 0
    # print(v)
    ans_is_neg = False
    while j+K<=NB:
        mult = (v[j+K][0]//v[j][0]) % MOD
        if (v[j+K][1]-v[j][1]) % 2 == 1: # is negative sum
            mult *= -1
            if j == 0:
                ans_is_neg = True
                ans = mult%MOD
                # print("a",ans)
            elif ans_is_neg:
                ans = max(mult%MOD,ans)
                # print("b",ans)
        else:
            if ans_is_neg:
                ans = mult%MOD
                # print("c",ans)
            else:
                ans = max(mult%MOD,ans)
                # print("d",ans)
            
            ans_is_neg = False
                

        j += 1



    print(ans)


    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

n,k = map(int,input().split())
A = list(map(int,input().split()))
B = [0,0,0]
C = [[],[]]
D = [[abs(A[i]), A[i]] for i in range(n)]
D.sort(reverse=True)
ans = 1
mod = 10**9+7
for i in range(n):
    if A[i] > 0:
        B[0] += 1
        C[0].append(A[i])
    elif A[i] < 0:
        B[1] += 1
        C[1].append(-A[i])
    else:
        B[2] += 1
C[0].sort()
C[1].sort()

if k == 1:
    print(max(A))
elif k == 2:
    ans = 1
    if B[0] >= 2:
        ans = max(ans, C[0][0]*C[0][1])
    if B[1] >= 2:
        ans = max(ans, C[1][0]*C[1][1])
    if B[2] > 0:
        ans = max(ans, 0)
    print(ans%mod)

else:

    if (k%2==1 and B[0]==0) or (k%2==0 and k==n and B[1]%2==0):
        if B[2] > 0:
            print(0)
        else:
            D.sort()
            for i in range(k):
                ans = (ans * D[i][1]) % mod
            print(ans)
    elif B[0]+(B[1]//2)*2 < k and B[2] > 0:
        print(0)
    else:
        ind = 0
        for i in range(k-3):
            ans = (ans * D[ind][1]) % mod
            ind += 1
        if ans < 0:
            K = []
            L = ["001","100","010","111"]
            for i in range(len(L)):
                mm = 1
                for j in range(3):
                    while ind < n and ((D[ind][1]<0 and L[j]=="0") or(D[ind][1]>=0 and L[j]=="1")):
                        ind += 1
                    if ind == n:
                        break
                    else:
                        mm *= D[ind][0]
                        K.append(mm)
                        ind += 1
        else:
            K = []
            L = ["101","110","011","000"]
            for i in range(len(L)):
                mm = 1
                for j in range(3):
                    while ind < n and ((D[ind][1]<0 and L[j]=="0") or(D[ind][1]>=0 and L[j]=="1")):
                        ind += 1
                    if ind == n:
                        break
                    else:
                        mm *= D[ind][0]
                        K.append(mm)
                        ind += 1
        print((abs(ans) * max(K)) % mod)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


# mod m におけるaの逆元
def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m

    # 負の場合は m を足して正の数にする
    if u < 0:
        u += m
    return u


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

    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
        print(ans)
        return

    B = []
    n_plus = 0
    for a in A:
        if a >= 0:
            B.append((a, True))
            n_plus += 1
        else:
            B.append((-a, False))

    if n_plus == 0:
        A.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD
        print(ans)
        return

    B.sort(key=lambda x: x[0], reverse=True)
    cnt = 0
    prev_minus = None
    prev_plus = None
    ans = 1
    for i in range(K):
        b, flag = B[i]

        ans *= b
        ans %= MOD

        if flag:
            prev_plus = b
        else:
            cnt += 1
            prev_minus = b

    if cnt % 2 == 0 or ans == 0:
        print(ans)
        return

    if N == K:
        print(-ans)
        return

    next_minus = None
    next_plus = None
    for i in range(K, N):
        b, flag = B[i]
        if flag:
            if next_plus is None:
                next_plus = b
        else:
            if next_minus is None:
                next_minus = b

    if next_plus is not None and prev_minus is not None:
        inv = modinv(prev_minus, MOD)
        tmp1 = inv * ans
        tmp1 %= MOD
        tmp1 *= next_plus
        tmp1 %= MOD
        mult1 = next_plus / prev_minus
    else:
        mult1 = -INF
        tmp1 = -INF

    if next_minus is not None and prev_plus is not None:
        inv = modinv(prev_plus, MOD)
        tmp2 = inv * ans
        tmp2 %= MOD
        tmp2 *= next_minus
        tmp2 %= MOD
        mult2 = next_minus / prev_plus
    else:
        mult2 = -INF
        tmp2 = -INF

    if mult1 > mult2:
        print(tmp1)
    else:
        print(tmp2)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineering College

'''
from os import path
import sys
from functools import cmp_to_key as ctk
from collections import deque,defaultdict as dd 
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())
abc='abcdefghijklmnopqrstuvwxyz'
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]

def bo(i):
    return ord(i)-ord('a')

file = 0

def solve():
    



    # for _ in range(ii()):

    n,k=mi()
    a=li()
    pos,neg=[],[]
    zero=0
    for i in a:
        if i<0:
            neg.append(i)
        if i>0:
            pos.append(i)
        if i==0:
            zero+=1

    if k>len(pos)+len(neg):
        print(0)
        exit(0)
    
    if len(pos)==0 and k%2:
        if zero:
            print(0)
        else:
            neg.sort(reverse=True)
            ans1=1
            for i in range(k):
                ans1*=neg[i]
                ans1%=mod
            print(ans1)
        exit(0)
    ans=[]

    for i in pos:
        ans.append([i,0])
    for i in neg:
        ans.append([abs(i),1])
    ans.sort(reverse=True)
    f=-1
    f1=-1
    c=0
    for i in range(k):
        if ans[i][1]:
            c+=1
            f=i
        else:
            f1=i
    if c%2:
        if len(ans)==k:
            print(0)


        else:
            ans1=1
            for i in range(k):
                if i==f or i==f1:
                    continue
                ans1*=ans[i][0]
                ans1%=mod

            if(f1!=-1):
                f1=ans[f1][0]
            f=ans[f][0]
            # print(f,f1)
            f3,f4=-1,-1
            for i in range(k,len(ans)):
                if ans[i][1] and f3==-1:
                    f*=ans[i][0]
                    f3=1
                if ans[i][1]==0 and f4==-1:
                    if f1==-1:
                        f1=ans[i][0]
                    else:
                        f1*=ans[i][0]
                        f4=1
                if f3!=-1 and f4!=-1:
                    break
            if f4==-1:
                ans1*=f
                ans1%=mod
            elif(f3==-1):
                ans1*=f1
                ans1%=mod
            elif(f>f1):
                ans1*=f
                ans1%=mod
            else:
                ans1*=f1
                ans1%=mod
            print(ans1)

    else:
        ans1=1
        for i in range(k):
            ans1*=ans[i][0]
            ans1%=mod
        print(ans1)

























  
















if __name__ =="__main__":

    if(file):

        if path.exists('input1.txt'):
            sys.stdin=open('input1.txt', 'r')
            sys.stdout=open('output1.txt','w')
        else:
            input=sys.stdin.readline
    solve()