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
mod=10**9+7
def solve(n,k,a):
  if min(a)>0:
    ans=1
    a.sort(reverse=1)
    for i in a[:k]:
      ans*=i
      ans%=mod
    return ans
  if max(a)<0:
    if k%2==0:
      a.sort()
      ans=1
      for i in a[:k]:
        ans*=i
        ans%=mod
      return ans
    else:
      a.sort(reverse=1)
      ans=1
      for i in a[:k]:
        ans*=i
        ans%=mod
      return ans
  if n==k:
    ans=1
    for i in a:
      ans*=i
      ans%=mod
    return ans
  if k==1:
    return max(a)
  if n-k==1:
    ans=1
    if a.count(0)>1:return 0
    p=[]
    m=[]
    for i in a:
      if i>0:p.append(i)
      elif i<0:m.append(i)
    if 0 in a:
      if len(m)%2==0:
        for i in a:
          if i==0:continue
          ans=(ans*i)%mod
      else:ans=0
    else:
      if len(m)%2==0:
        for i in sorted(p)[1:]+m:ans=(ans*i)%mod
      else:
        for i in p+sorted(m)[:-1]:ans=(ans*i)%mod
    return ans


  ans=1
  p=[]
  m=[]
  for i in a:
    if i<0:m.append(i)
    elif i>=0:p.append(i)
  p.sort()
  m.sort(reverse=1)

  while k>1:
    if k<=5:
      ans*=solve2(len(p)+len(m),k,m+p)
      ans%=mod
      k=0
      break
    if len(p)<2:
      ans*=m.pop()*m.pop()
      k-=2
    elif len(m)<2:
      ans*=p.pop()*p.pop()
      k-=2
    elif m[-1]*m[-2]>p[-1]*p[-2]:
      ans*=m.pop()*m.pop()
      k-=2
    else:
      ans*=p.pop()*p.pop()
      k-=2
    ans%=mod
  if k:
    ans*=p.pop()
  return ans
  print(ans%mod)

def solve2(n,k,a):
  ans=-10**20
  for c in combinations(range(n),k):
    anss=1
    for i in c:anss*=a[i]
    ans=max(ans,anss)
  return ans%mod

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

"""
from random import randint
for i in range(10000):
  n=randint(1,10)
  k=randint(1,n)
  a=sorted([randint(-10,10)for _ in range(n)])
  print(n,k,a)
  ans1=solve(n,k,a)
  ans2=solve2(n,k,a)
  if ans1==ans2:print("ok")
  else:
    print("error")
    print(n,k)
    print(*a)
    print(ans1,ans2)
    exit()
"""

Submission status: Time Limit Exceeded

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

import itertools
times = []
for team in itertools.combinations(a,k):
    temp = team[0]
    for i in range(1,len(team)):
        temp *= team[i]
    times.append(temp)

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

Submission status: Time Limit Exceeded

Solution code:
from queue import PriorityQueue
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


mod = 10**9+7


def prod(l):
    ret = 1
    for e in l:
        ret = (ret*e) % mod

    return ret


def main():
    n, k = geta(int)
    a = list(geta(int))

    p, n, z = [], [], 0
    for ai in a:
        if ai > 0:
            p.append(ai)
        elif ai < 0:
            n.append(-ai)
        else:
            z += 1

    ans = 1
    p.sort()
    n.sort()
    if k & 1 == 1:
        if len(p) == 0:
            if z > 0:
                print(0)
                exit()
            else:
                print(-prod(n[0:k]) % mod)
                exit()
        else:
            k -= 1
            ans *= p.pop()

    if len(p) + len(n) < k:
        print(0)
        exit()

    q = PriorityQueue()

    n = n[::-1]
    for i in range(len(n)//2):
        q.put(-n[2*i]*n[2*i+1])

    p = p[::-1]
    for i in range(len(p)//2):
        q.put(-p[2*i]*p[2*i+1])

    cnt = 0
    while cnt < k:
        ans = ans * (-q.get()) % mod
        cnt += 2

    print(ans % mod)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k=input().split()
n=int(n)
k=int(k)
arr=list(map(int,input().split()))
neg=[]
pos=[]
rneg=[]
zero=0
for i in arr:
	if i<=0:
		neg.append(i)
		rneg.append(i)
	elif i>0:
		pos.append(i)

neg.sort()
rneg.sort(reverse=True)
pos.sort(reverse=True)
pre1=[]
prd=1
for i in neg:
	prd*=i
	pre1.append(prd)
prd=1
pre3=[]
for i in rneg:
	prd*=i
	pre3.append(prd)
pre2=[]
prd=1
for i in pos:
	prd*=i
	pre2.append(prd)

# print(pre1)
# print(pre2)
ans=0
flg=0
for i in range(0,k-1):
	if i < len(pre1) and k-i-2 < len(pre2):
		if i%2==0:
			ans1=pre3[i]*pre2[k-i-2]
		else:
			ans1=pre1[i]*pre2[k-i-2]
		# ans1=pre1[i] * pre2[k-i-2]
		# print(i,ans1)
		if flg==0:
			flg=1
			ans=ans1
		else:
			ans=max(ans,ans1)

if k-1 < len(pre2):
	ans1=pre2[k-1]
	if flg==0:
		flg=1
		ans=ans1
		ans=max(ans,ans1)

	# ans=max(ans,ans1)
if k-1 <len(pre1):

	if k%2==0:
		ans1=pre1[k-1]
	else:
		ans1=pre3[k-1]
	# ans1=pre1[k-1]
	if flg==0:
		flg=1
		ans=ans1
	else:
		ans=max(ans,ans1)
mod=1e9+7
mod=int(mod)
# print(mod)
ans=ans%mod
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

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

A.sort(key=lambda x: abs(x))

neg = []
pos = []
zero = 0

for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    elif A[i] < 0:
        neg.append(A[i])
    else:
        zero += 1

res = 1

for i in range(K):
    res *= A[~i]

if res > 0:
    print(res % MOD)

else:
    tmp1 = res
    minneg = None
    for i in range(K):
        if A[~i] < 0:
            minneg = ~i
    maxpos = None
    for i in range(N - K):
        if A[i] > 0:
            maxpos = i
    if maxpos is not None:
        tmp1 *= A[maxpos]
        tmp1 //= A[minneg]
    tmp2 = res
    minpos = None
    for i in range(K):
        if A[~i] > 0:
            minpos = ~i
    maxneg = None
    for i in range(N - K):
        if A[i] < 0:
            maxneg = i
    if maxneg is not None and minpos is not None:
        tmp2 *= A[maxneg]
        tmp2 //= A[minpos]
    if tmp1 > 0 or tmp2 > 0:
        print(max(tmp1, tmp2) % MOD)
    else:
        if zero:
            print(0)
        else:
            res = 1
            for i in range(K):
                res *= A[i]
            print(res % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys, math,os
from io import BytesIO, IOBase
#data = BytesIO(os.read(0,os.fstat(0).st_size)).readline
# from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
# from decimal import Decimal
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
#sys.setrecursionlimit(100000 + 1)
INF = 10**9
mod = 10**9 + 7


n,k=mdata()
a=mdata()
n1,p=-1,-1
a1=[(abs(a[i]),a[i]) for i in range(n)]
a1.sort(reverse=True)
ans=1
for i in range(k):
    if a1[i][1]>0:
        p=i
    else:
        n1=i
    ans*=a1[i][1]
if ans>=0:
    out(ans%mod)
else:
    for i in range(k,n):
        if a1[i][1]>=0:
            ans=max((ans//a1[n1][1])*a1[i][1],ans)
        if a1[i][1]<0 and p!=-1:
            ans=max((ans//a1[p][1])*a1[i][1],ans)
    if ans<0:
        ans=1
        for i in range(k):
            ans *= a1[n-i-1][1]
    out(ans%mod)

Submission status: Time Limit Exceeded

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

ret = 1
mod = 10 ** 9 + 7

left = k
mptr = 0
pptr = len(a) - 1
mls = []
a.sort()
for i in range(len(a)):
    if i % 2 == 0:
        continue
    else:
        if a[i] < 0 and a[i-1] < 0:
            mls.append(a[i] * a[i-1])
        else:
            break

while left > 0:
    if left > 1:
        if mptr < len(mls) or (pptr >= 0 and a[pptr] > 0):
            if pptr - 1 >= 0 and a[pptr - 1] > 0:
                if mptr < len(mls) and (mls[mptr] >= (a[pptr] * a[pptr - 1])):
                    ret = (mls[mptr] % mod) * ret % mod
                    left -= 2
                    mptr += 1
                else:
                    ret *= a[pptr] % mod
                    left -= 1
                    pptr -= 1
            else:
                if mptr < len(mls) and (mls[mptr] >= a[pptr]):
                    ret = (mls[mptr] % mod) * ret % mod
                    left -= 2
                    mptr += 1
                else:
                    ret *= a[pptr] % mod
                    left -= 1
                    pptr -= 1
        else:
            ret = 0
            break
    else:
        if pptr >= 0 and a[pptr] > 0:
            left -= 1
            ret *= a[pptr] % mod
            pptr -= 1
        else:
            ret = 0
            break

if ret > 0:
    print(ret % mod)
else:
    a.sort(key=lambda x: abs(x))
    ret = 1
    for i in range(k):
        ret *= a[i] % (10 ** 9 + 7)
        if ret == 0:
            break
    print(ret % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

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

plus = []
minus = []
zero = []

for i in range(N):
    if A[i] > 0:
        plus.append(A[i])
    elif A[i] < 0:
        minus.append(-A[i])
    else:
        zero.append(A[i])

plus.sort(reverse=True)
minus.sort(reverse=True)

for i in range(1,len(plus)):
    plus[i] = plus[i-1]*plus[i]

for i in range(1,len(minus)):
    minus[i] = minus[i-1]*minus[i]

plus = [1]+plus
minus = [1]+minus

ans = 0 if len(zero) else -float('inf')
for i in range(K+1):
    if i < len(plus) and K-i < len(minus):
        temp = plus[i]*minus[K-i]*(-1)**((K-i)%2)
        if temp > 0 and temp > ans:
            ans = temp



plus = []
minus = []
zero = []

for i in range(N):
    if A[i] > 0:
        plus.append(A[i])
    elif A[i] < 0:
        minus.append(-A[i])
    else:
        zero.append(A[i])

plus.sort()
minus.sort()

for i in range(1,len(plus)):
    plus[i] = plus[i-1]*plus[i]

for i in range(1,len(minus)):
    minus[i] = minus[i-1]*minus[i]

plus = [1]+plus
minus = [1]+minus

for i in range(K+1):
    if i < len(plus) and K-i < len(minus):
        temp = plus[i]*minus[K-i]*(-1)**((K-i)%2)
        if temp < 0 and temp > ans:
            ans = temp

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
aas = list(map(int, input().split()))
from itertools import combinations as comb
res = -float('inf')
for p in comb(aas, k):
    res_tmp = 1
    for i in p:
        res_tmp *= i
    res = max(res, res_tmp)
print(int(res%1000000007))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 7 + 10**9
    if N == K:
        r = 1
        for i in A:
            r *= i
            r %= mod
        return r % mod
    if max(A) <= 0 and K % 2 == 1:
        A.sort(reverse=True)
        r = 1
        for i in range(K):
            r *= A[i]
            r %= mod
        return r % mod
    a = []
    for i in A:
        a.append((abs(i), i))
    a.sort(reverse=True)
    cm = 0
    lp = None
    lm = None
    for i in range(K):
        if a[i][1] >= 0:
            lp = i
        else:
            lm = i
            cm += 1
    if cm % 2 == 0:
        r = 1
        for i in range(K):
            r *= a[i][1]
            r %= mod
        return r
    if not lp:
        r = 1
        for i in range(K-1):
            r *= a[i][1]
            r %= mod
        r *= max(A)
        return r % mod
    np = None
    nm = None
    for i in range(K, N):
        if a[i][1] >= 0 and not np:
            np = i
        if a[i][1] < 0 and not nm:
            nm = i
        if np and nm:
            break
    if not np:
        r = 1
        for i in range(K):
            if i != lp:
                r *= a[i][1]
                r %= mod
        r *= a[nm][1]
        return r % mod
    if not nm:
        r = 1
        for i in range(K):
            if i != lm:
                r *= a[i][1]
                r %= mod
        r *= a[np][1]
        return r % mod
    r = 1
    for i in range(K):
        if i not in (lp, lm):
            r *= a[i][1]
    r *= max(a[np][1] * a[lp][1], a[lm][1] * a[nm][1])
    return r % mod
print(main())

Submission status: Time Limit Exceeded

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

ret = 1
mod = 10 ** 9 + 7

left = k
mptr = 0
pptr = len(a) - 1
mls = []
a.sort()
for i in range(len(a)):
    if i % 2 == 0:
        continue
    else:
        if a[i] < 0 and a[i-1] < 0:
            mls.append(a[i] * a[i-1])
        else:
            break

while left > 0:
    if left > 1:
        if mptr < len(mls) or (pptr >= 0 and a[pptr] > 0):
            if pptr - 1 >= 0 and a[pptr - 1] > 0:
                if mptr < len(mls) and (mls[mptr] >= (a[pptr] * a[pptr - 1])):
                    ret *= mls[mptr] % mod
                    left -= 2
                    mptr += 1
                else:
                    ret *= a[pptr] % mod
                    left -= 1
                    pptr -= 1
            else:
                if mptr < len(mls) and (mls[mptr] >= a[pptr]):
                    ret *= mls[mptr] % mod
                    left -= 2
                    mptr += 1
                else:
                    ret *= a[pptr] % mod
                    left -= 1
                    pptr -= 1
        else:
            ret = 0
            break
    else:
        if pptr >= 0 and a[pptr] > 0:
            left -= 1
            ret *= a[pptr] % mod
            pptr -= 1
        else:
            ret = 0
            break

if ret > 0:
    print(ret % mod)
else:
    a.sort(key=lambda x: abs(x))
    ret = 1
    for i in range(k):
        ret *= a[i] % (10 ** 9 + 7)
    print(ret % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import math  # noqa: F401
from collections import deque  # noqa: F401
from functools import lru_cache
from typing import Deque, Dict, List, Optional, Tuple, Union  # noqa: F401

MOD = 10 ** 9 + 7


@lru_cache(maxsize=None)
def max_product_subarray_of_size_k(A, n, k):
    # A.sort()
    product = 1

    if A[-1] == 0 and (k & 1):
        return 0

    if A[-1] <= 0 and (k & 1):
        for a in A[n - k : n]:
            product *= a
        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


def main(N: int, K: int, A: List[int]):
    x = max_product_subarray_of_size_k(tuple(sorted(A)), N, K)
    print(x % MOD)


if __name__ == "__main__":
    N, K = map(int, input().split())
    A: List[int] = list(map(int, input().split()))
    main(N, K, A)

Submission status: Time Limit Exceeded

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

MOD = 1000000007
val = False
ans = 0
for comb in itertools.combinations(a, k):
    tmp = 1
    for i in range(len(comb)):
        tmp *= comb[i]
        if abs(tmp)>MOD:
            tmp %= MOD
    if not val:
        ans = tmp
        val = True
    else:
        if tmp > ans:
            ans = tmp

if ans < 0:
    ans %= MOD
print (ans)

Submission status: Time Limit Exceeded

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

P,Q=[],[] #P,Q...+,-の要素
Z=0 #Z...0の個数

for a in A:
    if a>0:
        P.append(a)
    elif a<0:
        Q.append(a)
    else:
        Z+=1

P.sort(reverse=True)
X=[1]
for p in P:
    X.append(X[-1]*p)
    
Q.sort()
Y=[1]
for q in Q:
    Y.append(Y[-1]*q)

J=-1
S=len(P)
for m in range(0,len(Q)+1,2):
    if 0<=K-m<=S:
        J=max(J,X[K-m]*Y[m])

if J>0:
    print(J%M)
else:
    if Z==0:
        J=1
        for i in range(K):
            J*=Q[-(i+1)]
        print(J%M)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
n, k = map(int, input().split())
a_i = list(map(int, input().split()))
list.sort(a_i)
ans = 1
if k % 2 == 0:
    left = 0
    right = n - 1
else:
    left = 0
    right = n - 2
    ans *= a_i[n - 1]
for x in range(k // 2):
    if ans * a_i[left] * a_i[left + 1] < ans * a_i[right] * a_i[right - 1]:
        ans *= a_i[right] * a_i[right - 1]
        right -= 2
    else:
        ans *= a_i[left] * a_i[left + 1]
        left += 2
    if ans >= mod: ans %= mod
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
mod = 10**9+7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

pl = []
mn = []
zr = []

tmp = 1
cnt = 0

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mn.append(-x)
    else:
        zr.append(x)

pl = sorted(pl, reverse=True)
mn = sorted(mn, reverse=True)

ans = 0

if len(mn) >= k and k % 2:
    tmp = 1
    for i in range(1, k+1):
        tmp *= mn[-i]
    ans = -tmp

if len(zr) > 0:
    ans = max(0, ans)

pl_cum = [1]
for i, x in enumerate(pl):
    pl_cum.append(pl_cum[-1]*x)

mn_cum = [1]
for i, x in enumerate(mn):
    mn_cum.append(mn_cum[-1]*x)

for p in range(0, k+1, 2):
    if len(mn) < p:
        break
    if len(pl) >= k-p:
        ans = max(pl_cum[k-p]*mn_cum[p], ans)

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
def main():
    n, k = map(int, input().split())# 正0でコーナー
    a = list(map(int, input().split()))
    pos = []
    neg = []
    zero = []
    for v in a:
        if v == 0:
            zero.append(v)
        elif 0 < v:
            pos.append(v)
        else:
            neg.append(v)
    if len(pos) + len(neg) < k:
        print(0)
    else:
        if k%2 == 0:
            if len(pos) + len(neg) == k and len(pos) % 2 == 1:#負になる
                if len(zero) > 0:
                    print(0)
                else:
                    ans = 1
                    for v in pos:
                        ans *= v
                        ans %= MOD
                    for v in neg:
                        ans *= v
                        ans %= MOD
                    print(ans % MOD)
            else:
                pos.sort(reverse=True)
                neg.sort()
                for i in range(1, len(pos)):
                    pos[i] *= pos[i-1]
                for i in range(1, len(neg)):
                    neg[i] *= neg[i-1]
                ans = 0
                for i in range(0, k+1, 2):
                    if len(pos) < i or len(neg) < k-i:
                        continue
                    tmp = 1
                    if 0 < i:
                        tmp *= pos[i-1]
                    if 0 < k-i:
                        tmp *= neg[k-i-1]
                    if ans < tmp:
                        ans = tmp
                print(ans % MOD)
        else:
            if 0 == len(pos):
                if 0 < len(zero):
                    print(0)
                else:
                    neg.sort(reverse=True)
                    ans = 1
                    for i in range(k):
                        ans *= neg[i]
                        ans %= MOD
                    print(ans)
            else:
                pos.sort(reverse=True)
                neg.sort()
                for i in range(1, len(pos)):
                    pos[i] *= pos[i-1]
                for i in range(1, len(neg)):
                    neg[i] *= neg[i-1]
                ans = 0
                for i in range(1, k+1, 2):
                    if len(pos) < i or len(neg) < k-i:
                        continue
                    tmp = 1
                    if 0 < i:
                        tmp *= pos[i-1]
                    if 0 < k-i:
                        tmp *= neg[k-i-1]
                    if ans < tmp:
                        ans = tmp
                print(ans % MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#ちょうどK個
#絶対値の大きいものから選びたい
#正の数を1個選ぶ時,2個選ぶ時,…k個選ぶ時
#絶対値が小さいもの同士または絶対値が大きいもの同士
#負の時は絶対値小さいものk個
mod=10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
a1=[]
a2=[]
a3=[]
for i in range(n):
    if a[i]>0:
        a1.append(a[i])
    elif a[i]<0:
        a2.append(a[i])
    else:
        a3.append(a[i])
#絶対値の小さい順
a1.sort()
a2.sort(reverse=True)
ans=[]
if len(a3):
    ans.append(0)
from itertools import accumulate
suma11=list(accumulate(a1,lambda x,y:x*y))
suma12=list(accumulate(a1[::-1],lambda x,y:x*y))
suma21=list(accumulate(a2,lambda x,y:(x*y)))
suma22=list(accumulate(a2[::-1],lambda x,y:x*y))
#print(suma11)
#print(suma12)
#print(suma21)
#print(suma22)
#正の数の個数
l1=len(a1)
l2=len(a2)
for i in range(0,k+1):
    if i==0:
        if k<=l1:
            ans.append(suma12[k-1])
        continue
    if i==k:
        if k<=l2:
            ans.append(suma21[k-1])
        continue
    if i<=l1 and k-i<=l2:
        ans.append(suma11[i-1]*suma21[k-i-1])
        ans.append(suma12[i-1]*suma22[k-i-1])
print(max(ans)%mod)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
c = [int(i) for i in input().split()]
a = []
b = []
for i in c:
    if i >= 0:
        a.append(i)
    else:
        b.append(i)
a.sort()
a.reverse()
b.sort()
p = [1] * (len(a)+1)
m = [1] * (len(b)+1)

for i in range(len(a)):
    p[i+1] = p[i] * a[i]
for i in range(1, len(b)+1):
    if i == 1:
        m[i] = b[-1]
    elif i%2:
        m[i] = m[i-2] * b[-i+1] * b[-i]
    else:
        m[i] = m[i-2] * b[i-2] * b[i-1]

cand = []
for i in range(len(p)):
    if k-i >= 0 and k-i<len(m):
        cand.append(p[i]*m[k-i])
print(max(cand)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math  # noqa: F401
from collections import deque  # noqa: F401
from typing import Deque, Dict, List, Optional, Tuple, Union  # noqa: F401

MOD = 10 ** 9 + 7


def max_product_subarray_of_size_k(A, n, k):
    A.sort()
    product = 1

    if A[-1] == 0 and (k & 1):
        return 0

    if A[-1] <= 0 and (k & 1):
        for a in A[n - k : n]:
            product *= a
        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


def main(N: int, K: int, A: List[int]):
    x = max_product_subarray_of_size_k(A, N, K)
    print(x % MOD)


if __name__ == "__main__":
    N, K = map(int, input().split())
    A: List[int] = list(map(int, input().split()))
    main(N, K, A)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n,k=map(int,input().split())
a=list(map(int,input().split()))
p=list(permutations(a,k))
l=-1000000000000000001
for i in range(len(p)):
    x=1
    for j in range(k):
        x=x*p[i][j]
    l=max(l,x)
print(l%(1000000007))

Submission status: Time Limit Exceeded

Solution code:
def proc(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 % (10**9+7)
  
    # 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 A[-k:]: 
            product *= i
        return product % (10**9+7) 
  
    # 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 % (10**9+7)

n, k = map(int, input().split())
A = list(map(int, input().split()))
print((proc(A, n, k)))

Submission status: Time Limit Exceeded

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__": 
	
	n,k = input().split()
	n = int(n)
	k = int(k)
	A = list(map(int, input().split()))
	n = len(A) 
	print(maxProductSubarrayOfSizeK(A, n, k)%1000000007) 

# This code is contributed by ita_c

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from operator import mul

def funct(arr, k):
    if k > len(arr): return None
    
    if k == 1: return max(arr)
    
    if k == len(arr):
        prod = reduce(mul, arr)
        return prod
    
    arr = sorted(arr)
    prods = []
    for i in range(k+1):
        nums = arr[:k-i] + (arr[-i:] if i else [])
        prods.append(reduce(mul, nums))
    
    return max(prods)
n, k = map(int, input().split())
x = [int(x) for x in input().split()]
print(funct(x, k) % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
def funct(arr, k):
    n = len(arr)
    if (k>n):
        return None
    
    t_plus =[]
    t_minus = []
    res = []
    for to in arr:
        if (to==0):
            res.append(0)
        elif to>0:
            t_plus.append(to)
        else:
            t_minus.append(to)
            
    t_plus.sort()
    t_minus.sort()
    
    for to in t_plus:
        res.append(to)
    for to in t_minus:
        res.append(to)
    
    ans = 1
    
    for i in range(k):
        ans = ans*res[i];
        
    
    ans_max = ans
    
    for i in range(n-k+1):
        ans = 1
        for j in range(i,i+k):
            ans=ans*res[j]
            
        
        ans_max = max(ans,ans_max)
    
    
    return (ans_max)
n, k = map(int, input().split())
x = [int(x) for x in input().split()]
print(funct(x, k) % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from math import prod
n, k = map(int, input().split())
ln = list(map(int, input().split()))
l = list(combinations(ln, k))
MOD = 10**9+7
lans = []
for i in l:
    lans.append(prod(i))
print(max(lans)%MOD)

Submission status: Time Limit Exceeded

Solution code:
import math  # noqa: F401
from collections import deque  # noqa: F401
from typing import Deque, Dict, List, Optional, Tuple, Union  # noqa: F401

MOD = 10 ** 9 + 7


def max_product_subarray_of_size_k(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


def main(N: int, K: int, A: List[int]):
    x = max_product_subarray_of_size_k(A, N, K)
    print(x % MOD)


if __name__ == "__main__":
    N, K = map(int, input().split())
    A: List[int] = list(map(int, input().split()))
    main(N, K, A)