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())
l=sorted(list(map(int,input().split())))
MOD=1000000007

def maxProductSubarrayOfSizeK(A, n, k):
    t=1
    #case 1: when the max.element is 0 and k is odd
    if(max(l)==0 and k%2!=0):
        return 0
    #case 2:when the max.element is less than 0 and k is again odd
    if(l[n-1]<=0 and k%2!=0):
        for i in range(n-1,n-k+1,-1):
            t=t*l[i]
            t=t%MOD
        return t%MOD
    s=k//2
    i=0
    j=n-1
    #case3: when the max.element is greater than 0 and k is odd
    if(l[n-1]>0 and k%2!=0):
          y=a[n-1]
          j=j-1
          s=s-1
    
    #case 4 when k is even
    for i in range(s):
        lp=a[i]*a[i+1]
        rp=a[j]*a[j-1]
        if(lp>rp):
            t=t*lp
            i=i+2   
            t%=MOD
        else:
            t=t*lp
            j=j-2
            t%=MOD
    return t%MOD
print(maxProductSubarrayOfSizeK(l,n,k))

Submission status: Runtime Error

Solution code:
n = int(input())
print(-n % 1000)

Submission status: Runtime Error

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

b0=[]
c0=[]

for i in a0:
	if i<0:
		b0+=[-i]
		c0+=[-1]
	else:
		b0+=[i]
		c0+=[1]

import numpy as np
d0=np.array([a0,b0,c0])
d=d0[:, d0[1].argsort()]

indexer = np.lexsort((c0, b0))
b1=[b0[i] for i in indexer]
c1=[c0[i] for i in indexer]

if max(c1)==-1 and K%2==1:
	ans=1
	for i in range(K):
		ans*=-b1[i]
		ans=ans%(10**9+7)
	
	print(ans)

elif c1[(N-K):N].count(-1)%2==0:
	ans=1
	for i in range(N-K,N):
		ans*=b1[i]
		ans=ans%(10**9+7)
	
	print(ans)

elif c1[(N-K):N].count(-1)%2==1:
	alt1=b1[N-K-1-c1[0:(N-K)][::-1].index(1)]
	subst1=b1[c1[(N-K):N].index(-1)]
	alt2=b1[N-K-1-c1[0:(N-K)][::-1].index(-1)]
	subst2=b1[c1[(N-K):N].index(1)]
	if alt1*subst2>alt2*subst1:
		b1[N-K-1-c1[0:(N-K)][::-1].index(1)]=subst1
	else:
		b1[N-K-1-c1[0:(N-K)][::-1].index(-1)]=subst2
	
	ans=1
	for i in range(N-K,N):
		ans*=b1[i]
		ans=ans%(10**9+7)
	
	print(ans)

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    an = sorted([i for i in a if i < 0])
    ap = sorted([i for i in a if i > 0], reverse = True)
    a_s = list(sorted(a, key = lambda x: -abs(x)))
    num_n = 0
    num_p = 0
    zero = False
    ans = 1
    old_n = 0
    ald_p = 0
    if k == 1:
        print(max(a)%mod)
        return
    if k == n:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    for ai in a_s[:k]:
        if ai < 0:
            old_n = ai
            num_n += 1
        elif ai > 0:
            old_p = ai
            num_p += 1
        else:
            zero = True
    if zero:
        print(0)
        return
    if num_n%2 == 0:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    elif len([i for i in a if i > 0]) == 0:
        a_sr = list(sorted(a, reverse=True))[:k]
        for ai in a_sr:
            ans *= ai
            ans %= mod
        print(ans)
        return
    else:
        next_n = 0
        next_p = 0
        for i in a_s[k:]:
            if i < 0:
                next_n = i
                break
        for i in a_s[k:]:
            if i > 0:
                next_p = i
                break
        if old_p*next_p > old_n*next_n or next_n == 0:
            for ai in a_s[:k]:
                if ai == old_n:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_p
            ans %= mod
            print(ans)
            return
        else:
            print(-1)
            return
            for ai in a_s[:k]:
                if ai == old_p:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_n
            ans %= mod
            print(ans)
            return
        

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    an = sorted([i for i in a if i < 0])
    ap = sorted([i for i in a if i > 0], reverse = True)
    a_s = list(sorted(a, key = lambda x: -abs(x)))
    num_n = 0
    num_p = 0
    zero = False
    ans = 1
    old_n = 0
    ald_p = 0
    if k == 1:
        print(max(a)%mod)
        return
    if k == n:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    for ai in a_s[:k]:
        if ai < 0:
            old_n = ai
            num_n += 1
        elif ai > 0:
            old_p = ai
            num_p += 1
        else:
            zero = True
    if zero:
        print(0)
        return
    if num_n%2 == 0:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    elif len([i for i in a if i > 0]) == 0:
        a_sr = list(sorted(a, reverse=True))[:k]
        for ai in a_sr:
            ans *= ai
            ans %= mod
        print(ans)
        return
    else:
        next_n = 0
        next_p = 0
        for i in a_s[k:]:
            if i < 0:
                next_n = i
                break
        for i in a_s[k:]:
            if i > 0:
                next_p = i
                break
        if old_p*next_p > old_n*next_n or next_n == 0:
            for ai in a_s[:k]:
                if ai == old_n:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_p
            ans %= mod
            print(ans)
            return
        else:
            for ai in a_s[:k]:
                if ai == old_p:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_n
            ans %= mod
            print(ans)
            return
        

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

b0=[]
c0=[]

for i in a0:
	if i<0:
		b0+=[-i]
		c0+=[-1]
	else:
		b0+=[i]
		c0+=[1]

import numpy as np
d0=np.array([a0,b0,c0])
d=d0[:, d0[1].argsort()]

indexer = np.lexsort((c0, b0))
b1=[b0[i] for i in indexer]
c1=[c0[i] for i in indexer]

if c1[(N-K):N].count(-1)%2==0:
	ans=1
	for i in range(N-K,N):
		ans*=b1[i]
		ans=ans%(10**9+7)
	
	print(ans)

elif c1[(N-K):N].count(-1)%2==1:
	alt1=b1[N-K-1-c1[0:(N-K)][::-1].index(1)]
	subst1=b1[c1[(N-K):N].index(-1)]
	alt2=b1[N-K-1-c1[0:(N-K)][::-1].index(-1)]
	subst2=b1[c1[(N-K):N].index(1)]
	if alt1*subst2>alt2*subst1:
		b1[N-K-1-c1[0:(N-K)][::-1].index(1)]=subst1
	else:
		b1[N-K-1-c1[0:(N-K)][::-1].index(-1)]=subst2
	
	ans=1
	for i in range(N-K,N):
		ans*=b1[i]
		ans=ans%(10**9+7)
	
	print(ans)

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    an = sorted([i for i in a if i < 0])
    ap = sorted([i for i in a if i > 0], reverse = True)
    a_s = list(sorted(a, key = lambda x: -abs(x)))
    num_n = 0
    num_p = 0
    zero = False
    ans = 1
    old_n = 0
    ald_p = 0
    if k == 1:
        print(max(a)%mod)
        return
    if k == n:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    for ai in a_s[:k]:
        if ai < 0:
            old_n = ai
            num_n += 1
        elif ai > 0:
            old_p = ai
            num_p += 1
        else:
            zero = True
    if zero:
        print(0)
        return
    if num_n%2 == 0:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    elif len([i for i in a if i > 0]) == 0:
        a_sr = list(sorted(a, reverse=True))[:k]
        for ai in a_sr:
            ans *= ai
            ans %= mod
        print(ans)
        return
    else:
        next_n = 0
        next_p = 0
        for i in a_s[k:]:
            if i < 0:
                next_n = i
                break
        for i in a_s[k:]:
            if i > 0:
                next_p = i
                break
        if (old_p*next_p > old_n*next_n) or (next_n == 0):
            for ai in a_s[:k]:
                if ai == old_n:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_p
            ans %= mod
            print(ans)
            return
        else:
            for ai in a_s[:k]:
                if ai == old_p:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_n
            ans %= mod
            print(ans)
            return
        

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    an = sorted([i for i in a if i < 0])
    ap = sorted([i for i in a if i > 0], reverse = True)
    a_s = list(sorted(a, key = lambda x: -abs(x)))
    num_n = 0
    num_p = 0
    zero = False
    ans = 1
    old_n = 0
    ald_p = 0
    if k == 1:
        print(max(a)%mod)
        return
    if k == n:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    for ai in a_s[:k]:
        if ai < 0:
            old_n = ai
            num_n += 1
        elif ai > 0:
            old_p = ai
            num_p += 1
        else:
            zero = True
    if zero:
        print(0)
        return
    if num_n%2 == 0:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    elif len([i for i in a if i > 0]) == 0:
        print(-1)
        return
        a_sr = list(sorted(a, reverse=True))[:k]
        for ai in a_sr:
            ans *= ai
            ans %= mod
        print(ans)
        return
    else:
        next_n = 0
        next_p = 0
        for i in a_s[k:]:
            if i < 0:
                next_n = i
                break
        for i in a_s[k:]:
            if i > 0:
                next_p = i
                break
        if old_p*next_p > old_n*next_n or next_n == 0:
            for ai in a_s[:k]:
                if ai == old_n:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_p
            ans %= mod
            print(ans)
            return
        else:
            for ai in a_s[:k]:
                if ai == old_p:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_n
            ans %= mod
            print(ans)
            return
        

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    an = sorted([i for i in a if i < 0])
    ap = sorted([i for i in a if i > 0], reverse = True)
    a_s = list(sorted(a, key = lambda x: -abs(x)))
    num_n = 0
    num_p = 0
    zero = False
    ans = 1
    old_n = 0
    ald_p = 0
    if k == 1:
        print(max(a)%mod)
        return
    if k == n:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    for ai in a_s[:k]:
        if ai < 0:
            old_n = ai
            num_n += 1
        elif ai > 0:
            old_p = ai
            num_p += 1
        else:
            zero = True
    if zero:
        print(0)
        return
    if num_n%2 == 0:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    elif len([i for i in a if i > 0]) == 0:
        print(-1)
            return
        a_sr = list(sorted(a, reverse=True))[:k]
        for ai in a_sr:
            ans *= ai
            ans %= mod
        print(ans)
        return
    else:
        next_n = 0
        next_p = 0
        for i in a_s[k:]:
            if i < 0:
                next_n = i
                break
        for i in a_s[k:]:
            if i > 0:
                next_p = i
                break
        if old_p*next_p > old_n*next_n or next_n == 0:
            for ai in a_s[:k]:
                if ai == old_n:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_p
            ans %= mod
            print(ans)
            return
        else:
            for ai in a_s[:k]:
                if ai == old_p:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_n
            ans %= mod
            print(ans)
            return
        

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    an = sorted([i for i in a if i < 0])
    ap = sorted([i for i in a if i > 0], reverse = True)
    a_s = list(sorted(a, key = lambda x: -abs(x)))
    num_n = 0
    num_p = 0
    zero = False
    ans = 1
    old_n = 0
    ald_p = 0
    if k == 1:
        print(max(a)%mod)
        return
    if k == n:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    for ai in a_s[:k]:
        if ai < 0:
            old_n = ai
            num_n += 1
        elif ai > 0:
            old_p = ai
            num_p += 1
        else:
            zero = True
    if zero:
        print(0)
        return
    if num_n%2 == 0:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    elif len([i for i in a if i > 0]) == 0:
        a_sr = list(sorted(a, reverse=True))[:k]
        for ai in a_sr:
            ans *= ai
            ans %= mod
        print(ans)
        return
    else:
        print(-1)
            return
        next_n = 0
        next_p = 0
        for i in a_s[k:]:
            if i < 0:
                next_n = i
                break
        for i in a_s[k:]:
            if i > 0:
                next_p = i
                break
        if old_p*next_p > old_n*next_n or next_n == 0:
            for ai in a_s[:k]:
                if ai == old_n:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_p
            ans %= mod
            print(ans)
            return
        else:
            for ai in a_s[:k]:
                if ai == old_p:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_n
            ans %= mod
            print(ans)
            return
        

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    an = sorted([i for i in a if i < 0])
    ap = sorted([i for i in a if i > 0], reverse = True)
    a_s = list(sorted(a, key = lambda x: -abs(x)))
    num_n = 0
    num_p = 0
    zero = False
    ans = 1
    old_n = 0
    ald_p = 0
    if k == 1:
        print(max(a)%mod)
        return
    if k == n:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    for ai in a_s[:k]:
        if ai < 0:
            old_n = ai
            num_n += 1
        elif ai > 0:
            old_p = ai
            num_p += 1
        else:
            zero = True
    if zero:
        print(0)
        return
    if num_n%2 == 0:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    elif len([i for i in a if i > 0]) == 0:
        a_sr = list(sorted(a, reverse=True))[:k]
        for ai in a_sr:
            ans *= ai
            ans %= mod
        print(ans)
        return
    else:
        next_n = 0
        next_p = 0
        for i in a_s[k:]:
            if i < 0:
                next_n = i
                break
        for i in a_s[k:]:
            if i > 0:
                next_p = i
                break
        if old_p*next_p > old_n*next_n or next_n == 0:
            print(-1)
            return
            for ai in a_s[:k]:
                if ai == old_n:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_p
            ans %= mod
            print(ans)
            return
        else:
            for ai in a_s[:k]:
                if ai == old_p:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_n
            ans %= mod
            print(ans)
            return
        

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    mod = 10 ** 9 + 7

    As = sorted(A)

    M = 0
    Z = 0

    for i in range(N):
        if As[i] < 0:
            M += 1
        elif A[i] == 0:
            Z += 1

    P = N - M - Z

    if K - P - M > 0:
        print(0)
        sys.exit()

    if N == K:
        res = 1
        for i in range(K):
            res *= A[i]
            res %= mod
        print(res)
        sys.exit()

    if (N == M) & (K % 2 == 1):
        res = 1
        for i in range(K):
            res *= As[M-1-i]
            res %= mod
        print(res)
        sys.exit()

    multiM = [1] * (M+1)
    multiP = [1] * (P+1)

    for i in range(1,M+1):
        multiM[i] = multiM[i-1] * As[i-1]
        if multiM[i] >= 0:
            multiM[i] %= mod
        else:
            multiM[i] = ((- multiM[i]) % mod) * (-1)

    for i in range(1,P+1):
        multiP[i] = multiP[i-1] * As[N-i]

    res = -1

    for i in range(M+1):
        if i + P < K:
            continue
        temp = multiM[i] * multiP[K-i]
        if temp < 0:
            continue
        temp %= mod
        res = max(res,temp)

    print(res)



main()

Submission status: Runtime Error

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    mod = 10 ** 9 + 7

    As = sorted(A)

    M = 0
    Z = 0

    for i in range(N):
        if As[i] < 0:
            M += 1
        elif A[i] == 0:
            Z += 1

    P = N - M - Z

    if N - P - M > 0:
        print(0)
        sys.exit()

    if N == K:
        res = 1
        for i in range(K):
            res *= A[i]
            res %= mod
        print(res)
        sys.exit()

    if (N == M) & (K % 2 == 1):
        res = 1
        for i in range(K):
            res *= As[M-1-i]
            res %= mod
        print(res)
        sys.exit()

    multiM = [1] * (M+1)
    multiP = [1] * (P+1)

    for i in range(1,M+1):
        multiM[i] = multiM[i-1] * As[i-1]
        if multiM[i] >= 0:
            multiM[i] %= mod
        else:
            multiM[i] = ((- multiM[i]) % mod) * (-1)

    for i in range(1,P+1):
        multiP[i] = multiP[i-1] * As[N-i]

    res = -1

    for i in range(M+1):
        if i + P < K:
            continue
        temp = multiM[i] * multiP[K-i]
        if temp < 0:
            continue
        temp %= mod
        res = max(res,temp)

    print(res)



main()

Submission status: Runtime Error

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
        ans %= MOD
    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()
        ans %= MOD
    print(ans % MOD)
    exit()

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

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

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

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

ans = 1
mod = 10 ** 9 + 7
if len(A_p) == 0 and K % 2 != 0:
    while K != 0:
        ans = ans * A_n[0] % mod
        A_n.popleft()
        K -= 1
elif 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[0] * A_n[1]:
                ans = ans * A_p[0] * A_p[1] % mod
                A_p.popleft()
                A_p.popleft()
            else:
                ans = ans * A_n[0] * A_n[1] % mod
                A_n.popleft()
                A_n.popleft()
        elif len(A_p) >= 2:
            ans = ans * A_p[0] * A_p[1] % mod
            A_p.popleft()
            A_p.popleft()
        elif len(A_n) >= 2:
            ans = ans * A_n[0] * A_n[1] % mod
            A_n.popleft()
            A_n.popleft()
        K -= 2
else:
    while K > 1:
        if len(A_p) >= 2 and len(A_n) >= 2:
            if A_p[0] * A_p[1] > A_n[0] * A_n[1]:
                ans = ans * A_p[0] * A_p[1] % mod
                A_p.popleft()
                A_p.popleft()
            else:
                ans = ans * A_n[0] * A_n[1] % mod
                A_n.popleft()
                A_n.popleft()
        elif len(A_p) >= 2:
            ans = ans * A_p[0] * A_p[1] % mod
            A_p.popleft()
            A_p.popleft()
        elif len(A_n) >= 2:
            ans = ans * A_n[0] * A_n[1] % mod
            A_n.popleft()
            A_n.popleft()
        K -= 2
    ans = ans * A_p[0] % mod

print(ans)

Submission status: Runtime Error

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

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

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

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

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

    num.sort(reverse=True)

    for i in range(k // 2):
        ans *= num[i]
        ans %= MOD
    
    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()))

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

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

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

n_minus = 0
for a in A:
    if a < 0:
        n_minus += 1

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

elif n_minus == N and K % 2 == 1:
    A = sorted(A, key=lambda x: 10 ** 9 if x == 0 else abs(x))

    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD

    print(ans)

else:
    A = sorted(A, key=lambda x: abs(x), reverse=True)
    padding = None
    plus = deque()
    minus = deque()
    tplus = deque()
    tminus = deque()

    for i in range(K):
        if A[i] >= 0:
            if padding is None and K % 2 == 1:
                padding = A[i]
            else:
                tplus.append(A[i])

                if len(tplus) == 2:
                    plus.append(tplus.pop() * tplus.pop())
        else:
            tminus.append(A[i])

            if len(tminus) == 2:
                minus.append(tminus.pop() * tminus.pop())

    ans = 1
    if padding is not None:
        ans *= padding
        ans %= MOD

    for _ in range(K // 2):
        if len(plus) == 0:
            ans *= minus.popleft()
            ans %= MOD
        elif len(minus) == 0:
            ans *= plus.popleft()
            ans %= MOD
        elif plus[0] > minus[0]:
            ans *= plus.popleft()
            ans %= MOD
        else:
            ans *= minus.popleft()
            ans %= MOD

    print(ans)

Submission status: Runtime Error

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

flag = 0
for i in range(N):
    if A_list[i] >= 0:
        break
    if i == N-1:
        flag = 1

if flag == 1 and K % 2 ==1:
    A_list.sort(reverse = True)
    ans = 1
    for i in A_list[:K]:
        ans *= i
    print(ans % (10 ** 9 + 7))
else:
    A_list.sort(key=abs,reverse=True)
    ans = 1
    for i in A_list[:K]:
        ans *= i
    if ans >= 0:
        pass
    else:
        # (1)
        list_p = [x for x in A_list[K:] if x >= 0]
        list_n = [x for x in A_list[:K] if x < 0]

        ans1 = ans * list_p[0] / list_n[-1]
        # (2)
        list_p = [x for x in A_list[:K] if x >= 0]
        list_n = [x for x in A_list[K:] if x < 0]
        ans2 = ans * list_n[0] / list_p[-1]

        ans = max(ans1, ans2)
    print(ans % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True,key=lambda x:abs(x))
a=[]
b=[]
c=0
mod=10**9+7
ans=1
for i in range(N):
  if A[i]<0:
    c+=1
    b.append(A[i])
  else:
    a.append(A[i])
if K==N:
  for i in range(N):
    ans*=A[i]
    ans%=mod
else:
  if c==N and K%2==1:
    for i in range(N-1,N-1-K,-1):
      ans*=A[i]
      ans%=mod
  else:
    d,e=0,0
    for i in range(K):
      ans*=A[i]
      if A[i]<0:
        d+=1
      else:
        e+=1
    if ans<0:
      bns=ans//b[d-1]*a[e]
      cns=ans//a[e-1]*b[d]
      ans=max(bns,cns)
      ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,k = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
plus = []
minus = []
zero= 0 
for ai in A:
  if ai <0:
    minus.append(ai)
  else:
    plus.append(ai)
pn = len(plus)
mn = len(minus)
minusdouble = []
plus0double = []
plus1double = []
for i in range(pn//2):
  plus0double.append(plus[i*2]*plus[i*2+1])
for i in range(1,(pn)//2):
  plus1double.append(plus[i*2-1]*plus[i*2])
for i in range(mn//2):
  minusdouble.append(minus[i*2]*minus[i*2+1])
alldouble0 = plus0double + minusdouble
alldouble1 = plus1double + minusdouble
alldouble0.sort(reverse = True)
alldouble1.sort(reverse = True)
if k == 1:
  print(max(A)%mod)
elif n-mn%2 < k:
  out = 1
  for i in range(k):
    out *= A[i]
    out%= mod
  print(out)
else:
  if pn == 0:
    ans1 = ans2 = 1
    for i in range(k):
      ans1 *= minus[i]
      ans1 %= mod
    for i in range(mn-1,mn-1-k,-1):
      ans2 *= minus[i]
      ans2 %= mod
    print(max(ans1,ans2))
  elif k % 2 == 1:
    out = 1
    out *= plus[0]
    for i in range(k//2):
      out *= alldouble1[i]
      out %= mod
    print(out)
  else:
    out = 1
    for i in range(k//2):
      out *= alldouble0[i]
      out %=mod
    print(out)

# print(alldouble0)
# print(alldouble1)

Submission status: Runtime Error

Solution code:
import numpy
N, K=map(int, input().split())
A_list = list(map(int, input().split()))

flag = 0
for i in range(N):
    if A_list[i] >= 0:
        break
    if i == N-1:
        flag = 1

if flag == 1 and K % 2 ==1:
    A_list.sort(reverse = True)
    print(numpy.prod(A_list[:K]) % (10 ** 9 + 7))
else:
    A_list.sort(key=abs,reverse=True)
    ans = 1
    for i in A_list[:K]:
        ans *= i
    if ans >= 0:
        pass
    else:
        # (1)
        list_p = [x for x in A_list[K:] if x >= 0]
        list_n = [x for x in A_list[:K] if x < 0]

        ans1 = ans * list_p[0] / list_n[-1]
        # (2)
        list_p = [x for x in A_list[:K] if x >= 0]
        list_n = [x for x in A_list[K:] if x < 0]
        ans2 = ans * list_n[0] / list_p[-1]

        ans = max(ans1, ans2)
    print(ans % (10 ** 9 + 7))