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:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) > 0 and len(pla) > 0:
        if abs(mia[-1]) <= pla[-1]:
            tmp = pla.pop()
        elif abs(mia[-1]) > pla[-1]:
            tmp = mia.pop()
    elif len(mia) == 0:
        tmp = pla.pop()
    elif len(pla) == 0:
        tmp = mia.pop()
    num.append(tmp)

cnt = sum(i < 0 for i in num)
for i in num:
    ans = ans * i % mod

print(cnt)
if cnt % 2 == 1:
    if len(mia) > 0:
        for i in num[::-1]:
            if i >= 0:
                p, q = i, mia.pop()
                break
        if len(pla) == 0:
            ans *= q * pow(p, mod - 2, mod)
    if len(pla) > 0:
        for i in num[::-1]:
            if i < 0:
                r, s = i, pla.pop()
                break
        if len(mia) == 0:
            ans *= s * pow(r, mod - 2, mod)
    if len(mia) > 0 and len(pla) > 0:
        if p * r >= q * s:
            ans *= s * pow(r, mod - 2, mod)
        if p * r < q * s:
            ans *= q * pow(p, mod - 2, mod)
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
with open('random_pm00.txt') as f:
    n, k = map(int, f.readline().split())
    a = list(map(int, f.readline().split()))
#n, k = map(int, input().split())
#a = list(map(int, input().split()))
mod = 10 ** 9 + 7

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) > 0 and len(pla) > 0:
        if abs(mia[-1]) <= pla[-1]:
            tmp = pla.pop()
        elif abs(mia[-1]) > pla[-1]:
            tmp = mia.pop()
    elif len(mia) == 0:
        tmp = pla.pop()
    elif len(pla) == 0:
        tmp = mia.pop()
    num.append(tmp)

cnt = sum(i < 0 for i in num)
for i in num:
    ans = ans * i % mod

print(cnt)
if cnt % 2 == 1:
    if len(mia) > 0:
        for i in num[::-1]:
            if i >= 0:
                p, q = i, mia.pop()
                break
        if len(pla) == 0:
            ans *= q * pow(p, mod - 2, mod)
    if len(pla) > 0:
        for i in num[::-1]:
            if i < 0:
                r, s = i, pla.pop()
                break
        if len(mia) == 0:
            ans *= s * pow(r, mod - 2, mod)
    if len(mia) > 0 and len(pla) > 0:
        if p * r >= q * s:
            ans *= s * pow(r, mod - 2, mod)
        if p * r < q * s:
            ans *= q * pow(p, mod - 2, mod)
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if not P or not N:
    A.sort(key=lambda a: abs(a), reverse=True)
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if ans < 0:
            ans *= N.pop()
        if ans >= 0:
            ans *= P.pop()
        break

    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop() * P.pop()
        else:
            ans *= N.pop() * N.pop()
        K -= 2
        continue
    if len(P) <= 1 or len(N) <= 1:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            continue

        if len(N) == 1:
            n = N.pop()
            if ans < 0:
                ans *= n
                K -= 1
            continue

        if len(P) == 1:
            p = P.pop()
            if K % 2 == 0 and ans < 0 or K % 2 == 1 and ans > 0:
                ans *= p
                K -= 1

print(ans % MOD)

Submission status: Runtime Error

Solution code:
from collections import deque

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

P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if not P or not N:
    A.sort(key=lambda a: abs(a), reverse=True)
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if ans < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        break

    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop() * P.pop()
        else:
            ans *= N.pop() * N.pop()
        K -= 2
        continue
    if len(P) <= 1 or len(N) <= 1:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            continue

        if len(N) == 1:
            n = N.pop()
            if ans < 0:
                ans *= n
                K -= 1
            continue

        if len(P) == 1:
            p = P.pop()
            if ans < 0 and K % 2 == 0 or ans >= 0 and K % 2 == 1:
                ans *= p
                K -= 1
            continue

print(ans % MOD)

Submission status: Runtime Error

Solution code:
from collections import deque

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

P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if ans < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        break

    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop() * P.pop()
        else:
            ans *= N.pop() * N.pop()
        K -= 2
        continue
    if len(P) <= 1 or len(N) <= 1:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            continue

        if len(N) == 1:
            n = N.pop()
            if ans < 0:
                ans *= n
                K -= 1
            continue

        if len(P) == 1:
            p = P.pop()
            if ans < 0 and K % 2 == 0 or ans >= 0 and K % 2 == 1:
                ans *= p
                K -= 1
            continue

print(ans % MOD)

Submission status: Runtime Error

Solution code:
from collections import deque

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

P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if ans < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        break

    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop() * P.pop()
        else:
            ans *= N.pop() * N.pop()
        K -= 2
        continue
    if len(P) <= 1 or len(N) <= 1:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            continue

        if len(N) == 1:
            n = N.pop()
            if ans < 0:
                ans *= n
                K -= 1
            continue

        if len(P) == 1:
            p = P.pop()
            if ans < 0 and K % 2 == 0 or ans >= 0 and K % 2 == 1:
                ans *= p
                K -= 1
            continue
        1 / 0

print(ans % MOD)

Submission status: Runtime Error

Solution code:
from collections import deque

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

P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if ans < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        break

    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop() * P.pop()
        else:
            ans *= N.pop() * N.pop()
        K -= 2
        continue
    if len(P) <= 1 or len(N) <= 1:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            continue

        if len(N) == 1:
            n = N.pop()
            if ans < 0:
                ans *= n
                K -= 1
            continue

        if len(P) == 1:
            p = P.pop()
            if ans < 0 and K % 2 == 0 or ans >= 0 and K % 2 == 1:
                ans *= p
                K -= 1
            continue
    1 / 0

print(ans % MOD)

Submission status: Runtime Error

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) > 0 and len(pla) > 0:
        if abs(mia[-1]) <= pla[-1]:
            tmp = pla.pop()
        elif abs(mia[-1]) > pla[-1]:
            tmp = mia.pop()
    elif len(mia) == 0:
        tmp = pla.pop()
    elif len(pla) == 0:
        tmp = mia.pop()
    num.append(tmp)

cnt = sum(i < 0 for i in num)
for i in num:
    ans = ans * i % mod

if cnt % 2 == 1:
    if len(mia) > 0:
        for i in num[::-1]:
            if i >= 0:
                a, b = i, mia.pop()
                break
        if len(pla) == 0:
            ans *= b * pow(a, mod - 2, mod)
    if len(pla) > 0:
        for i in num[::-1]:
            if i < 0:
                c, d = i, pla.pop()
                break
        if len(mia) == 0:
            ans *= d * pow(c, mod - 2, mod)
    if len(mia) > 0 and len(pla) > 0:
        if a * d >= b * c:
            ans *= d * pow(c, mod - 2, mod)
        if a * d < b * c:
            ans *= b * pow(a, mod - 2, mod)
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if ans < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        break

    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop() * P.pop()
        else:
            ans *= N.pop() * N.pop()
        K -= 2
    else:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            continue

        if len(N) == 1:
            n = N.pop()
            if ans < 0:
                ans *= n
                K -= 1
            continue

        if len(P) == 1:
            p = P.pop()
            if ans < 0 and K % 2 == 0 or ans >= 0 and K % 2 == 1:
                ans *= p
                K -= 1
            continue

        1 / 0

print(ans % MOD)

Submission status: Runtime Error

Solution code:
from collections import deque

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

P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if ans < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        break

    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop() * P.pop()
        else:
            ans *= N.pop() * N.pop()
        K -= 2
    else:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            continue

        if len(N) == 1:
            n = N.pop()
            if K % 2 == 1:
                ans *= n
                K -= 1
            continue

        if len(P) == 1:
            p = P.pop()
            if ans < 0 and K % 2 == 0 or ans >= 0 and K % 2 == 1:
                ans *= p
                K -= 1
            continue

        1 / 0

print(ans % MOD)

Submission status: Runtime Error

Solution code:
from collections import deque

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

P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if ans < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        break

    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop() * P.pop()
        else:
            ans *= N.pop() * N.pop()
        K -= 2
    else:
        if len(N) == 1:
            n = N.pop()
            if ans < 0:
                ans *= n
                K -= 1
            continue

        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            continue

        if len(P) == 1:
            p = P.pop()
            if K % 2 == 1:
                ans *= p
                K -= 1
            continue

        1 / 0

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

1 / 0
P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if ans < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        break

    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop() * P.pop()
        else:
            ans *= N.pop() * N.pop()
        K -= 2
    else:
        if len(N) == 1:
            n = N.pop()
            if ans < 0:
                ans *= n
                K -= 1
            continue
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue
        if len(P) == 1:
            p = P[-1]
            n = N[-1] * N[-2]
            if p > n:
                ans *= P.pop()
                K -= 1
            else:
                ans *= N.pop() * N.pop()
                K -= 2
        else:
            ans *= N.pop() * N.pop()
            K -= 2

print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop


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

MOD = 10**9 + 7

# case1. N == K のときは答えは確定
if N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
# case2. A が全部負の数のとき、 Kが奇数ならば残念ながら答えは負になるのでなるべく絶対値を小さくする
elif max(A) < 0 and K % 2 == 1:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
else:
    # case3. それ以外は正にできる

    # K が奇数のとき、非負要素から1つ取って偶数の場合に帰着
    # K が偶数のとき、面倒なので 2 つセットで考えて K//2 個取る問題に帰着

    if K%2 == 1:
        ans = A.pop(0)  # あらかじめ最大値を確保
        n = (K-1)//2
    else:
        ans = 1
        n = K//2

    # 絶対値の降順にソートする
    A = sorted(A, key=lambda x: abs(x), reverse=True)

    # 候補テーブルを作成
    cand = []  # 非負要素、負要素をそれぞれ絶対値の大きい順に 2 つずつ掛けたもの

    BIGINT = 10**9 + 1  # tmp 用
    tmp1 = BIGINT
    tmp2 = BIGINT
    for a in A:
        if a >= 0:
            if tmp1 == BIGINT:
                tmp1 = A
            else:
                heappush(cand, -tmp1*a)
                tmp1 = BIGINT
        else:
            if tmp2 == BIGINT:
                tmp2 = a
            else:
                heappush(cand, -tmp2*a)
                tmp2 = BIGINT

    # あとは大きい方から n 個取る
    for i in range(n):
        ans *= -heappop(cand)
        ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
def e_multiplication_4(MOD=10**9 + 7):
    from functools import reduce
    N, K = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]

    sign = {-1: 0, 0: 0, 1: 0}  # A の各要素の符号
    for a in A:
        sign[a // abs(a)] += 1

    if sign[1] == 0 and K % 2 == 1:
        # どうやっても解は負。絶対値の小さなものから掛けていく
        A.sort(reverse=True)
        return reduce(lambda x, y: (x * y) % MOD, A[:K])
    if sign[1] == 0 and K % 2 == 0:
        # 先程と違って絶対値の大きなものから掛けても解は正になる
        A.sort()
        return reduce(lambda x, y: (x * y) % MOD, A[:K])

    A.sort()
    ans = 1
    i, j = 0, N - 1
    while K > 0:
        # 負の絶対値が大きいものから 2 個取るか？　正の絶対値が大きいものから 1 個取るか？
        # i, j がそれぞれ負の値、非負の値を指さなくなった場合、if 文のどちらかを
        # 確実に通らなくなるので、i, j についての条件は必要ない
        if K > 1 and A[i] * A[i + 1] >= A[j] * A[j - 1]:
            ans *= A[i] * A[i + 1]
            i += 2
            K -= 2
        else:
            ans *= A[j]
            j -= 1
            K -= 1
        ans %= MOD
    return ans

print(e_multiplication_4())

Submission status: Runtime Error

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

# case1. N == K のときは答えは確定
if N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
# case2. A が全部負の数のとき、 Kが奇数ならば残念ながら答えは負になるのでなるべく絶対値を小さくする
elif max(A) < 0 and K % 2 == 1:
    ans = 1
    A = sorted(A, reverse=True)
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
else:
    # case3. それ以外は正にできるので、絶対値の降順にソートする
    A = sorted(A, key=lambda x: abs(x), reverse=True)

    # 候補テーブルを作成
    A1 = []  # 非負要素のリスト（降順）
    A2 = []  # 負要素を絶対値の大きい順に2つずつ掛けたリスト（降順）
    tmp = 1
    for a in A:
        if a >= 0:
            A1.append(a)
        else:
            if tmp != 1:
                A2.append(tmp*a)
                tmp = 1
            else:
                tmp *= a

    # cost が K を上回らなように大きいものから埋めていく〜
    cost = 0
    while cost < K:
        if (K - cost) >= 2:
            # このときは A2 からも入れてよし
            if A1 and A2:
                if A1[0] >= A2[0]:
                    cost += 1
                    ans *= A1.pop(0)
                else:
                    cost += 2
                    ans *= A2.pop(0)
            elif A1:
                cost += 1
                ans *= A1.pop(0)
            else:
                cost += 2
                ans *= A2.pop(0)
            ans %= MOD
        else:
            cost += 1
            ans *= A1.pop(0)
            ans %= MOD

    print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))
def main():
    N,K = inpl()
    Als = inpl()

    Als = sorted(Als,key=lambda x:abs(x),reverse=True)

    bans = 1
    count = 0
    last = 0
    llast = 0
    for i,a in enumerate(Als[:K]):
        if a < 0:
            count += 1
            llast = i
        else:
            last = i
        bans = (bans * abs(a))%mod

    if count % 2 == 0:
        print(bans%mod)
    elif K==N:
        print(bans%mod)
    else:
        for item in Als[K+1:]:
            if item < 0:
                cans = int(bans/Als[last])
                cans = (bans * abs(item))%mod
                break
        else:
            print((int(bans/abs(Als[llast]))*Als[K+1])%mod)
            return
        for item2 in Als[K+1:]:
            if item2 >0:
                dans = int(bans/abs(Als[llast]))
                dans = (dans * item2)%mod
                break
        else:
            print((int(bans/abs(Als[llast]))*Als[K+1])%mod)
            return
        ans = max(cans,dans)
        print(ans)
main()

Submission status: Runtime Error

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

# case1. N == K のときは答えは確定
if N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
# case2. A が全部負の数のとき、 Kが奇数ならば残念ながら答えは負になるのでなるべく絶対値を小さくする
elif max(A) < 0 and K % 2 == 1:
    ans = 1
    A = sorted(A, reverse=True)
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
else:
    # case3. それ以外は正にできるので、絶対値の降順にソートする
    A = sorted(A, key=lambda x: abs(x), reverse=True)
    # とりあえず大きい順に K 個掛けてみる
    ans = 1
    for i in range(K):
        ans *= A[i]
    if ans >= 0:
        ans %= MOD
        print(ans)
    else:
        # 取り除く対象を old, 取り込む対象を new とする
        # case3-1. 負数を取り除いて非負数を取り込む
        # まずは new を探す
        j = K
        while j < N and A[j] < 0:
            j += 1
        if j < N:
            new1 = A[j]
        # old を探す
        l = K-1
        while A[l] >= 0:
            l -= 1
        old1 = A[l]
        if new1 and old1:
            cand1 = ans // old1 * new1
        # case3-2. 非負数を取り除いて負数を取り込む
        # まずは new を探す
        j = K
        while j < N and A[j] >= 0:
            j += 1
        if j < N:
            new2 = A[j]
        # old を探す
        l = K-1
        while A[l] < 0:
            l -= 1
        old2 = A[l]
        if new2 and old2:
            cand2 = ans // old2 * new2

        if cand1 and cand2:
            ans = max(cand1, cand2) % MOD
        elif cand1:
            ans = cand1 % MOD
        else:
            ans = cand2 % MOD
        print(ans)

Submission status: Runtime Error

Solution code:
with open('random_pm00.txt') as f:
    n, k = map(int, f.readline().split())
    a = list(map(int, f.readline().split()))
#n, k = map(int, input().split())
#a = list(map(int, input().split()))
mod = 10 ** 9 + 7
print(n,k)

mia, pla = [], []
for ai in a:
    if ai < 0:
        mia.append(ai)
    elif ai >= 0:
        pla.append(ai)
mia.sort(reverse=True)
pla.sort()

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i % mod
else:
    while k > 0:
        if k == 1 or len(mia) <= 1:
            if len(pla) == 0:
                cnt = cnt * mia.pop() % mod
            elif len(pla) > 0:
                cnt = cnt * pla.pop() % mod
            k -= 1
        elif len(pla) <= 1:
            if k == 1:
                cnt = cnt * pla.pop() % mod
                k -= 1
            elif k > 1:
                cnt = cnt * mia.pop() * mia.pop() % mod
                k -= 2
        elif len(pla) >= 2 and len(mia) >= 2:
            if pla[-1] * pla[-2] > mia[-1] * mia[-2]:
                cnt = cnt * pla.pop() % mod
                k -= 1
            elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
                cnt = cnt * mia.pop() * mia.pop() % mod
                k -= 2
print(cnt)

Submission status: Runtime Error

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

# case1. N == K のときは答えは確定
if N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
# case2. A が全部負の数のとき、 Kが奇数ならば残念ながら答えは負になるのでなるべく絶対値を小さくする
elif max(A) < 0 and K % 2 == 1:
    ans = 1
    A = sorted(A, reverse=True)
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
else:
    # case3. それ以外は正にできるので、絶対値の降順にソートする
    A = sorted(A, key=lambda x: abs(x), reverse=True)
    # とりあえず大きい順に K 個掛けてみる
    ans = 1
    for i in range(K):
        ans *= A[i]
    if ans >= 0:
        ans %= MOD
        print(ans)
    else:
        # 取り除く対象を old, 取り込む対象を new とする
        # case3-1. 負数を取り除いて非負数を取り込む
        # まずは new を探す
        j = K
        while j < N or A[j] < 0:
            j += 1
        if j < N:
            new1 = A[j]
        # old を探す
        l = K-1
        while A[l] >= 0:
            l -= 1
        old1 = A[l]
        if new1 and old1:
            cand1 = ans // old1 * new1
        # case3-2. 非負数を取り除いて負数を取り込む
        # まずは new を探す
        j = K
        while j < N or A[j] >= 0:
            j += 1
        if j < N:
            new2 = A[j]
        # old を探す
        l = K-1
        while A[l] < 0:
            l -= 1
        old2 = A[l]
        if new2 and old2:
            cand2 = ans // old2 * new2

        if cand1 and cand2:
            print(cand1, cand2)
            ans = max(cand1, cand2) % MOD
        elif cand1:
            ans = cand1 % MOD
        else:
            ans = cand2 % 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

# case1. N == K のときは答えは確定
if N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
# case2. A が全部負の数のとき、 Kが奇数ならば残念ながら答えは負になるのでなるべく絶対値を小さくする
elif max(A) < 0 and K % 2 == 1:
    ans = 1
    A = sorted(A, reverse=True)
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
else:
    # case3. それ以外は正にできるので、絶対値の降順にソートする
    A = sorted(A, key=lambda x: abs(x), reverse=True)
    # とりあえず大きい順に K 個掛けてみる
    ans = 1
    for i in range(K):
        ans *= A[i]
    if ans >= 0:
        ans %= MOD
        print(ans)
    else:
        # 取り除く対象を old, 取り込む対象を new とする
        # case3-1. 負数を取り除いて非負数を取り込む
        # まずは new を探す
        j = K
        while j < N or A[j] < 0:
            j += 1
        if j < N:
            new1 = A[j]
        # old を探す
        l = K-1
        while A[l] >= 0:
            l -= 1
        old1 = A[l]
        if new1 and old1:
            cand1 = ans * pow(old1, MOD-2, MOD) * new1
        # case3-2. 非負数を取り除いて負数を取り込む
        # まずは new を探す
        j = K
        while j < N or A[j] >= 0:
            j += 1
        if j < N:
            new2 = A[j]
        # old を探す
        l = K-1
        while A[l] < 0:
            l -= 1
        old2 = A[l]
        if new2 and old2:
            cand2 = ans * pow(old2, MOD-2, MOD) * new2

        if cand1 and cand2:
            print(cand1, cand2)
            ans = max(cand1, cand2) % MOD
        elif cand1:
            ans = cand1 % MOD
        else:
            ans = cand2 % MOD
        print(ans)