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: Runtime Error

Solution code:
import heapq

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

MOD = 10**9+7

A_pos = []
A_neg = []
for a in A:
    if a >= 0:
        A_pos.append(-a)
    else:
        A_neg.append(a)

# 積が負にしかならない
if len(A_pos) == 0 and k%2==1:
    A_neg.sort(reverse=True)
    ans = 1
    for a in A_neg[:k]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

A_pos2 = [-A_pos[i*2]*A_neg[i*2+1] for i in range(len(A_pos)//2)]
A_neg2 = [-A_neg[i*2]*A_neg[i*2+1] for i in range(len(A_neg)//2)]

heapq.heapify(A_pos2)  # 絶対値が大きいものが先頭
heapq.heapify(A_neg2)  # 絶対値が大きいものが先頭

if k%2==0:
    ans = 1
    for i in range(k//2):
        if not A_pos2:
            ans *= -heapq.heappop(A_neg2)
            ans %= MOD
        elif not A_neg2:
            ans *= -heapq.heappop(A_pos2)
            ans %= MOD
        else:
            if A_pos[0] <= A_neg[0]:
                ans *= -heapq.heappop(A_pos2)
                ans %= MOD
            else:
                ans *= -heapq.heappop(A_neg2)
                ans %= MOD
    print(ans)
    exit()

if False:
    ans = 1
    cnt = 0
    for i in range(k // 2 - 1):
        if not A_pos2:
            ans *= -heapq.heappop(A_neg2)
            ans %= MOD
        elif not A_neg2:
            ans *= -heapq.heappop(A_pos2)
            ans %= MOD
            cnt += 1
        else:
            if A_pos[0] <= A_neg[0]:
                ans *= -heapq.heappop(A_pos2)
                ans %= MOD
                cnt += 1
            else:
                ans *= -heapq.heappop(A_neg2)
                ans %= MOD
    # if cnt*2+1 == len(A_pos):

else:
    ans = 1
    cnt = 0
    for i in range(k // 2):
        if not A_pos2:
            ans *= -heapq.heappop(A_neg2)
            ans %= MOD
        elif not A_neg2:
            ans *= -heapq.heappop(A_pos2)
            ans %= MOD
            cnt += 1
        else:
            if A_pos[0] <= A_neg[0]:
                ans *= -heapq.heappop(A_pos2)
                ans %= MOD
                cnt += 1
            else:
                ans *= -heapq.heappop(A_neg2)
                ans %= MOD
    A_pos.sort(reverse=True)
    ans *= A_pos[cnt*2]
    ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A_minus = []
A_plus = []
for i in A:
    if i < 0:
        A_minus.append(i)
    elif i >= 0:
        A_plus.append(i)

len_plus = len(A_plus)
len_minus = len(A_minus)
plus = True
if (K > len_plus):
    if K % 2 == 1:
        if len_plus > 0:
                len_plus -= 1
                K -= 1
    K -= (len_plus // 2) * 2
    if K < len_minus:
        plus = False
ans = 1
if plus:
    A_plus.sort(reverse=True)
    A_minus.sort()
    for i in range(K):
        if ans < 0:
            ans *= A_minus.pop()
            continue
        if i < K - 1:
            if (len(A_plus) > 0) & (len(A_minus) > 0):
                if A_plus[0] < abs(A_minus[0]):
                    ans *= A_minus.pop()
                    continue
            if len(A_plus) > 0:
                ans *= A_plus.pop()
else:
    A_plus.sort()
    A_minus.sort(reverse=True)
    for i in range(K):
        if ans < 0:
            ans *= A_minus.pop()
            continue
        if i < K - 1:
            if (len(A_plus) > 0) & (len(A_minus) > 0):
                if A_plus[0] < abs(A_minus[0]):
                    ans *= A_minus.pop()
                    continue
            if len(A_plus) > 0:
                ans *= A_plus.pop()
print(ans % mod)

Submission status: Runtime Error

Solution code:
from collections import deque
n,k=map(int,input().split())
a=list(map(int, input().split()))
a.sort(reverse=True)
if a[-1]>=1:
    print(sum(a[:k+1]))
    exit()
if a[k]<0 and 
a=deque(a)
flag=True
ans1=a.popleft()
ans2=ans1
if k==1:
    print(ans)
    exit()
    i=0
while i<k:
    tmp1=a.popleft()
    tmp2=a.pop()
    if tmp1==0:
        tmp1=a.popleft()
    if tmp2==0:
        tmp2=a.pop()
    ans2=ans1*tmp1
    ans1=ans1*max(abs(tmp1),abs(tmp2))
    if tmp2<0 and flag:
        flag=False
    elif tmp2<0 and not flag:
        flag=True
    i+=1
if flag:
    print(ans1%(10**9+7))
else:
    print(ans2%(10**9+7))

Submission status: Runtime Error

Solution code:
from bisect import bisect_right, bisect_left


def mod_pow(a, n):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


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

l_1 = sorted(a, key=lambda x: abs(x), reverse=True)
l_2 = sorted(a)

mod = 10 ** 9 + 7
res = 1

if n == k:
    for v in a:
        res = res * v % mod

elif l_2[-1] <= 0:
    if k % 2 == 0:
        for v in l_2[:k]:
            res = res * v % mod
    else:
        for v in l_2[n-1:n-k-1:-1]:
            res = res * v % mod

else:
    for v in l_1[:k]:
        res = res * abs(v) % mod
    
    cnt = 0
    for v in l_1[:k]:
        if v < 0:
            cnt += 1

    if cnt % 2 == 1:
        if l_1[k-1] > 0:
            pos_1 = bisect_right(l_2, -l_1[k-1]) - 1
            pos_2 = bisect_left(l_2, l_1[k-1])
        else:
            pos_1 = bisect_right(l_2, l_1[k-1]) - 1
            pos_2 = bisect_left(l_2, -l_1[k-1])
        
        if l_2[pos_1+1] >= 0:
            res = (res * mod_pow(-l_2[pos_1], mod-2) % mod) * l_2[pos_2-1] % mod
        elif l_2[pos_2-1] <= 0:
            res = (res * mod_pow(l_2[pos_2], mod-2) % mod) * l_2[pos_1+1] % mod
        else:
            if l_2[pos_1] * l_2[pos_1+1] > l_2[pos_2] * l_2[pos_2-1]:
                res = (res * mod_pow(l_2[pos_2], mod-2) % mod) * l_2[pos_1+1] % mod
            else:
                res = (res * mod_pow(-l_2[pos_1], mod-2) % mod) * l_2[pos_2-1] % mod

print(res)

Submission status: Runtime Error

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

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

ans = 1
mod = 10 ** 9 + 7

minus_cnt = 0
for a in A:
    if a < 0:
        minus_cnt += 1

if K == 1:
    print(max(A))
elif K == N:
    for a in A:
        ans *= abs(a)
        ans %= mod
    if minus_cnt % 2 == 1:
        ans *= (-1)
    print(ans % mod)
else:
    minus_cnt = 0
    new_A = []
    select_ls = []

    for a in A:
        new_A.append([abs(a), 0 if a >= 0 else -1])
    new_A.sort(reverse=True)

    for i in range(K):
        select_ls.append(new_A[i])
        minus_cnt += new_A[i][1]

    if minus_cnt % 2 == 0:
        for s in select_ls:
            ans *= s[0]
            ans %= mod
        print(ans)
    else:
        ok = False
        for i in range(K, N):
            if new_A[i][1] == 0:
                ok = True
                ans *= new_A[i][0]
                select_ls.sort()
                skip = False
                for j in range(len(select_ls)):
                    if select_ls[i][1] == -1:
                        if skip:
                            ans *= select_ls[j][0]
                        else:
                            skip = True
                            continue
                    else:
                        ans *= select_ls[j][0]
                    ans %= mod
        if not ok:
            if 0 in A:
                print(0)
                exit()
            new_A.sort()
            for i in range(K):
                ans *= new_A[i][0]
                ans %= mod
            ans *= (-1)
        print(ans % mod)

Submission status: Runtime Error

Solution code:
n , k = map(int, input().split())
a = list(map(int, input().split()))
neg = []
pos = []
mod = 10**9+7
for i in range(n):
    if a[i] > 0:
        pos.append(a[i])
    else:
        neg.append(a[i])
neg.sort()
pos.sort(reverse = True)
min_num = -1
good_num = -1
if k % 2 == 1 and len(pos) == 0:
    ans = 1
    neg.sort(reverse = True)
    for i in range(k):
        ans *= neg[i]
        ans %= mod
    print(ans)
else:
    #最大化するとき
    for i in range(0,k+1,2):
        #i個だけnegから取る。
        if i > len(neg) or k - i > len(pos):
            continue
        m = 0
        if i - 1 >= 0:
            m = abs(neg[i-1])
        if k-i-1 >= 0:
            m = min(m, pos[k-i-1])
        if m > min_num:
            min_num = m
            good_num = i
    ans = 1
    for i in range(good_num):
        ans *= neg[i]
        ans %= mod
    for i in range(k - good_num):
        ans *= pos[i]
        ans %= mod
    print(ans % mod)

Submission status: Runtime Error

Solution code:
mod=1000000007
def maxp(arr, n, k) : 
    
    # Initialize the MaxProduct to 1,  
    # as all elements in the array  
    # are positive 
    MaxProduct = 1
    for i in range(0, k) : 
        MaxProduct = MaxProduct * arr[i]
          
    prev_product = MaxProduct 
   
    # Consider every product beginning 
    # with arr[i] where i varies from 
    # 1 to n-k-1 
    for i in range(1, n - k + 1) : 
        curr_product = (prev_product // arr[i-1]) * arr[i+k-1] 
        MaxProduct = max(MaxProduct, curr_product) 
        prev_product = curr_product 
      
      
    # Return the maximum product found 
    return MaxProduct
  
# Driver Code 
if __name__ == "__main__": 
      
    n, k = [int(x) for x in input().split()]
    a = list(map(int,input().strip().split()))[:n]
    print(maxp(a,n,k)%mod)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 1000000007

zeros = []
pluss = []
minuss = []

for i in range(N):
    if A[i]>0:
        pluss.append(A[i])
    elif A[i]==0:
        zeros.append(A[i])
    else:
        minuss.append(A[i])

pluss = sorted(pluss, reverse = True)
minuss = sorted(minuss)


if len(pluss) + (min(len(minuss), K)//2)*2 >= K:
    answer_type = 1
elif len(zeros) > 0:
    answer_type = 2
else:
    answer_type = 3

rest = K
if answer_type == 1:
    plus_now = 0
    minus_now = 0
    minus_counter = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = -1000000000000
        
        if minus_now < len(minuss):
            minus_target = minuss[minus_now]
        else:
            minus_target = 1000000000000
        
        if plus_target >= -minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
            minus_counter += 1
    
    if minus_counter%2 == 1:
        if plus_now >= len(pluss):
            answer = answer * pow(minuss[minus_now-1],mod-2,mod)
            answer = answer * pluss[plus_now]
        elif minus_now >= len(minuss):
            answer = answer * pow(pluss[plus_now-1],mod-2,mod)
            answer = answer * minuss[minus_now]
        elif pluss[plus_now]/(-1*minuss[minus_now-1]) > -1*minuss[minus_now]/(-1*pluss[plus_now-1]):
            answer = answer * pow(minuss[minus_now-1],mod-2,mod)
            answer = answer * pluss[plus_now]

elif answer_type == 2:
    answer = 0
elif answer_type == 3:
    minuss = sorted(minuss, reverse = True)
    pluss = sorted(pluss, reverse = True)
    plus_now = 0
    minus_now = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = 10000000000000
        
        if minus_now < len(minuss):
            minus_target = minuss[minus_now]
        else:
            minus_target = -1000000000000  
        
        if plus_target <= -minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
print(answer%mod)

Submission status: Runtime Error

Solution code:
# coding: utf-8


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = sorted(A, key=lambda x: abs(x), reverse=True)
    Bp = [x for x in B if x > 0]
    Bm = [x for x in B if x < 0]
    Bpm = [x for x in B if x != 0]
    Bmm = []
    for i in range(0, len(Bm)-1, 2):
        Bmm.append(Bm[i]*Bm[i+1])

    q = 10**9 + 7

    n_plus, n_zero, n_minus = 0, 0, 0
    for a in A:
        if a > 0:
            n_plus += 1
        elif a < 0:
            n_minus += 1
        else:
            n_zero += 1

    if K > n_plus + n_minus:
        return 0

    # ans != 0
    rest = K
    ans = 1
    if K > n_plus and ((n_plus == 0 and n_minus % 2 == 1) or (K == n_plus+n_minus and (K-n_plus) % 2 == 1)):
        # ans < 0
        for i in range(K):
            ans = (ans * Bpm[len(Bpm)-1-i]) % q
        return ans
    else:
        # ans > 0
        i, j = 0, 0
        while rest > 0:
            if rest >= 2 and j < len(Bmm):
                if i+1 < len(Bp):
                    if Bmm[j] >= Bp[i] * Bp[i+1]:
                        ans = (ans * (Bmm[j] % q)) % q
                        j += 1
                        rest -= 2
                    else:
                        ans = (ans * Bp[i]) % q
                        i += 1
                        rest -= 1
                elif i < len(Bp):
                    if Bmm[j] >= Bp[i]:
                        ans = (ans * (Bmm[j] % q)) % q
                        j += 1
                        rest -= 2
                    else:
                        ans = (ans * Bp[i]) % q
                        i += 1
                        rest -= 1
                else:
                    ans = (ans * (Bmm[j] % q)) % q
                    j += 1
                    rest -= 2
            else:
                ans = (ans * Bp[i]) % q
                i += 1
                rest -= 1
        return ans

        # i = 0
        # ip = 0
        # im = 0
        # while rest > 0:
        #     if B[i] > 0:
        #         ans = (ans * B[i]) % q
        #         i += 1
        #         ip += 1
        #         rest -= 1
        #     else:  # B[i] < 0
        #         if rest == 1:
        #             i += 1
        #         elif B[i+1] < 0:  # rest >= 2
        #             ans = (ans * (B[i]*B[i+1] % q)) % q
        #             i += 2
        #             im += 2
        #             rest -= 2
        #         else:  # rest >= 2 and B[i+1] > 0
        #             if Bp[ip] * Bp[ip+1] > Bm[im] * Bm[im+1]:
        #                 ans = (ans * (Bp[ip]*Bp[ip+1] % q)) % q


print(main())

Submission status: Runtime Error

Solution code:

def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    A = sorted(A)

    mod = 10**9+7
    fst = 0
    lst = N-1

    if K==1:
        print(A[lst])
        return

    elif A[N-1]<=0:
        ans =A[N-1]
        lst = N-2
        for i in range(K-1):
            ans *= A[lst]
            # print(ans,A[lst])
            lst -= 1
            ans %= mod
        print(ans)
        # print( (((-1)%mod)*((-2)%mod)*((-3)%mod))%mod)
        return

    for i in range(K):
        pass



    if A[lst]*A[lst-1] >= A[fst]*A[fst+1]:
        ans = A[lst]*A[lst-1]
        lst -= 2
    else:
        ans = A[fst]*A[fst+1]
        fst += 2

    mm = 1
    cnt = 2
    while(cnt<K):
        if A[lst]*A[lst-1] <= A[fst]*A[fst+1] and K-cnt>=2:
            ans *= A[fst]*A[fst+1]
            fst += 2
            cnt += 2
            # print(A[fst], A[fst+1])
        
        else:
            ans *= A[lst]
            lst -= 1
            cnt += 1
            mm *= A[lst]//abs(A[lst])
            # print(A[lst])
        # print(fst,lst)
        ans %= mod
    # print(mm)
    if mm <= 0:
        for i in range(N):
            if A[i]>=0:
                aa = A[i]
                break
                # print(aa)

        ans = 1
        for i in range(fst+1):
            ans *= A[i]
            ans %= mod
            # print(A[i])
        for i in range(lst+1,N):
            if A[i]==aa:
                aa = 10**20
                continue
            ans *= A[i]
            ans %= mod
            # print(A[i])
        print(ans)
        return
    else:
        print(ans)
        return
        


main()

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
Alist = list(map(int, input().split()))

plus = []
minus = []

for a in Alist:
    if a >= 0:
        plus.append(a)
    else:
        minus.append(a)

mflg = False

if K%2!=0:
    tmp1 = K-1
else:
    tmp1 = K

if len(minus)%2!=0:
    tmp2 = len(minus)-1
else:
    tmp2 = len(minus)

tmp = min(tmp1, tmp2)
if K - tmp > len(plus):
    mflg = True


if mflg:
    minus = [-m for m in minus]
    nums = minus + plus
    nums.sort()
    ans = 1
    for k in range(K):
        ans = ans * nums[k]
        ans %= (1000000007)
    
    ans = (-ans % 1000000007)
    print(ans)

else:
    plus.sort()
    minus.sort()
    plus = plus[::-1]
    minus = [-m for m in minus]

    for k in range(0, len(minus)+1, 2):
        if K - k > len(plus):
            continue
        km = k
        kp = K - k
        break

    m = plus[:km]
    p = plus[:kp]
    ans = 1
    for i in p+m:
        ans *= i
    
    for k in range(km+2, len(minus)+1, 2):
        kp = K - k
        if kp < 0:
            break
        if plus[kp] == 0:
            break
        tmp = tmp * minus[k-2] * minus[k-1] / plus[kp+1] / plus[kp+2]
        ans = max(ans, tmp)
    
    ans %= 1000000007
    print(ans)

Submission status: Runtime Error

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

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
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()
     
cnt = 1

def powmod(x, n):
    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = ans*x
            ans %= mod
        x = x*x
        x %= mod
        n = n >> 1
    return ans % mod

def gyaku(n):
    return powmod(n, mod - 2)

def smp_solve(arr, n):
    ans = 1
    for i in range(n):
        ans *= arr[i]
        ans %= mod
    return ans

def compare_two_give_max(pos, neg, pos_pair, neg_pair, K):
    i = 0
    j = 0
    ans = 1
    neg_last = True
    while i < len(pos_pair) and j < len(neg_pair) and K > 0:
        if pos_pair[i] > neg_pair[j]:
            ans *= pos_pair[i]
            i += 1
            neg_last = False
        else:
            ans *= neg_pair[j]
            j += 1
            neg_last = True
        K -= 2
        ans %= mod

    while K > 0 and i == len(pos_pair) and j < len(neg_pair):
        # negがなくなるまでタス
        ans *= neg_pair[j]
        j += 1
        K -= 2
        ans %= mod
        neg_last = True

    while K > 0 and i < len(pos_pair) and j == len(neg_pair):
        # posがなくなるまでタス
        ans *= pos_pair[i]
        i += 1
        K -= 2
        ans %= mod
        neg_last = False

    if K == -1:
        if neg_last:
            # 足しすぎた分をわる
            ans *= gyaku(neg_pair[j-1])
            ans *= pos[2*i]
            # TODO: iがoutOfArray
            ans %= mod
        else:
            ans *= gyaku(pos_pair[2*i-1])
            ans %= mod
    return ans, K

def main():
    global cnt
    N, K = LI()
    A = LI()
    if N == K:
        ans = smp_solve(A, N)
        print(ans)
        return

    neg = []
    pos = []
    zero_exist = False
    for a in A:
        if a < 0:
            neg.append(a)
        elif a > 0:
            pos.append(a)
        else:
            zero_exist = True
    neg = sorted(neg) # -12, -3
    pos = sorted(pos)[::-1] # 4, 3, 2, 1
    if len(pos) == 0:
        ans = 1
        neg = neg[::-1] # -3, -12
        for n in neg[:K]:
            ans *= n
            ans %= mod
        if zero_exist:
            ans *= 0
        print(ans % mod)
        return

    if len(neg) == 0:
        ans = 1
        for p in pos[:K]:
            ans *= p
            ans %= mod
        print(ans % mod)
        return


    neg_paired = []
    pos_paired = []

    i = 0
    neg_amari = -inf
    while i+1 < len(neg):
        neg_paired.append(neg[i] * neg[i+1])
        i += 2
    if len(neg) % 2 == 1:
        neg_amari = neg[-1]

    i = 0
    pos_amari = -inf
    while i+1 < len(pos):
        pos_paired.append(pos[i] * pos[i+1])
        i += 2
    if len(pos) % 2 == 1:
        pos_amari = pos[-1]

    # print('pos: ', pos)
    # print('neg: ', neg)
    # print('pos_pair: ', pos_paired)
    # print('neg_pair: ', neg_paired)
    if len(pos_paired) == 0 and len(neg_paired) == 0:
        if K == 1:
            cnt *= pos_amari
        elif K == 2:
            if zero_exist:
                cnt = 0
            else:
                cnt = pos_amari * neg_amari


    else:
        res, k = compare_two_give_max(pos, neg, pos_paired, neg_paired, K)
        # print('res: ', res)
        # print('k: ', k)
        cnt *= res
        if k > 1:
            if pos_amari != -inf:
                cnt *= pos_amari
            elif neg_amari != -inf:
                if zero_exist:
                    cnt *= 0
                else:
                    cnt *= neg_amari
    print(cnt % mod)
    return

main()

Submission status: Runtime Error

Solution code:
import numpy as np
n,k = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True,key=lambda x: abs(x))

def main(n,k,a):
    a = np.array(a)
    if (a<0).all() and k%2==1 : return np.prod(a[-1*k:])
    prod = np.prod(a[:k-2])

    if prod<0:
        p_flag,n_flag = False,False
        p_done,n_done = False,False
        p,n = 0,0
        for i in range(k-2,len(a)):
            if a[i] > 0 :
                if not p_flag:
                    p = a[i]
                    p_flag =True
                if n_flag and not n_done:
                    n *= a[i]
                    n_done = True
            if a[i] < 0:
                if not n_flag:
                    n = a[i]
                    n_flag =True
                if p_flag and not p_done:
                    p *= a[i]
                    p_done = True
    if prod>0:
        p_flag,n_flag = False,False
        p_done,n_done = False,False
        p,n = 0,0
        for i in range(k-2,len(a)):
            if a[i] > 0 :
                if not p_flag:
                    p = a[i]
                    p_flag =True
                else:
                    p *= a[i]
                    p_done = True
            if a[i] < 0:
                if not n_flag:
                    n = a[i]
                    n_flag =True
                else:
                    n *= a[i]
                    n_done = True
    return max(prod*n,prod*p)
main(n,k,a)%1000000007

Submission status: Runtime Error

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

if all(a<0 for a in A):
    A.sort()
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()

arr = []
for a in A:
    if a < 0:
        arr.append((-a,1))
    else:
        arr.append((a,0))

arr.sort()
psz = []
ng = []
ans = 1
for _ in range(K):
    a,s = arr.pop()
    if s:
        ng.append(a)
    else:
        psz.append(a)

if len(ng)%2:
    ng.pop()
    while A:
        a,s = arr.pop()
        if s==0:
            ans = a
            break
    else:
        assert False

for a in ng:
    ans *= a
    ans %= MOD
for a in psz:
    ans *= a
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
#create date: 2020-07-05 21:39

import sys
stdin = sys.stdin
mod = 10**9 + 7

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

def calc(pos, neg):
    res = 1
    if pos:
        for p in pos:
            res *= p
            res %= mod
    if neg:
        for n in neg:
            res *= (-n)
            res %= mod
    return res

def main():
    n, k = na()
    a = na()
    po = list(); ne = list()
    for ai in a:
        if ai > 0:
            po.append(ai)
        if ai < 0:
            ne.append(ai)
    po.sort(reverse=True)
    ne.sort()
    if len(po) + len(ne) < k:
        print(0)
        quit()
    if len(po) == 0 and k % 2 == 1:
        if 0 in a:
            print(0)
            quit()
        else:
            ans = -calc(None, ne[(n-k):]) % mod
            print(ans)
            quit()
    if len(ne) == 0:
        ans = calc(po[:k], None)
        print(ans)
        quit()
    else:
        poi = len(po)
        nei = k - poi
        if nei % 2 == 1:
            poi -= 1
            nei += 1
        poi_pre = poi; nei_pre = nei
        while poi >= 0:
            poi -= 2
            nei += 2
            #print(poi, nei)
            if poi < 0 or nei > len(ne):
                break
            positive = po[poi] * po[poi+1]
            negative = ne[nei-2] * ne[nei-1]
            if positive < negative:
                poi_pre = poi; nei_pre = nei
            else:
                ans = calc(po[:poi_pre], ne[(n-nei_pre):])
                print(ans)
                quit()
        ans = calc(po[:poi_pre], ne[(n-nei_pre):])
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

mod = 10**9 + 7
p = []
m = []
z_cnt = 0

for i in range(N):
    if A[i] < 0:
        m.append(-A[i])
    elif A[i] > 0:
        p.append(A[i])
    else:
        z_cnt += 1

p.sort(reverse=True)
m.sort(reverse=True)

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

tmp = K
while(tmp > len(p)):
    tmp -= 2

ans = None
flg = True
while(tmp >= 0 and K - tmp <= len(m)):
    if flg:
        ans = 1
        tmp_list = p[:tmp] + m[:K-tmp]
        for i in tmp_list:
            ans = (ans * i) % mod
        flg = False

    elif p[tmp] * p[tmp+1] < m[K-tmp-2] * m[K-tmp-1]:
        tmp_list = p[:tmp] + m[:K-tmp]
        ans = 1
        for i in tmp_list:
            ans = (ans * i) % mod
    
    tmp -= 2

if ans != None:
    print(ans)
else:
    tmp = K - 1
    while(tmp > len(p)):
        tmp -= 2

    flg = True
    while(tmp >= 0 and K - tmp <= len(m)):
        if flg:
            ans = 1
            tmp_list = p[len(p)-tmp:] + m[len(m)-K-tmp:]
            for i in tmp_list:
                ans = (ans * i) % mod
            flg = False

        elif p[len(p)-tmp-2] * p[len(p)-tmp-1] > m[K-tmp] * m[K-tmp+1]:
            tmp_list = p[len(p)-tmp:] + m[len(m)-K-tmp:]
            ans = 1
            for i in tmp_list:
                ans = (ans * i) % mod

        tmp -= 2

    print(-ans%mod)

Submission status: Runtime Error

Solution code:
from functools import reduce
import sys

Z = 10 ** 9 + 7


def input():
    return sys.stdin.readline().rstrip('\n')


def prod(l):
    return reduce(lambda x, y: x * y, l, 1)

def calc(N, K, A):
    A = [a for a in A if a != 0]
    if len(A) < K:
        return 0
    A.sort(key=lambda x: -x)
    ans = 0
    if A[0] < 0:
        ans = prod(A[:K]) if K % 2 == 1 else prod(A[N - K:])
    else:
        p = prod(A[:K])
        r = 1
        m = 1
        j = 0
        for i in range(1, K + 1):
            s = r * A[N - i] / A[K - i]
            if p < 0 and s < m:
                j = i
                m = s
            elif p > 0 and s > m:
                j = i
                m = s
            r = s
        ans = prod(A[:K - j]) * prod(A[N - j:])
    return ans % Z


(N, K) = tuple([int(s) for s in input().split()])
A = [int(s) for s in input().split()]
print(calc(N, K, A))

Submission status: Runtime Error

Solution code:
#関数リスト
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

n, k = MI()
mylist = LI()
temp1 = sorted(mylist)
temp2 = sorted(mylist, reverse = True)
mod = 1.0e9 + 7
start = 1
for i in range(k):
    start *= temp1[i]

for i in range(k):
    s1 = temp1[k-1-i]
    r1 = temp2[i]
    if r1 >= 1:
        break
    if start < start * r1 / s1:
        start =  start * r1 / s1
        
print(int(start % mod))

Submission status: Runtime Error

Solution code:
N = list(map(int, input().split()))
A = list(map(int, input().split()))

A_rezero = [i for i in A if i != 0]
if len(A_rezero) < K:
    print(0)
else:
    A_sorted = sorted(A_rezero)
    inint = A_sorted[0]
    for i in range(1,K):
        inint=inint*A_sorted[i]

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

Submission status: Runtime Error

Solution code:
n,k = map(int, raw_input().split(' '))
ais = map(int , raw_input().split(' '))

pos = [ai for ai in ais if ai > 0]
pos.sort(key = lambda x:-x)
neg = [-ai for ai in ais if ai < 0]
neg.sort(key = lambda x:-x)

def g(neg, k):
	i = len(neg) -1
	r = 1
	while(k):
		r *= -neg[i]
		i -=1
		k -=1
		r %= (10 ** 9) + 7
	return r
def gg(pos, k):
	r =  1
	for i in range(k):
		r *= pos[i]
		r %= (10 **9) + 7
	return r
def f(pos,neg, k):

	if len(pos) == 0: return g(neg, k)
	if len(neg) <= 1: return gg(pos, k)

	i,j = 0,0
	p = 1
	mod = (10 ** 9) + 7
	while(k >= 2 and i < len(pos) and j+1 < len(neg)):
		if j + 1 < len(neg):
			if neg[j] * neg[j+1] > pos[i] * (pos[i+1] if i+1 < len(pos) else 1):
				p *= neg[j] * neg[j+1]
				p %= mod
				j += 2
				k -= 2
			else:
				p *= pos[i]
				i +=1
				p %= mod
				k -=1
	while(k and i < len(pos)):
		p *= pos[i]
		p %+ mod
		k-=1
		i+=1
	return p
print f(pos,neg, k)