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: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    A = list(map(int, input().split()))
    B = [(abs(x), x) for x in A]
    B.sort(reverse=True)

    ans = 1

    if N == K:
        for x in A:
            ans *= x
            ans %= mod
        print(ans)
        return

    minus_count = 0

    for i in range(K):
        if B[i][-1] < 0:
            minus_count += 1
        ans *= B[i][0]
        ans %= mod

    if minus_count % 2 == 0:
        print(ans)
        return

    else:
        if minus_count == K:
            # all<0
            sub_data = 1
            for i in range(K-1):
                sub_data *= B[i][-1]
                sub_data %= mod
            V = B[K-1][-1]
            for i in range(K, N):
                if B[i][-1] >= 0:
                    print(sub_data*B[i][-1] % mod)
                    return
            A.sort(reverse=True)
            ans = 1
            for i in range(K):
                ans *= A[i]
                ans %= mod
            print(ans)
            return

        else:
            plus_count = K-minus_count
            plus = []
            minus = []
            for i in range(K):
                if B[i][-1] >= 0:
                    plus.append(B[i][-1])
                else:
                    minus.append(B[i][-1])
            if B[K][-1] >= 0:
                res = 1
                for i in range(plus_count):
                    res *= plus[i]
                    res %= mod
                for i in range(minus_count-1):
                    res *= minus[i]
                    res %= mod
                res *= B[K][-1]
                print(res % mod)
                return

            elif B[K][-1] < 0:
                res = 1
                for i in range(plus_count-1):
                    res *= plus[i]
                    res %= mod
                for i in range(minus_count):
                    res *= minus[i]
                    res %= mod
                res *= B[K][-1]
                print(res % mod)
                return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

mod = 10**9+7

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

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

det = -1###Aのすべての要素が負か否か
for i in range(K):
    if A[i] >= 0:
        det = 1
        break

if det == -1 and K%2 == 1:
    value = 1
    A.sort(reverse = True)
    for i in range(K):
        value *= A[i]
        value %= mod
    print(value)
    sys.exit(0)

A.sort(key = lambda x:abs(x), reverse = True)

###
#print(A[(K-100):K])
#print(A[K:(K+100)])
###

value = 1
sgn = 1
for i in range(K):
    value *= A[i]
    value %= mod
    if A[i] < 0:
        sgn *= -1
    elif A[i] == 0:
        sgn = 0

#print(sgn,value)

if N==K:
    print(value)

elif sgn >=0:
    print(value)
else:
    ###この場合、A[0],...,A[K-1]の中に0はないと断言できることに注意

    X = ['','']###A[K-1],A[K-2],...の中にある絶対値最小の正の数、負の数の絶対値
    num = K
    while (X[0] == '' or X[1] == '') and num > 0:
        #print(A[num])
        num -= 1
        if A[num] > 0 and X[0] == '':
            X[0] = A[num]
        elif A[num] < 0 and X[1] == '':
            X[1] = - A[num]
        ###
        #print(X)
        ###
    
    Y = ['','']###A[K], A[k+1],...の中にある絶対値最大の非負の数、負の数
    ###こちらでは0が登場しないとは言えない
    ###前者にだけ0を入れることでカバー
    num = K-1
    while (Y[0] == '' or Y[1] == '') and num < N-1:
        num += 1
        if A[num] > 0 and Y[0] == '':
            Y[0] = A[num]
        elif A[num] < 0 and Y[1] == '':
            Y[1] = -A[num]
    
    #print(X)
    #print(Y)

    if X[0] != '' and X[1] != '' and Y[0] != '' and Y[1] != '':
        if X[0]*Y[0] >= X[1]*Y[1]:
            value *= Y[0]
            value *= pow(X[1],mod-2,mod)
            value %= mod
            print(value)
        else:
            value *= Y[1]
            value *= pow(X[0],mod-2,mod)
            value %= mod
            print(value)

    elif X[1] != '' and Y[0] != '':
        value *= Y[0]
        value *= pow(X[1],mod-2,mod)
        value %= mod
        print(value)
    
    else:
        value *= Y[1]
        value *= pow(X[0],mod-2,mod)
        value %= mod
        print(value)

Submission status: Wrong Answer

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

minus = []
plus = []

for i in range(N):
    if(A[i] >= 0):
        plus.append(A[i])
    else:
        minus.append(A[i])
plus.sort(reverse=True)
minus.sort()
cnt = K
i = 0
j = 0
ans = 1

if(len(plus) == N):
    for i in range(K):
        ans *= plus[i]
        ans %= mod
elif(len(minus) == N):
    c = 0
    for i in minus[::-1]:
        if(c == K):
            break
        ans *= i
        ans %= mod
        c += 1
else:
    while cnt > 0:
        if(j+1 > len(minus)-1):
            if(i <= len(plus)-1):
                ans *= plus[i]
                ans %= mod
                i += 1
                cnt -= 1
            else:
                break
        elif(i > len(plus)-1):
            if(j+1 > len(minus)-1):
                ans *= (minus[j]*minus[j+1])
                ans %= mod
                j += 2
                cnt -= 2
            else:
                ans *= minus[j]
                ans %= mod
                j += 1
                cnt -= 1
                break
        elif(plus[i] >= minus[j]*minus[j+1]):
            ans *= plus[i]
            ans %= mod
            i += 1
            cnt -= 1
        else:
            if(cnt >= 2):
                ans *= (minus[j]*minus[j+1])
                ans %= mod
                j += 2
                cnt -= 2
            else:
                ans *= plus[i]
                ans %= mod
                i += 1
                cnt -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
        res %= MOD
    print(res)
    exit()
A = []
allsgn = 0
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
    allsgn += a<0
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s0
if allsgn==N:
    if K%2==1:
        print((-prod(A[-K:]))%MOD)
        exit()
    else:
        print(prod(A[:K])%MOD)
        exit()
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    res1 = prod(A[:K-1])*A[firstA][0] if firstA is not None else -float("inf")
    res2 = prod(A[:lastA])*prod(A[lastA+1:K+1]) if lastA != -1 else -float("inf")
    res = max(res1, res2)
print(res%MOD)
"""
6 4
5 -3 -3 -3 -3 -2

5 4
-1 -2 -3 -4 -5
"""

Submission status: Wrong Answer

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
        res %= MOD
    print(res)
    exit()
A = []
allsgn = 0
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
    allsgn += a<0
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s0
if allsgn==N:
    if K%2==1:
        print(-prod(A[-K:])%MOD)
        exit()
    else:
        print(prod(A[:K])%MOD)
        exit()
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    res1 = prod(A[:K-1])*A[firstA][0] if firstA is not None else -float("inf")
    res2 = prod(A[:lastA])*prod(A[lastA+1:K+1]) if lastA != -1 else -float("inf")
    res = max(res1, res2)
print(res%MOD)
"""
6 4
5 -3 -3 -3 -3 -2

5 3
-1 -2 -3 -4 -5
"""

Submission status: Wrong Answer

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
        res %= MOD
    print(res)
    exit()
A = []
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s0
if sgn + sum(s for _, s in A[K:])==N:
    if K%2==1:
        print(-prod(A[-K:])%MOD)
        exit()
    else:
        print(prod(A[:K])%MOD)
        exit()
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    res1 = prod(A[:K-1])*A[firstA][0] if firstA is not None else -float("inf")
    res2 = prod(A[:lastA])*prod(A[lastA+1:K+1]) if lastA != -1 else -float("inf")
    res = max(res1, res2)
print(res%MOD)
"""
6 4
5 -3 -3 -3 -3 -2

5 3
-1 -2 -3 -4 -5
"""

Submission status: Wrong Answer

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
        res %= MOD
    print(res)
    exit()
A = []
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s0
if sgn + sum(s for _, s in A[K:])==N and K%2:
    print(-prod(A[-K:])%MOD)
    exit()
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    res1 = prod(A[:K-1])*A[firstA][0] if firstA is not None else -float("inf")
    res2 = prod(A[:lastA])*prod(A[lastA+1:K+1]) if lastA != -1 else -float("inf")
    res = max(res1, res2)
print(res%MOD)
"""
6 4
5 -3 -3 -3 -3 -2

5 3
-1 -2 -3 -4 -5
"""

Submission status: Wrong Answer

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
        res %= MOD
    print(res)
    exit()
A = []
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if sgn + sum(s for _, s in A[K:])==N and K%2:
    print(-prod(A[-K:])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    res1 = prod(A[:K-1])*A[firstA][0] if firstA is not None else -float("inf")
    res2 = prod(A[:lastA])*prod(A[lastA+1:K+1]) if lastA != -1 else -float("inf")
    res = max(res1, res2)
print(res%MOD)
"""
6 4
5 -3 -3 -3 -3 -2

5 4
-3 -3 -3 -3 -3
"""

Submission status: Wrong Answer

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
        res %= MOD
    print(res)
    exit()
A = []
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if sgn + sum(s for _, s in A[K:])==N:
    print((1-2*(K&1))*prod(A[-K:])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    res1 = prod(A[:K-1])*A[firstA][0] if firstA is not None else -float("inf")
    res2 = prod(A[:lastA])*prod(A[lastA+1:K+1]) if lastA != -1 else -float("inf")
    res = max(res1, res2)
print(res%MOD)
"""
6 4
5 -3 -3 -3 -3 -2

5 4
-3 -3 -3 -3 -3
"""

Submission status: Wrong Answer

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
        res %= MOD
    print(res)
    exit()
A = []
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if sgn + sum(s for _, s in A[K:])==N:
    print(-prod(A[-K:])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    res1 = prod(A[:K-1])*A[firstA][0] if firstA is not None else -float("inf")
    res2 = prod(A[:lastA])*prod(A[lastA+1:K+1]) if lastA != -1 else -float("inf")
    res = max(res1, res2)
print(res%MOD)
"""
6 4
5 -3 -3 -3 -3 -2

4 4
-3 -3 -3 -3
"""

Submission status: Wrong Answer

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
A = []
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
        res %= MOD
    print(res)
    exit()
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s0
lasts = s
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if sgn + sum(s for _, s in A[K:])==N:
    print(-prod(A[-K:])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    res1 = prod(A[:K-1])*A[firstA][0] if firstA is not None else -float("inf")
    res2 = prod(A[:lastA])*prod(A[lastA+1:K+1]) if lastA != -1 else -float("inf")
    res = max(res1, res2)
print(res%MOD)
"""
6 4
5 -3 -3 -3 -3 -2

4 4
-3 -3 -3 1  
"""

Submission status: Wrong Answer

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
A = []
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
    print(res)
    exit()
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s0
lasts = s
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if sgn + sum(s for _, s in A[K:])==N:
    print(-prod(A[-K:])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    res1 = prod(A[:K-1])*A[firstA][0] if firstA is not None else -float("inf")
    res2 = prod(A[:lastA])*prod(A[lastA+1:K+1]) if lastA != -1 else -float("inf")
    res = max(res1, res2)
print(res%MOD)
"""
6 4
5 -3 -3 -3 -3 -2

4 4
-3 -3 -3 1  
"""

Submission status: Wrong Answer

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

minus = []
plus = []

for i in range(N):
    if(A[i] >= 0):
        plus.append(A[i])
    else:
        minus.append(A[i])
plus.sort(reverse=True)
minus.sort()
cnt = K
i = 0
j = 0
ans = 1

if(len(plus) == N):
    for i in range(K):
        ans *= plus[i]
        ans %= mod
elif(len(minus) == N):
    c = 0
    for i in minus[::-1]:
        if(c == K):
            break
        ans *= i
        ans %= mod
        c += 1
else:
    while cnt > 0:
        if(j+1 > len(minus)-1):
            if(i <= len(plus)-1):
                ans *= plus[i]
                ans %= mod
                i += 1
                cnt -= 1
            else:
                break
        elif(i > len(plus)-1):
            if(j+1 > len(minus)-1):
                ans *= (minus[j]*minus[j+1])
                ans %= mod
                j += 2
                cnt -= 2
            else:
                ans *= minus[j]
                ans %= mod
                j += 1
                cnt -= 1
                break
        elif(plus[i] > minus[j]*minus[j+1]):
            ans *= plus[i]
            ans %= mod
            i += 1
            cnt -= 1
        else:
            if(cnt >= 2):
                ans *= (minus[j]*minus[j+1])
                ans %= mod
                j += 2
                cnt -= 2
            else:
                ans *= plus[i]
                ans %= mod
                i += 1
                cnt -= 1

print(ans)

Submission status: Wrong Answer

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

minus = []
plus = []

for i in range(N):
    if(A[i] >= 0):
        plus.append(A[i])
    else:
        minus.append(A[i])
plus.sort(reverse=True)
minus.sort()
cnt = K
i = 0
j = 0
ans = 1

if(len(plus) == N):
    for i in range(K):
        ans *= plus[i]
        ans %= mod
elif(len(minus) == N):
    c = 0
    for i in minus[::-1]:
        if(c == K):
            break
        ans *= i
        ans %= mod
        c += 1
else:
    while cnt > 0:
        if(j+1 > len(minus)-1):
            if(i <= len(plus)-1):
                ans *= plus[i]
                ans %= mod
                i += 1
                cnt -= 1
            else:
                break
        elif(i > len(plus)-1):
            if(j+1 > len(minus)-1):
                ans *= (minus[j]*minus[j+1])
                ans %= mod
                j += 2
                cnt -= 2
            else:
                break
        elif(plus[i] > minus[j]*minus[j+1]):
            ans *= plus[i]
            ans %= mod
            i += 1
            cnt -= 1
        else:
            if(cnt >= 2):
                ans *= (minus[j]*minus[j+1])
                ans %= mod
                j += 2
                cnt -= 2
            else:
                ans *= plus[i]
                ans %= mod
                i += 1
                cnt -= 1

print(ans)

Submission status: Wrong Answer

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

minus = []
plus = []

for i in range(N):
    if(A[i] >= 0):
        plus.append(A[i])
    else:
        minus.append(A[i])
plus.sort(reverse=True)
minus.sort()
cnt = K
i = 0
j = 0
ans = 1

if(len(plus) == N):
    for i in range(K):
        ans *= plus[i]%mod
        ans %= mod
elif(len(minus) == N):
    c = 0
    for i in minus[::-1]:
        if(c == K):
            break
        ans *= i%mod
        ans %= mod
        c += 1
else:
    while cnt > 0:
        if(j+1 > len(minus)-1):
            if(i <= len(plus)-1):
                ans *= plus[i]%mod
                ans %= mod
                i += 1
                cnt -= 1
            else:
                break
        elif(i > len(plus)-1):
            if(j+1 > len(minus)-1):
                ans *= (minus[j]*minus[j+1])%mod
                ans %= mod
                j += 2
                cnt -= 2
            else:
                break
        elif(plus[i] > minus[j]*minus[j+1]):
            ans *= plus[i]%mod
            ans %= mod
            i += 1
            cnt -= 1
        else:
            ans *= (minus[j]*minus[j+1])%mod
            ans %= mod
            j += 2
            cnt -= 2

print(ans)

Submission status: Wrong Answer

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

if A[-1]<0 and k%2==1:
    now=1
    for i in range(k):
        now*=A[-i-1]%mod
        now%=mod
#    print(now)
    exit()
	
l=0
r=n-1
ans=1
if k%2==1:
    ans=A[-1]
#    print(ans)
    r-=1	
for i in range(k//2):
    mi=A[l]*A[l+1]
#    print(mi)
    pl=A[r]*A[r-1]
#    print(pl)
    if mi>pl:
        ans*= mi%mod
        ans%=mod
        l+=2
    else:
        ans*= pl%mod
        ans%=mod
        r-=2
		
print(ans%mod)

Submission status: Wrong Answer

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

if A[-1] < 0 and k % 2 == 1:
    now = 1
    for i in range(k):
        now *= A[- i - 1] % mod
        now %= mod
#    print(now)
    exit()
	
ans = 1
l = 0
r = n - 1
if k % 2 == 1:
    ans = A[-1]
#    print(ans)
    r -= 1	
for i in range(k // 2):
    mi = A[l] * A[l + 1]
#    print(mi)
    pl = A[r - 1] * A[r]
#    print(pl)
    if mi > pl:
        ans *= mi % mod
        ans %= mod
        l += 2
    else:
        ans *= pl % mod
        ans %= mod
        r -= 2
		
print(ans % mod)

Submission status: Wrong Answer

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

if A[-1] < 0 or k % 2 == 1:
    now = 1
    for i in range(k):
        now *= A[- i - 1] % mod
        now %= mod
    print(now)
    exit()
	
ans = 1
l = 0
r = n - 1
if k % 2 == 1:
    ans = A[-1]
    r -= 1	
for i in range(k // 2):
    mi = A[l] * A[l + 1]
    pl = A[r - 1] * A[r]
    if mi > pl:
        ans *= mi % mod
        ans %= mod
        l += 2
    else:
        ans *= pl % mod
        ans %= mod
        r -= 2
		
print(ans % mod)

Submission status: Wrong Answer

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

if lst[-1] < 0 or k % 2 == 1:
    now = 1
    for i in range(k):
        now *= lst[- i - 1] % mod
        now %= mod
    print(now)
    exit()
	
ans2 = 1
l = 0
r = n - 1
if k % 2 == 1:
    ans2 = lst[-1]
    r -= 1	
for i in range(k // 2):
    mi = lst[l] * lst[l + 1]
    pl = lst[r - 1] * lst[r]
    if mi > pl:
        ans2 *= mi % mod
        ans2 %= mod
        l += 2
    else:
        ans2 *= pl % mod
        ans2 %= mod
        r -= 2
		
print(ans2 % mod)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split()]

def solve(N, K, A):
    """
    どうやっても負になるケースでは、
    できるだけ定数の絶対値を小さくしたい。

    a1, a2, ... | ..., aN
    a1 * a2 と aN-1 * aN
    """
    MOD = 10**9+7
    n, p, z = 0, 0, 0
    for a in A:
        if a < 0:
            n += 1
        elif a > 0:
            p += 1
        else:
            z += 1

    if n + p < K:
        return 0

    total = 1
    if p < K and n != 0 and (K-p)%2==1:
        if z:
            return 0
        A.sort(key=lambda x: abs(x))
        for i in range(K):
            total = (total * A[i]) % MOD
        return total

    A.sort()

    r, l = 0, N-1
    while K >= 2 and r + 1 < l - 1:
        R = A[r]   * A[r+1]
        L = A[l-1] * A[l]
        if R < L:
            l-=2
            total = (total * L) % MOD
        else:
            r+=2
            total = (total * R) % MOD
        K-=2
    if K == 2: 
        L = A[l-1] * A[l]
        total = (total * L) % MOD
    if K == 1:
        total = (total * A[l]) % MOD
    return total
print(solve(N, K, A))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split()]

def solve(N, K, A):
    """
    どうやっても負になるケースでは、
    できるだけ定数の絶対値を小さくしたい。

    a1, a2, ... | ..., aN
    a1 * a2 と aN-1 * aN
    """
    MOD = 10**9+7
    n, p, z = 0, 0, 0
    for a in A:
        if a < 0:
            n += 1
        elif a > 0:
            p += 1
        else:
            z += 1

    if n + p < K:
        return 0

    total = 1
    if p < K and n != 0 and (K-p)%2==1:
        if z:
            return 0
        A.sort(key=lambda x: abs(x))
        for i in range(K):
            total = (total * A[i]) % MOD
        return total

    A.sort()

    r, l = 0, N-1
    while K >= 2 and r + 1 < l - 1:
        R = A[r]   * A[r+1]
        L = A[l-1] * A[l]
        if R < L:
            l-=2
            total = (total * L) % MOD
        else:
            r+=2
            total = (total * R) % MOD
        K-=2
      
    if K == 1:
        total = (total * A[l]) % MOD
    return total
print(solve(N, K, A))

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

max = -99999999

for ct in combinations(A, K):
    p = 1
    for c in ct:
        p *= c
    if p > max:
        max = p

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

Submission status: Wrong Answer

Solution code:
MOD = int(10e8)+7
def prod(arr):
    ans=1
    for i in arr:
        ans = (ans*abs(i))%MOD
    if not negs(arr):
        ans = MOD - ans
    return ans
n,k = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort(key=abs,reverse = True)
#print(arr)
def negs(arr):
    return len([i for i in arr if i<0])%2==0
#print(arr)
candi = prod(arr[:k])
if negs(arr[:k]) or k==n:
    print(((candi%MOD) + MOD)%MOD)
else:
    nextPos = max(arr[k:])
    smallNeg = -1
    for i in range(k-1,-1,-1):
        if arr[i]<0:
            smallNeg = i
            break
    candi = 1
    for i in range(k):
        if i!=smallNeg:
            candi = (candi*arr[i])%MOD
    candi = (candi*nextPos)%MOD
    if nextPos<0:
        ans = prod(arr[-k:])%MOD
        print(((ans%MOD) + MOD)%MOD)
    else:
        print(((candi%MOD) + MOD)%MOD)

Submission status: Wrong Answer

Solution code:
MOD = int(10e8)+7
def prod(arr):
    ans=1
    for i in arr:
        ans = (ans*abs(i))%MOD
    if not negs(arr):
        ans = MOD - ans
    return ans
n,k = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort(key=abs,reverse = True)
#print(arr)
def negs(arr):
    return len([i for i in arr if i<0])%2==0
#print(arr)
candi = prod(arr[:k])
if negs(arr[:k]) or k==n:
    print(candi%MOD)
else:
    nextPos = max(arr[k:])
    smallNeg = -1
    for i in range(k-1,-1,-1):
        if arr[i]<0:
            smallNeg = i
            break
    candi = 1
    for i in range(k):
        if i!=smallNeg:
            candi = (candi*arr[i])%MOD
    candi = (candi*nextPos)%MOD
    if nextPos<0:
        print(prod(arr[-k:])%MOD)
    else:
        print(candi%MOD)

Submission status: Wrong Answer

Solution code:
MOD = int(10e8)+7
def prod(arr):
    ans=1
    for i in arr:ans = (ans*i)%MOD
    return ans
n,k = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()
arr.sort(key=abs,reverse = True)
def negs():
    return len([arr[i] for i in range(k) if arr[i]<0])%2==0
#print(arr)
candi = prod(arr[:k])
if negs() or k==n:
    print(candi%MOD)
else:
    nextPos = max(arr[k:])
    smallNeg = -1
    for i in range(k-1,-1,-1):
        if arr[i]<0:
            smallNeg = i
            break
    candi = 1
    for i in range(k):
        if i!=smallNeg:
            candi = (candi*arr[i])%MOD
    candi = (candi*nextPos)%MOD
    if nextPos<0:
        print(prod(arr[-k:])%MOD)
    else:
        print(candi%MOD)

Submission status: Wrong Answer

Solution code:
MOD = int(10e8)+7
def prod(arr):
    ans=1
    for i in arr:ans = (ans*i)%MOD
    return ans
n,k = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort(reverse = True)
arr.sort(key=abs,reverse = True)
def negs():
    return len([arr[i] for i in range(k) if arr[i]<0])%2==0
#print(arr)
candi = prod(arr[:k])
if negs() or k==n:
    print(candi%MOD)
else:
    nextPos = max(arr[k:])
    smallNeg = -1
    for i in range(k-1,-1,-1):
        if arr[i]<0:
            smallNeg = i
            break
    candi = 1
    for i in range(k):
        if i!=smallNeg:
            candi = (candi*arr[i])%MOD
    candi = (candi*nextPos)%MOD
    if nextPos<0:
        print(prod(arr[-k:])%MOD)
    else:
        print(candi%MOD)

Submission status: Wrong Answer

Solution code:
MOD = int(10e8)+7
def prod(arr):
    ans=1
    for i in arr:ans = (ans*i)%MOD
    return ans
n,k = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort(key=abs,reverse = True)
def negs():
    return len([arr[i] for i in range(k) if arr[i]<0])%2==0
#print(arr)
candi = prod(arr[:k])
if negs() or k==n:
    print(candi%MOD)
else:
    nextPos = max(arr[k:])
    smallNeg = -1
    for i in range(k-1,-1,-1):
        if arr[i]<0:
            smallNeg = i
            
    candi = 1
    for i in range(k):
        if i!=smallNeg:
            candi = (candi*arr[i])%MOD
    candi = (candi*nextPos)%MOD
    if nextPos<0:
        print(prod(arr[-k:])%MOD)
    else:
        print(candi%MOD)

Submission status: Wrong Answer

Solution code:
MOD = int(10e8)+7
def prod(arr):
    ans=1
    for i in arr:ans = (ans*i)%MOD
    return ans
n,k = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort(key=abs,reverse = True)
def negs():
    return len([arr[i] for i in range(k) if arr[i]<0])%2==0
#print(arr)
candi = prod(arr[:k])
if negs() or k==n:
    print(candi%MOD)
else:
    nextPos = max(arr[k:])
    smallNeg = -1
    for i in range(k-1,-1,-1):
        if arr[i]<0:
            smallNeg = i
            break
    candi = 1
    for i in range(k):
        if i!=smallNeg:
            candi = (candi*arr[i])%MOD
    candi = (candi*nextPos)%MOD
    if nextPos<0:
        print(prod(arr[-k:])%MOD)
    else:
        print(candi%MOD)