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:
import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
div = 10**9+7
a = sorted(A)
n_a = np.array(a)
plus = n_a[n_a >= 0]
minus = n_a[n_a < 0]
ans = 1
if K % 2 != 0 and len(plus) == 0:
    while K > 0:
        ans *= a.pop(-1)
        ans %= div
        K -= 1
    print(ans)
    exit()
while K > 0:
    if K >= 2 and a[0] * a[1] > a[-1] * a[-2]:
        ans *= a.pop(0)
        ans %= div
        ans *= a.pop(0)
        ans %= div
        K -= 2
    else:
        ans *= a.pop(-1)
        ans %= div
        K -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f(P,M):
    S=0
    K=1
    for p in P[::-1]:
        S+=K*p
        K*=M
    return S

def g(X,Y,M):
    a,b=len(X),len(Y)
    Q=[0]*(len(X)+len(Y)-1)

    X=X[::-1]
    Y=Y[::-1]
    for i in range(a):
        for j in range(b):
            Q[i+j]+=X[i]*Y[j]
    Q=Q[::-1]

    T=0
    for i in range(len(Q)-1,-1,-1):
        F=T+Q[i]
        T=F//M
        Q[i]=F%M

    if T==0:
        return Q
    else:
        return h(T,M)+Q
    
def h(N,M):
    W=[]
    while N>0:
        W=[N%M]+W
        N//=M
    return W

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(h(a,M))
    elif a<0:
        Q.append(h(-a,M))
    else:
        Z+=1

P.sort(reverse=True)
X=[[1]]
for p in P:
    X.append(g(X[-1],p,M))

Q.sort()
Y=[[1]]
for q in Q:
    Y.append(g(Y[-1],q,M))

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod=1000000007
    inv=lambda x: pow(x,mod-2,mod)
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    B=A[::-1]
    ans=1
    if A[-1]<=0:
        if k%2==0:
            for a in A[:k]:
                ans*=a
                ans%=mod
        else:
            for a in B[:k]:
                ans*=a
                ans%=mod
        return ans
    if n==k:
        for a in A:
            ans*=a
            ans%=mod
        return ans
    Neg=[]; Pos=[]
    zero=0
    for a in A:
        if a>0:
            Pos.append(a)
        elif a<0:
            Neg.append(a)
        else:
            zero+=1
    if zero>n-k:
        return 0
    pos=len(Pos); neg=len(Neg)
    if neg==0:
        for a in B[:k]:
            ans*=a
            ans%=mod
        return ans
    for _ in range(zero):
        Neg.append(0)
    Neg.reverse()
    Pos.reverse()
    cnt=k
    while cnt>pos:
        cnt-=2
    Pos=Pos[:cnt]
    for p in Pos:
        ans*=p
        ans%=mod
    for _ in range(k-cnt):
        ans*=Neg.pop()
    while len(Pos)>=2 and len(Neg)>=2:
        p1=Pos.pop()
        p2=Pos.pop()
        n1=Neg.pop()
        n2=Neg.pop()
        if p1*p2<=n1*n2:
            ans*=inv(p1)*inv(p2)
            ans*=n1
            ans%=mod
            ans*=n2
            ans%=mod
        else:
            break
    return ans
    
if __name__=='__main__':
    print(main())

Submission status: Time Limit Exceeded

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

A = list(map(int,input().split()))
#cumsum = [0]*(N+1)
mod = pow(10,9)+7

A.sort()
counter = 1
if A[N-1]<0:
    for i in range(N-1,N-K-1,-1):
        counter *= A[i]
    
    print(counter %mod)
    exit()
if K%2==0:
    num = K//2
    right = N
    left = -1
    for k in range(num):
        a = A[left+1]*A[left+2]
        b = A[right-1]*A[right-2]
        if a>=b:
            counter *= a
            left +=2
        else:
            counter *= b
            right -=2
    print(counter%mod)
else:
    num = K//2
    right = N
    left = -1
    for k in range(num):
        a = A[left+1]*A[left+2]
        b = A[right-1]*A[right-2]
        if a>=b:
            counter *= a
            left +=2
        else:
            counter *= b
            right -=2
    ok = counter * A[right-1]
    print(ok%mod)

Submission status: Time Limit Exceeded

Solution code:
import copy

mod = 1000000007

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

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

plus_1 = []

minus_1 = []

for i in a:
    if i > 0:
        plus_1.append(i)
    else:
        minus_1.append(i)

plus_2 = plus_1.copy()
minus_2 = minus_1.copy()

plus_1.sort(reverse=True)
minus_1.sort()
maxa = 1

plus_2.sort()
minus_2.sort(reverse=True)
mini = 1

i = 0

while i < k:
    if len(plus_1) > 1 and len(minus_1) > 1:
        if plus_1[0]*plus_1[1] < minus_1[0]*minus_1[1] and i+2<=k:
            maxa *= minus_1[0]*minus_1[1]
            minus_1.pop(0)
            minus_1.pop(0)
            i += 2
        else:
            maxa *= plus_1[0]
            plus_1.pop(0)
            i += 1
    elif len(plus_1):
        maxa *= plus_1[0]
        plus_1.pop(0)
        i += 1
    else:
        maxa *= minus_1[0]
        minus_1.pop(0)
        i += 1

i = 0

while i < k:
    if len(plus_2) and len(minus_2):
        if plus_2[0] < abs(minus_2[0]):
            mini *= plus_2[0]
            plus_2.pop(0)
        else:
            mini *= minus_2[0]
            minus_2.pop(0)
    elif len(plus_2):
        mini *= plus_2[0]
        plus_2.pop(0)
    else:
        mini *= minus_2[0]
        minus_2.pop(0)
    i += 1

if maxa > 0:
    print(maxa%mod)
else:
    print(mini%mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
div = 10**9+7
a = sorted(A)
n_a = np.array(sorted(A))
plus = n_a[n_a >= 0]
minus = n_a[n_a < 0]
ans = 1
if K % 2 != 0 and len(plus) == 0:
    while K > 0:
        ans *= a.pop(-1)
        ans %= div
        K -= 1
    print(ans)
    exit()
while K > 0:
    if K >= 2 and a[0] * a[1] > a[-1] * a[-2]:
        ans *= a.pop(0)
        ans %= div
        ans *= a.pop(0)
        ans %= div
        K -= 2
    else:
        ans *= a.pop(-1)
        ans %= div
        K -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun May  3 16:22:00 2020

@author: neb0123
"""

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

if __name__ == "__main__":
    N,K = map(int, input().split(' '))
    A = list(map(int,input().split(' ')))
    print(maxProductSubarrayOfSizeK(A,N,K) % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
n,k=input().split()
n=int(n)
k=int(k)
a=input().split()
for i in range(n):
  a[i]=int(a[i])
  
for j in range(n):
  for l in range(n-j):
    if a[j]<a[j+l]:
      x=a[j]
      a[j]=a[j+l]
      a[j+l]=x
      
f=1;
e=1;
for q in range(k):
  f=f*a[q]
  e=e*a[n-q-1]
  
r=0
if e>f:
  r=e
if f>=e:
  r=f
r=r%1000000007
print(r)

Submission status: Time Limit Exceeded

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

resolve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
div = 10**9+7
a = sorted(A)
n_a = np.array(sorted(A))
plus = n_a[n_a >= 0]
minus = n_a[n_a < 0]
ans = 1
if K % 2 != 0 and len(plus) == 0:
    while K > 0:
        ans *= a.pop(-1)
        ans %= div
        K -= 1
    print(ans%div)
    exit()
while K > 0:
    if K >= 2 and a[0] * a[1] > a[-1] * a[-2]:
        ans *= a.pop(0)
        ans *= a.pop(0)
        ans %= div
        K -= 2
    else:
        ans *= a.pop(-1)
        ans %= div
        K -= 1
print(ans%div)

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):
        ml_number = ml_number * num
    if i == 1:
        max_number = ml_number
    else:
        max_number = max(max_number, ml_number)
    ml_number = 1
print(max_number % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, K = map(int, input().split())
a_list = list(map(int, input().split()))
a_list = deque(sorted(a_list))
MOD = 10**9 + 7
 
 
def choose1():
    l = 1
    if a_list[-1]*a_list[-2] >= a_list[0]*a_list[1]:
        l *= a_list.popleft()
        l *= a_list.popleft()
    else:
        l *= a_list.pop()
        l *= a_list.pop()
    return l

def choose2():
    l = 1
    if a_list[-1]*a_list[-2] >= a_list[0]*a_list[1]:
        l *= a_list.pop()
        l *= a_list.pop()
    else:
        l *= a_list.popleft()
        l *= a_list.popleft()
    return l
 
 
ans = 1
if K == 1:
    print(a_list[-1]%MOD)
    exit()
else:
    if K % 2 == 0:
        for _ in range(K//2):
            ans *= choose2() % MOD
    else:
        ans *= a_list.pop()
        if ans < 0:
            for _ in range((K-1)//2):
                ans *= choose1() % MOD
        else:
            for _ in range((K-1)//2):
                ans *= choose2() % MOD
 
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int, input().split())
A_list = list(map(int, input().split()))
A_list.sort()
result_list = []

tmp = -1 * np.inf
for i in range(K+1):#
    mi_r = 1
    for mi in range(i):
        mi_r *= A_list[mi]
        
    pl_r = 1
    
    for pl in range(K-i):
        pl_r *= A_list[-pl-1]
    if (mi_r * pl_r) > tmp:
        tmp = mi_r * pl_r
    
print(tmp % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    ans = [-float('inf'),0]
    mod = 10**9+7
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    minus = []
    plus = []
    for i in range(N):
        if A[i]>=0:
            plus.append(A[i])
        else:
            minus.append(A[i])
    plus.sort()
    minus.sort(reverse=True)
    p = len(plus)
    m = len(minus)
    plus_large = [[0,1] for _ in range(p+1)]
    plus_small = [[0,1] for _ in range(p+1)]
    minus_large = [[0,1] for _ in range(m+1)]
    minus_small = [[0,1] for _ in range(m+1)]
    for i in range(p):
        plus_large[i+1][1] = plus_large[i][1]*plus[p-i-1]%mod
        plus_large[i+1][0] = plus_large[i][0]*plus[p-i-1]+plus_large[i][1]*plus[p-i-1]//mod
        plus_small[i+1][1] = plus_small[i][1]*plus[i]%mod
        plus_small[i+1][0] = plus_small[i][0]*plus[i]+plus_small[i][1]*plus[i]//mod
    for i in range(m):
        minus_large[i+1][1] = minus_large[i][1]*minus[m-i-1]%mod
        minus_large[i+1][0] = minus_large[i][0]*minus[m-i-1]+minus_large[i][1]*minus[m-i-1]//mod
        minus_small[i+1][1] = minus_small[i][1]*minus[i]%mod
        minus_small[i+1][0] = minus_small[i][0]*minus[i]+minus_small[i][1]*minus[i]//mod
    
    for mi in range(K+1): 
        pl = K-mi
        if p>=K-mi and m>=mi:
            if mi%2==0: #正の数
                a,b = plus_large[pl]
                c,d = minus_large[mi]
            else: #負の数
                a,b = plus_small[pl]
                c,d = minus_small[mi]
            f = b*d%mod
            e = a*c*mod + b*c + a*d + b*d//mod
            if e>ans[0] or (e==ans[0] and f>ans[1]):
                ans = [e,f]
    return ans[1]
print(solve())

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = input_ints()
    A = input_int_list_in_line()

    Ap = []
    An = []
    Az = []
    for a in A:
        if a == 0:
            Az.append(a)
        elif a > 0:
            Ap.append(a)
        else:
            An.append(a)

    if len(An) == N and K % 2 == 1:
        An.sort(reverse=True)
        prod = 1
        for i in An[:K]:
            prod *= i

        print_ans(prod)
        exit()

    if len(Ap) == 0 and K % 2 == 1:
        print(0)
        exit()

    if N - len(Az) < K:
        print(0)
        exit()

    if N == K:
        prod = 1
        for i in A:
            prod *= i

        print_ans(prod)
        exit()

    if K == 1:
        print_ans(max(A))
        exit()

    prod = 1

    An.sort(reverse=False)
    Ap.sort(reverse=True)

    if len(An) % 2 == 1:
        An.pop(-1)

    An2 = []

    for i in range(len(An) // 2):
        An2.append(An[i*2] * An[i*2 + 1])

    i = 0
    j = 0

    while K > 0:
        if j not in range(len(An2)):
            prod = (prod * Ap[i])
            i += 1
            K -= 1
            continue

        if i not in range(len(Ap)):
            prod = (prod * An2[j])
            j += 1
            K -= 2
            continue

        if K >= 2 and (i+1) in range(len(Ap)) and Ap[i] * Ap[i+1] < An2[j]:
            prod = (prod * An2[j])
            j += 1
            K -= 2
            continue
        else:
            prod = (prod * Ap[i])
            i += 1
            K -= 1
            continue

    print_ans(prod)


def print_ans(n: int):
    print(n % (10**9 + 7))


def input_ints():
    line_list = input().split()

    if len(line_list) == 1:
        return int(line_list[0])
    else:
        return map(int, line_list)


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


def input_int_tuple_list(n: int):
    return [tuple(map(int, input().split())) for _ in range(n)]


main()

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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


p = []

for b in combinations(a, k):
    s = 1
    for i in range(k):
        s *= b[i]
    p.append(s)

p.sort(reverse = True)

print(p[0]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

ans = 1
a.sort()

check = (n for n in a if n > 0)
check = list(check)
azero = (n for n in a if n != 0)
azero = list(azero)

if len(azero) < k:
    print(0)
    sys.exit()

if len(check)!= 0:
    if k%2 == 1:
        ans = ans*a[-1]
        del a[-1]
        k -= 1
elif len(check) == 0 and k%2 == 1:
    for i in range(k):
        ans *= a[-i-1]
    print(ans%(10**9+7))
    sys.exit()
    
while k >= 2:
    if a[0]*a[1]> a[-1]*a[-2]:
        ans *= a[0]*a[1]
        del a[0:2]
        k -= 2
    else:
        ans *= a[-1]*a[-2]
        del a[-2:]
        k -= 2

print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
div = 10**9+7
a = sorted(A)
n_a = np.array(sorted(A))
plus = n_a[n_a >= 0]
minus = n_a[n_a < 0]
ans = 1
if K % 2 != 0 and len(plus) == 0:
    while K > 0:
        ans *= a.pop(-1)
        K -= 1
    print(ans%div)
    exit()
while K > 0:
    if K >= 2 and a[0] * a[1] > a[-1] * a[-2]:
        ans *= a.pop(0)
        ans *= a.pop(0)
        K -= 2
    else:
        ans *= a.pop(-1)
        K -= 1
print(ans%div)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import log2
from itertools import accumulate
from decimal import Decimal

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

N, K = MAP()
A = LIST()

A1 = []
A2 = []
B1 = []
B2 = []
zero = 0
for a in A:
    if a > 0:
        A1.append(a)
        B1.append(Decimal(a).log10())
    elif a < 0:
        A2.append(-a)
        B2.append(Decimal(-a).log10())
    else:
        zero += 1

A1.sort()
A2.sort()
B1.sort()
B2.sort()
acc1 = [0] + list(accumulate(B1))
accrev1 = [0] + list(accumulate(B1[::-1]))
acc2 = [0] + list(accumulate(B2))
accrev2 = [0] + list(accumulate(B2[::-1]))
mx = -INF
mn = INF
idx1 = (-1, -1)
idx2 = (-1, -1)
for i in range(K+1):
    j = K - i
    if len(B1) < i or len(B2) < j:
        continue
    if j % 2 == 0:
        sm = accrev1[i] + accrev2[j]
        if sm > mx:
            mx = sm
            idx1 = (i, j)
    else:
        sm = acc1[i] + acc2[j]
        if sm < mn:
            mn = sm
            idx2 = (i, j)

if mx != -INF:
    ans = 1
    n, m = idx1
    A1.reverse()
    A2.reverse()
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)
elif zero:
    print(0)
else:
    ans = 1
    n, m = idx2
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
data = [[abs(i), i < 0] for i in a]
all_minus = 0
for t in data:
    if t[1]:
        all_minus += 1
if all_minus == n:
    ans = 1
    data.sort()
    for i in range(k):
        ans = ans * data[i][0]
    print(-ans % mod)
    exit()
data.sort(reverse=True)
last_minus = 0
last_plus = 0
ans = 1
minus_amount = 0
for i in range(k):
    elem, sign = data[i][0], data[i][1]
    if elem == 0:
        print(0)
        exit()
    ans = ans * elem % mod
    minus_amount += sign
    if sign:
        last_minus = elem
    else:
        last_plus = elem
if minus_amount % 2 == 0:
    print(ans%mod)
    exit()
if n==k:
    print(-ans % mod)
    exit()
tmp_plus = 0
tmp_minus = 0
for i in range(k, n):
    elem, sign = data[i][0], data[i][1]
    if last_plus and sign and not tmp_minus:
        tmp_minus = elem
    elif last_minus and not sign and not tmp_plus:
        tmp_plus = elem
if tmp_plus == 0 and tmp_minus == 0:
    ans = 0
elif last_plus == 0:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
elif last_minus == 0:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
elif tmp_plus * last_plus > tmp_minus * last_minus:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
else:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7
A=sorted(A)
if K==1:
    print(A[-1]%mod)
else:
    ans=1
    A=deque(A)
    if A[-1]<0 and K%2==1:
        for i in range(K):
            ans*=A[-1]
            A.pop()
    else:
        while K>=2:
            if A[0]*A[1]>=A[-1]*A[-2]:
                ans*= A[0]*A[1]
                K-=2
                A.popleft()
                A.popleft()
            else:
                ans*=A[-1]*A[-2]
                K-=2
                A.pop()
                A.pop()
        if K==1:
            if A[0]>=A[-1]:
                ans*=A[0]
            else:
                ans*=A[-1]
    
    print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a=input()
al=[int(i) for i in a.split()]
al.sort()
plus=sum([1 for x in al if x>0])
minus=sum([1 for x in al if x<0])
zero=n-plus-minus
f=0
if n==minus and round(k/2)-k/2!=0:
    f=1
if zero==0 and round(minus/2)-minus/2!=0 and n==k:
    f=1
a=1
if f==0:
    for i in range(math.floor(k/2)):
        a1=al[0]*al[1]
        a2=al[-1]*al[-2]
        if a1>=a2:
            a*=a1
            del al[0]
            del al[0]
        else:
            a*=a2
            del al[-1]
            del al[-1]
        a=a%(10**9+7)
    if math.floor(k/2)-k/2!=0:
            a*=max(al)
    print(a%(10**9+7))
else:
    def checkio(al):
        return sorted(al, key=abs)
    al=checkio(al)
    for i in range(k):
        a*=al[i]
        a=a%(10**9+7)
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import itertools
m = []
data = []
n = input()
n = n.split()
N = int(n[0])
K = int(n[1])

da = input()
d = da.split()
for i in d:
    data.append(int(i))
for v in itertools.combinations(data, K):
    s = 1
    for j in v:
        s *= j
    m.append(s)
mm = max(m)
if mm < 0 or mm > (10**9 + 6):
    mm = mm % (10**9 + 7)
print(mm)

Submission status: Time Limit Exceeded

Solution code:

import itertools

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

for comb in itertools.combinations(a, k):
    mul = comb[0]
    if len(comb) > 1:
        for i in range(1,len(comb)):
            mul = mul*comb[i]
    if flag:
        mul_max = mul
        flag = 0
        continue
    if mul_max < mul:
        mul_max = mul

print(mul_max % (1000000007))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

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

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

res = -float('inf')
for v in itertools.permutations(a, k):
  if np.prod(v) > res:
    res = np.prod(v)
print(int(res%(10**9+7)))

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()
            heapq.heappush(AA, -a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            heapq.heappush(AA, -a1 * a2)
        ans = 1

        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()
            heapq.heappush(AA, -a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            heapq.heappush(AA, -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:
N, K = map(int, input().split())
A_list = list(map(int, input().split()))
A_list.sort()
result_list = []
for i in range(K+1):#
    mi_r = 1
    for mi in range(i):
        mi_r *= A_list[mi]
        
    pl_r = 1
    for pl in range(K-i):
        pl_r *= A_list[-pl-1]
    result_list.append(mi_r * pl_r)
    
print(max(result_list) % 1000000007)

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 = (ans*A[-1]) % (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 = (ans*A[-1]) % (10**9+7)
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
num = input().rstrip().split(" ")
line = list(map(int, input().split(" ")))
import itertools
lis = [list(a) for a in itertools.combinations(line, int(num[1]))]
count = len(lis)
count2 = len(lis[0])
ans_l = []
cul = 1
for i in range(count):
    for j in range(count2):
        cul *= int(lis[i][j])
    ans_l.append(cul)
    cul = 1
ans_s = sorted(ans_l,reverse = True)
ans = ans_s[0]
z = ans % (10**9 + 7)
print(z)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations as co
n,k=map(int,input().split())
a=list(map(int,input().split()))
m=float("-inf")
for c in co(a,k):
  p=1
  for i in c:
    p*=i
  m=max(m,p)
print(m%(10**9+7))

Submission status: Time Limit Exceeded

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

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	n, k = map(int, sys.stdin.readline().split())
	a = list(map(int, sys.stdin.readline().split()))
	a.sort(reverse=True)
	
	minus = list(filter(lambda x:x<0, a))
	minus.reverse()
	zero = list(filter(lambda x:x==0, a))
	natural = list(filter(lambda x:x>0, a))

	minus_mul = [1]
	for i in range(len(minus)):
		minus_mul.append(minus_mul[-1] * minus[i])

	natural_mul = [1]
	for i in range(len(natural)):
		natural_mul.append(natural_mul[-1] * natural[i])

	log.print(minus, zero, natural)
	ans = -float("inf")
	if k == 1:
		print(a[0])
		exit()
	mul = 1
	for i in range(k):
		mul *= a[i]
	ans = max(ans, mul)
	if len(natural_mul) > k:
		mul = natural_mul[k]
		ans = max(ans, mul)
	if len(minus_mul) > k:
		mul = minus_mul[k]
		ans = max(ans, mul)
	if k % 2 == 0:
		for i in range(0, k, 2):
			if len(natural_mul) <= i or len(minus_mul) <= k-i:
				continue
			log.print(natural_mul[i], minus_mul[k-i])
			mul = natural_mul[i] * minus_mul[k-i]
			ans = max(ans, mul)
	else:
		for i in range(0, k, 2):
			if len(natural_mul) <= k-i or len(minus_mul) <= i:
				continue
			log.print(natural_mul[k-i], minus_mul[i])
			mul = natural_mul[k-i] * minus_mul[i]
			ans = max(ans, mul)

	print(ans % (10**9+7))





main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
arr = list(map(int, input().split()))
mod = 10**9 + 7
def maxProductFinderK(array, k):
  data = list(array)
  data.sort(reverse=True)    
  variants = []
  for n in range(0, k+1, 2):
    mult = 1;
    for idx in range(-n, k-n):
      mult *= data[idx]
    variants.append(mult)
  return max(variants) % mod
print(maxProductFinderK(arr, k))

Submission status: Time Limit Exceeded

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