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:
import numpy as np
import sys
from functools import reduce
from operator import add, mul
 
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7
def factorial(p,q):
    fact=1
    for i in A[p:q]:
      fact *= i%MOD
    return fact%MOD

A=sorted(A)
#print(A)
ansA = 1
for a in A[0:K]:
  ansA *= a
  ansA %= MOD
A=sorted(A, reverse=True)
ansB = 1
for a in A[0:K]:
  ansB *= a
  ansB %= MOD
print(max(ansA, ansB))
exit()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
from functools import reduce
from operator import add, mul
 
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7
def factorial(p,q):
    fact=1
    for i in A[p:q]:
      fact *= i%MOD
    return fact%MOD

ans = 1
for a in A:
  ans *= a
  ans %= MOD
print(ans)
exit()

#print(factorial(0,30))
      
#A=sorted(A)
 
#Amin=factorial(0,K)
#if Amin<0 and 0 in A[K:N]:Amin=0

A=sorted(A, reverse=True)
 
Amax=factorial(0,K)
 
#A=sorted(A, key=lambda x: abs(x), reverse=True)
 
#B=A[0:K-1]
#C=A[K-1:N]
 
#Bmax=factorial(0,K-1)*C[0]
#print(factorial(0,K-1),C[0])
#print(Bmax)
 
#C=sorted(C)
#print(C)
#Bmin=factorial(0,K-1)*C[0]
#print(Bmin)
#print(Amax,Amin,Bmax,Bmin)
#print(max(Amax,Amin,Bmax,Bmin)%(10**9+7))
print(Amax)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
from functools import reduce
from operator import add, mul
 
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7
def factorial(p,q):
    fact=1
    for i in A[p:q]:
      fact *= i%MOD
    return fact%MOD

#print(factorial(0,30))
      
#A=sorted(A)
 
#Amin=factorial(0,K)
#if Amin<0 and 0 in A[K:N]:Amin=0

A=sorted(A, reverse=True)
 
Amax=factorial(0,K)
 
#A=sorted(A, key=lambda x: abs(x), reverse=True)
 
#B=A[0:K-1]
#C=A[K-1:N]
 
#Bmax=factorial(0,K-1)*C[0]
#print(factorial(0,K-1),C[0])
#print(Bmax)
 
#C=sorted(C)
#print(C)
#Bmin=factorial(0,K-1)*C[0]
#print(Bmin)
#print(Amax,Amin,Bmax,Bmin)
#print(max(Amax,Amin,Bmax,Bmin)%(10**9+7))
print(Amax)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
from functools import reduce
from operator import add, mul
 
N,K=map(int, input().split())
A =list(map(int,input().split()))

def factorial(p,q):
    fact=1
    for i in A[p:q]:
      fact *= i%(10**9+7)
    return fact%(10**9+7)

#print(factorial(0,30))
      
#A=sorted(A)
 
#Amin=factorial(0,K)
#if Amin<0 and 0 in A[K:N]:Amin=0

A=sorted(A, reverse=True)
 
Amax=factorial(0,K)
 
#A=sorted(A, key=lambda x: abs(x), reverse=True)
 
#B=A[0:K-1]
#C=A[K-1:N]
 
#Bmax=factorial(0,K-1)*C[0]
#print(factorial(0,K-1),C[0])
#print(Bmax)
 
#C=sorted(C)
#print(C)
#Bmin=factorial(0,K-1)*C[0]
#print(Bmin)
#print(Amax,Amin,Bmax,Bmin)
#print(max(Amax,Amin,Bmax,Bmin)%(10**9+7))
print(Amax)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
from functools import reduce
from operator import add, mul
 
N,K=map(int, input().split())
A =list(map(int,input().split()))

def factorial(p,q):
    fact=1
    for i in A[p:q]:
      fact *= i
    return fact%(10**9+7)

#print(factorial(0,30))
      
#A=sorted(A)
 
#Amin=factorial(0,K)
#if Amin<0 and 0 in A[K:N]:Amin=0

A=sorted(A, reverse=True)
 
Amax=factorial(0,K)
 
#A=sorted(A, key=lambda x: abs(x), reverse=True)
 
#B=A[0:K-1]
#C=A[K-1:N]
 
#Bmax=factorial(0,K-1)*C[0]
#print(factorial(0,K-1),C[0])
#print(Bmax)
 
#C=sorted(C)
#print(C)
#Bmin=factorial(0,K-1)*C[0]
#print(Bmin)
#print(Amax,Amin,Bmax,Bmin)
#print(max(Amax,Amin,Bmax,Bmin)%(10**9+7))
print(Amax)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
from functools import reduce
from operator import add, mul
 
N,K=map(int, input().split())
A =list(map(int,input().split()))

def factorial(p,q):
    fact=1
    for i in A[p:q]:
      fact *= i
    return fact%(10**9+7)

#print(factorial(0,30))
      
A=sorted(A)
 
Amin=factorial(0,K)
if Amin<0 and 0 in A[K:N]:Amin=0

A=sorted(A, reverse=True)
 
Amax=factorial(0,K)
 
 
A=sorted(A, key=lambda x: abs(x), reverse=True)
 
B=A[0:K-1]
C=A[K-1:N]
 
 
Bmax=factorial(0,K-1)*C[0]
#print(factorial(0,K-1),C[0])
#print(Bmax)
 
C=sorted(C)
#print(C)
Bmin=factorial(0,K-1)*C[0]
#print(Bmin)
#print(Amax,Amin,Bmax,Bmin)
print(max(Amax,Amin,Bmax,Bmin)%(10**9+7))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
from functools import reduce
from operator import add, mul
 
N,K=map(int, input().split())
A =list(map(int,input().split()))

def factorial(p,q):
    fact = 1
    for integer in A[p:q]:
        fact *= integer
    return fact
 
A=sorted(A)
 
Amin=factorial(0,K)
if Amin<0 and 0 in A[K:N]:Amin=0

A=sorted(A, reverse=True)
 
Amax=factorial(0,K)
 
 
A=sorted(A, key=lambda x: abs(x), reverse=True)
 
B=A[0:K-1]
C=A[K-1:N]
 
 
Bmax=factorial(0,K-1)*C[0]
#print(factorial(0,K-1),C[0])
#print(Bmax)
 
C=sorted(C)
#print(C)
Bmin=factorial(0,K-1)*C[0]
#print(Bmin)
#print(Amax,Amin,Bmax,Bmin)
print(max(Amax,Amin,Bmax,Bmin)%(10**9+7))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
 
N,K=map(int, input().split())
A =np.array(list(map(int,input().split())), dtype=np.int64)
#A=sorted(A, reverse=True)
 
def factorial(p,q):
    fact = 1
    for integer in A[p:q]:
        fact *= integer
        if fact>10**9+7:
          fact = fact%(10**9+7)
    return fact
 
A=sorted(A)
 
Amin=factorial(0,K)
if Amin<0 and 0 in A[K:N]:Amin=0

A=sorted(A, reverse=True)
 
Amax=factorial(0,K)
 
 
A=sorted(A, key=lambda x: abs(x), reverse=True)
 
B=A[0:K-1]
C=A[K-1:N]
 
 
Bmax=factorial(0,K-1)*C[0]
#print(factorial(0,K-1),C[0])
#print(Bmax)
 
C=sorted(C)
#print(C)
Bmin=factorial(0,K-1)*C[0]
#print(Bmin)
#print(Amax,Amin,Bmax,Bmin)
print(max(Amax,Amin,Bmax,Bmin)%(10**9+7))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
 
N,K=map(int, input().split())
A =np.array(list(map(int,input().split())), dtype=np.int64)
#A=sorted(A, reverse=True)
 
def factorial(p,q):
    fact = 1
    for integer in A[p:q]:
        fact *= integer
        fact = fact%(10**9+7)
    return fact
 
A=sorted(A)
 
Amin=factorial(0,K)%(10**9+7)
A=sorted(A, reverse=True)
 
Amax=factorial(0,K)%(10**9+7)
 
 
A=sorted(A, key=lambda x: abs(x), reverse=True)
 
B=A[0:K-1]
C=A[K-1:N]
 
 
Bmax=factorial(0,K-1)*C[0]
#print(factorial(0,K-1),C[0])
#print(Bmax)
 
C=sorted(C)
#print(C)
Bmin=factorial(0,K-1)*C[0]
#print(Bmin)
 
print(max(Amax,Amin,Bmax,Bmin)%(10**9+7))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
 
N,K=map(int, input().split())
A =np.array(list(map(int,input().split())), dtype=np.int64)
#A=sorted(A, reverse=True)
 
def factorial(p,q):
    fact = 1
    for integer in A[p:q]:
        fact *= integer
        fact = fact%(10**9+7)
    return fact
 
A=sorted(A)
 
Amin=factorial(0,K)%(10**9+7)
A=sorted(A, reverse=True)
 
Amax=factorial(0,K)%(10**9+7)
 
 
A=sorted(A, key=lambda x: abs(x), reverse=True)
 
B=A[0:K-1]
C=A[K-1:N]
 
 
Bmax=factorial(0,K-1)*C[0]%(10**9+7)
#print(factorial(0,K-1),C[0])
#print(Bmax)
 
C=sorted(C)
#print(C)
Bmin=factorial(0,K-1)*C[0]%(10**9+7)
#print(Bmin)
 
print(max(Amax,Amin,Bmax,Bmin))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
 
N,K=map(int, input().split())
A =np.array(list(map(int,input().split())), dtype=np.int64)
#A=sorted(A, reverse=True)
 
def factorial(p,q):
    fact = 1
    for integer in A[p:q]:
        fact *= integer
        if fact>=10**9+7:fact = fact%(10**9+7)
    return fact
 
A=sorted(A)
 
Amin=factorial(0,K)%(10**9+7)
A=sorted(A, reverse=True)
 
Amax=factorial(0,K)%(10**9+7)
 
 
A=sorted(A, key=lambda x: abs(x), reverse=True)
 
B=A[0:K-1]
C=A[K-1:N]
 
 
Bmax=factorial(0,K-1)*C[0]%(10**9+7)
#print(factorial(0,K-1),C[0])
#print(Bmax)
 
C=sorted(C)
#print(C)
Bmin=factorial(0,K-1)*C[0]%(10**9+7)
#print(Bmin)
 
print(max(Amax,Amin,Bmax,Bmin))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

N,K=map(int, input().split())
A =np.array(list(map(int,input().split())), dtype=np.int64)
#A=sorted(A, reverse=True)

def factorial(p,q):
    fact = 1
    for integer in A[p:q]:
        fact *= integer
        if fact>=10**9+7:fact = fact%(10**9+7)
    return fact

A=sorted(A)

Amin=factorial(0,K)%(10**9+7)
A=sorted(A, reverse=True)

Amax=factorial(0,K)%(10**9+7)


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

B=A[0:K-1]
C=A[K-1:N]


Bmax=factorial(0,K-1)*C[0]
#print(factorial(0,K-1),C[0])
#print(Bmax)

C=sorted(C)
#print(C)
Bmin=factorial(0,K-1)*C[0]
#print(Bmin)
#print(Amax,Amin,Bmax,Bmin)
print(max(Amax,Amin,Bmax,Bmin)%(10**9+7))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

N,K=map(int, input().split())
A =np.array(list(map(int,input().split())), dtype=np.int64)
#A=sorted(A, reverse=True)

def factorial(p,q):
    fact = 1
    for integer in A[p:q]:
        fact *= integer
        if fact>=10**9+7:fact = fact%(10**9+7)
    return fact

A=sorted(A)

Amin=factorial(0,K)
A=sorted(A, reverse=True)

Amax=factorial(0,K)


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

B=A[0:K-1]
C=A[K-1:N]


Bmax=factorial(0,K-1)*C[0]
#print(factorial(0,K-1),C[0])
#print(Bmax)

C=sorted(C)
#print(C)
Bmin=factorial(0,K-1)*C[0]
#print(Bmin)
#print(Amax,Amin,Bmax,Bmin)
print(max(Amax,Amin,Bmax,Bmin)%(10**9+7))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

N,K=map(int, input().split())
A =np.array(list(map(int,input().split())), dtype=np.int64)
#A=sorted(A, reverse=True)

def factorial(p,q):
    fact = 1
    for integer in A[p:q]:
        fact *= integer
        fact = fact%(10**9+7)
    return fact

A=sorted(A)

Amin=factorial(0,K)%(10**9+7)
A=sorted(A, reverse=True)

Amax=factorial(0,K)%(10**9+7)


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

B=A[0:K-1]
C=A[K-1:N]


Bmax=factorial(0,K-1)*C[0]%(10**9+7)
#print(factorial(0,K-1),C[0])
#print(Bmax)

C=sorted(C)
#print(C)
Bmin=factorial(0,K-1)*C[0]%(10**9+7)
#print(Bmin)

print(max(Amax,Amin,Bmax,Bmin))

Submission status: Wrong Answer

Solution code:
from functools import reduce
import operator
import numpy as np
import sys

N,K=map(int, input().split())
A =np.array(list(map(int,input().split())), dtype=np.int64)
A=sorted(A, reverse=True)
#print(A)
def factorial(p,q):
    fact = 1
    for integer in A[p:q]:
        fact *= integer
        fact = fact%(10**9+7)
    return fact

Amax=factorial(0,K)%(10**9+7)
Amin=factorial(N-K,N)%(10**9+7)
#print(Amax,Amin)

Bmin=A[-1]
A=sorted(A, key=lambda x: abs(x), reverse=True)
#print(A)

C=factorial(0,K-1)*A[K-1]

#print(C)

#if C<0:C=C*BB[0]%(10**9+7)
#else:C=(C*BB[-1])%(10**9+7)

  #M=max(ABSmax)
#print(BB)

print(max(Amax,Amin,C))

Submission status: Wrong Answer

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

    A.sort(reverse=True)  # 符号付きの大きい順
    B = sorted(A, key=lambda x: abs(x), reverse=True)  # 絶対値の大きい順
    C = []

    if k == n:
        C = A  # 全部使う
    elif k%2 == 1 and A[0] < 0:
        C = A[:k]  # 絶対値小さい順にk個
    else:
        plus = []
        minus = []
        for b in B[:k]:
            if b >= 0: plus.append(b)
            else: minus.append(b)

        if len(plus) > 0 and plus[-1] > 0 and len(minus) % 2 == 1:
            # 積が負になるので入れ替え検討
            rem1 = minus[-1]
            add1 = max(B[k:])
            rem2 = plus[-1]
            add2 = min(B[k:])
            if add1 >= 0 and add2 >= 0:
                minus[-1] = add1  # 残りは正値のみ
            elif add1 < 0 and add2 < 0:
                plus[-1] = add2  # 残りは負値のみ
            else:
                if add1 * rem2 > rem1 * add2:
                    minus[-1] = add1
                else:
                    plus[-1] = add2
        C = plus + minus

    ans = 1
    for c in C:
        ans *= c
        if ans < 0: ans += mod
        ans %= mod
    print(ans)

if __name__ == '__main__':
    abc173_e()

Submission status: Wrong Answer

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

    A.sort(reverse=True)  # 符号付きの大きい順
    B = sorted(A, key=lambda x: abs(x), reverse=True)  # 絶対値の大きい順
    C = []

    if k == n:
        C = A  # 全部使う
    elif k%2 == 1 and A[-1] < 0:
        C = A[:k]  # 絶対値小さい順にk個
    else:
        plus = []
        minus = []
        for b in B[:k]:
            if b >= 0: plus.append(b)
            else: minus.append(b)

        if len(plus) > 0 and plus[-1] > 0 and len(minus) % 2 == 1:
            # 積が負になるので入れ替え検討
            rem1 = minus[-1]
            add1 = max(B[k:])
            rem2 = plus[-1]
            add2 = min(B[k:])
            if add1 >= 0 and add2 >= 0:
                minus[-1] = add1  # 残りは正値のみ
            elif add1 < 0 and add2 < 0:
                plus[-1] = add2  # 残りは負値のみ
            else:
                if add1 * rem2 > rem1 * add2:
                    minus[-1] = add1
                else:
                    plus[-1] = add2
        C = plus + minus

    ans = 1
    for c in C:
        ans *= c
        if ans < 0: ans += mod
        ans %= mod
    print(ans)

if __name__ == '__main__':
    abc173_e()

Submission status: Wrong Answer

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

    A.sort(reverse=True)  # 符号付きの大きい順
    B = sorted(A, key=lambda x: abs(x), reverse=True)  # 絶対値の大きい順
    C = []

    if k == n:
        C = A  # 全部使う
    elif k%2 == 1 and A[-1] < 0:
        C = A[:k]  # 絶対値小さい順にk個
    else:
        plus = []
        minus = []
        for b in B[:k]:
            if b >= 0: plus.append(b)
            else: minus.append(b)

        if len(plus) > 0 and plus[-1] > 0 and len(minus) % 2 == 1:
            # 積が負になるので入れ替え検討
            rem1 = minus[-1]
            add1 = max(B[k:])
            rem2 = plus[-1]
            add2 = min(B[k:])
            if add1 >= 0 and add2 < 0:
                minus[-1] = add1
            elif add1 < 0 and add2 >= 0:
                plus[-1] = add2
            else:
                if add1 * rem2 > rem1 * add2:
                    minus[-1] = add1
                else:
                    plus[-1] = add2
        C = plus + minus

    ans = 1
    for c in C:
        ans *= c
        if ans < 0: ans += mod
        ans %= mod
    print(ans)

if __name__ == '__main__':
    abc173_e()

Submission status: Wrong Answer

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

# 積を正の数にできればf=True
# 選ばなくてはならない負の数 = K - (正の数の個数)
# これが偶数ならOK
# あるいは全て正の数から選べるなら
plus = 0
for i in range(N):
    if A[i] > 0:
        plus += 1
if plus >= K or (K - plus) % 2 == 0:
    f = True
else:
    f = False

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

chosen = []
minus_in_chosen = 0  # 選ばれた負の数の個数
last_minus = 0  # 選ばれた負の数のうち絶対値が最小のもののインデックス
for i in range(K):
    chosen.append(A[i])
    if A[i] < 0:
        minus_in_chosen += 1
        last_minus = i

if f and minus_in_chosen % 2 == 1:  # 正の数にできるはずなのに選んだものの中にマイナスが奇数個
    for j in range(i+1, N):
        if A[j] > 0:
            chosen[last_minus] = A[j]

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

print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int, input().split())
A=list(map(int,input().split()))
A=sorted(A)
#print('A:',A)
B=sorted(A, key=lambda x: abs(x), reverse=True)
#print('B:',B)

ABSmax=1
ABSmin=1
for i in range(K):
    ABSmax=ABSmax*B[i]%(10**9+7)
    ABSmin=ABSmin*B[-1-i]%(10**9+7)
#print(ABSmax,ABSmin)

C=1
for i in range(K-1):
  C=C*B[0]*(10**9+7)
  del B[0]

BB=sorted(B)
if C<0:C=C*BB[0]
else:C=C*BB[-1]

#print(BB)
print(max(ABSmax,ABSmin,C)%(10**9+7))

Submission status: Wrong Answer

Solution code:
N,K=map(int, input().split())
A=list(map(int,input().split()))
A=sorted(A)
#print('A:',A)
B=sorted(A, key=lambda x: abs(x), reverse=True)
#print('B:',B)

ABSmax=1
ABSmin=1
for i in range(K):
    ABSmax=ABSmax*B[i]%(10**9+7)
    ABSmin=ABSmin*B[-1-i]%(10**9+7)
#print(ABSmax,ABSmin)

C=1
for i in range(K-1):
  C=C*B[0]
  del B[0]

BB=sorted(B)
if C<0:C=C*BB[0]
else:C=C*BB[-1]

#print(BB)
print(max(ABSmax,ABSmin,C)%(10**9+7))

Submission status: Wrong Answer

Solution code:
N,K=map(int, input().split())
A=list(map(int,input().split()))
A=sorted(A)
print('A:',A)
B=sorted(A, key=lambda x: abs(x), reverse=True)
print('B:',B)

ABSmax=1
ABSmin=1
for i in range(K):
    ABSmax=ABSmax*B[i]%(10**9+7)
    ABSmin=ABSmin*B[-1-i]%(10**9+7)
print(ABSmax,ABSmin)

C=1
for i in range(K-1):
  C=C*B[0]
  del B[0]

BB=sorted(B)
if C<0:C=C*BB[0]
else:C=C*BB[-1]

print(BB)
print(max(ABSmax,ABSmin,C)%(10**9+7))

Submission status: Wrong Answer

Solution code:
N,K=map(int, input().split())
A=list(map(int,input().split()))
A=sorted(A)
print('A:',A)
B=sorted(A, key=lambda x: abs(x), reverse=True)
print('B:',B)

ABSmax=1
ABSmin=1
for i in range(K):
    ABSmax=ABSmax*B[i]
    ABSmin=ABSmin*B[-1-i]
print(ABSmax,ABSmin)

C=1
for i in range(K-1):
  C=C*B[0]
  del B[0]

BB=sorted(B)
if C<0:C=C*BB[0]
else:C=C*BB[-1]

print(BB)
print(max(ABSmax,ABSmin,C)%(10**9+7))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())),key=abs)[::-1]
mod=10**9+7
s=1
flag=0
if k%2 and all([i<=0 for i in a]):
  a=sorted(a,key=abs)
  flag=1
p,m=-1,-1
cnt=0
for i,j in enumerate(a[:k]):
  s*=j
  s%=mod
  if j<0:
    m=i
    cnt+=1
  elif j>0:p=i
if flag:
  print(s)
  exit()
if cnt%2==0:
  print(s)
  exit()
s-=mod
ans=0
for i in range(k,n):
  if p!=-1 and a[i]<=0:
    ans=max(ans,a[i]*s//a[p])
  if m!=-1 and a[i]>=0:
    ans=max(ans,a[i]*s//a[m])
print(max(ans,s)%mod)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())),key=abs)[::-1]
mod=10**9+7
s=1
flag=0
if k%2 and all([i<=0 for i in a]):
  a=sorted(a,key=abs)
  flag=1
p,m=-1,-1
cnt=0
for i,j in enumerate(a[:k]):
  s*=j
  s%=mod
  if j<0:
    m=i
    cnt+=1
  elif j>0:p=i
if flag:
  print(s)
  exit()
if cnt%2==0:
  print(s)
  exit()
s-=mod
ans=0
for i in range(k,n):
  if p!=-1 and a[i]<=0:
    ans=max(ans,a[i]*s//a[p])
    p=-1
  if m!=-1 and a[i]>=0:
    ans=max(ans,a[i]*s//a[m])
    m=-1
print(max(ans,s)%mod)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())),key=abs)[::-1]
mod=10**9+7
s=1
flag=0
if k%2 and all([i<=0 for i in a]):
  a=sorted(a,key=abs)
  flag=1
p,m=-1,-1
cnt=0
for i,j in enumerate(a[:k]):
  s*=j
  s%=mod
  if j<0:
    m=i
    cnt+=1
  elif j>0:p=i
if flag:
  print(s)
  exit()
if cnt%2==0:
  print(s)
  exit()
s-=mod
for i in range(k,n):
  if p!=-1 and a[i]<=0:
    s=max(s,a[i]*s//a[p])
    p=-1
  if m!=-1 and a[i]>=0:
    s=max(s,a[i]*s//a[m])
    m=-1
print(s%mod)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())),key=abs)[::-1]
mod=10**9+7
s=1
flag=0
if k%2 and all([i<=0 for i in a]):
  a=sorted(a,key=abs)
  flag=1
p,m=-1,-1
cnt=0
for i,j in enumerate(a[:k]):
  s*=j
  s%=mod
  if j<0:
    m=i
    cnt+=1
  elif j>0:p=i
if flag:
  print(s)
  exit()
if cnt%2==0:
  print(s)
  exit()
s-=mod
for i in range(k,n):
  if p!=-1 and a[i]<0:
    s=max(s,a[i]*s//a[p])
    p=-1
  if m!=-1 and a[i]>0:
    s=max(s,a[i]*s//a[m])
    m=-1
print(s%mod)

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
mod = 10**9+7
n,k = ma()
A = lma();A.sort(key=lambda x:abs(x),reverse=True)
#print(A)
if k==n:
    prd=1
    for a in A:prd=(prd*a)%mod
    print(prd)
    exit()

Am = [-a for a in A if a<0]
Apz = [a for a in A if a>=0]
f=0 #F:plus T :minus
if k%2==1 and n == len(Am):
    f=1
prd=1
if f:
    A.sort(key=lambda x:abs(x))
    for i in range(k):
        prd =(prd*A[i])%mod
else:
    idxp=-1
    idxm=-1
    for i in range(k):
        prd=(prd*A[i]) %mod
        if A[i]<0:
            idxm+=1
        else:
            idxp+=1
    #print(idxp,idxm)
    if idxm%2==1:
        pass
    else:
        if idxp==-1 or idxp==len(Apz)-1:
            t2 = 0
        else:
            t2 = Apz[idxp]*Apz[idxp+1]
        if idxm==-1 or idxm ==len(Am)-1:
            t1=0
        else:
            t1 = Am[idxm]*Am[idxm+1]
        #print(t1,t2)
        if t1>t2:
            prd=1
            ip =-1
            for i in range(k):
                if A[i]>=0:
                    ip+=1
                if ip==idxp:
                    prd*=Am[idxm+1]
                else:
                    prd*=A[i]
                prd%=mod
        else:
            prd=1
            im = -1
            for i in range(k):
                if A[i]<0:
                    im+=1
                if im==idxm:
                    prd*=Apz[idxp+1]
                else:
                    prd*=A[i]
                prd%=mod
print(prd)

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
mod = 10**9+7
n,k = ma()
A = lma();A.sort(key=lambda x:abs(x),reverse=True)
#print(A)
if k==n:
    prd=1
    for a in A:prd=(prd*a)%mod
    print(prd)
    exit()

Am = [-a for a in A if a<0]
Apz = [a for a in A if a>=0]
f=0 #F:plus T :minus
if k>len(Apz):
    f=(k-len(Apz))%2
prd=1
if f:
    A.sort(key=lambda x:abs(x))
    for i in range(k):
        prd =(prd*A[i])%mod
else:
    idxp=-1
    idxm=-1
    for i in range(k):
        prd=(prd*A[i]) %mod
        if A[i]<0:
            idxm+=1
        else:
            idxp+=1
    #print(idxp,idxm)
    if idxm%2==1:
        pass
    else:
        if idxp==-1 or idxp==len(Apz)-1:
            t2 = 0
        else:
            t2 = Apz[idxp]*Apz[idxp+1]
        if idxm==-1 or idxm ==len(Am)-1:
            t1=0
        else:
            t1 = Am[idxm]*Am[idxm+1]
        #print(t1,t2)
        if t1>t2:
            prd=1
            ip =-1
            for i in range(k):
                if A[i]>=0:
                    ip+=1
                if ip==idxp:
                    prd*=Am[idxm+1]
                else:
                    prd*=A[i]
                prd%=mod
        else:
            prd=1
            im = -1
            for i in range(k):
                if A[i]<0:
                    im+=1
                if im==idxm:
                    prd*=Apz[idxp+1]
                else:
                    prd*=A[i]
                prd%=mod
print(prd)

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
mod = 10**9+7
n,k = ma()
A = lma();A.sort(key=lambda x:abs(x),reverse=True)
#print(A)
if k==n:
    prd=1
    for a in A:prd=(prd*a)%mod
    print(prd)
    exit()

Am = [-a for a in A if a<0]
Apz = [a for a in A if a>=0]
f=0 #F:plus T :minus
if k>len(Apz):
    f=(k-len(Apz))%2
prd=1
if f:
    A.sort(key=lambda x:abs(x))
    for i in range(k):
        prd =(prd*A[i])%mod
else:
    idxp=-1
    idxm=-1
    for i in range(k):
        prd=(prd*A[i]) %mod
        if A[i]<0:
            idxm+=1
        else:
            idxp+=1
    print(idxp,idxm)
    if idxm%2==1:
        pass
    else:
        if idxp==-1 or idxp==len(Apz)-1:
            t2 = 0
        else:
            t2 = Apz[idxp]*Apz[idxp+1]
        if idxm==-1 or idxm ==len(Am)-1:
            t1=0
        else:
            t1 = Am[idxm]*Am[idxm+1]
        #print(t1,t2)
        if t1>t2:
            prd=1
            ip =-1
            for i in range(k):
                if A[i]>=0:
                    ip+=1
                if ip==idxp:
                    prd*=Am[idxm+1]
                else:
                    prd*=A[i]
                prd%=mod
        else:
            prd=1
            im = -1
            for i in range(k):
                if A[i]<0:
                    im+=1
                if im==idxm:
                    prd*=Apz[idxp+1]
                else:
                    prd*=A[i]
                prd%=mod
print(prd)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7
if K == N:
    #そのままが答え
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans % MOD)
    exit()

# pos = [a for a in A if a > 0]
neg = [a for a in A if a < 0]
n_neg = len(neg)
if n_neg == N and K % 2 == 1:
    #負になるしかない
    A.sort(reverse=True)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans % MOD)
    exit()

# 正にできる
A.sort(key=lambda x: abs(x), reverse=True)
P = 1
is_p_neg = 0
for i in range(K):
    P *= A[i]
    if A[i] < 0:
        is_p_neg = not(is_p_neg)
        P %= MOD

if P >= 0:
    # P >= 0なら答え
    print(P%MOD)
    exit()

ng_left = N
ng_right = N
not_ng_right = N
po_left = N
for i in range(N):
    if A[i] > 0:
        po_left = i
        break
for i in range(N):
    if A[i] < 0:
        ng_left = i
        break
for i in range(K, N):
    if A[i] >= 0:
        not_ng_right = i
        break
for i in range(K, N):
    if A[i] > 0:
        ng_right = i
        break
is_not_pos = 1
A += [None] # right側のポインターが初期のままかどうかを判別
x1 = A[ng_left]
y1 = A[not_ng_right]
x2 = A[po_left]
y2 = A[ng_right]
if y1 is None:
    P //= x2
    P *= y2
    P %= MOD
elif y2 is None:
    P //= x1
    P *= y1
    P %= MOD
else:
    if abs(y1*x2) < abs(y2*x1):
        P //= x2
        P *= y2
        P %= MOD
    else:
        P //= x1
        P *= y1
        P %= MOD
print(P %MOD)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7
if K == N:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans % MOD)
    exit()

pos = [a for a in A if a > 0]
neg = [a for a in A if a < 0]
n_neg = len(neg)
if n_neg == N and K % 2 == 1:
    #負になる
    A.sort(reverse=True)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans % MOD)
    exit()
# 正にできる
A.sort(key=lambda x: abs(x), reverse=True)
P = 1
is_p_neg = 0
for i in range(K):
    P *= A[i]
    if A[i] < 0:
        is_p_neg = not(is_p_neg)

if P >= 0:
    print(P%MOD)
    exit()

ng_left = 0
ng_right = 0
not_ng_right = 0
po_left = 0
for i in range(N):
    if A[i] > 0:
        po_left = i
        break
for i in range(N):
    if A[i] < 0:
        ng_left = i
        break
for i in range(K, N):
    if A[i] >= 0:
        not_ng_right = i
        break
for i in range(K, N):
    if A[i] > 0:
        ng_right = i
        break

while P < 0:
    x1 = A[ng_left]
    y1 = A[not_ng_right]
    x2 = A[po_left]
    y2 = A[ng_right]
    if abs(y1*x2) < abs(y2*x1):
        P //= x2
        P *= y2
    else:
        P //= x1
        P *= y1
print(P %MOD)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from numpy import prod
n, k= map(int, input().split())
lst = list(map(int, input().split()))
data = list(combinations(lst, k))
maxx = prod(data[0])
for i in range(len(data)):
    if prod(data[i]) > maxx:
        maxx = prod(data[i])
print(maxx % ((10 ** 9) + 7))

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as H
  
ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())
def rec(h, w): return [[0] * w for i in range(h)] 

n, k = I()
xs = Is()
mod = 1000000007
pos = [-x for x in xs if x >= 0]
neg = [-x for x in xs if x < 0]
H.heapify(pos)
H.heapify(neg)

ans = 1
while k > 1:
  pp1 = bool(pos)
  p1 = H.heappop(pos) if pp1 else 0
  pp2 = bool(pos)
  p2 = H.heappop(pos) if pp2 else 0
  
  nn1 = bool(neg)
  n1 = H.heappop(neg) if nn1 else 0
  nn2 = bool(neg)
  n2 = H.heappop(neg) if neg else 0
  
  pp = p1 * p2
  nn = n1 * n2
  if pp > nn:
    ans = (ans * pp) % mod
    if nn1:
      H.heappush(neg, n1)
    if nn2:
      H.heappush(neg, n2)
  else:
    ans = (ans * nn) % mod
    if pp1:
      H.heappush(pos, p1)
    if pp2:
      H.heappush(pos, p2)
  
  k -= 2
  
if k == 1:
  if pos:
    ans *= -H.heappop(pos)
  else:
    ans *= -(min(neg))

print(ans % mod)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as H
  
ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())
def rec(h, w): return [[0] * w for i in range(h)] 

n, k = I()
xs = Is()
mod = 1000000007
pos = [-x for x in xs if x >= 0]
neg = [-x for x in xs if x < 0]
H.heapify(pos)
H.heapify(neg)

ans = 1
while k > 1:
  pp1 = bool(pos)
  p1 = H.heappop(pos) if pp1 else 0
  pp2 = bool(pos)
  p2 = H.heappop(pos) if pp2 else 0
  
  nn1 = bool(neg)
  n1 = H.heappop(neg) if nn1 else 0
  nn2 = bool(neg)
  n2 = H.heappop(neg) if neg else 0
  
  pp = p1 * p2
  nn = n1 * n2
  if pp > nn:
    ans = (ans * pp) % mod
    if nn1:
      H.heappush(neg, n1)
    if nn2:
      H.heappush(neg, n2)
  else:
    ans = (ans * nn) % mod
    if pp1:
      H.heappush(pos, p1)
    if pp2:
      H.heappush(pos, p2)
  
  k -= 2

if k == 1:
  if pos:
    ans *= -(max(pos))
  else:
    ans *= -(min(neg))

print(ans % mod)