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:
MOD = 10**9 + 7
INF = 10**9 + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    ans = modint(1)
    if N == K:
        for a in A:
            ans *= a
        return print(ans)
    elif all(a < 0 for a in A) and K % 2 == 1:
        A.sort(key=abs)
        for a in A[:K]:
            ans *= a
        return print(ans)
    # 以降，非負の答えにできる
    A.sort(reverse=True, key=abs)
    if sum(a < 0 for a in A[:K]) % 2 == 0:
        for a in A[:K]:
            ans *= a
    else:
        ans1 = modint(1)  # 正を取り除く
        ans2 = modint(1)  # 負を取り除く
        p_remove = False
        x1 = INF
        for a in A[:K][::-1]:
            if a > 0 and not p_remove:
                p_remove = True
                x1 = a
                continue
            ans1 *= a
        n_remove = False
        x2 = INF
        for a in A[:K][::-1]:
            if a < 0 and not n_remove:
                n_remove = True
                x2 = a
                continue
            ans2 *= a
        y1 = 0  # 一番大きい負
        y2 = 0  # 一番大きい正
        for a in A[K:]:
            if y1 == 0 and a < 0:
                y1 = a
            if y2 == 0 and a > 0:
                y2 = a
            if y1 != 0 and y2 != 0:
                break
        ans1 *= y1
        ans2 *= y2
        if x1 != INF and x2 != INF:
            if abs(x2*y1) <= abs(x1*y2):
                ans = ans2
            else:
                ans = ans1
        elif x1 == INF and x2 == INF:
            # all 0
            ans = 0
        elif x1 == INF:
            # A[:K]に正の整数がなかった
            ans = ans2
        else:
            # A[:K]に負の整数がなかった
            # でもこれのときはif sum(a < 0 for a in A[:K]) % 2 == 0
            # がTrueになるからいらなそう？
            ans = ans1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

print(e_multiplication_4())

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


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

MOD = 10**9 + 7

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

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

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

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

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

    BIGINT = 10**9 + 1  # tmp 用
    tmp1 = BIGINT
    tmp2 = BIGINT

    for a in A:
        if a >= 0:
            if tmp1 == BIGINT:
                tmp1 = a
            else:
                heappush(cand, -tmp1*a)
                tmp1 = BIGINT
        else:
            if tmp2 == BIGINT:
                tmp2 = a
            else:
                heappush(cand, -tmp2*a)
                tmp2 = BIGINT

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if (sum([1 for a in a_list if np.sign(a)!=-1])==0 and k%2==1) or (k==n and len([1 for a in a_list if np.sign(a)==-1])%2==1):
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()
else:
    a_list.sort(key = abs,reverse = True)
    add = 1
    remove = 1
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        negative_big = [num for num in a_list[:k] if np.sign(num)==-1]
        positive_big = [num for num in a_list[:k] if np.sign(num)!=-1]
        negative_small = [num for num in a_list[k:] if np.sign(num)==-1]
        positive_small = [num for num in a_list[k:] if np.sign(num)!=-1]
        
        
        if len(negative_big)==0 or len(positive_small)==0:
            remove = min(positive_big)
            add = min(negative_small)
        elif len(positive_big)==0 or len(negative_small)==0:
            remove = max(negative_big)
            add = max(positive_small)
        else:
            positive_small_max = max(positive_small)
            negative_big_max = max(negative_big)
            negative_small_min = min(negative_small)
            positive_big_min = min(positive_big)
            if positive_small_max*positive_big_min > negative_small_min*negative_big_max:
                remove = negative_big_max
                add = positive_small_max
            else:
                remove = positive_big_min
                add = negative_small_min
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def main():
  N, K = map(int , input().split())
  A = list(map(int, input().split()))
  
  if max(A) < 0 and K % 2 == 1:
    A.sort(reverse = True)
    ans = 1
    for i in range(K):
      ans = ans*A[i]%MOD
    print(ans%MOD)
  elif K == N:
    ans = 1
    for i in A:
      ans = ans*i%MOD
    print(ans%MOD)
  else:
    A_p = []
    A_m = []
    for i in A:
      if i >= 0:A_p.append(i)
      else:A_m.append(abs(i))
    A_p.sort(reverse =  True)
    A_m.sort(reverse = True)
    num = 0
    ans = 1
    posi_p = 0
    posi_m = 0
    sign = 0
    while (num < K):
      if posi_m == len(A_m) and posi_p < len(A_p):
        ans = ans*A_p[posi_p]%MOD
        posi_p += 1
        num += 1
      elif posi_p == len(A_p) and posi_m < len(A_m):
        ans = ans*A_m[posi_m]%MOD
        sign += 1
        posi_m += 1
        num += 1        
      elif  A_p[posi_p] >= abs(A_m[posi_m]):
        ans = ans*A_p[posi_p]%MOD
        posi_p += 1
        num += 1        
      else:
        ans = ans*A_m[posi_m]%MOD
        sign += 1
        posi_m += 1
        num += 1
      if num == K and sign % 2 == 1:
        if K == 1:
          ans = A_p[0]
        elif posi_m == len(A_m):
          ans = ans*pow(A_m[posi_m-1], MOD-2, MOD) % MOD
          ans = ans*A_p[posi_p] % MOD
        elif posi_p == len(A_p):
          ans = ans*pow(A_p[posi_p-1],  MOD-2, MOD)
          ans =  ans*A_m[posi_m] % MOD
        elif A_p[posi_p]*A_p[posi_p-1] >= A_m[posi_m]*A_m[posi_m-1]:
          ans = ans*pow(A_m[posi_m-1], MOD-2, MOD)%MOD
          ans = ans*A_p[posi_p] % MOD
        else:
          if posi_p != 0:
            ans = ans*pow(A_p[posi_p-1], MOD-2, MOD)%MOD
            ans = ans*A_m[posi_m]%MOD
          else:
            ans = ans*pow(A_m[posi_m-1], MOD-2, MOD)%MOD
            ans = ans *A_p[posi_p]%MOD
            
    print(ans%MOD)
          
    
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
mod = 10**9+7
a_list.sort()
ans = 1
if k % 2 == 1 and a_list[-1] < 0:
    for i in range(k):
        ans *= a_list[n - 1 - i]
        ans %= mod
else:
    l = 0
    r = -1
    mlt1 = a_list[0] * a_list[1]
    mlt2 = a_list[-2] * a_list[-1]
    count = 0
    while True:
        if count == k:
            break
        elif count == k - 1:
            ans *= a_list[r] % mod
            ans %= mod
            break
        if mlt1 >= mlt2:
            ans *= mlt1 % mod
            l += 2
            count += 2
            if l <= n - 2:
                mlt1 = a_list[l + 1] * a_list[l]
        else:
            ans *= a_list[r] % mod
            r -= 1
            count += 1
            if r >= - n + 1:
                mlt2 = a_list[r - 1] * a_list[r]
        ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
a.sort()
p=a.pop
s=b=~k%2or p()
i=0
while k>1:
 x=a[i]*a[i+1]
 if x*b>a[-1]*a[-2]*b:i+=2
 else:x=p()*p()
 s=s*x%(10**9+7);k-=2
print(s)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(i:=0).read().split())
a.sort()
p=a.pop
s=b=~k%2or p()
while k>1:
 if(x:=a[i]*a[i+1])*b>a[-1]*a[-2]*b:i+=2
 else:x=p()*p()
 s=s*x%(10**9+7);k-=2
print(s)

Submission status: Accepted

Solution code:
#正の場合、0の場合、負の場合で分ける
#負の数のみの場合は調整しようがない
#偶数の時は絶対値の大きい順
#奇数の時は絶対値の小さい順
#正の数のみの場合は大きい順
#大きい順

#他は調整できるので、正で大きくする方向で考える(正→0以上)
#負の数は偶数個ないと正にならないので二つ一組で先にかけて考える
#正の数も同様に先にかけて、その中で大きいものを選べば良い

#負の数が奇数個、正の数が奇数個の時(負の数が余る、正の数が余る)
#Kが偶数の時はいい感じに選んでく(N=kの時は仕方ないので全部)
#Kが奇数の時は正の中で最大のものを選ぶ
#負の数が偶数個、正の数が奇数個の時(正の数が余る)
#Kが偶数の時はいい感じに選んでく
#奇数の時は残りの正の中から選ぶ
#負の数が奇数個、正の数が偶数個の時(負の数が余る)
#N=Kの時は全部選ぶ、それ以外の場合は余った負の数はいらない
#Kが奇数の時は残りの正の中で最大のものを選べば良い
#負の数が偶数個、正の数が偶数個の時
#Kが奇数の時は残りの正の中で最大のものを選べば良い

#N=Kの時は別で分けて考えるとすると、負の数及び正の数によらず
#Kが偶数の時は大きいものからいい感じに選んでく
#Kが奇数の時は最後の残り一個は正の残りの中で最大のものを選ぶ
#と簡単に言い換えることができる

#x:配列
mod=10**9+7
def multarray(x):
    ret=1
    for i in x:
        ret*=i
        ret%=mod
    return ret

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

if n==k:
    print(multarray(a))
    exit()

ap,am=[],[]
for i in range(n):
    if a[i]>=0:
        ap.append(a[i])
    else:
        am.append(a[i])
#絶対値の順番
ap.sort(reverse=True)
am.sort()

if len(am)==0:
    print(multarray(ap[:k]))
    exit()
if len(ap)==0:
    if k%2==0:
        print(multarray(am[:k]))
    else:
        print(multarray(am[::-1][:k]))
    exit()

apm2=[]
for i in range(len(am)//2):
    apm2.append((am[2*i]*am[2*i+1],0))
for i in range(len(ap)//2):
    apm2.append((ap[2*i]*ap[2*i+1],1))
apm2.sort(reverse=True)

#+の次にどこを見るのかをチェックしておく
#まだかけない
p=0
ans=[]
for i in range(k//2):
    p+=(2*apm2[i][1])
    ans.append(apm2[i][0])

#ここで不正アクセスの可能性を避ける
#プラスが余ってない場合(一個減らして次のマイナス使う)
if k%2==0:
    print(multarray(ans))
    exit()
if p==len(ap):
    #一個減らす
    check_i=ans.index(ap[p-1]*ap[p-2])
    ans[check_i]=ap[p-2]
    ans.append(apm2[k//2][0])
    print(multarray(ans))
else:
    #余ってる場合もafter_contestで落ちる
    #その一個をとるのが最適とは限らない
    #一個減らして二個とる場合も
    ans_cand=[]
    #一個増やす場合
    ans_cand.append(multarray(ans)*ap[p]%mod)
    if p>=2:
        #一個減らして二個増やす場合
        check_i=ans.index(ap[p-1]*ap[p-2])
        #0除算を避ける
        ans[check_i]=ap[p-2]
        ans.append(apm2[k//2][0])
        ans_cand.append(multarray(ans))
    print(max(ans_cand))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
mod = 10 ** 9 + 7
from collections import deque

a = list(map(int, input().split()))
a.sort()
minus, zero, plus = 0, 0, 0
for i in range(n):
    if a[i] < 0:
        minus += 1
    elif a[i] == 0:
        zero += 1
    else:
        plus += 1

que = deque(a)

#ここを軽量化した
plus_flg = False
tmp = plus - k
if tmp >= 0:
    plus_flg = True
elif (-tmp <= minus and -tmp%2 == 0) or (-tmp < minus and plus >= 1):
    plus_flg = True

# plus可能
if plus_flg:
    ans = 1
    cnt = 0

    while cnt < k:
        if k - cnt >= 2:
            if que[0] * que[1] >= que[-1] * que[-2]:
                ans *= que.popleft()
                ans *= que.popleft()
                ans %= mod
                cnt += 2
            else:
                ans *= que.pop()
                ans %= mod
                cnt += 1
        else:
            ans *= que.pop()
            ans %= mod
            cnt += 1

    print(ans)



# zero
elif zero > 0:
    print(0)

# minus
else:
    a = [abs(a[i]) for i in range(n)]
    a.sort()
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= mod
    ans = -ans % mod
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mod = int(1e9+7)
    p = []
    m = []
    for a in A:
        if a >= 0:
            p.append(a)
        else:
            m.append(a)
    p.sort(reverse=True)
    m.sort(reverse=False)
    ans = 1
    if sum(np.sign(A)) == -N and K%2 == 1:
        A = sorted(A, reverse=True)
        for i in range(K):
            ans = (ans*A[i])%mod
        print(ans)
        return
    if N == K:
        for i in range(K):
            ans = (ans*A[i])%mod
        print(ans)
        return

    m_pair = []
    p_pair = []
    if K%2 == 1:
        ans *= p.pop(0)%mod
    for i in range(0, len(m), 2):
        if i+1 < len(m):
            m_pair.append(m[i]*m[i+1])
        # else:
        #     m_pair.append(m[i])
    for i in range(0, len(p), 2):
        if i+1 < len(p):
            p_pair.append(p[i]*p[i+1])
        else:
            p_pair.append(p[i])
    pairs = m_pair[:]
    pairs.extend(p_pair)
    pairs.sort(reverse=True)
    for i in range(K//2):
        ans = (ans*pairs[i])%mod
    print(ans)

main()

Submission status: Accepted

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

plus = []
minus = []
for i in a:
    if i >= 0: plus.append(i)
    if i < 0: minus.append(-i)
plus.sort(reverse=True)
minus.sort(reverse=True)

ans = 1
i, j = 0, 0
if n == k:
    for x in a:
        ans = (ans * x) % mod
else:
    if k % 2 == 1:
        if len(plus) != 0:
            ans = plus[0]
            i += 1
        else:
            minus.sort()
            ans = -minus[0]
            j += 1
    while i + j != k:
        x_p = plus[i] * plus[i + 1] if i < len(plus) - 1 else 0
        x_m = minus[j] * minus[j + 1] if j < len(minus) - 1 else 0
        if x_p >= x_m and i != len(plus):
            ans = (ans * x_p) % mod
            i += 2
        else:
            ans = (ans * x_m) % mod
            j += 2
print(ans)

Submission status: Accepted

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

plus = []
minus = []
for i in a:
    if i >= 0: plus.append(i)
    if i < 0: minus.append(-i)
plus.sort(reverse=True)
minus.sort(reverse=True)

ans = 1
i, j = 0, 0
if n == k:
    if len(plus) % 2 == 1:
        ans *= plus[0]
        i += 1
    if len(minus) % 2 == 1:
        ans *= -minus[0]
        j += 1
if n != k and k % 2 == 1:
    if len(plus) != 0:
        ans = plus[0]
        i += 1
    else:
        minus.sort()
        ans = -minus[0]
        j += 1
while i + j != k:
    x_p = plus[i] * plus[i + 1] if i < len(plus) - 1 else 0
    x_m = minus[j] * minus[j + 1] if j < len(minus) - 1 else 0
    if x_p >= x_m and i != len(plus):
        ans = (ans * x_p) % mod
        i += 2
    else:
        ans = (ans * x_m) % mod
        j += 2
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    M, P = [], []
    for a in A:
        M.append(a) if a < 0 else P.append(a)

    m, p = len(M), len(P)
    ok = False
    if p > 0:
        ok = m % 2 == 0 if n == k else True
    else:
        ok = k % 2 == 0

    res = 1
    if not ok:
        A.sort(key=lambda x: abs(x))
        for i in range(k):
            res = (res * A[i]) % mod
    else:
        P.sort()
        M.sort(reverse=True)
        if k % 2:
            a = P.pop()
            res = (res * a) % mod
        M_2 = []
        while len(P) >= 2:
            a = P.pop()
            a *= P.pop()
            M_2.append(a)
        while len(M) >= 2:
            a = M.pop()
            a *= M.pop()
            M_2.append(a)
        M_2.sort(reverse=True)
        for i in range(k // 2):
            res = (res * M_2[i]) % mod
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

plus = []
minus = []
for i in a:
    if i >= 0: plus.append(i)
    if i < 0: minus.append(-i)
plus.sort(reverse=True)
minus.sort(reverse=True)

ans = 1
if k == n:
    for x in a:
        ans = (ans * x) % mod
else:
    i, j = 0, 0
    if k % 2 == 1:
        if len(plus) != 0:
            ans = plus[0]
            i += 1
        else:
            minus.sort()
            ans = -minus[0]
            j += 1
    while i + j != k:
        x_p = plus[i] * plus[i + 1] if i < len(plus) - 1 else 0
        x_m = minus[j] * minus[j + 1] if j < len(minus) - 1 else 0
        if x_p > x_m:
            ans = (ans * x_p) % mod
            i += 2
        else:
            ans = (ans * x_m) % mod
            j += 2
print(ans)

Submission status: Accepted

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

plus = []
minus = []
for i in a:
    if i >= 0: plus.append(i)
    if i < 0: minus.append(-i)
plus.sort(reverse=True)
minus.sort(reverse=True)

ans = 1
if k == n:
    for x in a:
        ans = (ans * x) % mod
elif n == len(plus):
    for x in plus[:k]:
        ans = (ans * x) % mod
elif n == len(minus):
    if k % 2 == 1:
        ans = -1
        minus.sort()
    for x in minus[:k]:
        ans = (ans * x) % mod
else:
    i, j = 0, 0
    if k % 2 == 1:
        ans = plus[0]
        i += 1
    while i + j != k:
        x_p = plus[i] * plus[i + 1] if i < len(plus) - 1 else 0
        x_m = minus[j] * minus[j + 1] if j < len(minus) - 1 else 0
        if x_p > x_m:
            ans = (ans * x_p) % mod
            i += 2
        else:
            ans = (ans * x_m) % mod
            j += 2
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9+7
# s=正の数、t=負の数
s,t = [], []
for a in A:
  if a<0:
    t.append(a)
  else:
    s.append(a)

S = len(s)
T = len(t)
ok = False
if (S>0):
  if n==k:
    # すべての負の数をペアにできる
    ok = T%2==0
  else:
    # 負の数は考慮しない
    ok = True
else:
  # kが偶数個
  ok = (k%2==0)

ans = 1
if not ok:
  A.sort(key=lambda x: abs(x))
  for i in range(k):
    ans *= A[i]
    ans %= MOD
else:
  s.sort()
  t.sort(reverse=True)
  if k%2==1:
    ans *= s.pop()
    ans %= MOD

  p = []
  while len(s) >= 2:
    x = s.pop()
    x *= s.pop()
    p.append(x)

  while len(t) >= 2:
    x = t.pop()
    x *= t.pop()
    p.append(x)

  p.sort(reverse=True)
  for i in range(k//2):
    ans *= p[i]
    ans %= MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(key=lambda x: abs(x), reverse=True)

    res = 1

    if k == n:
        for e in a:
            res *= e
            res %= MOD
    elif max(a) < 0:
        if k % 2 == 1:
            for i in range(n - k, n):
                res *= a[i]
                res %= MOD
        else:
            for i in range(k):
                res *= a[i]
                res %= MOD
    else:
        plus_a = [e for e in a if e >= 0]
        minus_a = [e for e in a if e < 0]

        minus_cnt = min(k, len(minus_a))
        minus_cnt -= minus_cnt % 2
        plus_cnt = k - minus_cnt

        minus_a = minus_a[:minus_cnt]
        minus_a.reverse()

        max_change_cnt = min(minus_cnt, len(plus_a) - plus_cnt)
        max_change_cnt -= max_change_cnt % 2
        change_cnt = 0
        while change_cnt < max_change_cnt:
            if plus_a[plus_cnt + change_cnt] * plus_a[plus_cnt + change_cnt + 1]\
                    <= minus_a[change_cnt] * minus_a[change_cnt + 1]:
                break
            change_cnt += 2

        for i in range(change_cnt, minus_cnt):
            res *= minus_a[i]
            res %= MOD

        for i in range(plus_cnt + change_cnt):
            res *= plus_a[i]
            res %= MOD

    print(res)


main()