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: Runtime Error

Solution code:
#!/usr/bin/env python3
from functools import reduce

mod = 10**9 + 7
n, k, *a = map(int, open(0).read().split())
a.sort(key=lambda x: abs(x))
ans = reduce(lambda a, b: (a * b) % mod, a[-k:])

c = a[-k:]
j = sum(i < 0 for i in c) % 2
if j:
    c = a[-k:]
    neg = [i for i in c if i < 0]
    pos = [i for i in c if i > 0]
    b = sorted(a[:n - k])
    if 0 >= b[-1] / neg[0] > b[0] / pos[0]:
        ans = ans * pow(pos[0], mod - 2, mod) * b[0] % mod
    elif b[-1] / neg[0] <= 0:
        ans = ans * pow(neg[0], mod - 2, mod) * b[-1] % mod
    else:
        ans = reduce(lambda a, b: (a * b) % mod, a[:k])
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from functools import reduce

mod = 10**9 + 7
n, k, *a = map(int, open(0).read().split())
a.sort(key=lambda x: abs(x))
ans = reduce(lambda a, b: (a * b) % mod, a[-k:])

c = a[-k:]
j = sum(i < 0 for i in c) % 2
if j:
    c = a[-k:]
    neg = [i for i in c if i < 0]
    pos = [i for i in c if i > 0]
    b = sorted(a[:n - k])
    if 0 >= b[-1] / neg[0] > b[0] / pos[0]:
        ans = ans // pos[0] * b[0] % mod
    elif b[-1] / neg[0] <= 0:
        ans = ans // neg[0] * b[-1] % mod
    else:
        ans = reduce(lambda a, b: (a * b) % mod, a[:k])
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from functools import reduce

n, k, *a = map(int, open(0).read().split())
a.sort(key=lambda x: abs(x))
ans = reduce(lambda a, b: a * b, a[-k:])
if ans < 0:
    c = a[-k:]
    neg = [i for i in c if i < 0]
    pos = [i for i in c if i > 0]
    b = sorted(a[:n - k])
    if 0 >= b[-1] / neg[0] > b[0] / pos[0]:
        ans = ans // pos[0] * b[0]
    elif b[-1] / neg[0] <= 0:
        ans = ans // neg[0] * b[-1]
    else:
        ans = reduce(lambda a, b: a * b, a[:k])
print(ans % (10**9 + 7))

# 解法はあってるけど TLE した実装方法がまずい？？

Submission status: Runtime Error

Solution code:
from collections import deque

def solve(n,k,a):
    mod = 10**9 + 7
    ans = 1
    if k == n:
        for i in a:
            ans = ans * i % mod
        return ans
    else:
        pos = [i for i in a if i>0]
        neg = [i for i in a if i<0]

        if len(neg) + len(pos) < 0:
            return 0            
        elif len(pos)== 0 and k%2== 1:
            neg.sort(reverse=True)
            for i in neg[:k]:
                ans = ans * i % mod
            return ans
        else:
            pos.sort()
            neg.sort(reverse=True)
            ctr = k
            pos = deque(pos)
            neg = deque(neg)

            while ctr >= 2:
                if len(pos) >=2 and len(neg) >2:
                    tmp_p = pos[-1] * pos[-2] %mod
                    tmp_n = neg[-1] * neg[-2] %mod
                    if tmp_p >=tmp_n:
                        ans = ans * tmp_p %mod
                        pos.pop()
                        pos.pop()
                    else:
                        ans = ans * tmp_n %mod
                        neg.pop()
                        neg.pop()
                    ctr-=2
                elif len(neg) >= 2:
                    ans = ans * neg.pop() * neg.pop() %mod 
                    ctr-=2
                else:
                    ans = ans * pos.pop() %mod
                    ctr -=1
                
            if ctr == 1:
                ans = ans * pos.pop() % mod

            return ans
                    
n, k = map(int, input().split())
A = list(map(int,input().split()))
ans = solve(n,k,A)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

def solve(n,k,a):
    pos=[]
    neg=[]
    mod = 10**9 + 7
    ans = 1
    if k == n:
        for i in a:
            ans = ans * i % mod
        return ans
    else:
        for i in a:
            if i >0:
                pos.append(i)
            elif i<0:
                neg.append(i)

        if len(neg) + len(pos) < 0:
            return 0            
        elif len(pos)== 0:
            if k%2== 1:
                neg.sort(reverse=True)
                for i in neg[:k]:
                    ans = ans * i % mod
                return ans
            else:
                neg.sort()
                for i in neg[:k]:
                    ans = ans * i % mod
                return ans
        elif len(neg)==0:
            pos.sort(reverse=True)
            for i in pos[:k]:
                ans = ans * i % mod
            return ans
        else:
            pos.sort()
            neg.sort(reverse=True)
            ctr = 0
            if k%2 == 1:
                ans = ans * pos.pop() % mod
                ctr +=1
            pos = deque(pos)
            neg = deque(neg)

            while ctr < k:
                if len(pos) <= 1:
                    ans = ans * neg.pop() * neg.pop() %mod 
                elif len(neg) <= 1:
                    ans = ans * pos.pop() * pos.pop() %mod
                else:
                    tmp_p = pos[-1] * pos[-2] %mod
                    tmp_n = neg[-1] * neg[-2] %mod
                    if tmp_p >=tmp_n:
                        ans = ans * tmp_p %mod
                        pos.pop()
                        pos.pop()
                    else:
                        ans = ans * tmp_n %mod
                        neg.pop()
                        neg.pop()
                ctr+=2
            return ans
                    
n, k = map(int, input().split())
A = list(map(int,input().split()))
ans = solve(n,k,A)
print(ans)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

n_k = list(map(int, input().split()))
n = n_k[0]
k = n_k[1]
a = list(map(int, input().split()))
a_pos = list(filter(lambda v: v >= 0, a))
a_neg = list(filter(lambda v: v < 0, a))

a_pos.sort(reverse=True)
a_neg.sort()

mod = 10**9+7

ans = 1
if n == k:
    for a_i in a:
        ans = ans * a_i % mod
elif len(a_pos) == 0 and k % 2 == 1:
    for i in reversed(range(len(a_neg) - k, len(a_neg))):
        ans = ans * a_neg[i] % mod
else:
    i_p = 0
    i_n = 0
    i = 0
    while i < k:
        if i == k - 1 or i_n+1 >= len(a_neg) or a_pos[i_p] * (a_pos[i_p+1] if i_p+1 < len(a_pos) else 1) > a_neg[i_n] * a_neg[i_n+1]:
            ans = ans * a_pos[i_p] % mod
            i_p += 1
            i += 1
        else:
            ans = ans * a_neg[i_n] % mod * a_neg[i_n+1] % mod
            i_n += 2
            i += 2
print(ans)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

n_k = list(map(int, input().split()))
n = n_k[0]
k = n_k[1]
a = list(map(int, input().split()))
a_pos = list(filter(lambda v: v >= 0, a))
a_neg = list(filter(lambda v: v < 0, a))

a_pos.sort(reverse=True)
a_neg.sort()

mod = 10**9+7

ans = 1
if n == k:
    for a_i in a:
        ans = ans * a_i % mod
elif len(a_pos) == 0 and k % 2 == 1:
    for i in reversed(range(len(a_neg) - k, len(a_neg))):
        ans = ans * a_neg[i] % mod
else:
    i_p = 0
    i_n = 0
    i = 0
    while i < k:
        if i == k - 1 or i_n+1 >= len(a_neg) or a_pos[i_p] * (i_p+1 < len(a_pos) ? a_pos[i_p+1] : 1) > a_neg[i_n] * a_neg[i_n+1]:
            ans = ans * a_pos[i_p] % mod
            i_p += 1
            i += 1
        else:
            ans = ans * a_neg[i_n] % mod * a_neg[i_n+1] % mod
            i_n += 2
            i += 2
print(ans)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

n_k = list(map(int, input().split()))
n = n_k[0]
k = n_k[1]
a = list(map(int, input().split()))
a_pos = list(filter(lambda v: v >= 0, a))
a_neg = list(filter(lambda v: v < 0, a))

a_pos.sort(reverse=True)
a_neg.sort()

mod = 10**9+7

ans = 1
if n == k:
    for a_i in a:
        ans = ans * a_i % mod
elif len(a_pos) == 0 and k % 2 == 1:
    for i in reversed(range(len(a_neg) - k, len(a_neg))):
        ans = ans * a_neg[i] % mod
else:
    i_p = 0
    i_n = 0
    i = 0
    while i < k:
        if i == k - 1 or i_n+1 >= len(a_neg) or (i_p+1 >= len(a_pos) and a_pos[i_p] * a_pos[i_p+1] > a_neg[i_n] * a_neg[i_n+1]):
            ans = ans * a_pos[i_p] % mod
            i_p += 1
            i += 1
        else:
            ans = ans * a_neg[i_n] % mod * a_neg[i_n+1] % mod
            i_n += 2
            i += 2
print(ans)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

n_k = list(map(int, input().split()))
n = n_k[0]
k = n_k[1]
a = list(map(int, input().split()))
a_pos = list(filter(lambda v: v >= 0, a))
a_neg = list(filter(lambda v: v < 0, a))

a_pos.sort(reverse=True)
a_neg.sort()

mod = 10**9+7

ans = 1
if n == k:
    for a_i in a:
        ans = ans * a_i % mod
elif len(a_pos) == 0 and k % 2 == 1:
    for i in reversed(range(len(a_neg) - k, len(a_neg))):
        ans = ans * a_neg[i] % mod
else:
    i_p = 0
    i_n = 0
    i = 0
    while i < k:
        if i == k - 1 or i_n+1 >= len(a_neg) or a_pos[i_p] * a_pos[i_p+1] > a_neg[i_n] * a_neg[i_n+1]:
            ans = ans * a_pos[i_p] % mod
            i_p += 1
            i += 1
        else:
            ans = ans * a_neg[i_n] % mod * a_neg[i_n+1] % mod
            i_n += 2
            i += 2
print(ans)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

n_k = list(map(int, input().split()))
n = n_k[0]
k = n_k[1]
a = list(map(int, input().split()))
a_pos = list(filter(lambda v: v >= 0, a))
a_neg = list(filter(lambda v: v < 0, a))

a_pos.sort(reverse=True)
a_neg.sort()

ans = 1
if n == k:
    for a_i in a:
        ans = ans * a_i % 100000007
elif len(a_pos) == 0 and k % 2 == 1:
    for i in reversed(range(len(a_neg) - k, len(a_neg))):
        ans = ans * a_neg[i] % 100000007
else:
    i_p = 0
    i_n = 0
    i = 0
    while i < k:
        if i == k - 1 or i_n+1 >= len(a_neg) or a_pos[i_p] * a_pos[i_p+1] > a_neg[i_n] * a_neg[i_n+1]:
            ans = ans * a_pos[i_p] % 1000000007
            i_p += 1
            i += 1
        else:
            ans = ans * a_neg[i_n] % 1000000007 * a_neg[i_n+1] % 1000000007
            i_n += 2
            i += 2
print(ans)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

n_k = list(map(int, input().split()))
n = n_k[0]
k = n_k[1]
a = list(map(int, input().split()))
a_pos = list(filter(lambda v: v > 0, a))
a_neg = list(filter(lambda v: v < 0, a))

a_pos.sort(reverse=True)
a_neg.sort()

ans = 1
if n == k:
    for a_i in a:
        ans = ans * a_i % 100000007
elif len(a_pos) == 0 and k % 2 == 1:
    for i in reversed(range(len(a_neg) - k, len(a_neg))):
        ans = ans * a_neg[i] % 100000007
else:
    i_p = 0
    i_n = 0
    i = 0
    while i < k:
        if i == k - 1 or i_n+1 >= len(a_neg) or a_pos[i_p] * a_pos[i_p+1] > a_neg[i_n] * a_neg[i_n+1]:
            ans = ans * a_pos[i_p] % 1000000007
            i_p += 1
            i += 1
        else:
            ans = ans * a_neg[i_n] % 1000000007 * a_neg[i_n+1] % 1000000007
            i_n += 2
            i += 2
print(ans)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

n_k = list(map(int, input().split()))
n = n_k[0]
k = n_k[1]
a = list(map(int, input().split()))
a_pos = list(filter(lambda v: v > 0, a))
a_neg = list(filter(lambda v: v < 0, a))

a_pos.sort(reverse=True)
a_neg.sort()

ans = 1
if len(a_pos) == 0 and k % 2 == 1:
    for i in reversed(range(len(a_neg) - k, len(a_neg))):
        ans = ans * a_neg[i] % 100000007
else:
    i_p = 0
    i_n = 0
    i = 0
    while i < k:
        if i == k - 1 or i_n+1 >= len(a_neg) or a_pos[i_p] * a_pos[i_p+1] > a_neg[i_n] * a_neg[i_n+1]:
            ans = ans * a_pos[i_p] % 1000000007
            i_p += 1
            i += 1
        else:
            ans = ans * a_neg[i_n] % 1000000007 * a_neg[i_n+1] % 1000000007
            i_n += 2
            i += 2
print(ans)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

n_k = list(map(int, input().split()))
n = n_k[0]
k = n_k[1]
a = list(map(int, input().split()))
a_pos = list(filter(lambda v: v > 0, a))
a_neg = list(filter(lambda v: v < 0, a))

a_pos.sort(reverse=True)
a_neg.sort()

ans = 1
if len(a_pos) == 0 and k % 2 == 1:
    for i in reversed(range(len(a_neg) - k, len(a_neg))):
        ans = ans * a_neg[i] % 100000007
else:
    i_p = 0
    i_n = 0
    i = 0
    while i < k:
        if i == k - 1 or i_n+1 >= len(a_neg) or a_pos[i_p] > a_neg[i_n] * a_neg[i_n+1]:
            ans = ans * a_pos[i_p] % 1000000007
            i_p += 1
            i += 1
        else:
            ans = ans * a_neg[i_n] % 1000000007 * a_neg[i_n+1] % 1000000007
            i_n += 2
            i += 2
print(ans)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

n_k = list(map(int, input().split()))
n = n_k[0]
k = n_k[1]
a = list(map(int, input().split()))
a_pos = list(filter(lambda v: v > 0, a))
a_neg = list(filter(lambda v: v < 0, a))

a_pos.sort(reverse=True)
a_neg.sort()

ans = 1
if len(a_pos) == 0 and k % 2 == 1:
    j = len(a_neg) - 1
    for i in range(k):
        ans = ans * a_neg[j] % 100000007
        j -= 1
else:
    i_p = 0
    i_n = 0
    while i_p + i_n < k:
        if i_p + i_n == k - 1 or i_n >= len(a_neg) - 1 or a_pos[i_p] > a_neg[i_n] * a_neg[i_n+1]:
            ans = ans * a_pos[i_p] % 1000000007
            i_p += 1
        else:
            ans = ans * a_neg[i_n] % 1000000007 * a_neg[i_n+1] % 1000000007
            i_n += 2
print(ans)

Submission status: Runtime Error

Solution code:
n_k = list(map(int, input().split()))
n = n_k[0]
k = n_k[1]
a = list(map(int, input().split()))
a_pos = list(filter(lambda v: v > 0, a))
a_neg = list(filter(lambda v: v < 0, a))

a_pos.sort(reverse=True)
a_neg.sort()

ans = 1
if len(a_pos) == 0 and k % 2 == 1:
    j = len(a_neg) - 1
    for i in range(k):
        ans = ans * a_neg[j] % 100000007;
        j = j - 1
else:
    i = 0
    while True:
        if i >= k:
            break
        if i == k - 1 or len(a_neg) < 2 or a_pos[0] > a_neg[0] * a_neg[1]:
            ans = ans * a_pos[0] % 1000000007
            a_pos.pop(0)
            i = i + 1
        else:
            ans = ans * a_neg[0] * a_neg[1] % 1000000007
            a_neg.pop(0)
            a_neg.pop(0)
            i = i + 2
print(ans)

Submission status: Runtime Error

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

def main():
    n,k = map(int, input().split())
    A = map(int, input().split())
    A = sorted(A, key=lambda x: abs(x), reverse=True)

    ans = 1

    minK, maxK = None, None
    for a in A[:k]:
        ans *= a
        if minK is None or a < minK:
            minK = a
        if maxK is None or a > maxK:
            maxK = a

    if ans >= 0:
        print(ans % (10**9+7))
    else:
        minK_1, maxK_1 = None, None
        for a in A[k:]:
            if minK_1 is None or a < minK_1:
                minK_1 = a
            if maxK_1 is None or a > maxK_1:
                maxK_1 = a

        tmpMax = max(ans//minK * maxK_1, ans//maxK * minK_1)
        if tmpMax > ans:
            ans = tmpMax

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

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
A = list(map(int,input().split()))
mod = 10**9 + 7

ans = 1
if k == n:
    for i in A:
        ans*=i
elif sum([A[i]<0 for i in range(n)]) == n and k%2 ==1:
    A = sorted(A, key=abs)
    for i in range(k):
        ans *= A[i]
else:
    nega = []
    posi = []
    for i in A:
        if i>0:
            posi.append(i)
        else:
            nega.append(i)
    posi.sort(reverse=True)
    nega.sort()
    ctr = 0
    pi=0
    ni=0
    if k%2 == 1:
        ans*=posi[pi]
        pi+=1
        ctr+=1
        
    if ctr <k:
        tmp_p = posi[pi]*posi[pi+1]
        tmp_n = nega[ni]*nega[ni+1]
    while ctr < k:
        if tmp_p >= tmp_n:
            ans *= tmp_p
            pi += 2
            ctr+=2
            if ctr<k:
                tmp_p = posi[pi]*posi[pi+1]
        else:
            ans *= tmp_n
            ni += 2
            ctr+=2
            if ctr<k:
                tmp_n = nega[ni]*nega[ni+1]
    

ans %=mod 
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
A = list(map(int,input().split()))
mod = 10**9 + 7

ans = 1
if k == n:
    for i in A:
        ans*=i
elif sum([A[i]<0 for i in range(n)]) == n and k%2 ==1:
    A = sorted(A, key=abs)
    for i in range(k):
        ans *= A[i]
else:
    A = sorted(A, key=abs, reverse=True)
    ctr = 0
    i = 0
    negactr = 0
    posictr = 0
    nega = 1
    posi = 1
    if k%2 ==1:
        while posictr < 1:
            if A[i] > 0:
                posictr+=1
                ans *= A[i]
                ctr += 1
            else:
                negactr +=1
                nega*=A[i]

            if negactr ==2:
                negactr=0
                ctr+=2
                ans*=nega
                nega=1
            i+=1
        posictr=0

    while ctr < k:
        if A[i] > 0:
            posictr+=1
            posi *= A[i]
        else:
            negactr +=1
            nega*=A[i]

        if posictr ==2:
            posictr=0
            ctr+=2
            ans*=posi
            posi=1
        elif negactr ==2:
            negactr=0
            ctr+=2
            ans*=nega
            nega=1
        i+=1

ans %=mod 
print(ans)

Submission status: Runtime Error

Solution code:
import copy
N, K=map(int,input().split())
A=list(map(int,input().split()))
B=sorted([(a,abs(a)) for a in A],key=lambda x:x[1],reverse=True)
R=10**9+7
P=1
minus=0
last_neg=-1
last_pos=-1
for i in range(K):
    if B[i][0]>0:
        if last_pos != -1:
            P = (P * B[last_pos][1]) % R
        last_pos=i
    else:
        if last_neg != -1:
            P = (P * B[last_neg][1]) % R
        minus+=1
        last_neg=i
F=copy.copy(P)
if last_pos!=-1:
    F=(F*B[last_pos][1]) % R
if last_neg!=-1:
    F=(F*B[last_neg][1]) % R
if minus%2==1:
    if K == N:
        print(-F)
        exit()
    first_neg=-1
    first_pos=-1
    count=[0,0]
    for i in range(K,N):
        if count[0]==0 and B[i][0]>0:
            first_pos=i
            count[0]=1
        elif count[1]==0 and B[i][0]<0:
            first_neg=i
            count[1]=1
        elif count==[1,1]:
            break
    if first_pos==-1 and last_pos==-1:
        P = 1
        for i in range(K):
           P = (P * B[N - i - 1][0]) % R
        print(P)
        exit()
    list_product=[]
    if first_neg!=-1:
        list_product.append((P*B[last_neg][1]*B[first_neg][1]) %R)
    if first_pos!=-1:
        P1=(P*B[first_pos][1]) %R
        if last_pos!=-1:
            P1=(P1*B[last_pos][1]) %R
        list_product.append(P1)
    print(max(list_product))
else:
    print(F)

Submission status: Runtime Error

Solution code:
N, K=map(int,input().split())
A=list(map(int,input().split()))
B=sorted([(a,abs(a)) for a in A],key=lambda x:x[1],reverse=True)
R=10**9+7
P=1
minus=0
last_neg=-1
last_pos=-1
for i in range(K):
    if B[i][0]>0:
        if last_pos != -1:
            P = (P * B[last_pos][1]) % R
        last_pos=i
    else:
        if last_neg != -1:
            P = (P * B[last_neg][1]) % R
        minus+=1
        last_neg=i
if minus%2==1:
    first_neg=-1
    first_pos=-1
    count=[0,0]
    for i in range(K,N):
        if count[0]==0 and B[i][0]>0:
            first_pos=i
            count[0]=1
            if last_neg<last_pos:
                count[1]=1
                break
        elif count[1]==0 and B[i][0]<0:
            first_neg=i
            count[1]=1
            if last_pos<last_neg:
                count[0]=1
                break
        elif count==[1,1]:
            break
    if first_pos==-1 and last_pos==-1:
        P = 1
        for i in range(K):
           P = (P * B[N - i - 1][0]) % R
        print(P)
        exit()
    list_product=[]
    if first_neg!=-1:
        list_product.append((P*B[last_neg][1]*B[first_neg][1]) %R)
    if first_pos!=-1 and last_pos!=-1:
        list_product.append((P*B[last_pos][1]*B[first_pos][1]) %R)
    print(max(list_product))
else:
    if last_pos!=-1:
        print((P*B[last_pos][1]*B[last_neg][1]) %R)
    else:
        print((P*B[last_neg][1]) % R)

Submission status: Runtime Error

Solution code:

def main():
    n,k=map(int,input().split())
    A = map(int,input().split())

    def prod(iterables):
        res = None
        for element in iterables:
            tmp = 1
            for e in element:
                tmp *= e
            if res is None or tmp > res:
                res = tmp
        return res
    
    pos, neg = [], []
    for a in A:
        if a >= 0:
            pos.append(a)
        else:
            neg.append(a)

    pos_n, neg_n = len(pos), len(neg)
    ans = None

    for i in range(neg_n):
        if k-i > pos_n:
            continue
        tmp = prod(permutations(neg, i)) * prod(permutations(pos, k-i)) % (10**9+7)
        if ans is None or tmp > ans:
            ans = tmp
    print(ans)
main()

Submission status: Runtime Error

Solution code:


def main():
    n,k=map(int,input().split())
    A = map(int,input().split())

    def prod(iterables):
        res = None
        for element in iterables:
            tmp = 1
            for e in element:
                tmp *= e
            if res is None or tmp > res:
                res = tmp
        return res
    
    pos, neg = [], []
    for a in A:
        if a >= 0:
            pos.append(a)
        else:
            neg.append(a)

    pos_n, neg_n = len(pos), len(neg)
    pos, neg

    ans = None

    for i in range(neg_n):
        if k-i > pos_n:
            continue
        tmp = prod(permutations(neg, i)) * prod(permutations(pos, k-i)) % (10**9+7)
        if ans is None or tmp > ans:
            ans = tmp
    print(ans)
main()

Submission status: Runtime Error

Solution code:
N, K=map(int,input().split())
A=list(map(int,input().split()))
B=sorted([(a,abs(a)) for a in A],key=lambda x:x[1],reverse=True)
R=10**9+7
P=1
minus=0
last_neg=-1
last_pos=-1
for i in range(K):
    if i!=0:
        P=(P*B[i-1][1]) %R
    if B[i][0]>0:
        last_pos=i
    else:
        minus+=1
        last_neg=i
if minus%2==1:
    first_neg=-1
    first_pos=-1
    count=[0,0]
    for i in range(K,N):
        if count[0]==0 and B[i][0]>0:
            first_pos=i
            count[0]=1
            if last_neg<last_pos:
                count[1]=1
                break
        elif count[1]==0 and B[i][0]<0:
            first_neg=i
            count[1]=1
            if last_pos<last_neg:
                count[0]=1
                break
        elif count==[1,1]:
            break
    if last_pos==-1 and first_pos==-1:
        P=1
        for i in range(K):
            P=(P*B[N-i-1][0]) %R
        print(P)
        exit()
    list_product=[]
    if first_neg!=-1:
        list_product.append((P*B[first_neg][1]) %R)
    if first_pos!=-1:
        list_product.append((P*B[first_pos][1]) %R)
    print(max(list_product))
else:
    print(P*B[K-1][1] %R)

Submission status: Runtime Error

Solution code:
N, K=map(int,input().split())
A=list(map(int,input().split()))
B=sorted([(a,abs(a)) for a in A],key=lambda x:x[1],reverse=True)
R=10**9+7
P=1
minus=0
last_neg=-1
last_pos=-1
for i in range(K):
    if i!=0:
        P=P*B[i-1][1]
    if B[i][0]>0:
        last_pos=i
    else:
        minus+=1
        last_neg=i
if minus%2==1:
    first_neg=-1
    first_pos=-1
    count=[0,0]
    for i in range(K,N):
        if count[0]==0 and B[i][0]>0:
            first_pos=i
            count[0]=1
            if last_neg<last_pos:
                count[1]=1
                break
        elif count[1]==0 and B[i][0]<0:
            first_neg=i
            count[1]=1
            if last_pos<last_neg:
                count[0]=1
                break
        elif count==[1,1]:
            break
    if last_pos==-1 and first_pos==-1:
        P=1
        for i in range(K):
            P=(P*B[N-i-1][0]) %R
        print(P)
        exit()
    list_product=[]
    if first_neg!=-1:
        list_product.append((P*B[first_neg][1]) %R)
    if first_pos!=-1:
        list_product.append((P*B[first_pos][1]) %R)
    print(max(list_product))
else:
    print(P*B[K-1][1] %R)

Submission status: Runtime Error

Solution code:

N, K = map(int, input().split())
X = list(map(int, input().split()))
MOD = 10 ** 9 + 7

pos = sorted(v for v in X if v >= 0)
neg = sorted(-v for v in X if v < 0)

ok = False  # True: ans>0, False: ans<0
if pos:
    if N == K:
        # Select all -> number of negatives must be even
        ok = len(neg) % 2 == 0
    else:
        ok = True
else:
    # All negative
    ok = K % 2 == 0

ans = 1
if not ok:
    for i in range(K):
        ans = ans * (-neg[i]) % MOD
else:
    if K % 2 == 1 and pos:
        ans = ans * pos.pop() % MOD

    cand = []
    while len(pos) >= 2:
        x = pos.pop() * pos.pop()
        cand.append(x)

    while len(neg) >= 2:
        x = neg.pop() * neg.pop()
        cand.append(x)

    cand.sort(reverse=True)
    for i in range(K // 2):
        ans = ans * cand[i] % MOD

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

N, K = map(int, input().split())
table = list(map(int, input().split()))
jnum = K - sum(1 for i in table if i >= 0)
q_plus = deque(sorted([i for i in table if i >= 0], reverse=True))
q_mins = deque(sorted([-i for i in table if i < 0], reverse=True))
s_plus = []
s_mins = []
total = 1


if jnum < 0 or jnum % 2 == 0:
    for i in range(K):
        if not q_plus:
            s_mins.append(q_mins.pop())
        elif not q_mins:
            s_plus.append(q_plus.pop())
        elif q_plus[0] > q_mins[0]:
            s_plus.append(q_plus.pop())
        else:
            s_mins.append(q_mins.pop())
    if len(s_mins) % 2 == 1:
        if not q_plus:
            s_plus[-1] = q_mins[0]
        elif not q_mins:
            s_mins[-1] = q_plus[0]
        elif q_mins[0] * s_mins[-1] > q_plus[0] * s_plus[-1]:
            s_plus[-1] = q_mins[0]
        else:
            s_mins[-1] = q_plus[0]
    s_plus.extend(s_mins)
    for j in s_plus:
        total = total * j % (10 ** 9 + 7)

else:
    for i in range(K):
        if not q_plus:
            total = total * q_mins.pop() * -1 % (10 ** 9 + 7)
        elif not q_mins:
            total = total * q_plus.pop() * -1 % (10 ** 9 + 7)
        elif q_plus[-1] > q_mins[-1]:
            total = total * q_mins.pop() * -1 % (10 ** 9 + 7)
        else:
            total = total * q_plus.pop() * -1 % (10 ** 9 + 7)

print(total)

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7

def inv(n):
    n_inv=1
    for i in range(MOD-2):
        n_inv*=n
        n_inv%=MOD
    return n_inv

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



As.sort(key=lambda x:abs(x),reverse=True)
As_srt=sorted(As)

if N==K or (As_srt[-1]<0 and K%2==1):
    ans=1
    for i in range(K):
        ans *= As[N-i-1]
        ans %= MOD
    print(ans)
else:
    ans = 1
    sign = 1
    for i in range(K):
        ans *=As[i]
        ans %=MOD
        if As[i]<0:
            sign *= -1
    if sign < 0:
        # ansを正にする
        rm_p=None
        rm_n=None
        for i in range(K):
            if rm_p!=None and rm_n!=None:
                break
            if rm_p==None and As[K-i]>0:
                rm_p=As[k-i]
            if rm_n==None and As[K-i]<0:
                rm_n=As[K-i]
        
        apd_zp=None
        apd_n=None
        for i in range(N-K):
            if apd_zp!=None and apd_n!=None:
                break
            if apd_zp==None and As[K+i]>=0:
                apd_zp=As[k+i]
            if apd_n==None and As[K+i]<0:
                apd_n=As[K+i]
        if rm_n == None or apd_zp == None:
            rm=rm_p
            apd=apd_n
        elif rm_p == None or apd_n == None:
            rm=rm_n
            apd=apd_zp
        else:
            if abs(rm_p * apd_zp) <= abs(rm_n * apd_n):
               rm=rm_p
               apd=apd_n
            else:
                rm=rm_n
                apd=apd_zp
        ans *= apd
        ans %=MOD
        rm_inv = inv(rm)
        ans *= rm_inv
        ans %= MOD

    print(ans)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10 ** 9+ 7
    ans = 1

    def answer(a):
        ans =1
        for x in a:
            ans *= x
            ans %= mod
        return ans

    if n == k:
        print(answer(a))
        return
    a.sort(reverse=True, key= lambda x:abs(x))
    if sum(x<0 for x in a[:k])%2 == 0:
        print(answer(a[:k])
    else:
        if all(x < 0 for x in a):
            print(answer(a[-k:]))
        else:
            try:
                x1, y1= min([x for x in a[:k] if x > 0]), min([x for x in a[k:] if x < 0])
            except ValueError:
                x1, y1 = 1, 0
            try:
                x2, y2= max([x for x in a[:k] if x < 0]),\
                    max([x for x in a[k:] if x >= 0])
            except ValueError:
                x2, y2 = 1, 0
            if abs(x2*y1) > abs(x1*y2):           
                a[a.index(x1)] = y1
            else:
                a[a.index(x2)] = y2
            print(answer(a[:k]))
            


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10 ** 9+ 7
    ans = 1

    def answer(a):
        ans =1
        for i in range(k):
            ans *= a[i]
            ans %= mod
        print(ans)

    if n == k:
        answer(a)
        return

    if all([True if x < 0 else False for x in a]) and k%2 == 1:
        a.sort(reverse=True)
        answer(a)
        return

    a.sort(reverse=True, key=lambda x: abs(x))
    flag = 1
    for i in range(k):
        if a[i] < 0:
            flag ^= 1
    if flag or 0 in a[:k]:
        answer(a)
        return
    
    x1, x2, y1, y2 = k-1, k-1, k, k
    while a[x1] >= 0 and x1 >= 0:
        x1 -= 1
    while a[x2] < 0 and x2 >= 0:
        x2 -= 1
    while a[y1] < 0 and y1 < n:
        y1 += 1
    while a[y2] >= 0 and y2 < n:
        y2 += 1

    if x1 == -1 or y1 == n:
        a[x2], a[y2] = a[y2], a[x2]
    
    elif x2 == -1 or y2 == n:
        a[x1], a[y1] = a[y1], a[x1]
    else:
        if a[x1]*a[y2] > a[x2]*a[y1]:
            a[x2], a[y2] = a[y2], a[x2]
        else:
            a[x1], a[y1] = a[y1], a[x1]
    answer(a)
    
    

if __name__ == '__main__':
    main()