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:

def main():
    MOD = 10**9+7
    n,k = map(int, input().split())
    al = list(map(int, input().split()))
    al_abs = []
    al_nl = []
    for a in al: 
        if a > 0: sig = 1
        elif a < 0 : 
            sig = -1
            al_nl.append(a)
        else: sig = 0
        al_abs.append((abs(a), sig))

    if n == k:
        ans = 1
        for i in range(k):
            a = al[i]
            ans *= a
            ans %= MOD
        print(ans)
        exit()

    al_abs.sort(reverse=True)
    n_cnt = 0
    last_p = -1
    last_n = -1
    for i in range(k):
        a, sig = al_abs[i]
        if sig == -1:
            n_cnt+=1
            last_n = i
        elif sig == 1:
            last_p = i
    
    ans = 1
    if n_cnt%2 == 0:
        for i in range(k):
            a, sig = al_abs[i]
            ans *= a
            ans %= MOD
        print(ans)
        exit()


    next_p = -1
    next_n = -1 
    for i in range(k,n):
        a, sig = al_abs[i]
        if sig == 1 and next_p == -1:
            next_p = i
        elif sig == -1 and next_n == -1:
            next_n = i
        if next_n != -1 and next_p != -1:
            break

    comp_np = 0
    if next_p != -1:
        last_n_val = al_abs[last_n][0]
        next_p_val = al_abs[next_p][0]
        comp_np = next_p_val*(1.0)/last_n_val

    comp_pn = 0
    if next_n != -1 and last_p != -1:
        last_p_val = al_abs[last_p][0]
        next_n_val = al_abs[next_n][0]
        comp_pn = next_n_val*(1.0)/last_p_val

    if comp_np == 0 and comp_pn > 0:
        np_or_pn = False
    elif comp_pn == 0 and comp_np > 0:
        np_or_pn = True
    elif comp_np > 0 and comp_pn > 0:
        if next_p_val*last_p_val > next_n_val*last_n_val:
            np_or_pn = True
        else:
            np_or_pn = False

    elif comp_np == 0 and comp_pn == 0:
        if 0 in al:
            print(0)
            exit()
        else:
            al_nl.sort(reverse=True)
            for i in range(k):
                a = al_nl[i]
                ans *= (a)
                ans %= MOD
            print(ans)
            exit()


    # print(next_p, next_n, comp_np, comp_pn)

    for i in range(k):
        if np_or_pn and i == last_n:
            continue
        if (not np_or_pn) and i == last_p:
            continue
        a, sig = al_abs[i]
        ans *= a
        ans %= MOD

    if np_or_pn:
        ans *= next_p_val
        ans %= MOD
    else:
        ans *= next_n_val
        ans %= MOD

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod=10**9+7
def mull(a,b):
	return ((a%mod)*(b%mod))%mod
def maxProductSubarrayOfSizeK(A, n, k): 
  
    # sorting given input array 
    A.sort() 
  
    # variable to store final product of  
    # all element of sub-sequence of size k 
    product = 1
  
    # CASE I 
    # If max element is 0 and 
    # k is odd then max product will be 0 
    if (A[n - 1] == 0 and (k & 1)): 
        return 0
  
    # CASE II 
    # If all elements are negative and 
    # k is odd then max product will be 
    # product of rightmost-subarray of size k 
    if (A[n - 1] <= 0 and (k & 1)) : 
        for i in range(n - 1, n - k + 1, -1): 
            product =mull(product,A[i]) 
        return product 
  
    # else 
    # i is current left pointer index 
    i = 0
  
    # j is current right pointer index 
    j = n - 1
  
    # CASE III 
    # if k is odd and rightmost element in 
    # sorted array is positive then it 
    # must come in subsequence 
    # Multiplying A[j] with product and 
    # correspondingly changing j 
    if (k & 1): 
        product =mull(product,A[j]) 
        j-= 1
        k-=1
  
    # CASE IV 
    # Now k is even. So, Now we deal with pairs 
    # Each time a pair is multiplied to product 
    # ie.. two elements are added to subsequence  
    # each time. Effectively k becomes half 
    # Hence, k >>= 1 means k /= 2 
    k >>= 1
  
    # Now finding k corresponding pairs to get 
    # maximum possible value of product 
    for itr in range(k) : 
  
        # product from left pointers 
        left_product = A[i] * A[i + 1] 
  
        # product from right pointers 
        right_product = A[j] * A[j - 1] 
  
        # Taking the max product from two  
        # choices. Correspondingly changing 
        # the pointer's position 
        if (left_product > right_product) : 
            product =mull(product,left_product) 
            i += 2
          
        else : 
            product=mull(product,right_product) 
            j -= 2
  
    # Finally return product 
    return product 
def check(a):
	for i in a:
		if i>=0:
			return False 
	return True 
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
mod=10**9+7
ans=1 
if check(a):
	if k%2==0:
		a.sort()
		for i in a[:k]:
			ans=mull(ans,i+mod)  
	else:
		a.sort(reverse=True)
		for i in a[:k]: 
			ans=mull(ans,i+mod) 
	print(ans%mod)
else:
	print(maxProductSubarrayOfSizeK(a,n,k)%mod)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
d1, d2 = sorted([q for q in a if q > 0], reverse=True), sorted([q for q in a if q < 0])
C = 1000000007
if len(d1)+len(d2) < k:
    print(0)
elif k == n:
    ans = 1
    for q in a:
        ans = ans*q % C
    print(ans)
elif len(d1) == 0 and k % 2 == 0:
    ans = 1
    for q in range(k):
        ans = ans*d2[q] % C
    print(ans)
elif len(d1) == 0 and len(d2) < n:
    print(0)
elif len(d1) == 0:
    ans = 1
    for q in range(len(d2)-1, len(d2)-k-1, -1):
        ans = ans*d2[q] % C
    print(ans)
elif len(d2) == 0:
    ans = 1
    for q in range(k):
        ans = ans*d1[q] % C
    print(ans)
else:
    ind = 0
    ans, now, w = 0, 0, min(k+1, len(d2)+1)
    for q in range(max(0, (k-len(d1)+1)//2*2), w, 2):
        if now == 0:
            """now = 1
            for q1 in range(q):
                now *= d2[q1]
            for q1 in range(k-q):
                now *= d1[q1]
            ans = now"""
            now, ind = 1, q
        else:
            if d1[k-q+1]*d1[k-q] <= d2[q-2]*d2[q-1]:
                ind = q
    ans = 1
    for q in range(ind):
        ans = ans*d2[q] % C
    for q in range(k-ind):
        ans = ans*d1[q] % C
    print(ans)

Submission status: Accepted

Solution code:
MOD = 1000000007

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

A.sort(key=lambda x: abs(x))

neg = []
pos = []
zero = 0

for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    elif A[i] < 0:
        neg.append(A[i])
    else:
        zero += 1

res = 1
sign = 1

for i in range(K):
    res *= A[~i]
    res %= MOD
    if A[~i] < 0:
        sign *= -1

    if A[~i] == 0:
        sign = 0

if sign == 1:
    print(res % MOD)

elif sign == 0:
    print(0)

else:
    flag1 = False
    tmp1 = -1
    minneg = None
    for i in range(K):
        if A[~i] < 0:
            minneg = ~i
    maxpos = None
    for i in range(N - K):
        if A[i] > 0:
            flag1 = True
            maxpos = i
    if maxpos is not None:
        tmp1 *= A[maxpos]
        tmp1 /= A[minneg]
    flag2 = False
    tmp2 = -1
    minpos = None
    for i in range(K):
        if A[~i] > 0:
            minpos = ~i
    maxneg = None
    for i in range(N - K):
        if A[i] < 0:
            maxneg = i
    if maxneg is not None and minpos is not None:
        flag2 = True
        tmp2 *= A[maxneg]
        tmp2 /= A[minpos]
    if flag1 and flag2:
        if A[maxpos] * A[minpos] > A[maxneg] * A[minneg]:
            print(res * A[maxpos] * pow(A[minneg], MOD - 2, MOD) % MOD)
        else:
            print(res * A[maxneg] * pow(A[minpos], MOD - 2, MOD) % MOD)
    elif flag1:
        print(res * A[maxpos] * pow(A[minneg], MOD - 2, MOD) % MOD)
    elif flag2:
        print(res * A[maxneg] * pow(A[minpos], MOD - 2, MOD) % MOD)
    else:
        if zero:
            print(0)
        else:
            res = 1
            for i in range(K):
                res *= A[i]
                res %= MOD
            print(res % MOD)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = [int(a) for a in input().split()]
Ap, Am, A0 = [],[],[]
for a in A:
    if a>0: Ap.append(a)
    elif a<0 : Am.append(a)
    else: A0.append(a)
mod = 10**9+7

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

if len(Ap)==0 and K%2==1:
    if len(A0)==0:
        A.sort()
        A.reverse()
        for i in range(K):
            ans = (ans*A[i])%mod
        print(ans)
        exit()
    else:
        print(0)
        exit()

Ap.sort()
Ap.reverse()
Am.sort()
if K%2==1:
    ans = Ap[0]
    Ap = Ap[1:]
    K -= 1

if K > len(Ap)+len(Am):
    print(0)
    exit()
if K == len(Ap)+len(Am) and len(Am)%2==1:
    print(0)
    exit()

Apair = [Ap[i]*Ap[i+1] for i in range(0,len(Ap)-1,2)]
for i in range(0,len(Am)-1,2):
    Apair.append(Am[i]*Am[i+1])
Apair.sort()
Apair.reverse()
for i in range(K//2):
    ans = (ans*Apair[i])%mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

n, k = map(int, input().split())
a = [int(item) for item in input().split()]
# Use all
if n == k:
    ans = 1
    for item in a:
        ans *= item
        ans %= MOD
    print(ans % MOD)
    exit()
plus = 0; minus = 0; zero = 0
p = []; m = []
for item in a:
    if item > 0:
        plus += 1
        p.append(item)
    elif item == 0:
        zero += 1
    else:
        minus += 1
        m.append(-item)
p.sort()
m.sort()
# plus only, minus only
if plus == 0:
    if k % 2 == 0:
        if minus >= k:
            ans = 1
            for i in range(k):
                ans *= m.pop()
                ans %= MOD
            print(ans)
            exit()
        else:
            print(0)
            exit()
    else:
        if zero:
            print(0)
            exit()
        ans = 1
        for item in m[:k]:
            ans *= -item
            ans %= MOD
        print(ans % MOD)
        exit()
if minus == 0:
    if plus >= k:
        ans = 1
        for i in range(k):
            ans *= p.pop()
            ans %= MOD
        print(ans % MOD)
        exit()
    else:
        print(0)
        exit()

# Can make it positive
if k <= (minus // 2) * 2 + plus:
    if k % 2 == 0:
        ans = 1
    else:
        ans = p.pop()
        k -= 1
    for i in range(k // 2):
        pval = 0; mval = 0
        if len(p) > 1:
            pval = p[-1] * p[-2]
        if len(m) > 1:
            mval = m[-1] * m[-2]
        if pval > mval:
            p.pop(); p.pop()
            ans *= pval
            ans %= MOD
        else:
            m.pop(); m.pop()
            ans *= mval
            ans %= MOD
    print(ans % MOD)
    exit()
# Cannot make positive
else:
    if zero > 0:
        print(0)
        exit()
    else:
        # Not occur
        exit()

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
minus=[]
plus=[]
cnt=Counter(a)
zerocnt=cnt[0]
minuscnt=0
pluscnt=0
for i in range(n):
    if a[i]<0:
        minuscnt+=1
        minus.append(a[i])
    elif a[i]>0:
        pluscnt+=1
        plus.append(a[i])


if n==k:
    ans=1
    for i in range(n):
        ans*=a[i]
        ans%=mod
    print(ans%mod)
    quit()

if minuscnt==n:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=a[i]
            ans%=mod
        print(ans)
    else:
        for i in range(k):
            ans*=a[-1-i]
            ans%=mod
        print(ans)
    quit()

if minuscnt%2==1:
    minuscnt-=1

# print(minus)
plus.reverse()
# plus.append(0)
# plus.append(0)
# print(plus)

ans=1
nokori=k
m,p=0,0
# minuscnt=max(minuscnt,1)

while nokori:
    # print(pluscnt,p,m,nokori)
    if m==minuscnt:
        if p!=pluscnt:
            ans*=plus[p]
            p+=1
            nokori-=1
        else:
            ans=0
            nokori=0
    elif p==pluscnt:
        if nokori==1:
            ans=0
            nokori-=1
        else:
            ans*=minus[m]*minus[m+1]
            m+=2
            nokori-=2
    elif p+1==pluscnt:
        if nokori%2==0:
            ans*=minus[m]*minus[m+1]
            m+=2
            nokori-=2
            # if nokori==1:
        else:
            ans*=plus[p]
            p+=1
            nokori-=1
            # elif plus[p]>minus[m]*minus[m+1]:
            #     ans*=plus[p]
            #     p+=1
            #     nokori-=1
            # else:
            #     ans*=minus[m]*minus[m+1]
            #     m+=2
            #     nokori-=2
    elif nokori==1:
        ans*=plus[p]
        nokori-=1
    elif plus[p]*plus[p+1]>minus[m]*minus[m+1]:
        # if nokori%2==0:
        #     ans*=plus[p]*plus[p+1]
        #     p+=2
        #     nokori-=2
        # else:
        ans*=plus[p]
        p+=1
        nokori-=1
    else:
        ans*=minus[m]*minus[m+1]
        m+=2
        nokori-=2
    ans%=mod
print(ans%mod)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
if N == K:
    ans = 1
    for a in A:
        ans *= a
        ans %= mod
    print(ans)
    exit()
A.sort()
B = []
flag = False
F = False
tmp = 0
num = -1
ans = 1
tmp_ = -1
for i, a in enumerate(A):
    if a < 0:
        if flag:
            B.append(tmp * a)
            flag = False
        else:
            tmp = a
            flag = True
    elif a == 0:
        num = i
        F = True
    else:
        tmp_ = tmp
        num = i
        break

if num == -1:
    if K % 2 == 1:
        for i, a in enumerate(A[::-1]):
            ans *= a
            ans %= mod
            if i == K-1:
                print(ans)
                exit()
    else:
        B.sort(reverse=True)
        K //= 2
        for i, b in enumerate(B):
            ans *= b
            ans %= mod
            if i == K-1:
                print(ans)
                exit()
A = A[num:]
A.sort(reverse=True)
if K % 2 == 1:
    ans = A[0]
    A = A[1:]
    K -= 1
ans %= mod
flag = False
for a in A:
    if flag:
        B.append(tmp * a)
        flag = False
    else:
        tmp = a
        flag = True
K //= 2
if len(B) < K:
    if F:
        print(0)
        exit()
    else:
        ans *= tmp_

B.sort(reverse=True)
for i, b in enumerate(B):
    if K == i:
        break
    ans *= b
    ans %= mod

print(ans % mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N, K = na()
a_array = na()

mod = 10 ** 9 + 7

aa = []

for a in a_array:
    if a >= 0:
        aa.append([a, 1])
    else:
        aa.append([abs(a), 0])

aa = sorted(aa, key=lambda x: - (x[0]+0.1*x[1]))

minus_count = 0

last_plus = [0, 0]
last_minus = [0, 0]

for i in range(K):
    v, f = aa[i]
    if f == 0:
        minus_count += 1
        last_minus = [v, i]
    else:
        last_plus = [v, i]

ans = 1

if minus_count % 2 == 0:
    for i in range(K):
        ans = (ans * aa[i][0]) % mod
    print(ans)
    exit()
else:
    if aa[K-1][0] == 0:
        print(0)
        exit()
    plus_ok = 0
    minus_ok = 0
    change_plus = [-1, 0]
    change_minus = [0, 0]
    for i in range(K, N):
        v, f = aa[i]
        if plus_ok == 0 and minus_count != 0 and f == 1:
            plus_ok = 1
            change_plus = [v, i]
        elif minus_ok == 0 and minus_count != K and f == 0:
            minus_ok = 1
            change_minus = [v, i]
        if minus_ok == 1 and plus_ok == 1:
            break

    if minus_ok == 0 and plus_ok == 0:
        for i in range(N-1, N-K-1, -1):
            ans = (ans * aa[i][0]) % mod
        if ans == 0:
            print(0)
        else:
            print(mod - ans)
        exit()

    D = last_plus[0] * change_plus[0] - last_minus[0] * change_minus[0]

    # print(change_plus, change_minus, last_plus, last_minus)

    ans = 1

    if D >= 0:
        for i in range(K):
            if i != last_minus[1]:
                ans = (ans * aa[i][0]) % mod
        ans = ans * aa[change_plus[1]][0] % mod
        print(ans)
    else:
        for i in range(K):
            if i != last_plus[1]:
                ans = (ans * aa[i][0]) % mod
        ans = ans * aa[change_minus[1]][0] % mod
        print(ans)

Submission status: Accepted

Solution code:
MOD = int(1e9+7)
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
flag = 0
for a in A:
    if a>0:
        flag = 1
        break
if N==K:
    ans = 1
    for i in range(K):
        ans = (ans*A[i]) % MOD
    print(ans)

#すべてマイナスか0
elif flag == 0 and K%2==1:
    A.sort(reverse = True)
    ans = 1
    for i in range(K):
        ans = (ans*A[i]) % MOD
    print(ans)
#それ以外
else:
    A = sorted(A, key=abs, reverse = True)
    last_pos = -1
    last_neg = -1
    count_neg = 0
    is_zero = 0
    ans = 1
    for i in range(K):
        ans = (ans*A[i]) % MOD
        if A[i]>0:
            last_pos = i
        elif A[i]<0:
            last_neg = i
            count_neg += 1
        else:
            is_zero = 1
            break
    if is_zero == 1:
        print(0)
    elif count_neg%2 == 0:
        print(ans)
    else:
        flag_pos = 0
        flag_neg = 0
        new_pos = -1
        new_neg = -1
        for i in range(K,N):
            if A[i]>0 and flag_pos==0:
                flag_pos = 1
                new_pos = i
            elif A[i]<0 and flag_neg==0:
                flag_neg = 1
                new_neg = i
            if flag_pos == 1 and flag_neg == 1:
                break

        if last_pos > -1 and last_neg > -1 and new_pos > -1 and new_neg > -1:
            f1 = A[new_pos] * A[last_pos]
            f2 = A[new_neg] * A[last_neg]
            if f1>f2:
                ans = 1
                for i in range(K):
                    if i != last_neg:
                        ans = (ans*A[i]) % MOD
                ans = (ans*A[new_pos]) % MOD
            else:
                ans = 1
                for i in range(K):
                    if i != last_pos:
                        ans = (ans*A[i]) % MOD
                ans = (ans*A[new_neg]) % MOD
        elif last_pos > -1 and new_neg > -1:
            ans = 1
            for i in range(K):
                if i != last_pos:
                    ans = (ans*A[i]) % MOD
            ans = (ans*A[new_neg]) % MOD
        elif last_neg > -1 and new_pos > -1:
            ans = 1
            for i in range(K):
                if i != last_neg:
                    ans = (ans*A[i]) % MOD
            ans = (ans*A[new_pos]) % MOD
        else:
            ans = 0
            
        print(ans)

Submission status: Accepted

Solution code:
def main():
    MOD = 10 ** 9 + 7

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

    A.sort(key=abs, reverse=True)

    ans = 1
    sgn = 1

    lm, lp = None, None
    for i, x in enumerate(A[:K]):
        if x < 0:
            sgn = -sgn
            lm = x
        else:
            lp = x
        ans = ans * x % MOD

    if K == N or sgn == 1 or ans == 0:
        print(ans)
        return

    fm, fp, z = None, None, False
    for i, x in enumerate(A[K:]):
        if x < 0:
            if fm is None:
                fm = x
        elif x == 0:
            z = True
        else:
            if fp is None:
                fp = x

    # 交換できる場合
    if lp is None:
        # マイナスが奇数個のみ
        if fp is not None:
            ans = ((ans * pow(lm, MOD - 2, MOD)) % MOD) * fp % MOD
            print(ans)
            return

        if z:
            print(0)
            return

        A.sort(key=abs)
        ans = 1
        for i, x in enumerate(A[:K]):
            ans = ans * x % MOD
        print(ans)
        return

    else:
        if fp is not None and fm is not None:
            if fm * lm >= fp * lp:
                ans = ((ans * pow(lp, MOD - 2, MOD)) % MOD) * fm % MOD
                print(ans % MOD)
                return
            else:
                ans = ((ans * pow(lm, MOD - 2, MOD)) % MOD) * fp % MOD
                print(ans % MOD)
                return

        if fp is not None:
            ans = ((ans * pow(lm, MOD - 2, MOD)) % MOD) * fp % MOD
            print(ans)
            return

        if fm is not None:
            ans = ((ans * pow(lp, MOD - 2, MOD)) % MOD) * fm % MOD
            print(ans)
            return


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Accepted

Solution code:
n, k = map(int, input().split())

mod = 10**9+7
def _ans(_a):
    ret = _a[0]
    for _aa in _a[1:]:
        ret = (ret*_aa)%mod
    return ret


a = list(map(int, input().split()))
# マイナスでも全部かけるしかない
if len(a) == k:
    print(_ans(a))
    exit(0)

ap = [aa for aa in a if aa > 0]
an = [aa for aa in a if aa < 0]
apl, anl = len(ap), len(an)

# 0が入る
if apl + anl < k:
    print(0)
    exit(0)

ap.sort(reverse=True)
an.sort()

# プラスがない
if apl == 0:
    if k % 2 == 1:
        if apl + anl < n:
            print(0)
            exit(0)
        an = an[::-1]
    print(_ans(an[:k]))
    exit(0)

# マイナスは2の倍数個のみいれる
ans = 1
api, ani = 0, 0
if k % 2 == 1:
    ans = ap[0]
    api += 1
    k -= 1

while k > 0:
    if apl - api < 2:
        while k > 0:
            ans = (ans * an[ani] * an[ani+1]) % mod
            ani += 2
            k -= 2
        break
    if anl - ani < 2:
        while k > 0:
            ans = (ans * ap[api] * ap[api+1]) % mod
            api += 2
            k -= 2
        break

    app = ap[api] * ap[api+1]
    ann = an[ani] * an[ani+1]
    if app > ann:
        ans = (ans * app) % mod
        api += 2
    else:
        ans = (ans * ann) % mod
        ani += 2
    k -= 2

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
MOD = 10**9 + 7
A = list(map(int,input().split()))
Ap = [a for a in A if a >= 0]
An = [-a for a in A if a < 0]
Ap.sort()
Ap.reverse()
An.sort()
An.reverse()

if len(Ap) == 0 and K % 2 == 1:
	ans = 1
	An.reverse()
	for i in range(K):
		ans = (ans * -An[i]) % MOD
	print(ans)
	exit()

B = [(a, 1) if a >= 0 else (-a, -1) for a in A]
B.sort()
B.reverse()
M = [0 if B[0][1] > 0 else 1]
for i in range(1, N):
	M.append(M[i-1] + (0 if B[i][1] > 0 else 1))

i = K-1
if M[i] % 2 == 0 or K == N:
	ans = 1
	v = 1 if (M[i] % 2 == 0) else -1
	for j in range(K):
		ans = (ans * B[j][0]) % MOD
	print((ans * v) % MOD)
else:
	n = M[i]
	p = K - n
	if len(An) == n or p == 0:
		n -= 1
		p += 1
	elif len(Ap) == p:
		n += 1
		p -= 1
	elif Ap[p-1] * Ap[p] >= An[n-1] * An[n]:
		n -= 1
		p += 1
	else:
		n += 1
		p -= 1
	ans = 1
	for i in range(p):
		ans = (ans * Ap[i]) % MOD
	for i in range(n):
		ans = (ans * An[i]) % MOD
	print(ans)

Submission status: Accepted

Solution code:
import itertools
import sys

sys.setrecursionlimit(1000000)

import bisect
import math
import collections
import heapq

MOD = 10 ** 9 + 7


def solve(N, K, As):
    originalK = K
    # print(N, ",", K, ",", As)
    minus = [a for a in As if a < 0]
    minus.sort(reverse=True)
    zero = [a for a in As if a == 0]
    plus = [a for a in As if a > 0]
    plus.sort()

    if len(zero) and len(zero) > N - K:
        return 0

    ans = 1
    while K >= 2 and (len(plus) >= 2 or len(minus) >= 2):
        p1 = -1
        p2 = -1
        m = -1
        if len(plus) >= 1:
            p1 = plus[-1]
        if len(plus) >= 2:
            p2 = plus[-1] * plus[-2]
        if len(minus) >= 2:
            m = minus[-1] * minus[-2]

        if m >= p2:
            ans *= (m % MOD)
            ans %= MOD
            minus.pop()
            minus.pop()
            K -= 2
        else:
            ans *= (p1 % MOD)
            ans %= MOD
            plus.pop()
            K -= 1

    while K > 0:
        if len(plus):
            ans *= plus.pop()
            ans %= MOD
        else:
            ans *= minus.pop(0)
        K -= 1
    if ans < 0 and zero:
        return 0
    if ans < 0:
        minus = [a for a in As if a < 0]
        plus = [a for a in As if a > 0]
        minus.sort()
        plus.sort(reverse=True)
        ans = 1
        for _ in range(originalK):
            if plus and minus:
                if abs(plus[-1]) < abs(minus[-1]):
                    ans *= plus.pop()
                else:
                    ans *= minus.pop()
            elif plus:
                ans *= plus.pop()
            else:
                ans *= minus.pop()
            ans %= MOD
        ans %= MOD

    return ans


def slowsolve(N, K, As):
    ans = -10 ** 9
    for p in itertools.combinations(As, K):
        k = 1
        for i in p:
            k *= i
        ans = max(ans, k)
    return ans


# #
# assert (solve(1, 1, [0]) == 0)
# assert (solve(3, 2, [0, 1, 0]) == 0)
# assert (solve(3, 2, [0, 1, 0]) == 0)
# assert (solve(5, 2, [1, 2, -1, -3, -4]) == 12)
# assert (solve(1, 1, [-4]) == -4 % MOD)
# assert (solve(2, 1, [-4, 0]) == 0)
# assert (solve(2, 1, [-1, -4]) == -1  % MOD)
# assert (solve(10, 5, [-2, 1, -3, 2, 0, -1, 3, -2, -2, -3]) == 108)
# assert (solve(10, 5, [-1, 2, 2, 0, 2, -2, -1, 0, -3, -1]) == 48)
# assert (solve(10, 5, [0, 0, -3, 3, 3, 2, 2, 0, 3, -1]) == 108)
# assert (solve(10, 5, [-1, -2, -1, -3, -2, -3, -2, -3, -1, -2]) == -4 % MOD)

# (solve(5 , 5 , [-3, -5, -5, -4, -4] == (-3 * -5 * -5 * -4 * -4) % MOD))

#
# print(slowsolve(10 , 5 , [0, 0, -3, 3, 3, 2, 2, 0, 3, -1]))
# print(solve(10 , 5 , [0, 0, -3, 3, 3, 2, 2, 0, 3, -1]))
#
# exit()


def rand(N, a, b):
    import random
    return [random.randint(a, b) for _ in range(N)]


#
#
# for _ in range(100000):
#     N = 6
#     A = 1
#     B = 10
#     K = 3
#     As = rand(N, A, B)
#     slow = slowsolve(N, K, As)
#     ans = solve(N, K, As)
#     slow %= MOD
#     if slow != ans:
#         print(N, ",", K, ",", As)
#         print(slow)
#         print(ans)
#         assert (slow == ans)
#
# print("OK")

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))

Submission status: Accepted

Solution code:
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
d=deque(A)
import time
l=[]
if K%2==0 or (K%2==1 and A[0]>=0):
  for i in range(K//2):
    if d[0]*d[1]>d[-1]*d[-2] and (i==K//2-1 or (len(d)>2 and  d[2]>0)):
      l.append(d.popleft())
      l.append(d.popleft())
    else:
      l.append(d.pop())
      l.append(d.pop())
  if K%2==1:
    l.append(d[0])
else:
  for i in range(K):
    l.append(d.popleft())
      
ans=1
for i in l:
  ans*=i
  ans%=10**9+7
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7

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

A.sort(reverse=True)

ans = 1
left = 0
right = len(A)-1

# 全部負のとき
if A[0] < 0 and K % 2 == 1:
    for i in range(K):
        ans = (ans * A[i]) % mod
elif K % 2 == 0:
    while K > 0:
        r = A[right] * A[right-1]
        l = A[left] * A[left + 1]
        if l > r:
            ans = (ans * l) % mod
            left += 2
        else:
            ans = (ans * r) % mod
            right -= 2
        K -= 2
else:
    p = A.pop(0)
    K -= 1
    right -= 1
    while K > 0:
        r = A[right] * A[right-1]
        l = A[left] * A[left + 1]
        if l > r:
            ans = (ans * l) % mod
            left += 2
        else:
            ans = (ans * r) % mod
            right -= 2
        K -= 2
    ans = (ans * p) % mod
while ans < 0:
    ans = ans + mod

print(ans)