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:
_MULTITEST = False
##
def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    neg = sum(1 for x in a if x < 0)
    pos = sum(1 for x in a if x > 0)
    zeroes = a.count(0)
    
    ### Set lower bound for answer
    ans = 0
    if pos == 0:
        if zeroes == 0:
            ans = -1 * (10**16)
    
    ### Solve by window-sliding
    # set some initial vars
    prod = 1
    zero_counter = 0
    for i in range(n-1, n-1-k, -1):
        if a[i] == 0:
            zero_counter += 1
        else:
            prod *= a[i]
    if zero_counter > 0:
        ans = max(ans, 0)
    else:
        ans = max(ans, prod)
    
    # sliding
    p1 = 0
    p2 = (n-k)
    while p2 < n:
        if a[p1] == 0:
            zero_counter += 1
        else:
            prod *= a[p1]
        if a[p2] == 0:
            zero_counter -= 1
        else:
            prod //= a[p2]
        p1 += 1; p2 += 1;
        if zero_counter > 0:
            ans = max(ans, 0)
        else:
            ans = max(ans, prod)
    
    ###
    #print(ans)
    print(ans % (10**9 + 7))


##
if __name__ == "__main__":
    t = (int(input()) if _MULTITEST else 1)
    for tt in range(t):
        solve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import math
import numpy as np

# 標準入力を取得
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

# 求解処理
S = [a for a in A if a >= 0]
T = [a for a in A if a < 0]
can_plus = True
if len(S) > 0:
    if (N == K) and (len(T) % 2 == 1):
        can_plus = False
if len(S) == 0:
    if K % 2 == 1:
        can_plus = False

ans = 1
if can_plus:
    S = sorted(S, key=abs, reverse=True)
    T = sorted(T, key=abs, reverse=True)
    if K % 2 == 1:
        ans *= S[0]
        S = S[1:]
    S = [S[2 * i] * S[2 * i + 1] for i in range(len(S) // 2)]
    T = [T[2 * i] * T[2 * i + 1] for i in range(len(T) // 2)]
    L = []
    L.extend(S)
    L.extend(T)
    L = sorted(L, reverse=True)
    for l in L[:K // 2]:
        ans *= l
else:
    A = sorted(A, key=abs)
    for a in A[:K]:
        ans *= a
ans %= pow(10, 9) + 7

# 結果出力
print(ans)

Submission status: Time Limit Exceeded

Solution code:
_MULTITEST = False
##
def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    neg = [x for x in a if x < 0]
    pos = [x for x in a if x > 0]
    zeroes = a.count(0)
    #
    neg.sort()
    pos.sort()
    
    ### Set lower bound for answer
    ans = 0
    if len(pos) == 0:
        if zeroes == 0:
            ans = -1 * (10**16)
    
    ### Solve by window-sliding
    # set some initial vars
    prod = 1
    zero_counter = 0
    for i in range(n-1, n-1-k, -1):
        if a[i] == 0:
            zero_counter += 1
        else:
            prod *= a[i]
    if zero_counter > 0:
        ans = max(ans, 0)
    else:
        ans = max(ans, prod)
    
    # sliding
    p1 = 0
    p2 = (n-k)
    while p2 < n:
        if a[p1] == 0:
            zero_counter += 1
        else:
            prod *= a[p1]
        if a[p2] == 0:
            zero_counter -= 1
        else:
            prod //= a[p2]
        p1 += 1; p2 += 1;
        if zero_counter > 0:
            ans = max(ans, 0)
        else:
            ans = max(ans, prod)
    
    ###
    #print(ans)
    print(ans % (10**9 + 7))


##
if __name__ == "__main__":
    t = (int(input()) if _MULTITEST else 1)
    for tt in range(t):
        solve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul  5 21:49:24 2020

@author: NEC-PCuser
"""

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

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

A.sort()

minus_list = []
plus_list = []
for i in range(len(A)):
    if (A[i] <= 0):
        minus_list.append(A[i])
    else:
        plus_list.append(A[i])

ans = 1
mod = 10 ** 9 + 7   
if N == K:
    for i in A:
        ans = (ans * i) % mod
elif 0 == len(plus_list) and  K % 2 == 1:
    minus_list.sort(reverse=True)
    for i in range(K):
        ans = (ans * minus_list[i]) % mod
else:
    minus_list.sort()
    plus_list.sort(reverse=True)
    if K % 2 == 1:
        ans = plus_list.pop(0)
    for i in range(K // 2):
        if (len(plus_list) < 2):
            ans = (minus_list[0] * ans) % mod
            ans = (minus_list[1] * ans) % mod
            minus_list = minus_list[2:]
        elif (len(minus_list) < 2):
            ans = (plus_list[0] * ans) % mod
            ans = (plus_list[1] * ans) % mod
            plus_list = plus_list[2:]
        elif (plus_list[0] * plus_list[1] > minus_list[0] * minus_list[1]):
            ans = (plus_list[0] * ans) % mod
            ans = (plus_list[1] * ans) % mod
            plus_list = plus_list[2:]
        else:
            ans = (minus_list[0] * ans) % mod
            ans = (minus_list[1] * ans) % mod
            minus_list = minus_list[2:]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul  5 21:49:24 2020

@author: NEC-PCuser
"""

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

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

A.sort()

minus_list = []
plus_list = []
for i in range(len(A)):
    if (A[i] <= 0):
        minus_list.append(A[i])
    else:
        plus_list.append(A[i])

ans = 1
mod = 10 ** 9 + 7   
if N == K:
    for i in A:
        ans = (ans * i) % mod
elif 0 == len(plus_list) and  K % 2 == 1:
    minus_list.sort(reverse=True)
    for i in range(K):
        ans = (ans * minus_list[i]) % mod
else:
    minus_list.sort()
    plus_list.sort(reverse=True)
    if K % 2 == 1:
        ans = plus_list.pop(0)
    for i in range(K // 2):
        if (len(plus_list) < 2):
            ans = (minus_list.pop(0) * ans) % mod
            ans = (minus_list.pop(0) * ans) % mod
        elif (len(minus_list) < 2):
            ans = (plus_list.pop(0) * ans) % mod
            ans = (plus_list.pop(0) * ans) % mod
        elif (plus_list[0] * plus_list[1] > minus_list[0] * minus_list[1]):
            ans = (plus_list.pop(0) * ans) % mod
            ans = (plus_list.pop(0) * ans) % mod
        else:
            ans = (minus_list.pop(0) * ans) % mod
            ans = (minus_list.pop(0) * ans) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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

    MOD = 10 ** 9 + 7

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

    flag = False  # 積を正にできるか

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

    if len(pos) > 0:
        flag = True
    else:
        if K % 2 == 0:
            flag = True

    ans = 1
    if not flag:
        # 積を正にできないとき
        # 絶対値の小さい方からK個とる
        h = [abs(x) for x in A]
        heapq.heapify(h)

        for i in range(K):
            ans *= heapq.heappop(h)
            ans %= MOD
        ans *= -1
    else:
        hpos = [-x for x in pos]
        heapq.heapify(hpos)
        hneg = neg[:]
        heapq.heapify(hneg)
        if K % 2 == 1:
            # Kが奇数の時
            # 一番大きい偶数を1つとる。
            ans *= -heapq.heappop(hpos)
            ans %= MOD

        # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
        pairs = []
        while len(hpos) >= 2:
            x = -heapq.heappop(hpos)
            x *= -heapq.heappop(hpos)
            heapq.heappush(pairs, -x)
        while len(hneg) >= 2:
            x = heapq.heappop(hneg)
            x *= heapq.heappop(hneg)
            heapq.heappush(pairs, -x)
        if len(pairs):
            for i in range(K // 2):
                ans *= -heapq.heappop(pairs)
                ans %= MOD

    print(ans % MOD)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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

    MOD = 10 ** 9 + 7

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

    flag = False  # 積を正にできるか

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

    if len(pos) > 0:
        flag = True
    else:
        if K % 2 == 0:
            flag = True

    ans = 1
    if not flag:
        # 積を正にできないとき
        # 絶対値の小さい方からK個とる
        h = [abs(x) for x in A]
        heapq.heapify(h)

        for i in range(K):
            ans *= heapq.heappop(h)
        ans *= -1
    else:
        hpos = [-x for x in pos]
        heapq.heapify(hpos)
        hneg = neg[:]
        heapq.heapify(hneg)
        if K % 2 == 1:
            # Kが奇数の時
            # 一番大きい偶数を1つとる。
            ans *= -heapq.heappop(hpos) % MOD

        # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
        pairs = []
        while len(hpos) >= 2:
            x = -heapq.heappop(hpos)
            x *= -heapq.heappop(hpos)
            heapq.heappush(pairs, -x)
        while len(hneg) >= 2:
            x = heapq.heappop(hneg)
            x *= heapq.heappop(hneg)
            heapq.heappush(pairs, -x)
        if len(pairs):
            for i in range(K // 2):
                ans *= -heapq.heappop(pairs) % MOD

    print(ans % MOD)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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

    MOD = 10 ** 9 + 7

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

    flag = False  # 積を正にできるか

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

    if len(pos) > 0:
        flag = True
    else:
        if K % 2 == 0:
            flag = True

    ans = 1
    if not flag:
        # 積を正にできないとき
        # 絶対値の小さい方からK個とる
        h = [abs(x) for x in A]
        heapq.heapify(h)

        for i in range(K):
            ans *= heapq.heappop(h)
        ans *= -1
    else:
        hpos = [-x for x in pos]
        heapq.heapify(hpos)
        hneg = neg[:]
        heapq.heapify(hneg)
        if K % 2 == 1:
            # Kが奇数の時
            # 一番大きい偶数を1つとる。
            ans *= -heapq.heappop(hpos) % MOD

        # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
        pairs = []
        while len(hpos) >= 2:
            x = -heapq.heappop(hpos)
            x *= -heapq.heappop(hpos)
            pairs.append(x)
        while len(hneg) >= 2:
            x = heapq.heappop(hneg)
            x *= heapq.heappop(hneg)
            pairs.append(x)
        pairs = sorted(pairs, reverse=True)
        for p in pairs[: K // 2]:
            ans *= p % MOD

    print(ans % MOD)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import functools
import operator

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

arr = [int(x) for x in input().split()]

#print(arr)

mx_list = []

for x in itertools.combinations(arr, K):
    #print(x)
    mx_list.append(functools.reduce(operator.mul,x))

mx = max(mx_list)

y = (10**9 + 7)

print(mx % y)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

    MOD = 10 ** 9 + 7

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

    flag = False  # 積を正にできるか

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


    if len(pos) > 0:
        flag = True
    else:
        if K % 2 == 0:
            flag = True

    ans = 1
    if not flag:
        # 積を正にできないとき
        # 絶対値の小さい方からK個とる
        A = sorted([abs(x) for x in A])
        for a in A[:K]:
            ans *= a % MOD
        ans *= -1
    else:
        pos = sorted(pos)
        neg = sorted(neg, reverse=True)
        if K % 2 == 1:
            # Kが奇数の時
            # 一番大きい偶数を1つとる。
            ans *= pos.pop() % MOD

        # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
        pairs = []
        while len(pos) >= 2:
            x = pos.pop()
            x *= pos.pop()
            pairs.append(x)
        while len(neg) >= 2:
            x = neg.pop()
            x *= neg.pop()
            pairs.append(x)
        pairs = sorted(pairs, reverse=True)
        for p in pairs[: K // 2]:
            ans *= p % MOD

    print(ans % MOD)

    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

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

flag = False  # 積を正にできるか

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


if len(pos) > 0:
    flag = True
else:
    if K % 2 == 0:
        flag = True

ans = 1
if not flag:
    # 積を正にできないとき
    # 絶対値の小さい方からK個とる
    A = sorted([abs(x) for x in A])
    for a in A[:K]:
        ans *= a % MOD
    ans *= -1
else:
    pos = sorted(pos)
    neg = sorted(neg, reverse=True)
    if K % 2 == 1:
        # Kが奇数の時
        # 一番大きい偶数を1つとる。
        ans *= pos.pop() % MOD

    # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
    pairs = []
    while len(pos) >= 2:
        x = pos.pop()
        x *= pos.pop()
        pairs.append(x)
    while len(neg) >= 2:
        x = neg.pop()
        x *= neg.pop()
        pairs.append(x)
    pairs = sorted(pairs, reverse=True)
    for p in pairs[: K // 2]:
        ans *= p % MOD

print(ans % MOD)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

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

flag = False  # 積を正にできるか

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


if len(pos) > 0:
    flag = True
else:
    if K % 2 == 0:
        flag = True

ans = 1
if not flag:
    # 積を正にできないとき
    # 絶対値の小さい方からK個とる
    A = sorted([abs(x) for x in A])
    for a in A[:K]:
        ans *= a % MOD
    ans *= -1
else:
    pos.sort()
    neg.sort(reverse=True)
    if K % 2 == 1:
        # Kが奇数の時
        # 一番大きい偶数を1つとる。
        ans *= pos.pop() % MOD

    # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
    pairs = []
    while len(pos) >= 2:
        x = pos.pop()
        x *= pos.pop()
        pairs.append(x)
    while len(neg) >= 2:
        x = neg.pop()
        x *= neg.pop()
        pairs.append(x)
    pairs = sorted(pairs, reverse=True)
    for p in pairs[: K // 2]:
        ans *= p % MOD

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()
n,k = MI()
a = LI()
x = []
y = []
for i in range(n):
	if a[i]<0:
		x.append(a[i])
	else:
		y.append(a[i])
x2 = []
x.sort()
x3 = []
pro = 1
for i in range(0,len(x)):
	pro*=x[i]
	x2.append(pro)
x = x[:][::-1]
pro = 1
for i in range(0,len(x)):
	pro*=x[i]
	x3.append(pro)
y.sort(reverse  = True)
y2 = []
pro = 1
for i in range(len(y)):
	pro*=y[i]
	y2.append(pro)
l1 = len(x2)
l2 = len(y2)
m = -10**9-7
for i in range(-1,l1):
	if i+1>k:
		break
	if i == -1:
		if l2>=k:
			m = max(m,y2[k-1])
	else:
		if l2>=k-i-1:
			if k-i-2>=0:
				m = max(m,x2[i]*y2[k-i-2])
			else:
				m = max(m,x2[i])
for i in range(-1,l1):
	if i+1>k:
		break
	if i == -1:
		if l2>=k:
			m = max(m,y2[k-1])
	else:
		if l2>=k-i-1:
			if k-i-2>=0:
				m = max(m,x3[i]*y2[k-i-2])
			else:
				m = max(m,x3[i])
print(m%(10**9+7))

Submission status: Time Limit Exceeded

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

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = []
c = []
for x in a:
    if x > 0:
        b.append(x)
    elif x < 0:
        c.append(-x)
flg = 0
if len(b):
    if n == k:
        if len(c) % 2 == 0:
            flg = 1
    else:
        flg = 1
else:
    if k % 2 == 0:
        flg = 1
ans = 0
mod = 1000000007
if flg:
    if len(b) + len(c) < k:
        pass
    else:
        b.sort()
        b.reverse()
        c.sort()
        c.reverse()
        for i in range(1, len(b)):
            b[i] *= b[i - 1]
        for i in range(1, len(c)):
            c[i] *= c[i - 1]
        # print(' '.join(map(str, c)))
        for i in range(0, n):
            x = 1
            cnt = 2 * i + (k % 2)
            if cnt < 0 or cnt > len(b):
                continue
            if cnt:
                x = b[cnt - 1]
            cnt2 = k - cnt
            if cnt2 < 0 or cnt2 > len(c):
                continue
            if cnt2:
                print
                x = x * c[cnt2 - 1]
            ans = max(ans, x)
            # print(ans)
        ans = ans % mod
        ans = ans + mod
        ans = ans % mod
else:
    if len(b) + len(c) != n:
        pass
    else:
        for i in range(0, n):
            if a[i] < 0:
                a[i] = -a[i]
        a.sort()
        ans = 1
        for i in range(0, k):
            ans *= a[i]
            # print(a[i], ans)
        ans = -ans
        ans = ans % mod
        ans = ans + mod
        ans = ans % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
t=1
mod=10**9+7
while t:
	t-=1
	n,k=map(int,input().split())
	l=list(map(int,input().split()))
	l.sort()
	if l[n-1]==0 and k&1:
		print(0)
		continue
	if l[n-1]<0 and k&1:
		prod=1
		for i in range(n-1,n-k-1,-1):
			prod*=l[i]
		print(prod%mod)
		continue
	prod=1
	i,j=0,n-1
	if k&1:
		prod=l[n-1]
		j-=1
		k-=1
	k//=2
	for _ in range(k):
		lprod=l[i]*l[i+1]
		rprod=l[j]*l[j-1]
		if lprod>rprod:
			i+=2
			prod*=lprod
		else:
			j-=2
			prod*=rprod
	print(prod%mod)

Submission status: Time Limit Exceeded

Solution code:
t=1
mod=10**9+7
while t:
	t-=1
	n,k=map(int,input().split())
	l=list(map(int,input().split()))
	l.sort()
	if l[n-1]==0 and k&1:
		print(0)
		continue
	if l[n-1]<0 and k&1:
		prod=1
		for i in range(n-1,n-k-1,-1):
			prod*=l[i]
		print(prod%mod)
		continue
	prod=1
	i,j=0,n-1
	if k&1:
		prod=l[n-1]
		j=n-2
	k//=2
	for _ in range(k):
		lprod=l[i]*l[i+1]
		rprod=l[j]*l[j-1]
		if lprod>rprod:
			i+=2
			prod*=lprod
		else:
			j-=2
			prod*=rprod
	print(prod%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

mod = 1000000007

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

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

plus_1 = deque()
minus_1 = deque()
plus_2 = deque()
minus_2 = deque()

a.sort()

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

a.sort(reverse=True)

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

maxa = 1

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.popleft()
            minus_1.popleft()
            i += 2
        else:
            maxa *= plus_1[0]
            plus_1.popleft()
            i += 1
    elif len(plus_1):
        maxa *= plus_1[0]
        plus_1.popleft()
        i += 1
    else:
        maxa *= minus_1[0]
        minus_1.popleft()
        i += 1
if maxa > 0:
    print(maxa%mod)
    exit()

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.popleft()
        else:
            mini *= minus_2[0]
            minus_2.popleft()
    elif len(plus_2):
        mini *= plus_2[0]
        plus_2.popleft()
    else:
        mini *= minus_2[0]
        minus_2.popleft()
    i += 1

print(mini%mod)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9+7
# s=正の数、t=負の数
s,t = [], []
for a in A:
  if a<0:
    t.append(a)
  else:
    s.append(a)

S = len(s)
T = len(t)
ok = False
if (S>0):
  if n==k:
    # すべての負の数をペアにできる
    ok = T%2==0
  else:
    # 負の数は考慮しない
    ok = True
else:
  # kが偶数個
  ok = (k%2==0)

ans = 1
if not ok:
  A.sort(key=lambda x: abs(x))
  for i in range(k):
    ans *= A[i]
else:
  s.sort()
  t.sort(reverse=True)
  if k%2==1:
    ans *= s.pop()

  p = []
  while len(s) >= 2:
    x = s.pop()
    x *= s.pop()
    p.append(x)

  while len(t) >= 2:
    x = t.pop()
    x *= t.pop()
    p.append(x)

  p.sort(reverse=True)
  for i in range(k//2):
    ans *= p[i]

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
N,K = list(map(int,input().split()))
seki = 1
A_ = list(map(int,input().split()))
A = []
for i in range(N):
    if(A_[i] != 0):A.append(A_[i])
    seki *= A_[i]

A.sort()


if(K > len(A)):
    if(N == K):print(seki % (10 ** 9 + 7))
    else:print(0)
else:
    curright = 1
    for i in range(K):
        curright *= A[len(A)-i-1]

    mx = curright
    curleft = 1
    for i in range(K):
        curleft *= A[i]
        curright //= A[len(A)-K + i]
        mx = max(curleft*curright,mx)

    if(N != len(A)):mx = max(mx,0)
    print(mx % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import numpy

n, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

mm = None

for d in range(1 << n):
  if bin(d).count('1') != k:
    continue
  mul = 1
  for i in range(n):
    if (1 << i) & d:
      mul *= a[i]
  if mm is None or mul > mm:
    mm = mul

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

mod = 1000000007

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

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

plus_1 = deque()
minus_1 = deque()
plus_2 = deque()
minus_2 = deque()

a.sort()

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

a.sort(reverse=True)

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

maxa = 1

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.popleft()
            minus_1.popleft()
            i += 2
        else:
            maxa *= plus_1[0]
            plus_1.popleft()
            i += 1
    elif len(plus_1):
        maxa *= plus_1[0]
        plus_1.popleft()
        i += 1
    else:
        maxa *= minus_1[0]
        minus_1.popleft()
        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.popleft()
        else:
            mini *= minus_2[0]
            minus_2.popleft()
    elif len(plus_2):
        mini *= plus_2[0]
        plus_2.popleft()
    else:
        mini *= minus_2[0]
        minus_2.popleft()
    i += 1

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

Submission status: Time Limit Exceeded

Solution code:
n,k,*a=map(int,open(i:=0).read().split())
a.sort()
p=a.pop
s=b=~k%2or p()
exec(k//2*'if(x:=a[i]*a[i+1])*b>a[-1]*a[-2]*b:s*=x;i+=2\nelse:s*=p()*p()\ns%=10**9+7\n')
print(s)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
ans = 1

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

#全部取る
if n == k:
    for x in a:
        ans *= x
    print(ans % MOD)

#全部負かつ奇数個取る
elif max(a) < 0 and k % 2:
    a.sort()
    for i in range(1, k+1):
        ans *= a[-i]
    print(ans % MOD)

else:
    pos = []
    neg = []
    
    for x in a:
        if x >= 0:
            pos.append(x)
        else:
            neg.append(x)
    
    pos.sort(reverse=True)
    neg.sort()
    
    
    if k % 2:
        ans *= pos.pop(0)
        k -= 1
     
    #2個ずつ取る
    num = []
    for x, y in zip(pos[::2], pos[1::2]):
        num.append(x * y)
    for x, y in zip(neg[::2], neg[1::2]):
        num.append(x * y)

    num.sort(reverse=True)

    for i in range(k // 2):
        ans *= num[i]
        ans %= MOD
    
    print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
ans = 1

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

#全部取る
if n == k:
    for x in a:
        ans *= x
    print(ans % MOD)

#全部負かつ奇数個取る
elif max(a) < 0 and k % 2:
    a.sort()
    for i in range(1, k+1):
        ans *= a[-i]
    print(ans % MOD)

else:
    pos = []
    neg = []
    
    for x in a:
        if x >= 0:
            pos.append(x)
        else:
            neg.append(x)
    
    pos.sort(reverse=True)
    neg.sort()
    

    if k % 2:
        ans *= pos.pop(0)
        k -= 1
    
    l = []
    
    for i in range(1, len(pos), 2):
        l.append(pos[i] * pos[i - 1])
    
    for i in range(1, len(neg), 2):
        l.append(neg[i] * neg[i - 1])
    
    l.sort(reverse=True)
    
    for i in range(k // 2):
        ans *= l[i]
        ans %= MOD
    
    print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True,key=lambda x:abs(x))
if k==n:
  ans=1
  for i in range(n):
    ans*=arr[i]
    ans%=mod
  print(ans)
else:
  if k%2==1 and max(arr)<0:
    ans=1
    for i in range(k):
      ans*=arr[n-1-i]
      ans%=mod
    print(ans)
  else:
    ans=1
    cnt=0
    for i in range(k):
      if arr[i]<0:
        cnt+=1
      ans*=arr[i]
      ans%=mod
    if cnt%2==0:
      print(ans)
    else:
      min_plus=-1
      min_minus=1
      for i in range(k):
        if arr[i]>=0:
          min_plus=arr[i]
        else:
          min_minus=arr[i]
      max_plus=-1
      max_minus=1
      for i in range(k,n):
        if arr[i]>=0 and max_plus==-1:
          max_plus=arr[i]
        if arr[i]<0 and max_minus==1:
          max_minus=arr[i]
      if min_plus==-1:        
        arr.remove(min_minus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_plus
        ans%=mod
      elif min_minus==1:        
        arr.remove(min_plus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%-mod
        ans*=max_minus
        ans%=mod
      elif min_plus*max_plus>=min_minus*max_minus:
        arr.remove(min_minus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_plus
        ans%=mod
      else:
        arr.remove(min_plus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%-mod
        ans*=max_minus
        ans%=mod
      print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
ans = 1

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

pos = []
neg = []

for x in a:
    if x >= 0:
        pos.append(x)
    else:
        neg.append(x)

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

if n == k:
    for x in a:
        ans *= x
    print(ans % MOD)

elif len(pos) == 0 and k % 2:
    for i in range(1, k+1):
        ans *= neg[-i]
    print(ans % MOD)

else:
    if k % 2:
        ans *= pos.pop(0)
        k -= 1
    
    l = []
    
    for i in range(1, len(pos), 2):
        l.append(pos[i] * pos[i - 1])
    
    for i in range(1, len(neg), 2):
        l.append(neg[i] * neg[i - 1])
    
    l.sort(reverse=True)
    
    for i in range(k // 2):
        ans *= l[i]
        ans %= MOD
    
    print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
ans = 1

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

pos = []
neg = []

for x in a:
    if x >= 0:
        pos.append(x)
    else:
        neg.append(x)

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

if n == k:
    for x in a:
        ans *= x
    print(ans % MOD)
    exit()

elif len(pos) == 0 and k % 2:
    for i in range(1, k+1):
        ans *= neg[-i]
    print(ans % MOD)
    exit()
else:
    if k % 2:
        ans *= pos.pop(0)
        k -= 1
    
    l = []
    
    for i in range(1, len(pos), 2):
        l.append(pos[i] * pos[i - 1])
    
    for i in range(1, len(neg), 2):
        l.append(neg[i] * neg[i - 1])
    
    l.sort(reverse=True)
    
    for i in range(k // 2):
        ans *= l[i]
    
    print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
ans = 1

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

if n == k:
    for x in a:
        ans *= x
    print(ans % MOD)
    exit()

pos = []
neg = []

for x in a:
    if x >= 0:
        pos.append(x)
    else:
        neg.append(x)

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

if len(pos) == 0 and k % 2:
    for i in range(1, k+1):
        ans *= neg[-i]
    print(ans % MOD)
    exit()

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


l = []

for i in range(1, len(pos), 2):
    l.append(pos[i] * pos[i - 1])

for i in range(1, len(neg), 2):
    l.append(neg[i] * neg[i - 1])

l.sort(reverse=True)

for i in range(k // 2):
    ans *= l[i]

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
ans = 1

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

if n == k:
    for x in a:
        ans *= x
    print(ans % MOD)
    exit()

pos = []
neg = []

for x in a:
    if x >= 0:
        pos.append(x)
    else:
        neg.append(x)

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

if len(pos) == 0 and k % 2:
    for i in range(1, k+1):
        ans *= neg[-i]
    print(ans % MOD)
    exit()

pi = 0
ni = 0
if k % 2:
    ans *= pos[pi]
    pi += 1
    k -= 1

while k > 0:
    if pi < len(pos) - 1:
        sp = pos[pi] * pos[pi + 1]
    else:
        sp = 0
    
    if ni < len(neg) - 1:
        sn = neg[ni] * neg[ni + 1]
    else:
        sn = 0
    
    if sp > sn:
        ans *= sp
        pi += 2
    else:
        ans *= sn
        ni += 2
    
    ans %= MOD
    k -= 2

print(ans % MOD)