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 collections import deque

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

A.sort()
A.reverse()
flag = True
A_p = deque([i for i in A if i >= 0])
A_n = deque([i for i in A if i < 0])

ans = 1
if K % 2 == 0:
    while K != 0:
        if len(A_p) >= 2 and len(A_n) >= 2:
            if A_p[0] * A_p[1] > A_n[-1] * A_n[-2]:
                ans *= A_p[0] * A_p[1]
                A_p.popleft()
                A_p.popleft()
            else:
                ans *= A_n[-1] * A_n[-2]
                A_n.pop()
                A_n.pop()
        elif len(A_p) >= 2:
            ans *= A_p[0] * A_p[1]
            A_p.popleft()
            A_p.popleft()
        elif len(A_n) >= 2:
            ans *= A_n[-1] * A_n[-2]
            A_n.pop()
            A_n.pop()
        K -= 2
elif len(A_p) > 0:
    while K != 0:
        if K >= 2:
            if len(A_p) >= 2 and len(A_n) >= 2:
                if A_p[0] * A_p[1] > A_n[-1] * A_n[-2]:
                    ans *= A_p[0] * A_p[1]
                    A_p.popleft()
                    A_p.popleft()
                else:
                    ans *= A_n[-1] * A_n[-2]
                    A_n.pop()
                    A_n.pop()
            elif len(A_p) >= 2:
                ans *= A_p[0] * A_p[1]
                A_p.popleft()
                A_p.popleft()
            elif len(A_n) >= 2:
                ans *= A_n[-1] * A_n[-2]
                A_n.pop()
                A_n.pop()
            K -= 2
        elif K == 1:
            ans *= A_p[0]
            A_p.popleft()
            K -= 1
else:
    while K != 0:
        ans *= A_n[0]
        A_n.popleft()
        K -= 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

A.sort()
A.reverse()
flag = True
for i in range(len(A)):
    if A[i] < 0:
        A_p = A[:i]
        A_n = A[i:]
        flag = False
        break
if flag:
    A_p = deque(A)
    A_n = deque()
A_p = deque(A_p)
A_n = deque(A_n)

ans = 1
if K % 2 == 0:
    while K != 0:
        if len(A_p) >= 2 and len(A_n) >= 2:
            if A_p[0] * A_p[1] > A_n[-1] * A_n[-2]:
                ans *= A_p[0] * A_p[1]
                A_p.popleft()
                A_p.popleft()
            else:
                ans *= A_n[-1] * A_n[-2]
                A_n.pop()
                A_n.pop()
        elif len(A_p) >= 2:
            ans *= A_p[0] * A_p[1]
            A_p.popleft()
            A_p.popleft()
        elif len(A_n) >= 2:
            ans *= A_n[-1] * A_n[-2]
            A_n.pop()
            A_n.pop()
        K -= 2
elif len(A_p) > 0:
    while K != 0:
        if K >= 2:
            if len(A_p) >= 2 and len(A_n) >= 2:
                if A_p[0] * A_p[1] > A_n[-1] * A_n[-2]:
                    ans *= A_p[0] * A_p[1]
                    A_p.popleft()
                    A_p.popleft()
                else:
                    ans *= A_n[-1] * A_n[-2]
                    A_n.pop()
                    A_n.pop()
            elif len(A_p) >= 2:
                ans *= A_p[0] * A_p[1]
                A_p.popleft()
                A_p.popleft()
            elif len(A_n) >= 2:
                ans *= A_n[-1] * A_n[-2]
                A_n.pop()
                A_n.pop()
            K -= 2
        elif K == 1:
            ans *= A_p[0]
            A_p.popleft()
            K -= 1
else:
    while K != 0:
        ans *= A_n[0]
        A_n.popleft()
        K -= 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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()

p = []
m = []

for x in a:
    if x >= 0:
        p.append(x)
    else:
        m.append(x)

p.sort(reverse=True)
m.sort()

pos = deque(p)
neg = deque(m)

if len(p) == 0:
    for i in range(k):
        ans *= neg[-1]
        neg.pop()
    print(ans % MOD)
    exit()

while k > 1:
    if len(pos) >= 2 and len(neg) >= 2:
        if pos[0] * pos[1] > neg[0] * neg[1]:
            ans *= pos[0]
            pos.popleft()
            k -= 1
        else:
            ans *= neg[0] * neg[1]
            neg.popleft()
            neg.popleft()
            k -= 2
    elif len(pos) == 1 and len(neg) >= 2:
        if pos[0] > neg[0] * neg[1]:
            ans *= pos[0]
            pos.popleft()
            k -= 1
        else:
            ans *= neg[0] * neg[1]
            neg.popleft()
            neg.popleft()
            k -= 2
    else:
        ans *= pos[0]
        pos.popleft()
        k -= 1
if k == 1:
    ans *= pos[0]

print(ans % MOD)

Submission status: Time Limit Exceeded

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

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)
MOD = pow(10, 9) + 7

N, K, *A = map(int, read().split())
A_pos = [a for a in A if a >= 0]
A_neg = [a for a in A if a < 0]

if K == N:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
elif len(A_neg) == N and K % 2 == 1:
    A = sorted(A, key=lambda x: abs(x))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD

else:
    A_pos = sorted(A_pos, key=lambda x: -abs(x))
    A_neg = sorted(A_neg, key=lambda x: -abs(x))
    ans = 1
    cnt = 0
    while True:
        if len(A_pos) > 1:
            acc_pos = A_pos[0] * A_pos[1]
        else:
            acc_pos = 0

        if len(A_neg) > 1:
            acc_neg = A_neg[0] * A_neg[1]
        else:
            acc_neg = 0

        if acc_pos > acc_neg or cnt == K - 1:
            if len(A_pos) > 0:
                ans *= A_pos[0]
                A_pos = A_pos[1:]
            else:
                ans *= A_neg[0]
                A_neg = A_neg[1:]
            ans %= MOD
            cnt += 1
        else:
            ans *= acc_neg
            ans %= MOD
            A_neg = A_neg[2:]
            cnt += 2

        if cnt == K:
            break

print(ans % MOD)

Submission status: Time Limit Exceeded

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

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)
MOD = pow(10, 9) + 7

N, K, *A = map(int, read().split())
A_pos = [a for a in A if a >= 0]
A_neg = [a for a in A if a < 0]

if K == N:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
elif len(A_neg) == N and K % 2 == 1:
    A = sorted(A, key=lambda x: abs(x))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD

else:
    A_pos = sorted(A_pos, key=lambda x: -abs(x))
    A_neg = sorted(A_neg, key=lambda x: -abs(x))
    ans = 1
    cnt = 0
    while True:
        if len(A_pos) > 1:
            acc_pos = A_pos[0] * A_pos[1]
        elif len(A_pos) == 1:
            acc_pos = A_pos[0]
        else:
            acc_pos = 0

        if len(A_neg) > 1:
            acc_neg = A_neg[0] * A_neg[1]
        else:
            acc_neg = 0

        if acc_pos > acc_neg or cnt == K - 1:
            if len(A_pos) > 0:
                ans *= A_pos[0]
                A_pos = A_pos[1:]
            else:
                ans *= A_neg[0]
                A_neg = A_neg[1:]
            ans %= MOD
            cnt += 1
        else:
            ans *= acc_neg
            ans %= MOD
            A_neg = A_neg[2:]
            cnt += 2

        if cnt == K:
            break

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(i)
        else:
            AP.append(i%mod)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        
        AP.sort(reverse=True)
        AM.sort()
        
        ans = 1
        p = 0
        m = 0
        cnt = 0
        while True:
            if (K - cnt) == 1:
                ans *= AP[p]
                print(ans%mod)
                break
                
            elif 2 <= (len(AM) - m) and 2 <= (len(AP) - p):   
                if AP[p]*AP[p+1] >= AM[m]*AM[m+1]:
                    ans *= (AP[p]*AP[p+1])
                    p += 2
                    cnt += 2
                
                else:
                    ans *= (AM[m]*AM[m+1])
                    m += 2
                    cnt += 2 
                    
            elif 1 >= (len(AP) - p) and 2 <= (len(AM) - m):
                ans *= (AM[m]*AM[m+1])
                m += 2
                cnt += 2 
            
            elif 2 <= (len(AP) - p) and 1 >= (len(AM) - m):
                ans *= (AP[p]*AP[p+1])
                p += 2
                cnt += 2
            
            

            if cnt == K:
                print(ans%mod)
                break

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(i)
        else:
            AP.append(i)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        
        AP.sort(reverse=True)
        AM.sort()
        
        ans = 1
        p = 0
        m = 0
        cnt = 0
        while True:
            if (K - cnt) == 1:
                ans *= AP[p]
                print(ans%mod)
                break
                
            elif 2 <= len(AM) - m and 2 <= len(AP) - p:   
                if AP[p]*AP[p+1] >= AM[m]*AM[m+1]:
                    ans *= (AP[p]*AP[p+1])
                    p += 2
                    cnt += 2
                
                else:
                    ans *= (AM[m]*AM[m+1])
                    m += 2
                    cnt += 2 
                    
            elif 1 >= len(AP) - p and 2 <= len(AM) - m:
                ans *= (AM[m]*AM[m+1])
                m += 2
                cnt += 2 
            
            elif 2 <= len(AP) - p and 1 >= len(AM) - m:
                ans *= (AP[p]*AP[p+1])
                p += 2
                cnt += 2
            
            

            if cnt == K:
                print(ans%mod)
                break

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 10 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(sorted(A,key=lambda x: abs(x), reverse=True))

if K == N:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans % MOD)
    exit()
if K % 2 == 1 and len(list(filter(lambda x: x >= 0, A))) == 0:
    ans = 1
    for i in range(K):
        ans *= B[len(B) - 1 - i]
        ans %= MOD
    print(ans % MOD)
    exit()


ps = list(filter(lambda x: x >= 0, B))
ns = list(filter(lambda x: x < 0, B))

X = []
pi = 0
ni = 0
while len(X) < K:
    if pi + 1 < len(ps) and ni + 1 < len(ns):
        p = ps[pi] * ps[pi + 1]
        neg = ns[ni] * ns[ni + 1]
        if p > neg or K - 1 == len(X):
            X.append(ps[pi])
            pi += 1
        else:
            X.append(ns[ni])
            X.append(ns[ni + 1])
            ni += 2
    elif pi + 1 == len(ps):
        X.append(ps[pi])
        pi += 1
ans = 1
for x in X:
    ans *= x
    ans %= MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import mul
from functools import reduce
n, k = map(int, input().split())
arr = list(map(int, input().split()))


MOD = 10**9 + 7

# negを奇数個選ばないといけないシチュエーションかどうか
neg = [x < 0 for x in arr]

if all(neg) and k % 2 == 1:
    arr.sort(reverse=True)
    print(reduce(mul, arr[:k]) % MOD)
    sys.exit()

arr_p = [x for x in arr if x >= 0]
arr_n = [x for x in arr if x < 0]

arr_p.sort(reverse=True)
arr_n.sort()

ans = 1

while k >= 2:
    if k >= 2:
        if len(arr_p) >= 2 and len(arr_n) >= 2:
            pos = arr_p[0] * arr_p[1]
            neg = arr_n[0] * arr_n[1]
            if pos > neg:
                ans *= pos
                ans % MOD
                arr_p = arr_p[2:]
            else:
                ans *= neg
                ans % MOD
                arr_n = arr_n[2:]
        elif len(arr_p) >= 2 and len(arr_n) < 2:
            pos = arr_p[0] * arr_p[1]
            ans *= pos
            ans % MOD
            arr_p = arr_p[2:]
        else:
            neg = arr_n[0] * arr_n[1]
            ans *= neg
            arr_n = arr_n[2:]
        k -= 2

if k == 1:
    ans *= arr_p[0]

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import copy

# a = get_int()
def get_int():
    return int(input())

# a = get_string()
def get_string():
    return input()

# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]

# a_list = get_string_list():
def get_string_list():
    return input().split()

# a, b = get_int_multi()
def get_int_multi():  # a, b = get_int_multi()
    return map(int, input().split())

# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))

# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''

def main():

    n, k = get_int_multi()
    a_list = get_int_list()

    p_list=[]
    m_list=[]
    for num in a_list:
        if num > 0:
            p_list.append(num)
        else :
            m_list.append(num)


    p_list.sort()
    m_list.sort(reverse=True)


    if k % 2 == 1:
        if (len(p_list) > 0):
            ans = p_list.pop()
            k -= 1
        else:
            m_list.sort()
            ans = m_list.pop()
            k -= 1
    else:
        ans = 1

    nokori = k
    while nokori > 0:
        if len(p_list) == 1 and len(m_list) == 1:
            ans = ans * p_list.pop() * m_list[0]
            del m_list[0]
            nokori -= 2
        else:
            if len(p_list) >= 2:
                pval = p_list[-1] * p_list[-2]
            else:
                pval = 0

            if len(m_list) >= 2:
                mval = m_list[-1] * m_list[-2]
            else:
                mval = 0

            if pval > mval:
                p_list.pop()
                p_list.pop()
                ans = ans * pval
            else:
                m_list.pop()
                m_list.pop()
                ans = ans * mval
            nokori -= 2

    print(ans % 1000000007)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy

# a = get_int()
def get_int():
    return int(input())

# a = get_string()
def get_string():
    return input()

# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]

# a_list = get_string_list():
def get_string_list():
    return input().split()

# a, b = get_int_multi()
def get_int_multi():  # a, b = get_int_multi()
    return map(int, input().split())

# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))

# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''

def main():

    n, k = get_int_multi()
    a_list = get_int_list()

    p_list=[]
    m_list=[]
    for num in a_list:
        if num > 0:
            p_list.append(num)
        else :
            m_list.append(num)


    p_list.sort(reverse=True)
    m_list.sort()


    if k % 2 == 1:
        if (len(p_list) > 0):
            ans = p_list[0]
            del p_list[0]
            k -= 1
        else:
            m_list.sort(reverse=True)
            ans = m_list[0]
            del m_list[0]
            k -= 1
    else:
        ans = 1

    nokori = k
    while nokori > 0:
        if len(p_list) == 1 and len(m_list) == 1:
            ans = ans * p_list[0] * m_list[len(m_list) -1]
            del p_list[0]
            del m_list[0]
            nokori -= 2
        else:
            if len(p_list) >= 2:
                pval = p_list[0] * p_list[1]
            else:
                pval = 0

            if len(m_list) >= 2:
                mval = m_list[0] * m_list[1]
            else:
                mval = 0

            if pval > mval:
                del p_list[0]
                del p_list[0]
                ans = ans * pval % 1000000007
            else:
                del m_list[0]
                del m_list[0]
                ans = ans * mval % 1000000007
            nokori -= 2

    print(ans % 1000000007)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
div = 10**9+7
a = sorted(A)
ans = 1
if K == N or (K % 2 != 0 and a[-1] < 0):
    for _ in range(K):
        ans *= a.pop(-1)
        ans %= div
    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:
import copy

# a = get_int()
def get_int():
    return int(input())

# a = get_string()
def get_string():
    return input()

# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]

# a_list = get_string_list():
def get_string_list():
    return input().split()

# a, b = get_int_multi()
def get_int_multi():  # a, b = get_int_multi()
    return map(int, input().split())

# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))

# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''

def main():

    n, k = get_int_multi()
    a_list = get_int_list()

    p_list=[]
    m_list=[]
    for num in a_list:
        if num > 0:
            p_list.append(num)
        else :
            m_list.append(num)


    p_list.sort(reverse=True)
    m_list.sort()


    if k % 2 == 1:
        if (len(p_list) > 0):
            ans = p_list[0]
            del p_list[0]
            k -= 1
        else:
            m_list.sort(reverse=True)
            ans = m_list[0]
            del m_list[0]
            k -= 1
    else:
        ans = 1

    nokori = k
    while nokori > 0:
        if len(p_list) == 1 and len(m_list) == 1:
            ans = ans * p_list[0] * m_list[len(m_list) -1]
            del p_list[0]
            del m_list[0]
            nokori -= 2
        else:
            if len(p_list) >= 2:
                pval = p_list[0] * p_list[1]
            else:
                pval = 0

            if len(m_list) >= 2:
                mval = m_list[0] * m_list[1]
            else:
                mval = 0

            if pval > mval:
                del p_list[0]
                del p_list[0]
                ans = ans * pval
            else:
                del m_list[0]
                del m_list[0]
                ans = ans * mval
            nokori -= 2

    print(ans % 1000000007)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.read
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    if max(A) > 0:
        plus = True
    else:
        plus = False

    A.sort(reverse=True)

    if K%2==1 and plus==False:
        ans = 1
        for i in A[:K]:
            ans *= i % MOD
        ans %= MOD
    else:
        ans = 1
        left = 0
        right = N-1
        if K%2==1:
            ans *= A[left]
            left += 1
        for _ in range(K//2):
            if A[left]*A[left+1]>=A[right]*A[right-1]:
                ans *= A[left]*A[left+1]%MOD
                left += 2
            else:
                ans *= A[right]*A[right-1] % MOD
                right -= 2
        ans %= MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def maxProductSubarrayOfSizeK(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)): 
	    A.reverse()
	    for i in range(k):
	        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 

n, k = map(int, input().split(' '))
numbers = [int(x) for x in input().split(' ')]
MOD = 1000000007
ans = maxProductSubarrayOfSizeK(numbers, n, k)
#print(ans)
print((ans + MOD)%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.read
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    plus = False

    for a in A:
        if a>0:
            plus = True
            break

    A.sort(reverse=True)

    if K%2==1 and plus==False:
        ans = 1
        for i in A[:K]:
            ans *= i % MOD
        ans %= MOD
    else:
        A = deque(A)
        ans = 1
        left = 0
        right = N-1
        if K%2==1:
            ans *= A[left]
            left += 1
        for _ in range(K//2):
            if A[left]*A[left+1]>=A[right]*A[right-1]:
                ans *= A[left]*A[left+1]%MOD
                left += 2
            else:
                ans *= A[right]*A[right-1] % MOD
                right -= 2
        ans %= MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
div = 10**9+7
a = sorted(A)
ans = 1
if K == N or (K % 2 != 0 and a[-1] < 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:
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 = deque([])
    AAm = deque([])
    if N == K:
        ans = 1
        for i in A:
            ans *= i % mod
        print(ans % mod)

    elif K % 2 == 0:
        ans = 1

        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AAm.append(a1 * a2)

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


        for i in range(K // 2):
            if len(AAm)==0:
                temp = AA.popleft()
            elif len(AA) ==0:
                temp = AAm.popleft()
            elif AAm[0] > AA[0]:
                temp = AAm.popleft()
            else:
                temp = AA.popleft()
            ans *= temp % 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()
            AAm.append(a1 * a2)

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

        for i in range(K // 2):
            if len(AAm) == 0:
                temp = AA.popleft()
            elif len(AA) == 0:
                temp = AAm.popleft()
            elif AAm[0] > AA[0]:
                temp = AAm.popleft()
            else:
                temp = AA.popleft()
            ans *= temp % mod
        print(ans % mod)
if __name__ == "__main__":
    main()

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]
ans = 1
if K == N or (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:
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.read
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    plus = False

    for a in A:
        if a>0:
            plus = True
            break

    A.sort(reverse=True)

    if K%2==1 and plus==False:
        ans = 1
        for i in A[:K]:
            ans *= i % MOD
        ans %= MOD
    else:
        A = deque(A)
        ans = 1
        if K%2==1:
            ans *= A.popleft()
        for _ in range(K//2):
            if A[0]*A[1]>=A[-1]*A[-2]:
                ans *= A.popleft()*A.popleft()%MOD
            else:
                ans *= A.pop() * A.pop() % MOD
        ans %= MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.read
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    plus = False
    for a in A:
        if a>0:
            plus = True
            break

    A.sort(reverse=True)

    if K%2==1 and plus==False:
        ans = 1
        for i in A[:K]:
            ans *= i % MOD
        ans %= MOD
    else:
        A = deque(A)
        ans = 1
        if K%2==1:
            ans *= A.popleft()
        for _ in range(K//2):
            if A[0]*A[1]>=A[-1]*A[-2]:
                ans *= A.popleft()*A.popleft()%MOD
            else:
                ans *= A.pop() * A.pop() % MOD
        ans %= MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
num = list(map(int, input().split()))
max = -((10 ** 9) +7)
for i in range(2 ** n):
    wk = []
    cnt = 0
    numWk = 1
    for j in range(n):
        if ((i>>j) & 1):
            cnt +=1
            wk.append(num[j])
        if cnt > k:
            break
    if cnt == k:
        for j in range(k):
            numWk *= wk[j]
        if max < numWk:
            max = numWk
print(max % ((10 ** 9) +7))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.read
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    plus = []
    minus = []
    plus_count = 0
    zero_count = 0
    for a in A:
        if a>0:
            plus.append(a)
            plus_count += 1
        else:
            minus.append(a)

    if K%2==1 and plus_count==0:
        minus.sort(reverse=True)
        ans = 1
        for i in minus[:K]:
            ans *= i % MOD
        ans %= MOD
    else:
        A.sort(reverse=True)
        A = deque(A)
        ans = 1
        if K%2==1:
            ans *= A.popleft()
        for _ in range(K//2):
            if A[0]*A[1]>=A[-1]*A[-2]:
                ans *= A.popleft()*A.popleft()%MOD
            else:
                ans *= A.pop() * A.pop() % MOD
        ans %= MOD

    print(ans)

if __name__ == '__main__':
    main()