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:
mod = 10**9 + 7
import bisect
def do():
    n, k = map(int, input().split())
    dat = list(map(int, input().split()))
    buf = []
    nump, numm, numz = 0, 0, 0
    for i in range(n):
        if dat[i] == 0:
            numz += 1
        elif dat[i] > 0:
            nump += 1
            buf.append([dat[i], dat[i]])
        elif dat[i] < 0:
            numm += 1
            buf.append([dat[i], -dat[i]])
    indm = []
    indp = []
    # +と-を足してもk個に満たないなら 0 をかけるしかないので
    if nump + numm < k:
        print(0)
        return
    for i in range(n):
        if buf[i][0] < 0:
            indm.append(i)
        else:
            indp.append(i)
    buf.sort(key=lambda x: x[1], reverse=True)
    #print(nump, numm, numz)
    #print(buf)
    #print(indm)
    #print(indp)


    res = 1
    lastp = None
    lastm = None
    flagPosi = True
    for i in range(k):
        res *= buf[i][0]
        res %= mod
        if buf[i][0] > 0:
            lastp = buf[i][0]
        elif buf[i][0] < 0:
            lastm = buf[i][0]
            flagPosi = not flagPosi

    # k個選んで正なら、無条件にオッケー
    if flagPosi:
        print(res%mod)
        return

    def do2(): # negaしか作れないなら最も小さい値
        buf.sort(key=lambda x: x[1], reverse=False)
        res2 = 1
        for i in range(k):
            res2 *= buf[i][0] % mod
            res2 %= mod
        print(res2%mod)

    def do3(anti, kawari): # negaしか作れないなら最も小さい値
        ispass = False
        buf.sort(key=lambda x: x[1], reverse=True)
        res2 = 1
        for i in range(k):
            if ispass is False and buf[i][0] == anti:
                ispass = True
                continue
            res2 *= buf[i][0] % mod
            res2 %= mod
        res2 *= kawari
        print(res2%mod)

    # 負の場合は二パターン
    # 1. 正を抜いて、次に大きい負をかける
    # 2. 負を抜いて、次に大きい正をかける
    nextp = None
    nextm = None
    for i in range(k, len(buf)):
        if buf[i][0] > 0 and nextp is None:
            nextp = buf[i][0]
        elif buf[i][0] < 0 and nextm is None:
            nextm = buf[i][0]
    #print("---",lastp, lastm, nextp,nextm)
    if nextm is None and nextp is None: # これはないはず
        do2()
        return
    if (lastp is None or nextm is None) and (lastm is None or nextp is None):
        # この場合、動かせないので負しかないから
        do2()
        return
    if lastp is not None and lastm is not None and nextp is not None and nextm is not None:
        # 全部あるなら戦い
        if abs(nextm / lastp) > abs(nextp / lastm):
            # pをmにした方がいいので
            do3(lastp, nextm)
            return
        else:
            do3(lastm, nextp)
            return
    # この場合、どっちしかないので
    if (lastp is None or nextm is None):
        # この場合、 m-> p
        do3(lastm, nextp)
        return
    else:
        do3(lastp, nextm)
        return


do()

Submission status: Runtime Error

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))

    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 = True
    elif comp_pn == 0 and comp_np > 0:
        np_or_pn = False
    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: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    A = sorted([int(x) for x in input().strip().split()])
    zeros = A.count(0)
    max_A = max(A)
    mod = 10 ** 9 + 7
    if N == K:
        ans = 1
        for k in range(K):
            ans = (ans * A[k]) % mod
        print(ans)
        return
    if max_A < 0:
        if K % 2:
            ans = 1
            for k in range(K):
                ans = (ans * A[-1-k]) % mod
            print(ans)
            return
        else:
            for k in range(K):
                ans = (ans * A[k]) % mod
            print(ans)
            return
    elif max_A == 0:
        if A[-K] == 0:
            print(0)
            return
        else:
            if K % 2:
                print(0)
                return
            else:
                for k in range(K):
                    ans = (ans * A[k]) % mod
                print(ans)
                return
    else:
        if N - zeros < K:
            print(0)
            return
        elif N - zeros == K:
            if len([a for a in A if a < 0]) % 2:
                print(0)
                return
            else:
                ans = 1
                for a in A:
                    if a != 0:
                        ans = (ans * a) % mod
                print(ans)
                return
        ans = 1
        A.sort(key=lambda x: abs(x), reverse=True)
        minus = 0
        for k in range(K):
            if A[k] < 0:
                minus += 1
                minus_last = k
            ans = (ans * A[k]) % mod
        if minus % 2:
            for k in range(K):
                if k == minus_last:
                    continue
                ans = (ans * A[k]) % mod
        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 = []
N = []

for a in A:
    if a >= 0:
        P.append(a)
    else:
        N.append(a)
P.sort(reverse=True)
N.sort()
#print(P)
#print(N)

if len(P) == 0:
    if k%2 == 0:
        N.sort()
        ans = 1
        for i in range(k):
            ans *= N[i]
            ans %= mod
    else:
        N.sort(reverse=True)
        ans = 1
        for i in range(k):
            ans *= N[i]
            ans %= mod
    print(ans)
    exit()

if len(P) == 1:
    if k%2 == 0:
        N.sort()
        ans = 1
        for i in range(k):
            ans *= N[i]
            ans %= mod
    else:
        ans = P[0]
        N.sort(reverse=True)
        for i in range(k-1):
            ans *= N[i]
            ans %= mod
    print(ans)
    exit()


if len(N) == 0:
    ans = 1
    for i in range(k):
        ans *= P[i]
        ans %= mod
    print(ans)
    exit()

if len(N) == 1:
    if len(P) >= k:
        ans = 1
        for i in range(k):
            ans *= P[i]
            ans %= mod
        print(ans)
        exit()
    else:
        print(N[0])
        exit()

import heapq
if k%2 == 0:
    P_ = []
    N_ = []
    if len(P) != 1:
        for i in range(len(P)):
            if i%2 == 1:
                continue
            P_.append(-P[i]*P[i+1])
        for i in range(len(N)):
            if i%2 == 1:
                continue
            N_.append(-N[i]*N[i+1])
        heapq.heapify(P_)
        heapq.heapify(N_)
        q = k//2
        ans = 1
        for i in range(q):
            x = heapq.heappop(P_)*(-1)
            y = heapq.heappop(N_)*(-1)
            if x >= y:
                ans *= x
                heapq.heappush(N_, y*(-1))
            else:
                ans *= y
                heapq.heappush(P_, x*(-1))
    else:
        ans = 1
        for i in range(k):
            ans *= N[i]
            ans %= mod
else:
    p = P[0]
    P = P[1:]
    P_ = []
    N_ = []
    if len(P) != 1:
        for i in range(len(P)):
            if i%2 == 1:
                continue
            P_.append(-P[i]*P[i+1])
        for i in range(len(N)):
            if i%2 == 1:
                continue
            N_.append(-N[i]*N[i+1])
        heapq.heapify(P_)
        heapq.heapify(N_)
        q = k//2
        ans = p
        for i in range(q):
            x = heapq.heappop(P_)*(-1)
            y = heapq.heappop(N_)*(-1)
            if x >= y:
                ans *= x
                ans %= mod
                heapq.heappush(N_, y*(-1))
            else:
                ans *= y
                ans %= mod
                heapq.heappush(P_, x*(-1))
    else:
        ans = p
        for i in range(k):
            ans *= N[i]
            ans %= mod
print(ans)

Submission status: Runtime Error

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

N,K=map(int,input().split())
A=list(map(int,input().split()))
B = [0]*N
C = [1]*N
neg = 0
for i in range(N):
    B[i]=abs(A[i])
    if A[i]<0:
        C[i]=-1
        neg += 1
Neg = [0]*neg
Pos = [0]*(N-neg)
cneg = cpos = 0
for i in range(N):
    if A[i]<0:
        Neg[cneg] = A[i]
        cneg += 1
    elif A[i]>0:
        Pos[cpos] = A[i]
        cpos += 1

Neg.sort(reverse =True)
Pos.sort(reverse=True)

Ans = 1
mod = 10**9 + 7
flag = 0
if neg == N and K%2 == 1:
    for i in range(K):
        Ans = (Ans*Neg[i])%mod
    flag = 1
elif K==N:
    for i in range(K):
        Ans = (Ans*A[i])%mod
    flag = 1
j=1


while j*2<= K:
    if flag == 1:
        break
    if cneg>1 and cpos>1:
        if Neg[cneg-1]*Neg[cneg-2] > Pos[0]*Pos[1]:
            S = Neg[cneg-1]*Neg[cneg-2]
            Ans = (Ans*S)%mod
            Neg.pop(-1)
            Neg.pop(-1)
            cneg -= 2
        else:
            S = Pos[0]*Pos[1]
            Ans = (Ans*S)%mod
            S.pop(0)
            S.pop(0)
            cpos -= 2
    elif cneg>1 and cpos<2:
        S = Neg[cneg-1]*Neg[cneg-2]
        Ans = (Ans*S)%mod
        Neg.pop(-1)
        Neg.pop(-1)
        cneg -= 2
    elif cneg<2 and cpos>1:
        S = Pos[0]*Pos[1]
        Ans = (Ans*S)%mod
        Pos.pop(0)
        Pos.pop(0)
        cpos -= 2
    elif cneg<2 and cpos<2:
        Ans = 0
    j += 1

K = K - 2*j
if K==1 and flag == 0:
    Ans = (Ans*Pos[0])%mod
    print(Ans)
else:
    print(Ans)

Submission status: Runtime Error

Solution code:
def findMaxProduct(arr, n, k) : 
    MaxProduct = 1
    for i in range(0, k) : 
        MaxProduct = MaxProduct * arr[i] 
          
    prev_product = MaxProduct 
    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 MaxProduct 

n,k=map(int,input().split())
lst=list(map(int,input().split()))
lst.sort()
multi=findMaxProduct(lst, n, k)
print(multi%(10**9+7))

Submission status: Runtime Error

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

cnt = [0, 0]
for a in A:
    if 0 <= a:
        cnt[1] += 1
    else:
        cnt[0] += 1

if (k-cnt[1]) % 2 == 0:
    can_positive = 1
else:
    can_positive = 0

if can_positive:
    pos = []
    neg = []
    for a in A:
        if 0 <= a:
            pos.append(a)
        else:
            neg.append(a)
    pos.sort()
    neg.sort(reverse=True)
    neg_pair = []
    for a, b in zip(neg, neg[1:]):
        neg_pair.append(a*b)
    neg_pair.reverse()

    use = []
    cnt = 0
    while cnt != k:
        if 2 <= k-cnt:
            if neg_pair and 2 <= len(pos):
                if neg_pair[-1] < pos[-1]*pos[-2]:
                    cnt += 2
                    use.append(pos.pop())
                    use.append(pos.pop())
                else:
                    cnt += 2
                    use.append(neg_pair.pop())
            elif neg_pair:
                cnt += 2
                use.append(neg_pair.pop())
            else:
                cnt += 2
                use.append(pos.pop())
                use.append(pos.pop())
        else:
            a = pos.pop()
            cnt += 1
            use.append(a)

    ans = use[0]
    for a in use[1:]:
        ans *= a
        ans %= MOD
    print(ans)
else:
    pos = []
    neg = []
    for a in A:
        if 0 <= a:
            pos.append(a)
        else:
            neg.append(a)
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    use = [neg[0]]
    neg_pair = []
    for a, b in zip(neg[1:], neg[2:]):
        neg_pair.append(a*b)
    neg_pair.reverse()
    cnt = 1
    while cnt != k:
        if 2 <= k-cnt:
            if neg_pair and 2 <= len(pos):
                if neg_pair[-1] > pos[-1]*pos[-2]:
                    cnt += 2
                    use.append(pos.pop())
                    use.append(pos.pop())
                else:
                    cnt += 2
                    use.append(neg_pair.pop())
            elif neg_pair:
                cnt += 2
                use.append(neg_pair.pop())
            else:
                cnt += 2
                use.append(pos.pop())
                use.append(pos.pop())
        else:
            a = pos.pop()
            cnt += 1
            use.append(a)

    ans = use[0]
    for a in use[1:]:
        ans *= a
        ans %= MOD
    print(ans)

Submission status: Runtime Error

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

A.sort(reverse=True)

P = []
M = []
Ans = []
p = 0
m = 0

for i in range(N):
    if 0 <= A[i]:
        P.append(A[i])
    else:
        M.append(A[i])

if K % 2 == 1 and len(P) != 0:
    Ans.append(P[p])
    p += 1

while len(Ans) < K:

    #Mのストックがもうない時
    if m+1 >= len(M):
        Ans.append(P[p])
        if len(Ans) == K:
            break
        Ans.append(P[p + 1])
        p += 2
    elif p+1 >= len(P):
        Ans.append(M[m])
        if len(Ans) == K:
            break
        Ans.append(M[m + 1])
        m += 2
    else:
        if P[p]*P[p+1] < M[m]*M[m+1]:
            Ans.append(M[m])
            Ans.append(M[m+1])
            m += 2
        else:
            Ans.append(P[p])
            Ans.append(P[p + 1])
            p += 2

answer = 1
for i in range(K):
    answer = (answer * Ans[i]) % 1000000007

print(answer)

Submission status: Runtime Error

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))

    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 = True:
    elif comp_pn == 0 and comp_np > 0:
        np_or_pn = False:
    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: Runtime Error

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

ans = 1

p_list, m_list = [], []
for i in a:
    if i<0: m_list.append(i)
    elif i>0: p_list.append(i)
    else: zero_flag = True

n = len(p_list)+len(m_list)

if len(p_list)+len(m_list)<k:
    print(0)
    sys.exit()
if k==n:
    ans = a[0]
    for i in range(1, k):
        ans *= a[i]
        ans %= mod
    print(ans)
    sys.exit()
if n==len(m_list):
    if zero_flag:
        print(0)
        sys.exit()
    else:
        ans = m_list[-1]
        for i in range(1, k):
            ans *= m_list[n-i-1]
            ans %= mod
        print(ans)
        sys.exit()


p_num, m_num = len(p_list)-1, 0

while k>0:
    p_mul, m_mul = 0, 0
    if k==3:
        if m_mul+1<len(m_list) and p_mul+1<len(p_list):
            m_mul = m_list[m_num]*m_list[m_num+1]*p_list[p_num]
            p_mul = p_list[p_num]*p_list[p_num-1]*m_list[m_num]
        if p_mul>m_mul:
            ans *= p_mul
            ans %= mod 
        else:
            ans *= m_mul
            ans %= mod
        break
    if k==1:
        if p_num<0:
            if zero_flag:
                print(0)
                sys.exit()
        ans *= p_list[p_num]
        ans %= mod
        break
    if m_mul+1<len(m_list):
        m_mul = m_list[m_num]*m_list[m_num+1]
    if p_mul+1<len(p_list):
        p_mul = p_list[p_num]*p_list[p_num-1]
    if p_mul>m_mul:
        ans *= p_mul
        ans %= mod
        p_num -= 2
    else:
        ans *= m_mul
        ans %= mod
        m_num += 2
    k -= 2
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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

mod = 10**9 + 7

A = sorted(A, key=lambda x:-abs(x))

s = 1
ans = 1
for a in A[:K]:
  s *= np.sign(a)
  ans *= a
  ans %= mod
if s < 0:
  for a in A[K-1::-1]:
    if a > 0:
      x = a
  for b in A[K:]:
    if b < 0:
      y = b
  for c in A[K-1::-1]:
    if c < 0:
      z = c
  for d in A[K:]:
    if d > 0:
      w = d
  if (c == 0) or ((a * c != 0) and (b / a >= d / c)):
    ans *= b
    ans %= mod
    ans *= pow(a, -1, mod=mod)
    ans %= mod
  elif (a == 0) or ((a * c != 0) and (b / a < d / c)):
    ans *= d
    ans %= mod
    ans *= pow(c, -1, mod=mod)
    ans %= mod
  else:
    ans = 0
print(ans)

Submission status: Runtime Error

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s); sys.stdout.write('\n')
def wi(n): sys.stdout.write(str(n)); sys.stdout.write('\n')
def wia(a, sep=' '): sys.stdout.write(sep.join([str(x) for x in a])); sys.stdout.write('\n')


MOD = 10**9 + 7


def solve(n, k, a):
    positives = sum([1 for ai in a if ai > 0])
    negatives = sum([1 for ai in a if ai < 0])
    zeros = sum([1 for ai in a if ai == 0])

    a = sorted(a, reverse=True, key=lambda x: abs(x))
    sign = 1
    for i in range(k):
        if a[i] < 0:
            sign = -sign
        if a[i] == 0:
            sign = 0

    if sign == 0:
        return 0

    if sign == 1:
        ans = 1
        for i in range(k):
            ans = (ans * abs(a[i])) % MOD
        return ans

    if sign == -1:
        cc = []

        more_neg = -1
        for i in range(k, n):
            if a[i] < 0:
                more_neg = i
                break

        more_pos = -1
        for i in range(k, n):
            if a[i] > 0:
                more_pos = i
                break

        taken_neg = -1
        for i in range(k-1, -1, -1):
            if a[i] < 0:
                taken_neg = i
                break

        taken_pos = -1
        for i in range(k - 1, -1, -1):
            if a[i] > 0:
                taken_pos = i
                break

        if more_neg >= 0 and taken_pos >= 0:
            cc.append((taken_pos, more_neg))
        if more_pos >= 0 and taken_neg >= 0:
            cc.append((taken_neg, more_pos))
        cc = sorted(cc, key=lambda x: abs(a(x[1]) / a[x[0]]), reverse=True)

        if len(cc) > 0:
            ans = 1
            for i in range(k):
                if i != cc[0][0]:
                    ans = (ans * a[i]) % MOD
            ans = (ans * a[cc[0][1]]) % MOD
            return ans
        else:
            # product is negative, taking smallest
            ans = 1
            for i in range(k):
                ans = (ans * a[n-i-1]) % MOD
            return ans


def main():
    n, k = ria()
    a = ria()
    wi(solve(n, k, a))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split()))
N = int(a[0])
K = int(a[1])
A_i = list(map(int, input().split()))
A_pos = [i for i in A_i if i > 0]
A_neg = [i for i in A_i if i < 0]
A_zer = [i for i in A_i if i == 0]

A_pos = sorted(A_pos)
A_neg = sorted(A_neg)
A_neg.reverse()
# zettaiti tiisai jun

ret = 1

if len(A_pos) == 0:
    if len(A_zer) > 0:
        ret = 0
    for i in range(K):
        ret = ret * A_neg[i]
        ret = ret % (10**9+7)
    if ret < 0:
        ret += 10**9+7
else:
    if K % 2 == 1:
        ret *= A_pos[-1]
        A_pos = A_pos[:-1]
        K = K - 1

    for i in range(K//2):
        if len(A_pos) == 0 and len(A_neg) == 2:
            ret = ret * A_neg[0] * A_neg[1]
            break
        if len(A_pos) == 1 and len(A_neg) == 1:
            ret = ret * A_neg[0] * A_pos[0]
            break
        if len(A_pos) == 2 and len(A_pos) == 0:
            ret = ret * A_pos[0] * A_pos[1]
            break

        c1 = A_pos[-1] * A_pos[-2]
        if len(A_neg) >= 2:
            c2 = A_neg[-1] * A_neg[-2]
        else:
            c2 = 0

        if c1 > c2:
            ret = ret * A_pos[-1] * A_pos[-2]
            A_pos = A_pos[:-2]
        else:
            ret = ret * A_neg[-1] * A_neg[-2]
            A_neg = A_neg[:-2]
        ret = ret % (10**9+7)
        if ret < 0:
            ret += 10**9+7
print(ret)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=[int(x) for x in input().split()]
B=[]
C=[]
for i in range(N):
    if A[i]<0:
        B.append(A[i])
    else:
        C.append(A[i])
ans=1
mod=10**9+7

B=sorted(B)
C=sorted(C)

if N==K:
    for i in range(N):
        ans*=A[i]
    print(ans%mod)
    exit()
else:
    if len(C)==0:
        if K%2==1:
            for i in range(1,K+1):
                ans*=B[-i]
            print(ans%mod)
            exit()
        else:
            for i in range(K):
                ans*=B[i]
            print(ans%mod)
            exit()
    else:
        if K%2==1:
            x=C.pop(-1)
            ans*=x
            for i in range((K-1)//2):
                if len(C)>=2 and len(B)>=2:
                    if C[-1]*C[-2]>=B[0]*B[1]:
                        [x,y]=[C.pop(-1),C.pop(-2)]
                        ans*=x*y
                    else:
                        [x,y]=[B.pop(0),B.pop(1)]
                        ans*=x*y
                else:
                    if len(C)==0:
                        [x,y]=[B.pop(0),B.pop(1)]
                        ans*=x*y
                    else:
                        [x,y]=[C.pop(-1),C.pop(-2)]
                        ans*=x*y
            print(ans%mod)
            exit()
        else:
            for i in range(K//2):
                if len(C)>=2 and len(B)>=2:
                    if C[-1]*C[-2]>=B[0]*B[1]:
                        [x,y]=[C.pop(-1),C.pop(-2)]
                        ans*=x*y
                    else:
                        [x,y]=[B.pop(0),B.pop(1)]
                        ans*=x*y
                else:
                    if len(C)==0:
                        [x,y]=[B.pop(0),B.pop(1)]
                        ans*=x*y
                    else:
                        [x,y]=[C.pop(-1),C.pop(-2)]
                        ans*=x*y
            print(ans%mod)
            exit()

Submission status: Runtime Error

Solution code:
MOD=10**9+7
import bisect
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ans=set()
if 0 in ls:
  ans.add(0)

als=sorted(ls, key=lambda x: -abs(x))
mul=1
for i in range(K):
  mul*=als[i]
if mul>0:
  print(mul%MOD)
else:
  ls2=als[:K]
  ls3=als[K:]
  ls2.sort()
  ls3.sort()
  ans=set()
  ans.add(mul*ls3[0]//ls2[-1])
  ans.add(mul*ls3[-1]//ls2[0])
  ans.add(mul*ls3[-1]//ls2[-1])
  ans.add(mul*ls3[0]//ls2[0])
  print(max(ans)%MOD)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
b = a+a
mod = (10**9)+7
res = -1*(10**18)
pref = []
pref.append(a[0])
for i in range(1,len(b)):
    pref.append(pref[i-1]*b[i])

res = pref[k-1]
for i in range(k,len(pref)):
    res = max(res,pref[i]//pref[i-k])
print(res%mod)

Submission status: Runtime Error

Solution code:
import sys
n,k=map(int,input().split())
A=[]
mod=10**9+7

zero=0
a=list(map(int,input().split()))
for i in range(n):
    if a[i]>0:
        A.append([a[i],0])
    elif a[i]<0:
        A.append([-a[i],1])
    else:
        zero+=1        
if k>n-zero:
    print(0)
    sys.exit()

A=list(reversed(sorted(A)))
cnt=0
for i in range(k):
    cnt+=A[i][1]
chk=0
for i in range(n-zero):
    chk+=A[i][1]
    
if cnt%2==0:
    ans=1
    for i in range(k):
        ans=ans*A[i][0]%mod
    print(ans)
elif chk==n-zero:
    if zero>0:
        print(0)
        sys.exit()
    ans=1
    for i in range(k):
        ans=ans*A[n-i-1][0]%mod
    print((-ans)%mod)
else:
    if A[k][1]==0:
        p=A[k][0]
        m=0
        for i in range(k+1,n-zero):
            if A[i][1]==1:
                m=A[i][0]
                break
    else:
        m=A[k][0]
        p=0
        for i in range(k+1,n-zero):
            if A[i][1]==0:
                p=A[i][0]
                break
    #print(m,p)
    if A[k-1][1]==0:
        l=0
        for i in range(k-1):
            if A[k-i-2][1]==1:
                l=A[k-i-2][0]
                Xl=k-i-2
                break
        #print(l,k)
        if m*l>p*A[k-1][0]:
            ans=1
            for i in range(k-1):
                ans=ans*A[i][0]%mod
            ans=ans*m%mod
            print(ans)
        else:
            ans=1
            for i in range(k):
                if i==Xl:
                    continue
                ans=ans*A[i][0]%mod 
            ans=ans*p%mod
            print(ans)
    else:
        l=0
        for i in range(k-1):
            if A[k-i-2][1]==0:
                l=A[k-i-2][0]
                Xl=k-i-2
                break
        #print(l,k)
        if p*l>m*A[k-1][0]:
            ans=1
            for i in range(k-1):
                ans=ans*A[i][0]%mod
            ans=ans*p%mod
            print(ans)
        else:
            ans=1
            for i in range(k):
                if i==Xl:
                    continue
                ans=ans*A[i][0]%mod 
            ans=ans*m%mod
            print(ans)

Submission status: Runtime Error

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

mod = 10**9 + 7

import collections
import bisect
index = bisect.bisect_right(A, 0)

# print(A[:index])
# print(A[index:])

plus_list = collections.deque(A[index:])
minus_list = collections.deque(A[:index])

count = 0
ans = 1

plus_num = len(plus_list) - 1
minus_num = 0
while count < K:
    if K - count == 1:
        ans *= plus_list.pop() % mod
        count += 1
    else:
        if not plus_list:
            if ans > 0 and (K - count) % 2 == 0:
                for i in range(K - count):
                    ans *= minus_list[i] % mod
                    count += 1
            else:
                for i in range(K - count):
                    ans *= minus_list[i*(-1)-1] % mod
                    count += 1
            continue

        if len(minus_list) < 2:
            for i in range(K - count):
                ans *= plus_list.pop() % mod
                count += 1
            continue

        if plus_list[plus_num] >= minus_list[minus_num] * minus_list[minus_num+1]:
            ans *= plus_list[plus_num] % mod
            plus_num -= 1
            count += 1
        else:
            ans *= minus_list[minus_num] * minus_list[minus_num+1] % mod
            minus_num += 2
            count += 2
print(ans % mod)