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())
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
num_b = len(b)
num_c = len(c)
res = 1
if N==num_c and K%2==1:
    c = sorted(c)
    for val in c[:K]:
        res = res*val%MOD
    res = -res%MOD
else:
    d = sorted(d,reverse=True)
    for val in d[:K]:
        res = res*val%MOD
    if K > len(d):
        res = 0
print(res%MOD)

Submission status: Wrong Answer

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

if max(a)<0:
  if k%2==0:
    a.sort()
    ans=1
    for i in a[:k]:
      ans*=i
      ans%=mod
    print(ans)
  else:
    a.sort(reverse=1)
    ans=1
    for i in a[:k]:
      ans*=i
      ans%=mod
    print(ans)
  exit()
if a.count(0)>n-k:exit(print(0))

p=[]
m=[]
for i in a:
  if i<0:m.append(i)
  elif i>0:p.append(i)
h=[]
for i in p:h.append((i*i,i,1))
for _ in range(a.count(0)):h.append((0,0,1))
m.sort()
if len(m)%2==1:m=m[:-1]
for i in range(0,len(m),2):
  t=m[i]*m[i+1]
  h.append((t,t,2))
h.sort(reverse=1)
ans=1
for _,t,c in h:
  if c>k:continue
  k-=c
  ans*=t
  ans%=mod
print(ans)

Submission status: Wrong Answer

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

if max(a)<0:
  if k%2==0:
    a.sort()
    ans=1
    for i in a[:k]:
      ans*=i
      ans%=mod
    print(ans)
  else:
    a.sort(reverse=1)
    ans=1
    for i in a[:k]:
      ans*=i
      ans%=mod
    print(ans)
  exit()
if a.count(0)>n-k:exit(print(0))

p=[]
m=[]
for i in a:
  if i<0:m.append(i)
  elif i>0:p.append(i)
h=[]
for i in p:h.append((i*i,i,1))
m.sort()
if len(m)%2==1:m=m[:-1]
for i in range(0,len(m),2):
  t=m[i]*m[i+1]
  h.append((t,t,2))
h.sort(reverse=1)
ans=1
for _,t,c in h:
  if c>k:continue
  k-=c
  ans*=t
  ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    if n == k:
        ans = a[0]
        for i in a[1:]:
            ans *= i
            ans %= mod
        print(ans)
        return
    mi = []
    ma = []
    a.sort()
    for ai in a:
        if ai <= 0:
            heappush(mi, ai)
        else:
            heappush(ma, -ai)
    if not ma:
        ans = 1
        if k & 1:
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
        else:
            for i in range(k):
                ans *= a[i]
                ans %= mod
        print(ans)
        return
    ans = 1
    l = []
    t = 0
    for _ in range(k - 1):
        if len(mi) <= 1:
            if len(ma) <= 1: continue
            ans *= -ma[0]
            ans %= mod
            heappop(ma)
        else:
            if len(ma) <= 1:
                ans *= mi[0]
                ans %= mod
                heappop(mi)
                t += 1
            else:
                x = mi[0]
                y = -ma[0]
                if abs(x) <= abs(y):
                    ans *= y
                    heappop(ma)
                    ans %= mod
                else:
                    ans *= x
                    heappop(mi)
                    ans %= mod
                    t += 1
    if (t & 1 and mi) or not ma:
        ans *= mi[0]
    else:
        ans *= -ma[0]
    print(ans%mod)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
MOD = 1000000000 + 7
def maxProductSubarrayOfSizeK(A, n, k): 
  
    # sorting given input array 
    A.sort() 
  
    # variable to store final product of  
    # all element of sub-sequence of size k 
    product = 1
  
    # CASE I 
    # If max element is 0 and 
    # k is odd then max product will be 0 
    if (A[n - 1] == 0 and (k & 1)): 
        return 0
  
    # CASE II 
    # If all elements are negative and 
    # k is odd then max product will be 
    # product of rightmost-subarray of size k 
    if (A[n - 1] <= 0 and (k & 1)) : 
        for i in range(n - 1, n - k + 1, -1): 
            product = product*A[i]%MOD 
        return product 
  
    # else 
    # i is current left pointer index 
    i = 0
  
    # j is current right pointer index 
    j = n - 1
  
    # CASE III 
    # if k is odd and rightmost element in 
    # sorted array is positive then it 
    # must come in subsequence 
    # Multiplying A[j] with product and 
    # correspondingly changing j 
    if (k & 1): 
        product =product*A[j]%MOD 
        j-= 1
        k-=1
  
    # CASE IV 
    # Now k is even. So, Now we deal with pairs 
    # Each time a pair is multiplied to product 
    # ie.. two elements are added to subsequence  
    # each time. Effectively k becomes half 
    # Hence, k >>= 1 means k /= 2 
    k >>= 1
  
    # Now finding k corresponding pairs to get 
    # maximum possible value of product 
    for itr in range( k) : 
  
        # product from left pointers 
        left_product = A[i] * A[i + 1] %MOD
  
        # product from right pointers 
        right_product = A[j] * A[j - 1] %MOD
  
        # Taking the max product from two  
        # choices. Correspondingly changing 
        # the pointer's position 
        if (left_product > right_product) : 
            product *= left_product %MOD
            i += 2
          
        else : 
            product *= right_product %MOD
            j -= 2
  
    # Finally return product 
    return product %MOD
n,k = map(int,input().split())
L = list(map(int,input().split()))
print(maxProductSubarrayOfSizeK(L,n,k))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
S = A
ls1 = S[0:k]
ls2 = S[::-1][0:k]
mod = (10**9)+7
now1 = 1
now2 = 1
c1 = 0
c2 = 0
for i in range(len(ls1)):
    if ls1[i] == 0:
        now1 *= ls1[i]
        break
    else:
        now1 *= ls1[i]
        if now1 < 0:
            now1 = mod -(now1%mod)
            c1 += 1
        else:
            now1 %= mod
for i in range(len(ls2)):
    if ls2[i] == 0:
        now2 *= ls2[i]
        break
    else:
        now2 *= ls2[i]
        if now2 < 0:
            now2 = mod - (now2%mod)
            c2 += 1
        else:
            now2 %= mod
if c1 %2 == 1:
    now1 = -now1
if c2 %2 == 1:
    now2 = -now2
K = max(now1,now2)
print(K%mod)

Submission status: Wrong Answer

Solution code:
M=10**9+7
n,k,*a=map(int,open(0).read().split())
x,*y=[],
for i in a:
    if i>0:x+=i,
    if i<0:y+=i,
x.sort(reverse=1)
y.sort(reverse=1)
if len(x)+len(y)<k or len(x)<k and (k-len(x))%2 and len(x)+len(y)<n:
    exit(print(0))
if len(x)<k and (k-len(x))%2:
    c=1
    for i in x+y[:k-len(x)]:
        c=c*i%M
    exit(print(c))
y=[-i for i in y]
x=x[:k]
i=len(x)
if len(x)<k:
    j=k-i
    x+=y[:j]
    y=y[j:]
y=y[::-1]
while i>1 and len(y)>1:
    if x[i-1]*x[i-2]<y[-1]*y[-2]:
        x[i-1],x[i-2]=y.pop(),y.pop()
        i-=2
c=1
for i in x:
    c=c*i%M
print(c)

Submission status: Wrong Answer

Solution code:
def main():
    mod = 10**9+7
    n,k = map(int,input().split())
    arr = list(map(int,input().split()))
    pos = []
    neg = []
    for i in arr:
        if i > 0:
            pos.append(i)
        elif i < 0:
            neg.append(-i)

    prod = 1
    pos.sort()
    neg.sort()
    while pos and neg and k > 0:
        if pos[-1] >= neg[-1]:
            prod *= pos.pop()
            k -= 1
        elif len(neg) >= 2 and k >= 2:
            prod *= neg.pop()
            prod *= neg.pop()
            k -= 2
        elif pos:
            prod *= pos.pop()
            k -= 1

        prod %= mod

    while k > 0 and pos:
        prod *= pos.pop()
        k -= 1
        prod %= mod

    if k > 0:
        if k%2 == 0:
            while neg and k > 0:
                prod *= neg.pop()
                k -= 1
                prod %= mod
        else:
            while neg and k > 0:
                prod *= -neg.pop(0)
                k -= 1
                prod %= mod

    print(prod)


main()

Submission status: Wrong Answer

Solution code:
# Python 3 code to find maximum possible 
# product of sub-sequence of size k from 
# given array of n integers 

# Required function 
def maxProductSubarrayOfSizeK(A, n, k):
    # sorting given input array
    A.sort()

    # variable to store final product of
    # all element of sub-sequence of size k
    product = 1

    # CASE I
    # If max element is 0 and
    # k is odd then max product will be 0
    if (A[n - 1] == 0 and (k & 1)):
        return 0

    # CASE II
    # If all elements are negative and
    # k is odd then max product will be
    # product of rightmost-subarray of size k
    if (A[n - 1] <= 0 and (k & 1)):
        for i in range(n - 1, n - k + 1, -1):
            product *= A[i]
        return product

    # else
    # i is current left pointer index
    i = 0

    # j is current right pointer index
    j = n - 1

    # CASE III
    # if k is odd and rightmost element in
    # sorted array is positive then it
    # must come in subsequence
    # Multiplying A[j] with product and
    # correspondingly changing j
    if (k & 1):
        product *= A[j]
        j -= 1
        k -= 1

    # CASE IV
    # Now k is even. So, Now we deal with pairs
    # Each time a pair is multiplied to product
    # ie.. two elements are added to subsequence
    # each time. Effectively k becomes half
    # Hence, k >>= 1 means k /= 2
    k >>= 1

    # Now finding k corresponding pairs to get
    # maximum possible value of product
    for itr in range(k):

        # product from left pointers
        left_product = A[i] * A[i + 1]

        # product from right pointers
        right_product = A[j] * A[j - 1]

        # Taking the max product from two
        # choices. Correspondingly changing
        # the pointer's position
        if (left_product > right_product):
            product *= left_product
            i += 2

        else:
            product *= right_product
            j -= 2

    # Finally return product
    return product


# Driver Code
if __name__ == "__main__":
    mod= 10**9 +7
    n,k= map(int,input().split())
    A = [int(x) for x in input().split()]

    print(maxProductSubarrayOfSizeK(A, n, k)%mod)

Submission status: Wrong Answer

Solution code:
from sys import exit
MOD = 10**9+7
n, k = map(int, input().split())
b = list(map(int, input().split()))
a = []
if n == k:
	ans = 1
	for x in b:
		ans *= x
		ans %= MOD
	print(ans)
	exit()
for x in b:
	if x != 0:
		a.append(x)
if len(a) < k:
	print(0)
	exit()

a.sort(key=lambda x: -abs(x))
ans = 1
minus = 0
for i in range(k):
	ans *= a[i]
	ans %= MOD
	if a[i] < 0:
		minus ^= 1
if minus == 0:
	print(ans)
	exit()

if len(a) == k:
	if len(a) < n:
		print(0)
		exit()

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

else:
	for i in range(k-1, -1, -1):
		if a[i] > 0:
			ans *= pow(a[i], MOD-2, MOD)
			ans *= a[k]
			ans %= MOD
			print(ans)
			exit()
	for i in range(k+1, len(a)):
		if a[i] > 0:
			ans *= pow(a[k-1], MOD-2, MOD)
			ans *= a[i]
			ans %= MOD
			print(ans)
			exit()
	if len(a) < n:
		print(0)
		exit()
	ans = 1
	for i in range(k):
		ans *= a[-i-1]
		ans %= MOD
	print(ans)
	exit()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
k = K // 2
hu = [1]
sei = [1]
for i in range(1,K+1):
    p = i - 1
    q = N - i
    hu.append(hu[p]*A[p])
    sei.append(sei[p]*A[q])
ans = 0
for i in range(k+1):
    x = 2*i
    y = K - x
    ans = max(ans,hu[x]*sei[y])
ans = ans % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import io
import os
from heapq import merge

input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

MOD = 10 ** 9 + 7


def solve(N, K, A):
    assert 1 <= K <= len(A)
    A.sort()
    neg = [-x for x in A if x < 0][::-1]  # abs value only
    nonneg = [x for x in A if x >= 0]

    # Get product of the K smallest by absolute value
    # If there are no achievable nonneg products, then this will be the smallest negative product
    bestNeg = 1
    for i, x in enumerate(merge(neg, nonneg)):
        bestNeg *= x
        if i >= K - 1:
            break
    bestNeg = -bestNeg % MOD

    def getBestNonNeg(K):
        ans = 1
        if K % 2 == 1:
            # Num neg must be even, so we need an odd number of nonneg. Always take the highest nonneg
            if not nonneg:
                return None
            ans = nonneg.pop() % MOD
            K -= 1
        while K >= 2 and len(nonneg) >= 2 and len(neg) >= 2:
            if nonneg[-1] * nonneg[-2] < neg[-1] * neg[-2]:  # Take larger
                ans = (ans * neg.pop() * neg.pop()) % MOD
            else:
                ans = (ans * nonneg.pop() * nonneg.pop()) % MOD
            K -= 2
        while K >= 2 and len(neg) >= 2:
            ans = (ans * neg.pop() * neg.pop()) % MOD
            K -= 2
        while K >= 2 and len(nonneg) >= 2:
            ans = (ans * nonneg.pop() * nonneg.pop()) % MOD
            K -= 2
        if K == 0:
            return ans
        return None

    # Make largest nonnegative
    ans = getBestNonNeg(K)
    if ans is not None:
        return ans
    # Answer is negative
    return bestNeg


if False:
    from itertools import combinations
    import random

    random.seed(0)
    for t in range(10000000):
        N = random.randint(1, 10)
        A = [random.randint(-N, N) for i in range(N)]
        K = random.randint(1, N)
        ans = solve(N, K, A)
        expected = float("-inf")
        for combo in combinations(A, r=K):
            prod = 1
            for x in combo:
                prod *= x
            expected = max(expected, prod)
        print(N, K, A, ans, expected)
        assert ans == (expected % MOD)

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
print(solve(N, K, A))

Submission status: Time Limit Exceeded

Solution code:
from heapq import merge


MOD = 10 ** 9 + 7


def solve(N, K, A):
    assert 1 <= K <= len(A)
    A.sort()
    neg = [-x for x in A if x < 0][::-1]  # abs value only
    nonneg = [x for x in A if x >= 0]

    # Get product of the K smallest by absolute value
    # If there are no achievable nonneg products, then this will be the smallest negative product
    bestNeg = 1
    for i, x in enumerate(merge(neg, nonneg)):
        bestNeg *= x
        if i >= K - 1:
            break
    bestNeg = -bestNeg % MOD

    def getBestNonNeg(K):
        ans = 1
        if K % 2 == 1:
            # Num neg must be even, so we need an odd number of nonneg. Always take the highest nonneg
            if not nonneg:
                return None
            ans = nonneg.pop() % MOD
            K -= 1
        while K >= 2 and len(nonneg) >= 2 and len(neg) >= 2:
            if nonneg[-1] * nonneg[-2] < neg[-1] * neg[-2]:  # Take larger
                ans = (ans * neg.pop() * neg.pop()) % MOD
            else:
                ans = (ans * nonneg.pop() * nonneg.pop()) % MOD
            K -= 2
        while K >= 2 and len(neg) >= 2:
            ans = (ans * neg.pop() * neg.pop()) % MOD
            K -= 2
        while K >= 2 and len(nonneg) >= 2:
            ans = (ans * nonneg.pop() * nonneg.pop()) % MOD
            K -= 2
        if K == 0:
            return ans
        return None

    # Make largest nonnegative
    ans = getBestNonNeg(K)
    if ans is not None:
        return ans
    # Answer is negative
    return bestNeg


if False:
    from itertools import combinations
    import random

    random.seed(0)
    for t in range(10000000):
        N = random.randint(1, 10)
        A = [random.randint(-N, N) for i in range(N)]
        K = random.randint(1, N)
        ans = solve(N, K, A)
        expected = float("-inf")
        for combo in combinations(A, r=K):
            prod = 1
            for x in combo:
                prod *= x
            expected = max(expected, prod)
        print(N, K, A, ans, expected)
        assert ans == (expected % MOD)

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
print(solve(N, K, A))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
def multiplyList(myList):
    result = 1
    for x in myList:
        result = result * x
    return result

details = list(map(int, input().split()))
N = details[0]
K = details[1]
counter = 0

numbers = list(map(int, input().split()))
for numbers in combinations(numbers, K):
    current = multiplyList(numbers)
    if current > counter:
        counter = current
    elif counter == 0:
        counter = current
print(counter % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from math import log
mod = int(1e9) + 7
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
m, ok = 0, 0

def sign(v):
    if v == 0:
        return 0
    return 1 if v > 0 else -1

for i in range(k + 1):
    c = 1
    sm = 0
    sgn = 1
    for j in range(i):
        c = c * a[j] % mod
        sgn *= sign(a[j])
        if a[j] != 0:
            sm += log(abs(a[j]))
    for j in range(k - i):
        c = c * a[n - j - 1] % mod
        sgn *= sign(a[n - j - 1])
        if a[n - j - 1] != 0:
            sm += log(abs(a[n - j - 1]))
    if not ok:
        m = (sgn * sm, c)
        ok = 1
    else:
        m = max(m, (sgn * sm, c))
    
print(m[1])

Submission status: Time Limit Exceeded

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

if N==K:
  ans0 = 1
  for a in A[0:N]:
    ans0 *= a
    ans0 %= MOD
  print(ans0)
  exit()
A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 *= a
    ans1 %= MOD
  print(ans1)
  exit()

A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]

ansA = 1
for a in A[0:K]:
  ansA *= a
  ansA %= MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()

while ansA>0:
  ansA-=MOD

B1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]

if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
if not Bp:Bp.insert(0,B1[-1])
if not Bm:Bm.insert(0,B1[0])
  
#print(Bp,Bm,B2)

B1.remove(Bp[-1])
B1.append(min(B2[0],0))
#print(B1)
ansB = 1
for a in B1[0:K]:
  ansB *= a
#  ansB %= MOD

C1=A[0:K]
C1.remove(Bm[-1])
C1.append(max(B2[-1],0))

ansC = 1
for a in C1[0:K]:
  ansC *= a
#  ansC %= MOD

print(max(ansB,ansC)%MOD)

Submission status: Time Limit Exceeded

Solution code:
def prodd(lst):
    p = 1
    for i in range(len(lst)):
        p *= lst[i]
    return p

from itertools import combinations
n, k= map(int, input().split())
lst = list(map(int, input().split()))
lst1 = []
data = list(combinations(lst, k))
for i in range(len(data)):
    lst1.append(prodd(data[i]))
print(max(lst1) % ((10 ** 9) + 7))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = sorted(a,reverse = True)
c = sorted(a)
l = []
for i in range(0,k//2+1):
    result = 1
    for j in range(0,k-2*i):
        result *= b[j]
    for g in range(0,2*i):
        result *= c[g]
    l.append(result)

    
print(max(l) % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import itertools as it
from functools import reduce
from operator import mul


n,k = [int(i) for i in input().split()]
nums = [int(i) for i in input().split()]


print(max(list(map(lambda comb: reduce(mul, comb),it.combinations(nums, k)))) % ((10**9)+7))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    A = list(map(int, input().split()))
    B = [(abs(x), x) for x in A]
    B.sort(reverse=True)
    plus = []
    minus = []

    ans = 1

    if N == K:
        for x in A:
            ans *= x
            ans %= mod
        print(ans)
        return
    
    minus_count = 0
    
    for i in range(K):
        if B[i][-1] < 0:
            minus_count += 1
            minus.append(B[i][-1])
        else:
            plus.append(B[i][-1])
        ans *= B[i][-1]
        ans %= mod

    if minus_count % 2 == 0:
        print(ans)
        return

    else:
        if len(plus) > 0 and len(minus) > 0:
            S = 1
            for i in range(len(plus)-1):
                S *= plus[i]
                S %= mod
            for i in range(len(minus)-1):
                S *= minus[i]
                S %= mod
                
            plus_sub = -1
            minus_sub = -1
            
            for i in range(K, N):
                if B[i][-1] >= 0:
                    plus_sub = B[i][-1]*plus[-1]
                    break
            for i in range(K, N):
                if B[i][-1] < 0:
                    minus_sub = B[i][-1]*minus[-1]
            print(10**19999999999999999999999)
            print(S*max(plus_sub, minus_sub) % mod)
            return

        else:
            for i in range(K, N):
                if B[i][-1] >= 0:
                    minus.append(B[i][-1])
                    break
            if minus[-1] >= 0:
                res = 1
                for i in range(K-1):
                    res *= minus[i]
                    res %= mod
                res *= minus[-1]
                print(res % mod)
                return
            else:
                A.sort(reverse=True)
                res = 1
                for i in range(K):
                    res *= A[i]
                    res %= mod
                print(res)
                return


main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


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

    MOD = 10**9 + 7

    num_zero = 0
    neg_list = []
    pos_list = []
    for a in A:
        if a == 0:
            num_zero += 1
        elif a < 0:
            neg_list.append(a)
        else:
            pos_list.append(a)

    # 0にしかできない
    if len(pos_list) + len(neg_list) < K:
        print(0)
    else:
        min_num_neg = K - len(pos_list)
        max_num_neg = min(K, len(neg_list))
        # 負にしかできない
        if min_num_neg == max_num_neg and min_num_neg % 2 == 1:
            if num_zero > 0:
                print(0)
                return

            ans = 1
            neg_list.sort()
            pos_list.sort(reverse=True)
            for i in range(K):
                use_pos = False
                if len(neg_list) == 0 or len(pos_list) == 0:
                    if len(neg_list) == 0:
                        use_pos = True
                    else:
                        use_pos = False
                elif abs(neg_list[-1]) < pos_list[-1]:
                    use_pos = False
                else:
                    use_pos = True

                if use_pos:
                    ans *= pos_list[-1]
                    pos_list.pop()
                else:
                    ans *= neg_list[-1]
                    neg_list.pop()

            print(ans % MOD)

        else:
            # 正にできる
            ans = 0
            tmp = 1

            neg_list.sort()
            pos_list.sort(reverse=True)
            pos_list = pos_list[:K]

            # 全部posを使う
            for p in pos_list:
                tmp *= p

            num = len(pos_list)
            if num == K:
                ans = max(ans, tmp)

            pos_idx = len(pos_list) - 1
            for i in range(len(neg_list)):
                tmp *= neg_list[i]
                num += 1

                if num > K:
                    if pos_idx >= 0:
                        tmp //= pos_list[pos_idx]
                        pos_idx -= 1
                        num -= 1
                    else:
                        break

                if num == K:
                    ans = max(ans, tmp)

            if num_zero:
                ans = max(0, ans)
            print(ans % MOD)


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n0, k0 = [ int(x) for x in input().split() ]
buf = {k0: (1, 1)}
for x in input().split():
  x = int(x)
  if x == 0:
    for k,(x0,x1) in buf.copy().items():
      if k - 1 in buf: buf[k-1] = (min(buf[k-1][0], 0), max(buf[k-1][1], 1))
      elif k: buf[k-1] = (0,0)
  elif 0 < x:
    for k,(x0,x1) in buf.copy().items():
      if k - 1 in buf: buf[k - 1] = (min(buf[k-1][0], x0 * x), max(buf[k-1][1], x1 * x))
      elif k: buf[k-1] = (x0 * x, x1 * x)
  else:
    for k,(x0,x1) in buf.copy().items():
      if k - 1 in buf: buf[k - 1] = (min(buf[k-1][0], x1 * x), max(buf[k-1][1], x0 * x))
      elif k: buf[k-1] = (x1 * x, x0 * x)
print(buf[0][1] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
nums=input().rstrip().split()
num=int(nums[0])
k=int(nums[1])
mains=input().rstrip().split()
mai=[]
for i in range(len(mains)):
    mai.append(int(mains[i]))
main=sorted(mai,key=abs,reverse=True)
result=1
def findplus_plus(x):
    for i in range(x,len(main)-1):
        if main[i]>=0:
            return main[i]
    return -1
def findplus_minus(x):
    for i in range(x,len(main)-1):
        if main[i]<0:
            return main[i]
    return 0
def findminus_plus(x):
    for i in range(x-1,-1,-1):
        if main[i]>=0:
            return main[i]
    return -1
def findminus_minus(x):
    for i in range(x-1,-1,-1):
        if main[i]<0:
            return main[i]
    return 0
    
if num==k:
    for i in main:
        result*=i
elif sorted(main)[len(sorted(main))-1]<0:
    if (k%2)==0:
        for i in range(k):
            result*=main[i]
    else:
        for i in range(len(main)-1,len(main)-1-k,-1):
            result*=main[i]
else:
    for i in range(k):
        result*=main[i]
    if result<0:
        if findplus_plus(k)==-1:
            result1=0
            result2=int(result*findplus_minus(k)//findminus_plus(k))
        else:
            result1=int(result*findplus_plus(k)//findminus_minus(k))
            if findplus_minus(k)==0 or findminus_plus(k)==-1:
                result2=0
            else:
                result2=int(result*findplus_minus(k)//findminus_plus(k))
        result=max(result1,result2)
print(result%(10**9+7))

Submission status: Time Limit Exceeded

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

mod=10**9+7

if A[-1]<0 and k%2==1:
    now=1
    for i in range(k):
        now= now*A[-i-1]%mod
        # now%=mod
    print(now) ;exit()

l=0 ; r=n-1
ans=1
if k%2==1:
    ans=A[-1]
    r-=1

for i in range(k//2):
    mi=A[l]*A[l+1]
    pl=A[r]*A[r-1]
    if mi>pl:
        ans*= mi%mod
        l+=2
    else:
        ans*= pl%mod
        r-=2
print(ans%mod)