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:
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[]
l=0
for i in range(N):
    if(A[i]<0):
        l+=1

for i in range(N):
    if(A[i]<0):
        k=[-A[i],0]
    else:
        k=[A[i],1]
    B.append(k)
#print(B)
if(l==N):
    if(K%2==1):
        B.sort()
        ans=1
        for i in range(K):
            q=(ans*A[i]) % (10**9+6)
            ans=q
    else:
        B.sort(reverse=True)
        ans=1
        for i in range(K):
            q=(ans*A[i]) % (10**9+6)
            ans=q

else:
    B.sort(reverse=True)
    s=0
    for i in range(K):
        if(B[i][1]==0):
            s+=1
    ans=1
    if(s%2==0):
        for i in range(K):
            q=(ans*A[i]) % (10**9+6)
            ans=q
    else:
        for i in reversed(range(K)):
            if(B[i][1]==0):
                p=B[i][0]
                d=i
                break
        q=1
        markq=0
        for i in range(K,N):
            if(B[i][1]==0):
                q=B[i][0]
                markq=1
                break
        if(markq==0):
            for i in range(K):
                if(i!=d):
                    q=(ans*A[i]) % (10**9+6)
                    ans=q
            q=(ans*A[K]) % (10**9+6)
            ans=q
        else:
            r=p*q
            x=B[K-1][0]
            y=1
            marky=0
            for i in range(K,N):
                if(B[i][1]==1):
                    y=B[i][0]
                    marky=1
                    break
            z=x*y
            if(r>z):
                for i in reversed(range(K)):
                    if(B[i][1]==1):
                        p=B[i][0]
                        e=i
                        break
                for i in range(K):
                    if(i!=e):
                        q=(ans*A[i]) % (10**9+6)
                        ans=q
                q=(ans*y) % (10**9+6)
                ans=q
            else:
                for i in range(K):
                    if(i!=d):
                        q=(ans*A[i]) % (10**9+6)
                        ans=q
                q=(ans*A[K]) % (10**9+6)
                ans=q
print(ans)

Submission status: Runtime Error

Solution code:
def maxProductSubarrayOfSizeK(A, n, k): 
  
    MOD = 10**9+7
    A.sort()   
    product = 1
    
    if A[k-1] < 0 and k%2 ==1:
        temp = A[:A.index(0)]
        temp.sort(reverse=True)
        for i in range(K):
            product *= temp[i]
            product %= MOD
        
  
    if (A[n - 1] == 0 and (k & 1)): 
        return 0
  
    if (A[n - 1] <= 0 and (k & 1)) : 
        for i in range(n - 1, n - k + 1, -1): 
            product *= A[i] 
            product %= MOD
        return product 
  
    i = 0  
    j = n - 1
  
    if (k & 1): 
        product *= A[j] 
        j-= 1
        k-=1
  
    k >>= 1
  
    for itr in range( k) : 
  
        left_product = A[i] * A[i + 1] 
  
        right_product = A[j] * A[j - 1] 
  
        if (left_product > right_product) : 
            product *= left_product 
            product %= MOD
            i += 2
          
        else : 
            product *= right_product 
            product %= MOD
            j -= 2
  
    return product

N,K = map(int,input().split())
A = list(map(int,input().split()))
print((maxProductSubarrayOfSizeK(A, N, K))% MOD)

Submission status: Runtime Error

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

is_all_neg = 1
for i in range(N):
    if A[i] > 0:
        is_all_neg = 0
        
if is_all_neg:
    if K%2 == 1:
        A_1 = sorted(A, reverse=True)
        for i in range(K):
            ans *= A_1[i]
        print(ans % p)
    else:
        A_1 = sorted(A)
        for i in range(K):
            ans *= A_1[i]
        print(ans % p)
else:
    A_1 = sorted(A, key=lambda x: abs(x), reverse=True)
    is_pos = 1
    ans = 1
    minus = []
    for i in range(K):
        ans *= A_1[i] % p
        if A_1[i] < 0:
            minus.append(i)
        if ans > 0:
            is_pos = 1
        else:
            is_pos = 0
        if i == K-1:
            if is_pos:
                
                break
            else:
                idx = minus.pop()
                ans /= A_1[idx]
                for j in range(K, N):
                    if A_1[j] > 0:
                        ans *= A_1[j]
                        break
    print(int(ans)%p)

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7

def f(X):
    a = 1

    for x in X:
        a *= abs(x)
        a %= MOD

    return a


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

    if K%2 == 1 and len(filter(lambda x: x>=0, A)) == 0:
        return (-f(sorted(A)[:K]%MOD))

    B = sorted(map(lambda x:(abs(x), x), A), reverse=True)

    V1 = []
    V2 = []

    for val, org in B:
        if org >= 0:
            V1.append(val)
        else:
            V2.append(val)

    cnt = 0
    for b, org in B[:K]:
        if org < 0:
            cnt += 1

    if cnt%2 == 0:
        return f(map(lambda x:x[0], B[:K]))

    cnt1 = K-cnt
    cnt2 = cnt

    if len(V1) < cnt1 + 1:
        cnt1 -= 1
        cnt2 += 1
    elif len(V2) < cnt2 + 1:
        cnt2 -= 1
        cnt1 += 1
    elif  V1[cnt1-1]*V1[cnt1] < V2[cnt2-1]*V2[cnt2]:
        cnt1 -= 1
        cnt2 += 1
    else:
        cnt2 -= 1
        cnt1 += 1
        
    return f(map(lambda x:x[0], V1[:cnt1]))*f(map(lambda x:x[0], V2[:cnt2]))%MOD


print(main())

Submission status: Runtime Error

Solution code:
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    Ap = []
    Am = []
    for a in A:
        if a >= 0:
            Ap.append(a)
        else:
            Am.append(a)
    list.sort(Ap,reverse=True)
    list.sort(Am)
    p = 0
    m = 0
    ans = 1
    if len(Ap) > 0:
        for k in range(K):
            if k < K-2:
                if p < len(Ap):
                    if Ap[p] >= -Am[m]:
                        ans = (ans*Ap[p])%(10**9+7)
                        p += 1
                    else:
                        ans = (ans*(-Am[m]))%(10**9+7)
                        m += 1
                else:
                    ans = (ans*(-Am[m]))%(10**9+7)
                    m += 1
            elif k == K-2:
                if m%2 == 0 and m == len(Am)-1:
                    ans = (ans*Ap[p])%(10**9+7)
                    p += 1
                else:
                    if p < len(Ap):
                        if Ap[p] >= -Am[m]:
                            ans = (ans*Ap[p])%(10**9+7)
                            p += 1
                        else:
                            ans = (ans*(-Am[m]))%(10**9+7)
                            m += 1
                    else:
                        ans = (ans*(-Am[m]))%(10**9+7)
                        m += 1
            else:
                if m%2 == 1 and m < len(Am):
                    ans = (ans*(-Am[m]))%(10**9+7)
                else:
                    if p < len(Ap):
                        ans = (ans*Ap[p])%(10**9+7)
                    else:
                        ans = (ans*(Am[-1]))%(10**9+7)
    else:
        for k in range(K):
            if k < K-1:
                ans = (ans*(-Am[-1-k]))%(10**9+7)
                m += 1
            else:
                if m%2 != 1:
                    ans = (ans*(Am[-1-k]))%(10**9+7)
                else:
                    ans = (ans*(-Am[-1-k]))%(10**9+7)
                
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
aa=list(map(int,input().split()))
aa=sorted(aa,key=lambda x: x * x,reverse=True)
x=[]
p=1
for i in range(k):
    p*=aa[i]
if p>=0:
  print(p%(10**9+7))
else:
  hes=0
  for i in range(n):
    if aa[i]<0:
      hes+=1
  if hes==n:
    ans=1
    for i in range(1,k+1):
      ans*=aa[-i]
      while ans<0:
        ans+=(10**9+7)
      print(ans)
  else:
    while True:
      for i in range(k):
        tn=int(p/aa[k-1-i])
        for j in range(k,n):
          if tn*aa[j]>0:
            print(tn*aa[j]%(10**9+7))
            exit()

Submission status: Runtime Error

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def product(A):
    T = 1
    for a in A:
        T *= a
    return T


def solve():
    N, K = read_ints()
    A = read_ints()
    positives, negatives = [], []
    zero = 0
    modulo = 10**9+7
    while A:
        a = A.pop()
        if a > 0:
            positives.append(a)
        elif a < 0:
            negatives.append(a)
        else:
            zero += 1
    if len(positives) == 0:
        if len(negatives) < 2:
            if zero:
                return 0
    positives.sort()
    negatives.sort(reverse=True)
    if len(positives) == 0:
        if K%2 == 1:
            if zero:
                return 0
            else:
                return product(negatives[:K])%modulo
        else:
            return product(negatives[-K:])%modulo
    T = 1
    while K:
        if K >= 2 and len(negatives) > 1 and len(positives) > 1 and negatives[-1]*negatives[-2] > positives[-1]*positives[-2]:
            T = (T*negatives.pop()*negatives.pop())%modulo
            K -= 2
        elif len(positives) > 0:
            T = (T*positives.pop())%modulo
            K -= 1
        elif len(negatives) > 1:
            if K > 2:
                T = (T*negatives.pop()*negatives.pop())%modulo
                K -= 2
            else:
                T = (T*negatives.pop(0))%modulo
                K -= 1
        else:
            T = (T*negatives.pop())%modulo
            K -= 1
    return T


if __name__ == '__main__':
    print(solve())

Submission status: Runtime Error

Solution code:
from typing import Reversible


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

A.sort(key=lambda x: abs(x),reverse=True)
minus = sum(a <= 0 for a in A)
if N - K < A.count(0):
    print(0)
    exit()
if N == minus:
    if 0 in A:
        print(0)
    else:
        ans = 1
        A.sort(reverse=True)
        for a in A[:K]:
            ans = ans * a % mod
        print(ans)
    exit()
minus1 = 0
minus2 = 0
ans1 = 1
ans2 = 0
last_minus = 1
last_plus = -1
n = 0
for a in A:
    if a == 0:
        continue
    n += 1
    ans1 = ans1 * a % mod
    if a < 0:
        minus1 += 1
        last_minus = a
    if n == K:
        if minus1 % 2 != 0:
            ans1 = ans1 * pow(last_minus, mod-2, mod) % mod
            n -= 1
            minus1 -= 1
        else:
            break
else:
    raise ZeroDivisionError
n = 0
for a in A:
    if a == 0:
        continue
    n += 1
    ans2 = ans2 * a % mod
    if a < 0:
         minus2 += 1
    else:
        last_plus = a
    if n == K:
        if minus2 % 2 != 0:
            ans2 = ans2 // last_plus % mod
            n -= 1
        else:
            break
else:
    raise ZeroDivisionError
print(max(ans1, ans2))

Submission status: Runtime Error

Solution code:

n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
m=[]
p=[]

for i in range(n):
    if a[i]<0:
        m.append(a[i])
    else:
        p.append(a[i])
m.sort(reverse=True)
p.sort()
ans=1

if len(m)==n and k%2==1:
    for i in range(k):
        ans*=m[i]
        ans%=mod

elif k==1:
    ans=p[-1]

elif len(m)==1:
    if n==k:
        for i in range(len(p)):
            ans*=p[i]
            ans%=mod
        ans%m[-1]
    else:
        for i in range(k):
            ans*=p[i]
            ans%=mod

elif len(p)==1:
    if n==k:
        for i in range(len(m)):
            ans*=m[i]
            ans%=mod
        ans%p[-1]
    elif k%2==0:
        for i in range(k):
            ans*=m[i]
            ans%=mod
    else:
        for i in range(k-1):
            ans*=m[i]
            ans%=mod
        ans*=p[-1]

else:
    cnt=0
    for i in range(k-2):
        if len(m)==0:
            ans*=p.pop()
        elif len(p)==0:
            lm=m.pop()
            ans*=lm
            cnt+=1
        else:
            if abs(m[-1])<p[-1]:
                ans*=p.pop()
            else:
                lm=m.pop()
                ans*=lm
                cnt+=1
        ans%=mod
    
    if cnt%2==0:
        if len(p)>1 and len(m)>1:
            ans*=max(p[-1]*p[-2],m[-1]*m[-2])
        elif len(p)<2:
            ans*=m[-1]*m[-2]
        else:
            ans*=p[-1]*p[-2]
    elif len(m)>0:
        ans*=p[-1]*m[-1]
    else:
        ans=pow(ans,lm-2,mod)*p[-1]*p[-2]


print(ans%mod)

Submission status: Runtime Error

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

MOD = 10 ** 9 + 7

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

ans = []
mns = []
pls = []
itr = 0
while itr < k:
  ans.append(AA[itr])
  if AA[itr] < 0:
    mns.append(AA[itr])
  else:
    pls.append(AA[itr])
  itr += 1

mflg = False
pflg = False
zflg = False
if all(a < 0 for a in A) and k % 2 == 1:
  AA = sorted(A, key=lambda x: abs(x))
  mns = []
  for itr in range(k):
    mns.append(AA[itr])

elif len(mns) % 2 != 0:
  mm = mns[-1]
  pp = pls[-1]
  for i in range(itr, n):
    nn = AA[i]
    if nn > 0 and not pflg:
      pp *= nn
      pflg = True
      pv = nn
    elif nn < 0 and not mflg:
      mm *= nn
      mflg = True
      mv = nn
    elif nn == 0:
      zflg = True
  if mflg and not pflg:
    if pls:
      del pls[-1]
      mns.append(mv)
      
  elif pflg and not mflg:
    del mns[-1]
    pls.append(pv)

a = 1
for m in mns:
  a = (a * m) % MOD
for p in pls:
  a = (a * p) % MOD

print(a)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
p, m, ans = [], [], 1
for i in A:
    if i < 0:
        m.append(i)
    else:
        p.append(i)

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


if not len(p):
    for i in range(K):
        ans *= m[i]
        ans %= MOD

else:
    ispass = False
    tmp = len(p)
    for i in range(K):
        if ispass:
            ispass = False
            continue
        if K - i == 1:
            ans *= p[-1]
            ans %= MOD

        elif tmp < K - i - 1:
            ans *= -m[-1]
            ans %= MOD
            ans *= -m[-2]
            ans %= MOD
            m = m[0:-2]
            ispass = True

        else:
            if m[-1] * m[-2] > p[-1] * p[-2]:
                ans *= -m[-1]
                ans %= MOD
                ans *= -m[-2]
                ans %= MOD
                m = m[0:-2]
                isPass = True
            else:
                ans *= p[-1]
                ans %= MOD
                ans *= p[-2]
                ans %= MOD
                p = p[0:-2]
                isPass = True

print(ans)

Submission status: Runtime Error

Solution code:
# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7
    As = [(abs(a), a<0) for a in A]
    As.sort()
    As = As[::-1]


    # 大きい順
    last_plus = None
    last_minus = None
    is_minus = False
    ans = 1
    for a, m in As[:K]:
        ans = (ans * a) % MOD
        is_minus ^= m
        if m:
            last_minus = a
        else:
            last_plus = a
    
    if last_plus == 0:
        print(0)
        return
    # print(As)
    # print(ans, is_minus)
    # print(last_minus, last_plus)
    # 絶対値の大きい順に選択して、答えが負のとき
    if is_minus:
        # 答えが負の場合はK番目以降の最も絶対値の大きい正負の数を探す
        next_plus = None
        next_minus = None
        for a, m in As[K:]:
            if m and next_minus == None:
                next_minus = a
            elif not m and next_plus == None:
                next_plus = a
        # print(next_minus, next_plus)
        # Aが負の数だけの場合
        if next_plus == None and next_plus == None:
            ans = 1
            for a, m in As[-K:]:
                ans = (ans * a) % MOD
            ans = MOD - ans
        elif next_plus == None:
            if last_plus == None:
                ans = 1
                for a, m in As[-K:]:
                    ans = (ans * a) % MOD
                ans = MOD - ans
            else:
                ans = (ans * modinv(last_plus)) % MOD
                ans = (ans * next_minus) % MOD
        elif next_minus == None:
            ans = (ans * modinv(last_minus)) % MOD
            ans = (ans * next_plus) % MOD
        else:
            a = last_plus * next_plus
            b = last_minus * next_minus
            if a > b:
                ans = (ans * modinv(last_minus)) % MOD
                ans = (ans * next_plus) % MOD
            else:
                ans = (ans * modinv(last_plus)) % MOD
                ans = (ans * next_minus) % MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3


import functools
from numba import njit

M = 10 ** 9 + 7

@njit
def prods(xs):
    return functools.reduce(lambda x, y: x * y % M, xs) % M

@njit
def maximize_product(n, k, bs):
    cs = sorted(bs)
    if cs[-1] == 0 and k % 2 == 1:
        return 0
    elif cs[-1] <= 0 and k % 2 == 1:
        return prods(cs[n - k:]) % M
    i = 0
    j = n - 1
    res = 1
    if k % 2 == 1:
        res *= cs[j] % M
        j -= 1
        k -= 1
    k >>= 1
    for _ in range(k):
        lp = cs[i] * cs[i + 1]
        rp = cs[j] * cs[j - 1]
        if lp > rp: 
            res *= lp % M 
            i += 2
        else: 
            res *= rp % M 
            j -= 2
    res %= M
    return res
   


def main():
    n, k = (int(z) for z in input().split())
    bs = [int(b) for b in input().split()]
    res = maximize_product(n, k, bs)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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



flg = 0
plus_num = 0
for i in a:
    if i>0:
        plus_num+=1
minus_num = n-plus_num


if minus_num ==1 and k==n:
    flg = 1
if minus_num >=2 and plus_num>=1 and n-plus_num%2==1 and k==n:
    flg = 1
if  minus_num >=2  and plus_num==0 and k%2==1:
    flg = 2



if flg == 1:
    ans = 1
    for i in a:
        ans*=i
        if ans>0:
                ans %= (10**9+7)
        
        
if flg ==2:
    abs_a = sorted(a, key=abs)
    ans = 1
    for i in range(k):
        ans*=abs_a[i]
        if ans>0:
                ans %= (10**9+7)

else:
    abs_a = sorted(a, key=abs)
    abs_a.reverse()
    min_minus = 0
    ans = 1
    for i in range(k):
        if abs_a[i]>=0:
            ans*=abs_a[i]
            if ans>0:
                ans %= (10**9+7)
        else:
            ans *= abs_a[i]
            if ans>0:
                ans %= (10**9+7)
            min_minus = abs_a[i]
    if ans <0:
        ans /=min_minus
        while True:
            for i in range(k,n):
                if abs_a[i]>=0:
                    ans*=abs_a[i]
                    break
ans %= (10**9+7)
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    def solve():
        ret = 1
        for i in range(n):
            if L[i][2]:
                ret *= L[i][0]
                ret %= MOD
        return ret % MOD

    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    INF = float('inf')
    L = []
    p, m = 0, 0
    for a in A:
        if a < 0:
            m += 1
            L.append([abs(a), -1, False])
        else:
            L.append([a, 1, False])
    L = sorted(L, key= lambda x: x[0], reverse=True)
    pm = 1
    lp, lm = None, None
    for i in range(k):
        L[i][2] = True
        pm *= L[i][1]
        if L[i][1] >= 0:
            lp = i
        else:
            lm = i
    if pm >= 0:
        ans = solve()
    else:
        ans1, ans2 = -INF, -INF
        flag1, flag2 = 0, 0
        if lp:
            j = k
            while j < n:
                if L[j][1] < 0:
                    ans1 = L[j][0] / L[lp][0]
                    flag1 = 1
                    break
                j += 1
        if lm:
            l = k
            while j < n:
                if L[l][1] >= 0:
                    ans2 = L[l][0] / L[lm][0]
                    flag2 = 1
                    break
                j += 1
        if ans1 >= ans2 and flag1:
            L[lp][2] = False
            L[j][2] = True
        if ans2 >= ans1 and flag2:
            L[lm][2] = False
            L[l][2] = True
        ans = solve()
        if ans1 == ans2 == -INF:
            L = sorted(L, key=lambda x: x[0])
            ans = 1
            for i in range(k):
                ans *= L[i][0]
                ans %= MOD
            ans = -1 * ans
    print(ans % MOD)
main()

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush


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

mod = 10 ** 9 + 7

for a in A:
    num = a
    sign = True
    if a < 0:
        sign = False
        num *= -1

    heappush(B, (-num, sign))

candidate = []
neg_stock = False
keep_neg = 0
count = 0
ans = 1
pos_stock = False

while B and count < k:
    num, sign = heappop(B)
    num *= -1
    if not sign:
        if neg_stock:
            if count == k-1:
                continue
            neg_stock = 0
            ans = ans * num * keep_neg % mod
            count += 2

        else:
            neg_stock += 1
            keep_neg = num

    else:
        if count > k-2:
            ans = ans * num % mod
            count += 1

        else:
            if pos_stock:
                candidate.append(pos_stock*num)
                count -= 1

            else:
                pos_stock = num
                count -= 1

if neg_stock:
    if candidate:
        B.sort()
        if B[0] < 0:
            if neg_stock * -B[0] > candidate[0]:
                ans = ans * neg_stock * -B[0] % mod

    else:
        A.sort(key=lambda x: abs(x))
        ans = 1
        for i in range(k):
            ans = ans * A[i] % mod

print(ans % mod)

Submission status: Runtime Error

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

DIVIDER = 10 ** 9 + 7

Ap = []
Am = []
for Ai in A:
    if Ai >= 0:
        Ap.append(Ai)
    else:
        Am.append(-Ai)

Ap.sort(key=lambda x: -x)
Am.sort(key=lambda x: -x)
        
tab_p = [1]
tmp = 1
for Api in Ap:
    tmp = (tmp * Api) % DIVIDER
    tab_p.append(tmp)

tab_m = [1]
tmp = 1
for Ami in Am:
    tmp = (tmp * Ami) % DIVIDER
    tab_m.append(tmp)

if K % 2 == 1:
    if len(Ap) > 0:
        idx_p = K - 2 * (len(Am) // 2)
        while True:
            idx_m = K - idx_p
            if len(Ap) <= idx_p + 1: break
            if idx_m < 2: break
            #
            if Am[idx_m - 2] * Am[idx_m - 1] <= Ap[idx_p] * Ap[idx_p + 1]:
                idx_p += 2
            else:
                break
        #
        ans = 1
        for i in range(idx_p):
            ans = (ans * Ap[i]) % DIVIDER
        for i in range(K - idx_p):
            ans = (ans * Am[i]) % DIVIDER
    else:
        ans = 1
        for i in range(K):
            ans = (ans * -Am[-1 - i]) % DIVIDER
else:
    if max(len(Ap), len(Am)) < K and len(Am) % 2 > 0:
        ans = 1
        for i in range(min(K, len(Am))):
            ans = (ans * -Am[-1 - i]) % DIVIDER
        for i in range(K - min(K, len(Am))):
            ans = (ans * Ap[-1 - i]) % DIVIDER
    else:
        idx_p = K - 2 * (len(Am) // 2)
        while True:
            idx_m = K - idx_p
            if len(Ap) <= idx_p + 1: break
            if idx_m < 2: break
            #
            if Am[idx_m - 2] * Am[idx_m - 1] <= Ap[idx_p] * Ap[idx_p + 1]:
                idx_p += 2
            else:
                break
        #
        ans = 1
        for i in range(idx_p):
            ans = (ans * Ap[i]) % DIVIDER
        for i in range(K - idx_p):
            ans = (ans * Am[i]) % DIVIDER

print(ans)

Submission status: Runtime Error

Solution code:
N=10**9+7
n , k = map(int, input().split())
x = list(map(int,input().split()))
posi=[]
nega=[]
ze=[]
p=0
ne=0
z=0

for i in range(n):
    if x[i]<0:
        nega.append(x[i]*(-1))
        ze.append([x[i]*(-1),-1])
        ne+=1
    elif x[i]>0:
        posi.append(x[i])
        ze.append([x[i],1])
        p+=1
    else:
        z+=1

if n+p<k:
    print('0')
    exit

elif k%2==1 and p==0:
    if z>=1:
        print('0')
        exit()
    else:
        ans=1
        nega.sort()
        for i in range(k):
            ans*=nega[i]
            ans%=N
        print(ans*(-1)%N)
elif k%2==1:
    ze.sort(key = lambda x:x[0],reverse=True)
    ans=1
    fu=1
    for i in range(k):
        ans*=ze[i][0]
        fu*=ze[i][1]
        ans%=N
    if fu==-1:
        st=0
        gl=0
        for j in range(min(k,n-k)):
            if ze[k-j]<0 and st==0:
                st=k-j
            if ze[k+j]>0 and gl=0:
                gl=k+j
        for i in range(k):
            if i!=st:
                ans*=ze[i][0]
                ans%=N
            ans*=ze[gl]
            ans%=N
    print(ans)
else:
    ab=nega+posi
    ab.sort(reverse=True)
    ans=1
    for i in range(k):
        ans*=ab[i]
        ans%=N
    print(ans)

Submission status: Runtime Error

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

x, y, z = 0, 0, 0
for i in range(n):
    if a[i]>0:
        y+=1
    elif a[i]<0:
        x+=1
    else:
        z+=1

if n==k and z>0:
    print(0)
        
elif n==k:
    ans = 1
    for i in range(n):
        ans*=a[i]
        ans%=mod
    print(ans)
elif n==x:
    ans = 1
    a.sort(reverse=True)
    for i in range(k):
        ans*=a[i]
        ans%= mod
    print(ans)
else:
    ans = 0
    a.sort()
    aa=[]
    for i in range(x//2):
        aa.append(a[2*i]*a[2*i+1])
    if k%2==1:
        ans=a[-1]
        c = 1
        i  =0
        j =n-2
        while c<k:
            if aa[i]>a[j-1]*a[j-2]:
                ans+=aa[i]
                ans%=mod
                c+=2
                i+=1
            else:
                ans+=a[j-1]+a[j-2]
                j-=2
                c+=2
                ans%=mod
        print(ans)
    else:
        ans=0
        c = 0
        i  =0
        j =n-1
        while c<k:
            if aa[i]>a[j]*a[j-1]:
                ans+=aa[i]
                ans%=mod
                c+=2
                i+=1
            else:
                ans+=a[j]+a[j-1]
                j-=2
                c+=2
                ans%=mod
        print(ans)

Submission status: Runtime Error

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

mod = 10**9+7
ans = -10**10

p = []
m = []
cnt_0 = 0

for i in a:
    if i > 0:
        p.append(i)
    elif i == 0:
        cnt_0 += 1
    else:
        m.append(-i)

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

pp = [1] + p
mm = [1] + m

for i in range(1,len(pp)):
    pp[i] *= pp[i-1]
    pp[i] %= mod

for i in range(1,len(mm)):
    mm[i] *= mm[i-1]
    mm[i] %= mod

if len(m) == 0:
    print(pp[k])
    exit()
if len(p) == 0:
    if k % 2 == 0:
        print(mm[k])
        exit()
    else:
        m.sort()
        ans = 1
        for i in range(k):
            ans *= -m[i]
            ans %= mod
        print(ans)
        exit()

tmp = 1
for p1 in range(k+1):
    m1 = k - p1

    if len(pp) >= p1 and len(mm) >= m1:
        if ans == -10**10:
            if m1 % 2 == 0:
                ans = pp[p1] * mm[m1]
            else:
                ans = -pp[p1] * mm[m1]
            tmp = 1
        else:
            tmp *= -p[p1-1] / m[m1]
            if ans > 0 and tmp > 1:
                ans = pp[p1] * mm[m1]
                tmp = 1
            elif ans < 0 and tmp < 0:
                ans = pp[p1] * mm[m1]
                tmp = 1

print(ans%mod)

Submission status: Runtime Error

Solution code:
import copy

# a = get_int()
def get_int():
    return int(input())

# a = get_string()
def get_string():
    return input()

# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]

# a_list = get_string_list():
def get_string_list():
    return input().split()

# a, b = get_int_multi()
def get_int_multi():  # a, b = get_int_multi()
    return map(int, input().split())

# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))

# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''

def main():

    n, k = get_int_multi()
    a_list = get_int_list()

    p_list=[]
    m_list=[]
    z_list=[]
    for num in a_list:
        if num > 0:
            p_list.append(num)
        elif num < 0:
            m_list.append(num)
        else:
            z_list.append(num)

    p_list.sort(reverse=True)
    m_list.sort()


    if k % 2 == 1:
        if (len(p_list) > 0):
            ans = p_list[0]
            del p_list[0]
            k -= 1
        elif len(z_list) > 0:
            ans = 0
            del z_list[0]
            k -= 1
        else:
            ans = m_list[len(m_list) -1]
            del m_list[len(m_list) -1]
            k -= 1
            m_list.sort(reverse=True)

    else:
        ans = 1

    nokori = k
    while nokori > 0:

        if nokori == 1 and len(p_list) > 0:
            ans = ans * p_list[0]
            del p_list[0]
        elif nokori == 1 and len(z_list) > 0:
            ans = 0
        elif nokori == 1 :
            ans = ans * m_list[0]
            del m_list[0]

        elif len(p_list) == 1 and len(p_list) == 1 and len(z_list) > 0:
            ans = 0
            nokori -= 2
        elif len(p_list) == 1 and len(p_list) == 1 and len(z_list) == 0:
            ans = ans * p_list[0] * m_list[len(m_list) -1]
            del p_list[0]
            del m_list[0]
            nokori -= 2
        else:
            if len(p_list) >= 2:
                pval = p_list[0] * p_list[1]
            else:
                pval = 0

            if len(m_list) >= 2:
                mval = m_list[0] * m_list[1]
            else:
                mval = 0

            if pval > mval:
                del p_list[0]
                del p_list[0]
                ans = ans * pval
            else:
                del m_list[0]
                del m_list[0]
                ans = ans * mval
            nokori -= 2

    print(ans % 1000000007)

if __name__ == '__main__':
    main()