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: Time Limit Exceeded

Solution code:
from itertools import combinations as comb
n,k=map(int, input().split())
a=list(map(int, input().split()))
p=comb(a,k)
for i in p :
    q=1
    for j in i :
        q*=j
    break
for i in p :
    t=1
    for j in i :
        t*=j
#     print(t)
    if t>q :
        q=t
print(q%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
p = []
m = []
mod = 10**9 + 7
if n == k:
  ans = 1
  for x in a:
    ans *= x
    ans %= mod
  print(ans)
  exit()
zero = 0
for x in a:
  if x == 0:
    zero += 1
  if x > 0:
    p.append(x)
  else:
    m.append(-x)
p.sort(reverse=True)
m.sort(reverse=True)
#print(zero,p,m)
nowp = 0
nowm = 0
lenp = len(p)
lenm = len(m)
if k + zero > n:
  print(0)
  exit()
n -= zero
ans = 1
def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    y %= mod
    x -= mod % x
  return y
pp = 0
for _ in range(k):
  if nowp == lenp:
    ans *= -m[nowm]
    ans %= mod
    nowm += 1
    pp = 1-pp
  elif nowm == lenm:
    ans *= p[nowp]
    ans %= mod
    nowp += 1
  elif p[nowp] >= m[nowm]:
    ans *= p[nowp]
    ans %= mod
    nowp += 1
    #print('$$')
  else:
    ans *= -m[nowm]
    ans %= mod
    nowm += 1
    pp = 1-pp
    #print('$')
  #print(pp,nowp,nowm)
#print(pp,ans)
if pp == 0:
  print(ans)
  exit()
if lenm == 0:
  print(ans)
  exit()
if lenp == 0:
  ans = 1
  m.reverse()
  for d in range(k):
    ans *= -m[d]
    ans %= mod
  print(ans)
  exit()
if lenp == nowp:
  ans *= inv(p[-1])
  ans *= -m[nowm]
  ans %= mod
  print(ans)
  exit()
if lenm == nowm:
  ans *= inv(-m[-1])
  ans *= p[nowp]
  ans %= mod
  print(ans)
  exit()
if nowp == 0:
  ans *= inv(-m[nowm-1])
  ans *= p[0]
  ans %= mod
  print(ans)
  exit()
if nowm == 0:
  ans *= inv(p[nowp-1])
  ans *= -m[0]
  ans %= mod
  print(ans)
  exit()
pl = p[nowp-1]
pr = p[nowp]
ml = m[nowm-1]
mr = m[nowm]
if mr * ml > pl * pr:
  ans *= inv(pl)
  ans *= -mr
  ans %= mod
  print(ans)
else:
  ans *= inv(-ml)
  ans *= pr
  ans %= mod
  print(ans)

Submission status: Time Limit Exceeded

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

ans = 1
if (A[-1]<0) and (K%2==1):
  for i in range(K//2):
    ans = (ans*A[-1]) % (10**9+7)
    ans = (ans*A[-2]) % (10**9+7)
    A = A[:len(A)-2]
  ans *= A[-1]
  ans = ans % (10**9+7)
else:
  for i in range(K//2):
    a = A[0]*A[1]
    b = A[-1]*A[-2]
    if a <= b:
      ans = (ans*A[-1]) % (10**9+7)
      ans = (ans*A[-2]) % (10**9+7)
      A = A[:len(A)-2]
    else:
      ans = (ans*A[0]) % (10**9+7)
      ans = (ans*A[1]) % (10**9+7)
      A = A[2:]
  if K % 2 == 1:
    ans *= A[-1]
    ans = ans % (10**9+7)
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
mod = 1000000007
ml_number = 1
N, K = map(int, input().split())
num_list = list(map(int, input().split()))
t = itertools.combinations(num_list, K)
for i, group in enumerate(t, start=1):
    for j,num in enumerate(group, start=1):
        if j == 1:
            ml_number = num
        else:
            ml_number = ml_number * num
    if i == 1:
        max_number = ml_number
    else:
        max_number = max(max_number,ml_number)
print(max_number % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
# import bisect
# import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
import itertools
import heapq


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


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    A.sort()
    A = deque(A)
    #    print(A)
    A_minus = deque([s for s in A if s < 0])
    A_plus = deque([s for s in A if s >= 0])

    #    print(A_plus)
    #    print(A_minus)
    AA = []
    if N == K:
        ans = 1
        for i in A:
            ans *= i % mod
        print(ans % mod)

    elif K % 2 == 0:
        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AA.append(-a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            AA.append(-a1 * a2)
        ans = 1
        heapq.heapify(AA)
        for i in range(K // 2):
            ans *= (-1 * heapq.heappop(AA)) % mod
        print(ans % mod)

    elif len(A_plus) == 0:
        ans = 1
        for i in range(K):
            ans *= A_minus.pop() % mod
        print(ans % mod)

    else:
        ans = A_plus.pop()
        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AA.append(-a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            AA.append(-a1 * a2)

        heapq.heapify(AA)
        for i in range(K // 2):
            ans *= (-1 * heapq.heappop(AA)) % mod
        print(ans % mod)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def kmaxprod_v2(data, k):
    if len(data) < k:
        return np.nan
    data = np.asanyarray(data)
    dfp = data.astype(object) if data.dtype in (
        int, np.int64, np.int32, np.int16, np.int8) else data
    if len(data) == k:
        return np.prod(dfp)
    neg = data <= 0
    if k % 2 == 1 and np.count_nonzero(neg) == len(data):
        return np.prod(-np.partition(-data, k)[:k].astype(dfp.dtype))
    ap = np.argpartition(-np.absolute(data), k)
    low, high = ap[k:], ap[:k]
    greedy = np.prod(dfp[high])
    if greedy >= 0:
        return greedy
    bpo = np.max(dfp[low])
    if bpo <= 0:
        spfn = 0
    else:
        neg_high = np.where(neg[high])[0]
        wni_ind = np.argmax(data[high[neg_high]])
        wni_ind = neg_high[wni_ind]
        spfn = bpo*np.prod(dfp[high[:wni_ind]])*np.prod(dfp[high[wni_ind+1:]])
    pos_high = np.where(~neg[high])[0]
    if len(pos_high) == 0:
        snfp = 0
    else:
        wpi_ind = np.argmin(data[high[pos_high]])
        wpi_ind = pos_high[wpi_ind]
        bno = np.min(dfp[low])
        snfp = bno*np.prod(dfp[high[:wpi_ind]])*np.prod(dfp[high[wpi_ind+1:]])
    return max(spfn, snfp)

n, k = input().split()
val = list(map(int, input().strip().split()))
for x in val:
    x = x%1000000007
print(kmaxprod_v2(val, int(k))%1000000007)

Submission status: Time Limit Exceeded

Solution code:
N,K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
# A.sort(key = lambda x: abs(x), reverse = True)
dp = [[[float("inf"),-float("inf")] for i in range(K+1)] for j in range(N+1)]
dp[0][0] = [1,1]
for i in range(1,N+1):
    for j in range(min(i+1, K+1)):
        if j == 0:
            dp[i][j][0] = dp[i-1][j][0]
            dp[i][j][1] = dp[i-1][j][1]
        else:
            dp[i][j][0] = min(dp[i-1][j][0], dp[i-1][j-1][0]*A[i-1], dp[i-1][j-1][1]*A[i-1])
            dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]*A[i-1], dp[i-1][j-1][1]*A[i-1])
# for i in dp:
#     print(i)
print(max(dp[-1][-1])%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    ans = float('-inf')
    for i in range(2**n):
        x = format(i, '0'+str(n)+'b')
        if x.count('1') != k:
            continue
        curr = 1
        for j in range(n):
            if x[j] == '1':
                curr *= a[j]
        ans = max(ans, curr)
    
    print(ans % (10**9 + 7))

resolve()

Submission status: Time Limit Exceeded

Solution code:
mod=1000000007
def maxProduct(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] %mod)
        return product%mod 
    i=0 
    j=n-1
    if (k & 1): 
        product *= A[j] %mod 
        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%mod 
            i += 2
        else : 
            product *= right_product%mod 
            j -= 2 
    return product%mod 
    
n,k=map(int,input().split())
lst=list(map(int,input().strip().split()))[:n]
print((maxProduct(lst,n,k))%mod)

Submission status: Time Limit Exceeded

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

ans = 1
if (A[-1]<0) and (K%2==1):
  for i in range(K//2):
    ans = (ans*A[-1]*A[-2]) % (10**9+7)
    A = A[:len(A)-2]
  ans *= A[-1]
  ans = ans % (10**9+7)
else:
  for i in range(K//2):
    a = A[0]*A[1]
    b = A[-1]*A[-2]
    if a <= b:
      ans = ans * (b%(10**9+7))
      ans = ans % (10**9+7)
      A = A[:len(A)-2]
    else:
      ans = ans * (a%(10**9+7))
      ans = ans % (10**9+7)
      A = A[2:]
  if K % 2 == 1:
    ans *= A[-1]
    ans = ans % (10**9+7)
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
d1, d2 = sorted([q for q in a if q > 0], reverse=True), sorted([q for q in a if q < 0])
C = 1000000007
if len(d1)+len(d2) < k:
    print(0)
elif k == n:
    ans = 1
    for q in a:
        ans = ans*q % C
    print(ans)
elif len(d1) == 0 and k % 2 == 0:
    ans = 1
    for q in range(k):
        ans = ans*d2[q] % C
    print(ans)
elif len(d1) == 0 and len(d2) < n:
    print(0)
elif len(d1) == 0:
    ans = 1
    for q in range(len(d2)-1, len(d2)-k-1, -1):
        ans = ans*d2[q] % C
    print(ans)
elif len(d2) == 0:
    ans = 1
    for q in range(k):
        ans = ans*d1[q] % C
    print(ans)
else:
    ans, now, w = 0, 0, min(k+1, len(d2)+1)
    for q in range(max(0, (k-len(d1)+1)//2*2), w, 2):
        if now == 0:
            now = 1
            for q1 in range(q):
                now *= d2[q1]
            for q1 in range(k-q):
                now *= d1[q1]
            ans = now
        else:
            now //= d1[k-q+1]*d1[k-q]
            now *= d2[q-2]*d2[q-1]
            ans = max(ans, now)
    print(ans % C)

Submission status: Time Limit Exceeded

Solution code:
# 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)) : 
        count=0
        while(count<k):
            product*=A[n-count-1]
            count+=1
        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 

M=1000000007
n,k=map(int,input().split())
ar=list(map(int,input().split()))
ans=maxProductSubarrayOfSizeK(ar,n,k)
ans=(ans%M+M)%M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import functools
import operator
def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    p = []
    m = []
    for i in range(n):
        if a[i] >= 0:
            p.append(a[i])
        else:
            m.append(a[i])
    p.sort(reverse=True)
    m.sort()
    if k == 1: return p[0]%(int(1e9)+7)
    if k == n: return functools.reduce(operator.mul, a)%(int(1e9)+7)
    if len(m) == n: m.sort(reverse=True)
    
    cnt = 0
    ans = 1
    while cnt < k:
        pl = 0
        mi = 0
        if len(p)>=2: pl = p[0]*p[1]
        if len(m)>=2: mi = m[0]*m[1]
        if pl >= mi:
            ans *= pl
            cnt += 2
            p.pop(0)
            p.pop(0)
        else:
            ans *= mi
            cnt += 2
            m.pop(0)
            m.pop(0)
        if k - cnt == 1:
            if p:
                ans *= p[0]
                cnt += 1
            else:
                ans *= m[0]
                cnt += 1
    return ans%(int(1e9)+7)

        


print(solve())

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
all_minus = True
for i in range(n):
  if a[i] >= 0:
    all_minus = False
    break
if all_minus:
  a.sort(key = lambda x: abs(x))
  ans = 1
  for i in range(k):
    ans *= a[i]
  ans %= mod
  print(ans)
  exit()
a.sort(key = lambda x: abs(x))
a.reverse()
ans = 1
mcnt = 0
zcnt = 0
for i in range(n):
  if a[i] == 0:
    zcnt += 1
if zcnt > n - k:
  print(0)
  exit()
b = []
for i in range(n):
  if a[i] == 0:
    continue
  b.append(a[i])
m = len(b)
for i in range(k):
  ans *= b[i]
  if b[i] < 0:
    mcnt += 1
if mcnt % 2 == 0:
  ans = max(0, ans) % mod
  print(ans)
  exit()
lp = 0
lm = 0
for i in reversed(range(k)):
  if b[i] > 0:
    lp = b[i]
    break
for i in reversed(range(k)):
  if b[i] < 0:
    lm = b[i]
    break
base = ans
cp = True
cm = True
for i in range(k, m):
  temp = base
  if not cp and not cm:
    break
  if b[i] > 0 and cp:
    temp //= lm
    temp *= b[i]
    ans = max(ans, temp)
    cp = False
  if b[i] < 0 and cm and lp > 0:
    temp //= lp
    temp *= b[i]
    ans = max(ans, temp)
    cm = False
ans = max(0, ans) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

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

p, m = [], []
zero = False
for x in a:
    if x == 0:
        zero = True
        continue
    elif x >= 0: p.append(x)
    else: m.append(x)

if len(p) == 0 and len(m) == 0:
    print(0)
    exit()

p.sort(reverse=True)
m.sort()
mr = list(reversed(m))

def cum(s):
    n = len(s)
    cs = [1] * (n+1)
    for i in range(n):
        cs[i+1] = cs[i] * s[i]
    return cs

pc = cum(p)
mc = cum(m)
mrc = cum(mr)

ans = -float("inf")
pl, ml = len(p), len(m)

d = min(pl, k)

for pn in range(d+1)[::-1]:
    mn = k - pn
    if mn > ml: continue
    tmp = pc[pn] * mc[mn]
    tmp1 = pc[pn] * mrc[mn]

    ans = max(ans, tmp, tmp1)

if ans < 0 and zero:
    print(0)
else: 
    print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

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

    a.sort()
    ret = 1
    if k % 2 == 0 or a[-1] >= 0:
        for _ in range(k//2):
            mlt1 = a[0] * a[1]
            mlt2 = a[-2] * a[-1]
            if mlt1 >= mlt2:
                ret *= mlt1 % mod
                a = a[2:]
            else:
                ret *= mlt2 % mod
                a = a[:-2]
            ret %= mod

        if k % 2 == 1:
            ret *= a[-1]
            ret %= mod

    else:
        for i in range(k):
            ret *= a[n-1-i]
            ret %= mod

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
[N, K] = [int(i) for i in input().split()]
A = sorted([int(i) for i in input().split()], reverse=True)
D = 10**9 + 7

S = 1
i = K
top = 0
tail = N-1

f = 1
if A[0] < 0:
  f = -1

while i > 0:
  if i == 1:
    S *= A[top]
    i = 0
  else:
    s1 = A[top] * A[top+1]
    s2 = A[tail] * A[tail-1]
    if s1 * f > s2 * f:
      S *= s1
      top += 2
    else:
      S *= s2
      tail -= 2
  i -= 2
      
print((S+D)%D)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

MOD = 10 ** 9 + 7

A_pos = sorted(A, reverse=True)
A_neg = sorted(A)

B_pos = [A_pos[0]]
B_neg = [A_neg[0]]

for i in range(1, N):
    B_neg.append(B_neg[-1]*A_neg[i])
    B_pos.append(B_pos[-1]*A_pos[i])
ans = -float('inf')
for j in range(K-1, -2, -1):
    if j == K-1:
        ans = max(ans, B_pos[j])
    elif j == -1:
        ans = max(ans, B_neg[K-1])
    else:
        ans = max(ans, B_pos[j]*B_neg[K-j-2])

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import functools
import operator
n,k=map(int,input().split())
a=list(map(int,input().split()))
MOD=10**9+7
ans=-float('inf')
for i in itertools.combinations(a,k):
    #print(*i)
    b=functools.reduce(operator.mul,i)
    ans=max(ans,b)
    #print(ans)
ans=ans%MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3


import functools
from numba import jit


M = 10 ** 9 + 7


@jit
def prods(xs):
    return functools.reduce(lambda x, y: x * y % M, xs) % M


@jit
def maximize_product(n, k, bs):
    cs = sorted(bs)
    if cs[-1] == 0 and k % 2 == 1:
        return 0
    elif cs[-1] <= 0 and k % 2 == 1:
        return prods(cs[n - k:]) % M
    i = 0
    j = n - 1
    res = 1
    if k % 2 == 1:
        res *= cs[j] % M
        j -= 1
        k -= 1
    k >>= 1
    for _ in range(k):
        lp = cs[i] * cs[i + 1]
        rp = cs[j] * cs[j - 1]
        if lp > rp: 
            res *= lp % M 
            i += 2
        else: 
            res *= rp % M 
            j -= 2
    res %= M
    return res
   


def main():
    n, k = (int(z) for z in input().split())
    bs = [int(b) for b in input().split()]
    res = maximize_product(n, k, bs)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

A.sort(reverse=True)

mod=(10**9+7)
p=-10**100


for i in range(k//2+1):
    pp=1
    for j in range(k-2*i):
        pp=pp*A[j]
    for jj in range(i):
        pp=pp*A[-2*jj-1]*A[-2*jj-2]

    if pp>p:
        p=pp
print(p%mod)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys

sys.setrecursionlimit(1000000)

import bisect
import math
import collections
import heapq

MOD = 10 ** 9 + 7

def solve(N, K, As):
    originalK = K
    # print(N, ",", K, ",", As)
    minus = [a for a in As if a < 0]
    minus.sort(reverse=True)
    zero = [a for a in As if a == 0]
    plus = [a for a in As if a > 0]
    plus.sort()

    if len(zero) and len(zero) > N - K:
        return 0

    ans = 1
    while K >= 2 and (len(plus) >= 2 or len(minus) >= 2):
        p1 = -1
        p2 = -1
        m = -1
        if len(plus) >= 1:
            p1 = plus[-1]
        if len(plus) >= 2:
            p2 = plus[-1] * plus[-2]
        if len(minus) >= 2:
            m = minus[-1] * minus[-2]

        if m >= p2:
            ans *= m
            ans %= MOD
            minus.pop()
            minus.pop()
            K -= 2
        else:
            ans *= p1
            ans %= MOD
            plus.pop()
            K -= 1

    while K > 0:
        if len(plus):
            ans *= plus.pop()
            ans %= MOD
        else:
            ans *= minus.pop(0)
        K -= 1
    if ans < 0 and zero:
        return 0
    if ans < 0:
        minus = [a for a in As if a < 0]
        minus.sort()
        ans = 1
        for _ in range(originalK):
            ans *= minus.pop()
        ans %= MOD

    return ans


def slowsolve(N, K, As):
    ans = -1000
    for p in itertools.combinations(As, K):
        k = 1
        for i in p:
            k *= i
        ans = max(ans, k)
    return ans

# 
# assert (solve(1, 1, [0]) == 0)
# assert (solve(3, 2, [0, 1, 0]) == 0)
# assert (solve(3, 2, [0, 1, 0]) == 0)
# assert (solve(5, 2, [1, 2, -1, -3, -4]) == 12)
# assert (solve(1, 1, [-4]) == -4 % MOD)
# assert (solve(2, 1, [-4, 0]) == 0)
# assert (solve(2, 1, [-1, -4]) == -1  % MOD)
# assert (solve(10, 5, [-2, 1, -3, 2, 0, -1, 3, -2, -2, -3]) == 108)
# assert (solve(10, 5, [-1, 2, 2, 0, 2, -2, -1, 0, -3, -1]) == 48)
# assert (solve(10, 5, [0, 0, -3, 3, 3, 2, 2, 0, 3, -1]) == 108)
# assert (solve(10, 5, [-1, -2, -1, -3, -2, -3, -2, -3, -1, -2]) == -4 % MOD)
# 

#
# print(slowsolve(10 , 5 , [0, 0, -3, 3, 3, 2, 2, 0, 3, -1]))
# print(solve(10 , 5 , [0, 0, -3, 3, 3, 2, 2, 0, 3, -1]))
#
# exit()


def rand(N, a, b):
    import random
    return [random.randint(a, b) for _ in range(N)]
#
#
# for _ in range(100000):
#     N = 5
#     A = -5
#     B = 5
#     K = 2
#     As = rand(N, A, B)
#     slow = slowsolve(N, K, As)
#     ans = solve(N, K, As)
#     if slow != ans:
#         print(N, ",", K, ",", As)
#         print(slow)
#         print(ans)
#         assert (slow == ans)
#
# print("OK")

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
arr = [int(x) for x in input().split()]

mod = 10**9 + 7

def solve(A, n, k): 
    mod = 10**9 + 7
  
    # sorting given input array 
    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): 
            # print(i,A[i])
            product *= (A[i] % mod) 
        return product % mod
    i = 0 
    j = n - 1 
    if (k & 1): 
        product *= (A[j] % mod)
        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 % mod)
            i += 2
        else : 
            product *= (right_product % mod)
            j -= 2
    return product % mod
print(solve(arr, n, k) % mod)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,K = map(int,input().split())
A = [int(i) for i in input().split()]
max1 = -float('inf')
for a in itertools.combinations(A,K):
    mpl = 1
    for i in a:
        mpl = i * mpl
    if mpl >= max1:
        max1 = mpl
result = max1%(10**9+7)
print(result)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

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

def abssort(A):
    return sorted(A, key = lambda x:abs(x), reverse= True)

tmp = 1
A_abs = abssort(A)
for i in range(K):
    tmp *= A_abs[i]

if tmp >= 0:
    print(tmp % mod)
    sys.exit()
else:
    tmp_1 = copy.deepcopy(tmp)
    tmp_2 = copy.deepcopy(tmp)
    changes = A_abs[:K]
    changes.reverse()
    # -を一つ消す
    for i in range(K):
        if changes[i] < 0:
            tmp_1 //= changes[i]
            break
    for i in range(K, N):
        if A_abs[i] > 0:
            tmp_1 *= A_abs[i]
            break
    else:
        # +がなかった時
        tmp_1 = 1
        A_abs.reverse()
        for i in range(K):
            tmp_1 *= A_abs[i]
    # +を消して-を追加
    cnt = 0
    for i in range(K):
        if changes[i] > 0:
            tmp_2 //= changes[i]
            cnt += 1
            break
    if cnt == 1:
        for i in range(K, N):
            if A_abs[i] < 0:
                tmp_2 *= A_abs[i]
                break
# print(tmp_1, tmp_2)
print(max(tmp_1, tmp_2) % mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction as F
mod=10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
ret=1
cnt=0
for x in a:
	if x<0:
		b.append((-x,0))
	else:
		b.append((x,1))
b.sort(reverse=True)
p=-1
m=-1
for i in range(k):
	ret*=b[i][0]
	ret%=mod
	if b[i][1]==0:
		cnt+=1
		m=i
	else:
		p=i
if cnt%2==0:
	print(ret)
	exit()
ret1=-1
ret2=-1
f1=f2=0
if p!=-1:
	ret1=ret*pow(b[p][0],mod-2,mod)%mod
	for i in range(k,n):
		if b[i][1]==0:
			ret1*=b[i][0]
			ret1%=mod
			f1=1
			val1=F(b[i][0],b[p][0])
			break
if m!=-1:
	ret2=ret*pow(b[m][0],mod-2,mod)%mod
	for i in range(k,n):
		if b[i][1]==1:
			ret2*=b[i][0]
			ret2%=mod
			f2=1
			val2=F(b[i][0],b[m][0])
			break
if f1==0:
	ret1=-1
if f2==0:
	ret2=-1
if ret1==ret2==-1:
	ret=-1
	for i in range(k):
		ret*=b[-i-1][0]
	print(ret%mod)
elif ret1==-1:
	print(ret2)
elif ret2==-1:
	print(ret1)
else:
	if val1>val2:
		print(ret1)
	else:
		print(ret2)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3


import functools


M = 10 ** 9 + 7


def prods(xs):
    return functools.reduce(lambda x, y: x * y % M, xs) % M


def maximize_product(n, k, bs):
    cs = sorted(bs)
    if cs[-1] == 0 and k % 2 == 1:
        return 0
    elif cs[-1] <= 0 and k % 2 == 1:
        return prods(cs[n - k:]) % M
    i = 0
    j = n - 1
    res = 1
    if k % 2 == 1:
        res *= cs[j] % M
        j -= 1
        k -= 1
    k >>= 1
    for _ in range(k):
        lp = cs[i] * cs[i + 1]
        rp = cs[j] * cs[j - 1]
        if lp > rp: 
            res *= lp % M 
            i += 2
        else: 
            res *= rp % M 
            j -= 2
    res %= M
    return res
   


def main():
    n, k = (int(z) for z in input().split())
    bs = [int(b) for b in input().split()]
    res = maximize_product(n, k, bs)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+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): 
            # print(i)
            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

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3


import functools


M = 10 ** 9 + 7


def prods(xs):
    return functools.reduce(lambda x, y: x * y % M, xs) % M


def maximize_product(n, k, bs):
    cs = sorted(bs)
    if cs[-1] == 0 and k % 2 == 1:
        return 0
    elif cs[-1] <= 0 and k % 2 == 1:
        return prods(cs[n - k:])
    i = 0
    j = n - 1
    res = 1
    if k % 2 == 1:
        res *= cs[j] % M
        j -= 1
        k -= 1
    k >>= 1
    for _ in range(k):
        lp = cs[i] * cs[i + 1] 
        rp = cs[j] * cs[j - 1] 
        if lp > rp: 
            res *= lp % M 
            i += 2
        else: 
            res *= rp % M 
            j -= 2
    res %= M
    return res
   


def main():
    n, k = (int(z) for z in input().split())
    bs = [int(b) for b in input().split()]
    res = maximize_product(n, k, bs)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def choose(ans):
    l = 1
    if ans < 0:
        if a_list[-1]*a_list[-2] >= a_list[0]*a_list[1]:
            l *= a_list.pop(0)
            l *= a_list.pop(0)
        else:
            l *= a_list.pop(-1)
            l *= a_list.pop(-1)
    else:
        if a_list[-1]*a_list[-2] >= a_list[0]*a_list[1]:
            l *= a_list.pop(-1)
            l *= a_list.pop(-1)
        else:
            l *= a_list.pop(0)
            l *= a_list.pop(0)
    return l % MOD


ans = 1
if K == 1:
    print(a_list[-1]%MOD)
    exit()
else:
    if K % 2 == 0:
        for _ in range(K//2):
            ans *= choose(ans)
    else:
        ans *= a_list.pop(-1)
        for _ in range((K-1)//2):
            ans *= choose(ans)

print(ans%MOD)