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: Accepted

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


def solve(N, K, A):
    ans = 1
    # K = N の場合は明らか
    if K == N:
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    # Ai の全ての数が負かつ K が奇数のとき、
    elif max(A) < 0 and K % 2 == 1:
        A.sort(reverse=True)
        # 絶対値が小さい方から K 個の積
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    # それ以外の場合、積は必ず非負
    else:
        # {Ai} を絶対値の降順にソート
        A.sort(key=abs, reverse=True)
        # 最初の K 個の積
        sign = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD
            if A[i] < 0:
                sign *= -1
            elif A[i] == 0:
                sign *= 0
        # P が負の場合
        if sign < 0:
            small_nonneg = [a for a in A[K:] if a >= 0]
            small_neg = [a for a in A[K:] if a < 0]
            large_nonneg = [a for a in A[:K] if a >= 0]
            large_neg = [a for a in A[:K] if a < 0]
            if not small_neg or not large_nonneg:
                ans *= max(small_nonneg)
                ans %= MOD
                ans *= pow(max(large_neg), MOD - 2, MOD)
                ans %= MOD
            elif not small_nonneg or not large_neg:
                ans *= min(small_neg)
                ans %= MOD
                ans *= pow(min(large_nonneg), MOD - 2, MOD)
                ans %= MOD
            else:
                if min(small_neg) * max(large_neg) > max(small_nonneg) * min(
                    large_nonneg
                ):
                    # (2) 正の数を 1 つ取り除き、負の数を 1 つ加える
                    ans *= min(small_neg)
                    ans %= MOD
                    ans *= pow(min(large_nonneg), MOD - 2, MOD)
                    ans %= MOD
                else:
                    # (1) 負の数を 1 つ取り除き、非負の数を 1 つ加える
                    ans *= max(small_nonneg)
                    ans %= MOD
                    ans *= pow(max(large_neg), MOD - 2, MOD)
                    ans %= MOD
    return ans


print(solve(N, K, A))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
mod=10**9+7
ans=1
i=0
j=-1
k_1=k
while k_1>1:
  if a[i]*a[i+1]>a[j]*a[j-1]:
    ans=ans*a[i]*a[i+1]%mod
    i+=2
    k_1-=2
  else:
    ans=ans*a[j]%mod
    j-=1
    k_1-=1
if k_1==1:
  ans=ans*a[j]%mod
if a[-1]<0 and k%2==1:
  ans=1
  for i in a[n-k:]:
    ans=ans*i%mod
print(ans)

Submission status: Accepted

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

B,C=[],[]
for i in A:
    if i>=0:B.append(i)
    else:C.append(i)

B.sort()
C.sort(key=lambda x:abs(x))

ans,flag=1,1
while k!=0:
    if k>=2:
        point=0
        if len(B)>=2 and len(C)>=2:
            if B[-1]*B[-2]>C[-1]*C[-2]:
                ans *=B.pop()
                point=1
            else:ans *=C.pop()*C.pop()
        elif len(B)>=2:ans *=B.pop()*B.pop()
        elif len(C)>=2:ans *=C.pop()*C.pop()
        else:flag=0
        k -=2-point
    else:
        if len(B)>=1:ans *=B.pop()
        else:flag=0
        k -=1
    ans %=mod

if flag:print(ans)
else:
    ans=1
    A=sorted(A,key=lambda x:abs(x))
    for i in range(K):
        ans *=A[i]
        ans %=mod
    print(ans)

Submission status: Accepted

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

B,C=[],[]
for i in A:
    if i>=0:B.append(i)
    else:C.append(i)

B.sort()
C.sort(key=lambda x:abs(x))

ans,flag=1,1
while k!=0:
    if k>=2:
        if len(B)>=2 and len(C)>=2:
            if B[-1]*B[-2]>C[-1]*C[-2]:
                ans *=B.pop()
                k -=1
            else:
                ans *=C.pop()*C.pop()
                k -=2
        elif len(B)>=2:
            ans *=B.pop()*B.pop()
            k -=2
        elif len(C)>=2:
            ans *=C.pop()*C.pop()
            k -=2
        else:
            k -=k
            flag=0
    else:
        if len(B)>=1:ans *=B.pop()
        else:flag=0
        k -=1

    ans %=mod

if flag:print(ans)
else:
    ans=1
    A=sorted(A,key=lambda x:abs(x))
    for i in range(K):
        ans *=A[i]
        ans %=mod
    print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,k = LI()
    a = sorted(LI())

    r = 1
    i = n - 1
    j = 0
    if k % 2 == 1:
        r = a[i]
        i -= 1

    mf = r < 0

    for _ in range(k//2):
        t = a[i] * a[i-1]
        u = a[j] * a[j+1]
        if (not mf and t >= u) or (mf and t < u):
            r *= t
            r %= mod
            i -= 2
        else:
            r *= u
            r %= mod
            j += 2

    return r


print(main())

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

def prod(a):
    res = 1
    for x in a:
        res = (res * x) % MOD
    return res

def solve(n, k, a):
    if k == 1:
        return max(a)
    elif k == n:
        return prod(a)
    elif (max(a) < 0) and (k % 2 == 1):
        a = sorted(a, reverse=True)
        return prod(a[:k])
    else:
        a = sorted(a, key=lambda x: -abs(x))
        num_negative = len(list(filter(lambda x: x < 0, a[:k])))
        if num_negative % 2 == 0:
            return prod(a[:k])
        else:
            i1, j1 = None, None
            for i in range(k):
                if a[i] < 0:
                    i1 = i
            for j in range(k,n):
                if a[j] >= 0:
                    j1 = j
                    break
            i2, j2 = None, None
            for i in range(k):
                if a[i] >= 0:
                    i2 = i
            for j in range(k, n):
                if a[j] < 0:
                    j2 = j
                    break
            if (i1 is None) or (j1 is None):
                return prod(a[:i2] + a[i2+1:k] + [a[j2]])
            elif (i2 is None) or (j2 is None):
                return prod(a[:i1] + a[i1+1:k] + [a[j1]])
            elif abs(a[j1] * a[i2]) > abs(a[i1] * a[j2]):
                return prod(a[:i1] + a[i1+1:k] + [a[j1]])
            else:
                return prod(a[:i2] + a[i2+1:k] + [a[j2]])

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

def prod(a):
    res = 1
    for x in a:
        res = (res * x) % MOD
    return res

def solve(n, k, a):
    if k == 1:
        return max(a)
    elif k == n:
        return prod(a)
    elif (max(a) < 0) and (k % 2 == 1):
        a = sorted(a, reverse=True)
        return prod(a[:k])
    else:
        a = sorted(a, key=lambda x: -abs(x))
        num_negative = len(list(filter(lambda x: x < 0, a[:k])))
        if num_negative % 2 == 0:
            return prod(a[:k])
        else:
            i1, j1 = None, None
            for i in range(k):
                if a[i] < 0:
                    i1 = i
            for j in range(k,n):
                if a[j] >= 0:
                    j1 = j
                    break
            i2, j2 = None, None
            for i in range(k):
                if a[i] >= 0:
                    i2 = i
            for j in range(k, n):
                if a[j] < 0:
                    j2 = j
                    break
            if ((i1 is None) or (j1 is None)) and ((i2 is None) or (j2 is None)):
                return prod(a[:k])
            elif (i1 is None) or (j1 is None):
                return prod(a[:i2] + a[i2+1:k] + [a[j2]])
            elif (i2 is None) or (j2 is None):
                return prod(a[:i1] + a[i1+1:k] + [a[j1]])
            elif abs(a[j1] * a[i2]) > abs(a[i1] * a[j2]):
                return prod(a[:i1] + a[i1+1:k] + [a[j1]])
            else:
                return prod(a[:i2] + a[i2+1:k] + [a[j2]])

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

Submission status: Accepted

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

positives = [a for a in A if a > 0]
negatives = [a for a in A if a < 0]
positive_cnt = len(positives)
negative_cnt = len(negatives)
zero_cnt = A.count(0)


if 2 * min(K // 2, negative_cnt // 2) + positive_cnt >= K:
    ans = 1
    positives.sort(key=lambda x: abs(x), reverse=True)
    negatives.sort(key=lambda x: abs(x), reverse=True)

    if K % 2 == 1:
        ans *= positives.pop(0)
        K -= 1

    X = []
    for pair in zip(*[iter(positives)] * 2):
        X.append(reduce(operator.mul, pair, 1))
    for pair in zip(*[iter(negatives)] * 2):
        X.append(reduce(operator.mul, pair, 1))
    X.sort(reverse=True)

    ans *= reduce(lambda a, b: a * b % MOD, X[:K // 2], 1)
    print(ans % MOD)

elif zero_cnt:
    print(0)

else:
    A.sort(key=lambda x: abs(x))
    print(reduce(lambda a, b: a * b % MOD, A[:K], 1) % MOD)

Submission status: Accepted

Solution code:
import functools

def sign(x):
    if x>0:
        return 1
    elif x==0:
        return 0
    else:
        return -1

def multiply(x,y):
    ans = x*y
    if ans>=10**9+7 or ans<0:
        ans %= (10**9+7)
    return ans

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

if (A[-1]<0 and K%2==1):
    combi = A[-K:]
    if K >1:
        answer =  functools.reduce(multiply,combi)

elif K == N:
    answer = functools.reduce(multiply,A)

else:
    signs = 1
    i,j = 0,0
    for _ in range(K):
        if abs(A[i]) > abs(A[N-j-1]):
            signs *= sign(A[i])
            i += 1

        else:
            signs *= sign(A[N-j-1])
            j += 1
    combi = A[N-j:] + A[:i]
    del A[N-j:]
    del A[:i]
    combi = combi[::-1]

    if signs == -1:
        if A:
            if combi[-1]<0:
                del combi[0]
                combi.append(A[-1])
            elif A[0]>=0:
                del combi[0]
                combi.append(A[-1])
            elif A[0]<0 and A[-1] >0:
                if combi[0]*A[0] > combi[-1]*A[-1]:
                    del combi[-1]
                    combi.insert(0,A[0])
                else:
                    del combi[0]
                    combi.append(A[-1])
            elif A[-1] <= 0:
                del combi[-1]
                combi.insert(0,A[0])

    answer =  functools.reduce(multiply,combi)
print(answer)

Submission status: Accepted

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

def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    l, r = 0, N-1
    MOD = 10**9+7
    if K == N:
        ans = 1
        for num in A:
            ans *= num
            ans = (ans+MOD)%MOD
        print((ans+MOD)%MOD)
        exit()
    elif A[-1] < 0 and K%2 == 1:
        ans = 1
        for i in range(K):
            ans *= A[-i-1]
            ans = (ans+MOD)%MOD
        print(ans)
        exit()
    ans = 1
    if K%2 == 1:
        ans *= A[-1]
        r -= 1
    for _ in range(K//2):
        nl = A[l]*A[l+1]
        nr = A[r]*A[r-1]
        if nl > nr:
            ans *= nl
            l += 2
        else:
            ans *= nr
            r -= 2
        ans = (ans+MOD)%MOD
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import functools

def sign(x):
    if x>0:
        return 1
    elif x==0:
        return 0
    else:
        return -1
    
def multiply(x,y):
    ans = x*y
    if ans>=10**9+7 or ans<0:
        ans %= (10**9+7)
    return ans

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

if (A[-1]<0 and K%2==1):
    combi = A[-K:]
    if K >1:
        answer =  functools.reduce(multiply,combi)

elif K == N:
    answer = functools.reduce(multiply,A)
    
else:
    signs = 1
    i,j = 0,0
    for _ in range(K):
        if abs(A[i]) > abs(A[N-j-1]):
            signs *= sign(A[i])
            i += 1
            
        else:
            signs *= sign(A[N-j-1])
            j += 1
    combi = A[N-j:] + A[:i]
    del A[N-j:]
    del A[:i]
    combi = combi[::-1]     
       
    if signs == -1:
        if A:
            if combi[-1]<0:
                del combi[0]
                combi.append(A[-1])
            elif A[0]>=0:
                del combi[0]
                combi.append(A[-1])
            elif A[0]<0 and A[-1] >0:
                if combi[0]*A[0] > combi[-1]*A[-1]:
                    del combi[-1]
                    combi.insert(0,A[0])
                else:
                    del combi[0]
                    combi.append(A[-1])
            elif A[-1] <= 0:
                del combi[-1]
                combi.insert(0,A[0]) 
                
    answer =  functools.reduce(multiply,combi)
print(answer)

Submission status: Accepted

Solution code:
"""
E.
"""
from functools import reduce
from collections import deque


def prod(x, y):
    return x * y % MOD

    
N, K = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
# abs_a_list = sorted(a_list, key=abs, reverse=True)
MOD = 10**9 + 7

if K%2 == 1:
    flg = True
    for a in a_list:
        if a >= 0:
            flg = False
            break
    if flg:
        print(reduce(prod, a_list[:K]))
        exit()

S = []
a_list = deque(a_list)
i = 0
while i < K:
    if len(a_list)>=2:
        if a_list[0]*a_list[1] >= a_list[-1]*a_list[-2]:
            S.append(a_list.popleft())
            i += 1
        elif a_list[0]*a_list[1] < a_list[-1]*a_list[-2] and i <= K-2:
            S.append(a_list.pop())
            S.append(a_list.pop())
            i += 2
        else:
            S.append(a_list.popleft())
            i += 1
    else:
        S.append(a_list.popleft())
        i += 1
        
ans = reduce(prod, S)
print(ans)

Submission status: Accepted

Solution code:
"""
E.
"""
from functools import reduce
from collections import deque


def prod(x, y):
    return x * y % MOD

    
N, K = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
# abs_a_list = sorted(a_list, key=abs, reverse=True)
MOD = 10**9 + 7

if K%2 == 1:
    flg = True
    for a in a_list:
        if a >= 0:
            flg = False
            break
    if flg:
        print(reduce(prod, a_list[:K]))
        exit()

S = []
a_list = deque(a_list)
i = 0
while i < K:
    if len(a_list)>=2:
        if a_list[0]*a_list[1] > a_list[-1]*a_list[-2]:
            S.append(a_list.popleft())
            i += 1
        elif a_list[0]*a_list[1] <= a_list[-1]*a_list[-2] and i <= K-2:
            S.append(a_list.pop())
            S.append(a_list.pop())
            i += 2
        else:
            S.append(a_list.popleft())
            i += 1
    else:
        S.append(a_list.popleft())
        i += 1
        
ans = reduce(prod, S)
print(ans)

Submission status: Accepted

Solution code:
    #n,k,*a=map(int,open(0).read().split())
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
mod=10**9+7
ans=1
i=0
j=-1
kk=k
while kk>1:
    if a[i]*a[i+1]>a[j]*a[j-1]:
        ans=ans*a[i]*a[i+1]%mod
        i+=2
        kk-=2
    else:
        ans=ans*a[j]%mod
        j-=1
        kk-=1
if kk==1:
    ans=ans*a[j]%mod

if a[-1]<0 and k%2==1:
    ans=1
    for i in a[n-k:]:
        ans=ans*i%mod
print(ans)

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
Q = 10**9+7
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()))
    if K == 1:
        print(max(A))
        return
    positive = 0
    zero = 0
    negative = 0
    for a in A:
        if a > 0:
            positive += 1
        elif a == 0:
            zero += 1
        else:
            negative += 1
    # print(positive, negative, zero)
    # print(positive+negative, K)
    if positive+negative < K:
        print(0)
        return
    if positive == 0:
        if K%2 == 1:
            if zero > 0:
                print(0)
                return
            else:
                A.sort(reverse=True)
                ans = 1
                for a in A[:K]:
                    ans *= a
                    ans %= Q
                print(ans)
                return
        else:
            A.sort()
            ans = 1
            for a in A[:K]:
                ans *= a
                ans %= Q
            print(ans)
            return
    # if K == 2:
    #     if negative <= 1:
    #         A.sort(reverse=True)
    #         print(A[0]*A[1]%Q)
    #         return
    if negative <= 1:
        A.sort(reverse=True)
        ans = 1
        for a in A[:K]:
            ans *= a
            ans %= Q
        print(ans)
        return
    if K == negative + positive:
        if negative%2 == 1:
            if zero > 0:
                print(0)
                return
        ans = 1
        for a in A:
            if a != 0:
                ans *= a
                ans %= Q
        print(ans)
        return
    B = [(abs(a), a) for a in A]
    B.sort(reverse = True)
    minus = False
    minus_value = 0
    plus_value = 0
    ans = 1
    for b in B[:K]:
        ans *= b[0]
        ans %= Q
        if b[1] < 0:
            minus = not minus
            minus_value = b[0]
        elif b[1] > 0:
            plus_value = b[0]
    # print(plus_value, minus_value)
    if minus:
        ans_plus = ans_minus = ans
        plus_replaced_value = 0
        minus_replaced_value = 0
        if minus_value > 0:
            for b in B[K:]:
                if b[1] > 0:
                    ans_plus = ans*pow(minus_value,Q-2,Q)%Q*b[0]%Q
                    if plus_value == 0:
                        plus_replaced_value = b[0]
                    else:
                        plus_replaced_value = plus_value*b[0]
                    break
        if plus_value > 0:
            for b in B[K:]:
                if b[1] < 0:
                    ans_minus = ans*pow(plus_value,Q-2,Q)%Q*b[0]%Q
                    if minus_value == 0:
                        minus_replaced_value = b[0]
                    else:
                        minus_replaced_value = minus_value*b[0]
                    break
        if plus_replaced_value == 0 and minus_replaced_value == 0:
            pass
        elif plus_replaced_value < minus_replaced_value:
            ans = ans_minus
        else:
            ans = ans_plus
    # print(plus_replaced_value, minus_replaced_value)
    # print(ans, ans_minus, ans_plus)
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import sys
from functools import reduce
from operator import mul
input = lambda: sys.stdin.readline().strip()
n, k = [int(x) for x in input().split()]
a = sorted((int(x) for x in input().split()), key=abs)
sgn = [0 if x == 0 else x // abs(x) for x in a]
M = 10**9 + 7
def modmul(x, y):
    return x * y % M
if reduce(mul, sgn[-k:]) >= 0:
    print(reduce(modmul, a[-k:], 1))
else:
    largest_unselected_neg = next(i for i, x in enumerate(reversed(a[:-k])) if x < 0) if any(x < 0 for x in a[:-k]) else None
    largest_unselected_pos = next(i for i, x in enumerate(reversed(a[:-k])) if x > 0) if any(x > 0 for x in a[:-k]) else None
    smallest_selected_neg = next(i for i, x in enumerate(a[-k:]) if x < 0) if any(x < 0 for x in a[-k:]) else None
    smallest_selected_pos = next(i for i, x in enumerate(a[-k:]) if x > 0) if any(x > 0 for x in a[-k:]) else None
    can1 = largest_unselected_neg is not None and smallest_selected_pos is not None
    can2 = largest_unselected_pos is not None and smallest_selected_neg is not None
    def ans1():
        return list(reversed(a[:-k]))[largest_unselected_neg] * reduce(modmul, (x for i, x in enumerate(a[-k:]) if i != smallest_selected_pos), 1) % M 
    def ans2():
        return list(reversed(a[:-k]))[largest_unselected_pos] * reduce(modmul, (x for i, x in enumerate(a[-k:]) if i != smallest_selected_neg), 1) % M
    if can1 and not can2:
        print(ans1())
    elif can2 and not can1:
        print(ans2())
    elif can1 and can2:
        if list(reversed(a[:-k]))[largest_unselected_neg] * a[-k:][smallest_selected_neg] > list(reversed(a[:-k]))[largest_unselected_pos] *  a[-k:][smallest_selected_pos]:
            print(ans1())
        else:
            print(ans2())
    else:
        print(reduce(modmul, a[:k], 1))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
# import bisect
# import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
import itertools
import heapq


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    A.sort()
    A = deque(A)
    #    print(A)
    A_minus = deque([s for s in A if s < 0])
    A_plus = deque([s for s in A if s >= 0])

    #    print(A_plus)
    #    print(A_minus)
    AA = []
    if N == K:
        ans = 1
        for i in A:
            ans *= i % mod
            ans %=mod
        print(ans % mod)

    elif K % 2 == 0:
        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            heapq.heappush(AA, -a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            heapq.heappush(AA, -a1 * a2)
        ans = 1

        for i in range(K // 2):
            ans *= (-1 * heapq.heappop(AA))
            ans %= mod
        print(ans % mod)

    elif len(A_plus) == 0:
        ans = 1
        for i in range(K):
            ans *= A_minus.pop() % mod
            ans %= mod
        print(ans % mod)

    else:
        ans = A_plus.pop()
        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            heapq.heappush(AA, -a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            heapq.heappush(AA, -a1 * a2)

        heapq.heapify(AA)
        for i in range(K // 2):
            ans *= (-1 * heapq.heappop(AA)) % mod
            ans %=mod
        print(ans% mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,K = map(int, readline().split())
    A = [int(i) for i in readline().split()]

    MOD = 10**9+7
    ans = 1
    if K == N:
        for a in A:
            ans *= a
            ans %= MOD
        print(ans)
        exit()

    plus = []
    minus = []

    for a in A:
        if a < 0:
            heappush(minus, a)
        else:
            heappush(plus, -a)

    if not plus:
        if K % 2 == 1:
            for _ in range(N-K):
                heappop(minus)
            for _ in range(K):
                ans *= heappop(minus)
                ans %= MOD
        else:
            for _ in range(K):
                ans *= heappop(minus)
                ans %= MOD
        print(ans)
        exit()

    p = []
    m = []
    for _ in range(K):
        if plus and minus:
            if plus[0] <= minus[0]:
                p.append(-heappop(plus))
            else:
                m.append(heappop(minus))
        elif plus:
            p.append(-heappop(plus))
        else:
            m.append(heappop(minus))

    for i in p:
        ans *= i
        ans %= MOD
    for j in m:
        ans *= j
        ans %= MOD

    if len(m) % 2 == 0:
        print(ans)

    else:
        if plus and minus and p and m:
            if p[-1] * (-plus[0]) >= m[-1] * minus[0]:
                ans *= pow(m[-1], MOD-2, MOD)
                ans *= -plus[0]
                ans %= MOD
            else:
                ans *= pow(p[-1], MOD-2, MOD)
                ans *= minus[0]
                ans %= MOD
        elif plus:
            ans *= pow(m[-1], MOD-2, MOD)
            ans *= -plus[0]
            ans %= MOD
        else:
            ans *= pow(p[-1], MOD-2, MOD)
            ans *= minus[0]
            ans %= MOD
        
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

def main():
    N,K = map(int, readline().split())
    A = [int(i) for i in readline().split()]

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

    plus = []
    minus = []

    for a in A:
        if a < 0:
            heappush(minus, a)
        else:
            heappush(plus, -a)

    if not plus:
        if K % 2 == 1:
            for _ in range(N-K):
                heappop(minus)
            for _ in range(K):
                ans *= heappop(minus)
                ans %= MOD
        else:
            for _ in range(K):
                ans *= heappop(minus)
                ans %= MOD
        print(ans)
        exit()

    p = []
    m = []
    for _ in range(K):
        if plus and minus:
            if plus[0] <= minus[0]:
                p.append(-heappop(plus))
            else:
                m.append(heappop(minus))
        elif plus:
            p.append(-heappop(plus))
        else:
            m.append(heappop(minus))

    for i in p:
        ans *= i
        ans %= MOD
    for j in m:
        ans *= j
        ans %= MOD

    if len(m) % 2 == 0:
        print(ans)

    else:
        if plus and minus and p and m:
            if p[-1] * (-plus[0]) >= m[-1] * minus[0]:
                ans *= pow(m[-1], MOD-2, MOD)
                ans *= -plus[0]
                ans %= MOD
            else:
                ans *= pow(p[-1], MOD-2, MOD)
                ans *= minus[0]
                ans %= MOD
        elif plus:
            ans *= pow(m[-1], MOD-2, MOD)
            ans *= -plus[0]
            ans %= MOD
        else:
            ans *= pow(p[-1], MOD-2, MOD)
            ans *= minus[0]
            ans %= MOD
        
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD=10**9+7
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls=sorted(ls, key=lambda x: -abs(x))

#かける数をフラグで管理
flag=[0 for _ in range(N)]

sign=0
for i in range(K):
  flag[i]=1
  if ls[i]<0:
    sign=(sign+1)%2

if sign==1: #絶対値が大きい順にかけた数は負か？
  #フラグのない負の数を、フラグのある正の数と取り換え可能か？
  swap_neg_to_pos=[]
  for i in range(K,N):
    if ls[i]<0:
      for j in range(K):
        if ls[K-1-j]>0:
          swap_neg_to_pos=[i,K-1-j,ls[K-1-j],-ls[i]]
          break
      break
  #フラグのない正の数を、フラグのある負の数と取り換え可能か？
  swap_pos_to_neg=[]
  for i in range(K,N):
    if ls[i]>0:
      for j in range(K):
        if ls[K-1-j]<0:
          swap_pos_to_neg=[i,K-1-j,-ls[K-1-j],ls[i]]
          break
      break

  #フラグを修正        
  if swap_neg_to_pos!=[] and swap_pos_to_neg!=[]: #どちらも取り換え可能なとき
    #負の数にフラグを与えたほうがロスが少ないとき
    if swap_neg_to_pos[2]*swap_pos_to_neg[3]<swap_pos_to_neg[2]*swap_neg_to_pos[3]: 
      flag[swap_neg_to_pos[0]]=1
      flag[swap_neg_to_pos[1]]=0
    else: #正の数にフラグを与えたほうがロスが少ないとき
      flag[swap_pos_to_neg[0]]=1
      flag[swap_pos_to_neg[1]]=0
  elif swap_neg_to_pos==[] and swap_pos_to_neg==[]: #どちらも取り換え不可能なとき 
    flag.reverse()
  elif swap_pos_to_neg!=[]: #正の数にフラグを与えることのみ可能なとき
    flag[swap_pos_to_neg[0]]=1
    flag[swap_pos_to_neg[1]]=0
  else:                     #負の数にフラグを与えることのみ可能なとき
    flag[swap_neg_to_pos[0]]=1
    flag[swap_neg_to_pos[1]]=0

ans=1
for i in range(N):
  if flag[i]==1:
    ans=(ans*ls[i])%MOD
print(ans)

Submission status: Accepted

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

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

# from random import randint
# n = 10
# k = 4
# A = []
# for i in range(10):
#     A.append(randint(-20,20))
# anss=0
# for i in range(n):
#     for j in range(i+1,n):
#         for ii in range(j+1,n):
#             for jj in range(ii+1,n):
#                 anss = max(anss, A[i]*A[j]*A[ii]*A[jj])
# print(anss)
# print(A)


B = [[], []]
for i in range(n):
    if A[i] >= 0:
        B[0].append(A[i])
    else:
        B[1].append(A[i])
B[0].sort(reverse=True)
B[1].sort()

if k % 2 == 1 and len(B[0]) == 0:
    ans = 1
    ind = len(B[1])-1
    for i in range(k):
        ans = (ans * B[1][ind]) % mod
        ind -= 1
    print(ans)
elif k == n and len(B[1]) % 2 == 1:
    ans = 1
    for i in range(n):
        ans = (ans * A[i]) % mod
    print(ans)
else:
    k0 = min(len(B[0]), k)
    k1 = k-k0
    if k1%2==1:
        k0 -= 1
        k1 += 1
    # print(B,k0,k1)
    while k1+1 < len(B[1]) and k0-2 >= 0 and B[1][k1]*B[1][k1+1] > B[0][k0-1]*B[0][k0-2]:
        k1 += 2
        k0 -= 2
        # print(k0,k1)
        # print(k1+1 < len(B[1]),B[1][k1]*B[1][k1+1] , B[0][k0-1]*B[0][k0-2])
    ans = 1
    for i in range(k0):
        ans = (ans * B[0][i]) % mod
    for i in range(k1):
        ans = (ans * B[1][i]) % mod
    print(ans)