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 sys

n, k = map(int, input().split())
a = [int(i) for i in input().split()]

if n == k:
    ans = 1
    for i in range(n):
        ans *=  a[i]
        ans %= 10**9 + 7
    
    print(ans)
    sys.exit()

plus = []
minus = []

for num in a:
    if num < 0:
        minus.append(num)
    else:
        plus.append(num)

plus.sort(reverse=True)
minus.sort()

if len(plus) == 0 and k % 2 == 1:
    ans = 1
    minus.sort(reverse=True)
    for i in range(k):
        ans *= minus[i]
        ans %= 10**9 + 7
        
    print(ans)
    sys.exit()
    
mi_cnt, pl_cnt = 0, 0
ans = 1
while mi_cnt + pl_cnt < k:
    if k < mi_cnt + pl_cnt + 2:
        #print(plus[pl_cnt])
        ans *= plus[pl_cnt]
        ans %= 10**9 + 7
        pl_cnt += 1
        break
    
    pl = plus[pl_cnt]
    mi = minus[mi_cnt] * minus[mi_cnt + 1]
    #print(pl, mi)
    
    if pl < mi:
        #print(mi)
        ans *= mi
        ans %= 10**9 + 7
        mi_cnt += 2
    else:
        #print(pl)
        ans *= pl
        ans %= 10**9 + 7
        pl_cnt += 1
        
print(ans)

Submission status: Runtime Error

Solution code:
import sys

n, k = map(int, input().split())
a = [int(i) for i in input().split()]

if n == k:
    ans = 1
    for i in range(n):
        ans *=  a[i]
        ans %= 10**9 + 7
    
    print(ans)
    sys.exit()

plus = []
minus = []

for num in a:
    if num < 0:
        minus.append(num)
    else:
        plus.append(num)

plus.sort(reverse=True)
minus.sort()

if len(plus) == 0 and k % 2 == 1:
    ans = 1
    minus.sort(reverse=True)
    for i in range(k):
        ans *= minus[i]
        ans %= 10**9 + 7
        
    print(ans)
    sys.exit()
    
mi_cnt, pl_cnt = 0, 0
ans = 1
while mi_cnt + pl_cnt < k:
    if k < mi_cnt + pl_cnt + 2:
        #print(plus[pl_cnt])
        ans *= plus[pl_cnt]
        ans %= 10**9 + 7
        pl_cnt += 1
        continue
    
    pl = plus[pl_cnt]
    mi = minus[mi_cnt] * minus[mi_cnt + 1]
    #print(pl, mi)
    
    if pl < mi:
        #print(mi)
        ans *= mi
        ans %= 10**9 + 7
        mi_cnt += 2
    else:
        #print(pl)
        ans *= pl
        ans %= 10**9 + 7
        pl_cnt += 1
        
print(ans)

Submission status: Runtime Error

Solution code:

def main():
  n, k = map(int, input().split())

  plus = []
  minus = []

  for num in input().split():
    num = int(num)
    if num >= 0:
      plus.append(num)
    else:
      minus.append(num)

  pn = len(plus)
  mn = len(minus)

  mod = 10 ** 9 + 7

  if pn == 0 and k % 2 == 1:
    minus.sort(reverse = True)
    ans = 1
    for i in range(k):
      ans = (-ans * minus[i]) % mod

    print((-ans) % mod)
    return


  plus.sort(reverse = True)
  minus.sort()

  pi = 0
  mi = 0

  while k > 0:
    if pi + 1 == pn:
      if k % 2 == 0:
        mi += k
      else:
        pi += 1
        mi += k - 1

      break

    if pi == pn:
      mi += k
      break

    if mi + 1 >= mn:
      pi += k
      break

    if k == 1 or plus[pi] * plus[pi + 1] >= minus[mi] * minus[mi + 1]:
      pi += 1
      k -= 1
    else:
      mi += 2
      k -= 2

  ans = 1
  for i in range(pi):
    ans = (ans * plus[i]) % mod

  for i in range(mi):
    ans = (-ans * minus[i]) % mod

  print(ans % mod)


main()

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
Ap=[]
Am=[]
Az=[]
for i in range(n):
    if A[i]>0:
        Ap.append(A[i])
    if A[i]<0:
        Am.append(A[i])
    if A[i]==0:
        Az.append(A[i])

for i in range(0,len(Am)-1):
    Am[i]*=Am[i+1]

Ap.sort(reverse = True)
cnt=0
cntp=0
cntm=0
ans=1
if len(Ap)!=0:
    while cnt!=k:
        if  cntm<len(Am) and Ap[cntp]<Am[cntm]:
            ans*=Am[cntm]
            cnt+=2
            cntm+=2
        elif cntp<len(Ap):
            ans*=Ap[cntp]
            cnt+=1
            cntp+=1
        elif cntp==len(Ap) and cntm>=len(Am):
            ans=0
            break
else:
    if k%2==0:
        while cnt!=k:
            ans*=Am[cnt]
            cnt+=2
    else:
        Am.sort()
        while cnt!=k+1:
            ans*=Am[cnt]
            cnt+=2

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

Submission status: Runtime Error

Solution code:

def main():
  n, k = map(int, input().split())

  plus = []
  minus = []

  for num in input().split():
    num = int(num)
    if num >= 0:
      plus.append(num)
    else:
      minus.append(num)

  pn = len(plus)
  mn = len(minus)

  mod = 10 ** 9 + 7

  if pn == 0 and k % 2 == 1:
    minus.sort(reverse = True)
    ans = 1
    for i in range(k):
      ans = (-ans * minus[i]) % mod

    print((-ans) % mod)
    return


  plus.sort(reverse = True)
  minus.sort()

  pi = 0
  mi = 0

  while k > 0:
    if pi + 1 == pn:
      if k % 2 == 0:
        mi += k
      else:
        pi += 1
        mi += k - 1

      break

    if pi == pn:
      mi += k
      break

    if mi + 1 >= mn:
      pi += k
      break

    if plus[pi] * plus[pi + 1] >= minus[mi] * minus[mi + 1]:
      pi += 1
      k -= 1
    else:
      mi += 2
      k -= 2

  ans = 1
  for i in range(pi):
    ans = (ans * plus[i]) % mod

  for i in range(mi):
    ans = (-ans * minus[i]) % mod

  print(ans % mod)


main()

Submission status: Runtime Error

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


    B = []
    flg_m = 0
    flg_p = 0

    for a in A:
        if a < 0:
            B.append([abs(a),-1])
            flg_m = 1
        else:
            B.append([abs(a),1])
            flg_p = 1

        b = 0
    ans = -10**9
    if k == 1:
        for a in A:
            ans = max(ans,a)
        print(ans)
        exit()

    B.sort(reverse=True)
    if flg_p == 0 and k%2 == 1:
        B.sort()
        L = B[:k]
        ans = cal_ans(L)
        ans *=-1
        print(ans%MOD)
        exit()
    elif flg_p * flg_m == 0:
        L = B[:k]
        ans = cal_ans(L)
        print(ans)
        exit()

    flg_p = 0
    flg_m = 0
    # print(B)
    for i,(n,sign) in enumerate(B):
        if i < k:
            if sign == -1:
                last_m = n
            else:
                last_p = n
        else:
            if sign == -1:
                if flg_m == 0:
                    first_m = n
                    flg_m = 1
            else:
                if flg_p == 0:
                    first_p = n
                    flg_p = 1

    L = B[:k]
    ans = cal_ans(L)
    c = 0
    for n,sign in L:
        if sign == -1:
            c += 1
    if c % 2 == 0:
        print(ans)
        exit()
    if flg_p == 1 and flg_m == 1:
        if first_p * last_p >= first_m*last_m:
            a = first_p
            b = last_m
        else:
            a = first_m
            b = last_p
    elif flg_p == 1:
            a = first_p
            b = last_m
    elif flg_m == 1:
            a = first_m
            b = last_p
    else:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
        print(ans)
        exit()


    ans *= a
    ans %= MOD
    ans *= pow(b,MOD-2,MOD)
    ans %= MOD
    print(ans)

def cal_ans(L):
    MOD = 10**9+7
    ans = 1
    for i,j in L:
        ans *= i
        ans %= MOD
    return ans



main()

Submission status: Runtime Error

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

cumsum = [1]
for a in A:
  cumsum.append(cumsum[-1]*a)

res = -10**16
for i in range(k, n+1):
  res = max(res, cumsum[i]//cumsum[i-k])

print(res%MOD)

Submission status: Runtime Error

Solution code:

def main():
  n, k = map(int, input().split())

  plus = []
  minus = []

  for n in input().split():
    n = int(n)
    if n >= 0:
      plus.append(n)
    else:
      minus.append(n)

  mod = 10 ** 9 + 7

  if len(plus) == 0 and k % 2 == 1:
    minus.sort(reverse=True)
    ans = 1
    for i in range(k):
      ans *= minus[i]

    print(ans % mod)
    return


  plus.sort(reverse = True)
  minus.sort()

  pn = 0
  mn = 0

  while k > 0:
    if pn + 1 == len(plus):
      pn += 1
      mn += k - 1
      break

    if pn == len(plus):
      mn += k
      break

    if mn + 1 >= len(minus):
      pn += k
      break

    if plus[pn] * plus[pn + 1] >= minus[mn] * minus[mn + 1]:
      pn += 1
      k -= 1
    else:
      mn += 2
      k -= 2

  ans = 1
  for i in range(pn):
    ans = (ans * plus[i]) % mod

  for i in range(mn):
    ans = (ans * (-minus[i])) % mod

  print(ans % mod)


main()

Submission status: Runtime Error

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    ans = 1
    ok = True
    plus = []
    minus = []
    for a in A:
        if a >= 0:
            ok = False
            plus.append(a)
        else:
            minus.append(a)
    
    if ok and N == K and K % 2 == 0:
        ok = False
    
    if ok:
        A.sort(reverse=True)
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    else:
        plus.sort(reverse=True)
        minus.sort()
        B = []
        if K % 2 == 0:
            for i in range(0,len(plus),2):
                if i + 1 < len(plus):
                    B.append(plus[i] * plus[i+1])
            for i in range(0,len(minus),2):
                if i + 1 < len(minus):
                    B.append(minus[i] * minus[i+1])
            B.sort(reverse=True)
            for i in range(K//2):
                ans *= B[i]
                ans %= MOD
        else:
            ans = plus.pop(0)
            for i in range(0,len(plus),2):
                if i + 1 < len(plus):
                    B.append(plus[i] * plus[i+1])
            for i in range(0,len(minus),2):
                if i + 1 < len(minus):
                    B.append(minus[i] * minus[i+1])
            B.sort(reverse=True)
            for i in range(K//2):
                ans *= B[i]
                ans %= MOD

    print(ans)
            



if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

    B = []
    flg_m = 0
    flg_p = 0
    for a in A:
        if a < 0:
            B.append([abs(a),-1])
            flg_m = 1
        else:
            B.append([abs(a),1])
            flg_p = 1

    B.sort(reverse=True)
    if flg_p == 0 and k%2 == 1:
        B.sort()
        L = B[:k]
        ans = cal_ans(L)
        ans *=-1
        print(ans%MOD)
        exit()
    elif flg_p * flg_m == 0:
        L = B[:k]
        ans = cal_ans(L)
        print(ans)
        exit()

    flg_p = 0
    flg_m = 0
    # print(B)
    for i,(n,sign) in enumerate(B):
        if i < k:
            if sign == -1:
                last_m = n
            else:
                last_p = n
        else:
            if sign == -1:
                if flg_m == 0:
                    first_m = n
                    flg_m = 1
            else:
                if flg_p == 0:
                    first_p = n
                    flg_p = 1

    L = B[:k]
    ans = cal_ans(L)
    c = 0
    for n,sign in L:
        if sign == -1:
            c += 1
    if c % 2 == 0:
        print(ans)
        exit()
    if flg_p == 1 and flg_m == 1:
        if first_p * last_p >= first_m*last_m:
            a = first_p
            b = last_m
        else:
            a = first_m
            b = last_p
    elif flg_p == 1:
            a = first_p
            b = last_m
    elif flg_m == 1:
            a = first_m
            b = last_p
    else:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
        print(ans)
        exit()


    ans *= a
    ans %= MOD
    ans *= pow(b,MOD-2,MOD)
    ans %= MOD
    print(ans)

def cal_ans(L):
    MOD = 10**9+7
    ans = 1
    for i,j in L:
        ans *= i
        ans %= MOD
    return ans



main()

Submission status: Runtime Error

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

    B = []
    flg_m = 0
    flg_p = 0
    for a in A:
        if a < 0:
            B.append([abs(a),-1])
            flg_m = 1
        else:
            B.append([abs(a),1])
            flg_p = 1

    B.sort(reverse=True)
    if flg_p == 0 and k%2 == 1:
        B.sort()
        L = B[:k]
        ans = cal_ans(L)
        ans *=-1
        print(ans%MOD)
        exit()
    elif flg_p * flg_m == 0:
        L = B[:k]
        ans = cal_ans(L)
        print(ans)
        exit()

    flg_p = 0
    flg_m = 0
    # print(B)
    for i,(n,sign) in enumerate(B):
        if i < k:
            if sign == -1:
                last_m = n
            else:
                last_p = n
        else:
            if sign == -1:
                if flg_m == 0:
                    first_m = n
                    flg_m = 1
            else:
                if flg_p == 0:
                    first_p = n
                    flg_p = 1

    L = B[:k]
    ans = cal_ans(L)
    c = 0
    for n,sign in L:
        if sign == -1:
            c += 1
    if c % 2 == 0:
        print(ans)
        exit()
    if flg_p == 1 and flg_m == 1:
        if first_p * last_p >= first_m*last_m:
            a = first_p
            b = last_m
        else:
            a = first_m
            b = last_p
    elif flg_p == 1:
            a = first_p
            b = last_m
    elif flg_m == 1:
            a = first_m
            b = last_p

    ans *= a
    ans %= MOD
    ans *= pow(b,MOD-2,MOD)
    ans %= MOD
    print(ans)

def cal_ans(L):
    MOD = 10**9+7
    ans = 1
    for i,j in L:
        ans *= i
        ans %= MOD
    return ans



main()

Submission status: Runtime Error

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k = MAP()

a = LIST()

pos = []
neg = []
zero = []

for el in a:
    if(el<0):
        neg.append(el)
    elif(el>0):
        pos.append(el)
    else:
        zero.append(el)

pos = sorted(pos)[::-1]
neg = sorted(neg)[::-1]

ans = 1

if(k==n):
    for el in a:
        ans = (ans%mod*el%mod)%mod
else:

    if(len(pos)==0):
        if(k%2==0):
            temp = 0
            for i in range(len(neg)-1, -1, -1):
                if(temp==k):
                    break
                ans = (ans%mod*neg[i]%mod)%mod
                temp+=1
            if(temp<k):
                ans = 0
        else:
            temp = 0
            for i in range(len(neg) - 1):
                if (temp == k):
                    break
                ans = (ans%mod * neg[i]%mod) % mod
                temp += 1
            if (temp < k):
                ans = 0
    else:

        if(k%2==0):

            left = k

            i,j = 0, len(neg)-1

            while(left>0):
                temp, temp1 = 0, 0
                if(i<len(pos)-1):
                    temp = pos[i]*pos[i+1]
                    # i+=2
                if(j>=1):
                    temp1 = neg[j]*neg[j-1]
                    # j-=2
                if(temp==0 and temp1==0):
                    break
                if(temp1>temp):
                    ans = (ans*(temp1%mod))%mod
                    j-=2
                else:
                    ans = (ans*(temp%mod))%mod
                    i+=2
                left -= 2
            if(left>0):
                ans = 0

        else:
            prefPos = [pos[0]]

            for i in range(1, len(pos)):
                prefPos.append((pos[i]*prefPos[i-1])%mod)

            neg = neg[::-1]

            prefNeg = [neg[0]]

            for i in range(1, len(neg)):
                prefNeg.append((neg[i]*prefNeg[i-1])%mod)


            ans = prefPos[0]

            flag = 0

            for i in range(1, len(prefNeg), 2):
                if(k-i-2>=0 and k-i-2<len(pos)):
                    ans = max(ans, prefNeg[i]*prefPos[k-i-2])%mod
                else:
                    flag = 1
                    break
                # print(ans)
            if(flag==1):
                ans = 0
        # print(prefPos, prefNeg)
print(ans)

Submission status: Runtime Error

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k = MAP()

a = LIST()

pos = []
neg = []
zero = []

for el in a:
    if(el<0):
        neg.append(el)
    elif(el>0):
        pos.append(el)
    else:
        zero.append(el)

pos = sorted(pos)[::-1]
neg = sorted(neg)[::-1]

ans = 1

if(k==n):
    for el in a:
        ans = (ans%mod*el%mod)%mod
else:

    if(len(pos)==0):
        if(k%2==0):
            temp = 0
            for i in range(len(neg)-1, -1, -1):
                if(temp==k):
                    break
                ans = (ans%mod*neg[i]%mod)%mod
                temp+=1
            if(temp<k):
                ans = 0
        else:
            temp = 0
            for i in range(len(neg) - 1):
                if (temp == k):
                    break
                ans = (ans%mod * neg[i]%mod) % mod
                temp += 1
            if (temp < k):
                ans = 0
    else:

        if(k%2==0):

            left = k

            i,j = 0, len(neg)-1

            while(left>0):
                temp, temp1 = 0, 0
                if(i<len(pos)-1):
                    temp = pos[i]*pos[i+1]
                    # i+=2
                if(j>=1):
                    temp1 = neg[j]*neg[j-1]
                    # j-=2
                if(temp==0 and temp1==0):
                    break
                if(temp1>temp):
                    ans = (ans*(temp1%mod))%mod
                    j-=2
                else:
                    ans = (ans*(temp%mod))%mod
                    i+=2
                left -= 2
            if(left>0):
                ans = 0

        else:
            prefPos = [pos[0]]

            for i in range(1, len(pos)):
                prefPos.append((pos[i]*prefPos[i-1])%mod)

            neg = neg[::-1]

            prefNeg = [neg[0]]

            for i in range(1, len(neg)):
                prefNeg.append((neg[i]*prefNeg[i-1])%mod)


            ans = prefPos[0]

            for i in range(1, len(prefNeg), 2):
                ans = max(ans, prefNeg[i]*prefPos[k-i-2])%mod
                # print(ans)

        # print(prefPos, prefNeg)
print(ans)

Submission status: Runtime Error

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

    B = []
    flg_m = 0
    flg_p = 0
    for a in A:
        if a < 0:
            B.append([abs(a),-1])
            flg_m = 1
        else:
            B.append([abs(a),1])
            flg_p = 1

    B.sort(reverse=True)
    if flg_p == 0 and k%2 == 1:
        B.sort()
        L = B[:k]
        ans = cal_ans(L)
        ans *=-1
        print(ans%MOD)
        exit()
    elif flg_p * flg_m == 0:
        L = B[:k]
        ans = cal_ans(L)
        print(ans)
        exit()

    flg_p = 0
    flg_m = 0
    # print(B)
    for i,(n,sign) in enumerate(B):
        if i < k:
            if sign == -1:
                last_m = n
            else:
                last_p = n

        else:
            if sign == -1:
                if flg_m == 0:
                    first_m = n
                    flg_m = 1
            else:
                if flg_p == 0:
                    first_p = n
                    flg_p = 1

    L = B[:k]
    ans = cal_ans(L)
    c = 0
    for n,sign in L:
        if sign == -1:
            c += 1
    if c % 2 == 0:
        print(ans)
        exit()

    if first_p * last_p >= first_m*last_m:
        a = first_p
        b = last_m
    else:
        a = first_m
        b = last_p

    ans *= a
    ans %= MOD
    ans *= pow(b,MOD-2,MOD)
    ans %= MOD
    print(ans)

                


def cal_ans(L):
    MOD = 10**9+7
    ans = 1
    for i,j in L:
        ans *= i
        ans %= MOD
    return ans



main()

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
m,p=[],[]
pr=10**9+7
z=0
for i in A:
    if i>=0:
        p.append(i)
    elif i:
        m.append(i)
    else:
        z+=1
lm=len(m)
m.sort()
p.sort(reverse=1)
lp=len(p)
if N==K:
    a=1
    for i in A:
        a=a*i%pr
    print(a)
    exit()
mm,pp=[],[]
for i in range(1,lm,2):
    mm.append((m[i-1]*m[i],0,i))
for i in range(1,lp,2):
    pp.append((p[i-1]*p[i],1,i))
l=mm+pp
l.sort(reverse=1)
def gya(n):
    return pow(n,pr-2,pr)
mt,pt=-1,-1
a=1
if len(l)*2>=K:
    for i in l[:K//2]:
        a=a*i[0]%pr
        if i[1]:
            pt=i[2]
        else:
            mt=i[2]
    if K%2:
        if pt<lp-1:
            a=a*p[pt+1]%pr
        elif pt==-1:
            a=1
            m=m[::-1]
            for i in m[:K]:
                a=a*i%pr
        else:
            a=a*gya(p[pt])*m[mt+1]*m[mt+2]%pr
else:
    for i in l:
        a=a*i[0]%pr
        if i[1]:
            pt=i[2]
        else:
            mt=i[2]
    a=a*p[pt+1]%pr
print(a)

Submission status: Runtime Error

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

    B = []
    flg_m = 0
    flg_p = 0
    for a in A:
        if a < 0:
            B.append([abs(a),-1])
            flg_m = 1
        else:
            B.append([abs(a),1])
            flg_p = 1

    B.sort(reverse=True)
    if flg_p == 0 and k%2 == 1:
        B.sort()
        L = B[:k]
        ans = cal_ans(L)
        ans *=-1
        print(ans%MOD)
        exit()
    elif flg_p * flg_m == 0:
        L = B[:k]
        ans = cal_ans(L)
        print(ans)
        exit()

    flg_p = 0
    flg_m = 0
    for i,(n,sign) in enumerate(B):
        if i < k:
            if sign == -1:
                last_m = n
            else:
                last_p = n

        else:
            if sign == -1:
                if flg_m == 0:
                    first_m = n
                    flg_p = 1
            else:
                if flg_p == 0:
                    first_p = n
                    flg_p = 1

    L = B[:k]
    ans = cal_ans(L)
    c = 0
    for n,sign in L:
        if sign == -1:
            c += 1
    if c % 2 == 0:
        print(ans)
        exit()

    if first_p * last_p >= first_m*last_m:
        a = first_p
        b = last_m
    else:
        a = first_m
        b = last_p

    ans *= a
    ans %= MOD
    ans *= pow(b,MOD-2,MOD)
    ans %= MOD
    print(ans)

                


def cal_ans(L):
    MOD = 10**9+7
    ans = 1
    for i,j in L:
        ans *= i
        ans %= MOD
    return ans



main()

Submission status: Runtime Error

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N,K = LMIIS()
    A = LMIIS()
    positive = []
    negative = []
    zero = []
    for a in A:
        if a >0:
            positive.append(a)
        elif a == 0:
            zero.append(a)
        else:
            negative.append(a)
    positive.sort(reverse=True)
    negative.sort()
    ans = 1
    num_used = 0
    num_used_negative = 0

    if len(positive) + len(negative) < K:
        print(0)
        return

    necessary_negative = K-len(positive)
    if len(positive) >= K or necessary_negative %2 == 0:

        if len(positive) >= 2:
            comp = positive[0] * positive[1]
        else:
            comp = positive[0]
        
        for i in range(0,min(len(negative)//2,K//2)):
            if negative[i*2] * negative[i*2+1] >= comp or num_used + len(positive) < K:
                ans = ans * negative[i*2] * negative[i*2+1] % P
                num_used += 2
            else:
                break
        for i in range(K-num_used):
            ans = ans * positive[i] % P
            num_used += 1
        print(ans)
        return
    else:

        #答えが負
        if zero:
            print(0)
            return
        ans = 1
        for a in positive:
            ans = ans * a % P
        negative = negative[::-1]
        for i in range(K-len(positive)):
            ans = ans * negative[i] % P
        print(ans)
        return
                



    
main()

Submission status: Runtime Error

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N,K = LMIIS()
    A = LMIIS()
    positive = []
    negative = []
    zero = []
    for a in A:
        if a >0:
            positive.append(a)
        elif a == 0:
            zero.append(a)
        else:
            negative.append(a)
    positive.sort(reverse=True)
    negative.sort()
    ans = 1
    num_used = 0
    num_used_negative = 0

    if len(positive) + len(negative) < K:
        print(0)
        return

    necessary_negative = K-len(positive)
    if len(positive) >= K or necessary_negative %2 == 0:

        if len(positive) >= 2:
            comp = positive[0] * positive[1]
        else:
            comp = positive[0]
        
        for i in range(0,min(len(negative)//2,K//2)):
            if negative[i*2] * negative[i*2+1] >= comp or num_used + len(positive) < K:
                ans = ans * negative[i] * negative[i+1] % P
                num_used += 2
            else:
                break
        for i in range(K-num_used):
            ans = ans * positive[i] % P
            num_used += 1
        print(ans)
        return
    else:

        #答えが負
        if zero:
            print(0)
            return
        ans = 1
        for a in positive:
            ans = ans * a % P
        negative = negative[::-1]
        for i in range(K-len(positive)):
            ans = ans * negative[i] % P
        print(ans)
        return
                



    
main()

Submission status: Runtime Error

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

s = []  # v >= 0
t = []  # v < 0
for i in range(N):
    if A[i] < 0:
        t.append(A[i])
    else:
        s.append(A[i])
        
ok = False
if len(s) > 0:
    if N == K:
        ok = len(t) % 2 == 0
    else:
        ok = True
else:
    ok = K % 2 == 0

ans = 1
if not ok:
    x = sorted(abs(v) for v in A)
    for i in range(L):
        ans = ans * x[i] % MOD
else:
    s.sort()
    t.sort()
    if K % 2 == 1:
        ans = ans * s.pop() % MOD
        
    p = []
    while len(s) >= 2:
        x = s.pop() * s.pop() % MOD
        p.append(x)
    
    while len(t) >= 2:
        x = t.pop() * t.pop() % MOD
        p.append(x)
        
    p.sort(reverse=True)
    for i in range(K // 2):
        ans *= p[i]
    
print(ans)