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


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= mod
        return ans

    neg = []
    pos = []
    for a in A:
        if a > 0:
            pos.append(a)
        elif a < 0:
            neg.append(a)
    if K > len(pos) + len(neg):
        return 0
    pos.sort()
    neg.sort(reverse=True)
    print(pos)
    print(neg)

    if len(neg) == N:
        res = 1
        for i in range(K):
            res *= neg[i]
            res %= mod
        return res

    ans = 1

    if K & 1:
        ans *= pos.pop()
        K -= 1
    # この時点でKは偶数
    while K > 1 and len(pos) > 1 and len(neg) > 1:
        K -= 2
        if pos[-1] * pos[-2] > neg[-1] * neg[-2]:
            ans *= pos.pop()
            ans *= pos.pop()
            ans %= mod
        else:
            ans *= neg.pop()
            ans *= neg.pop()
            ans %= mod
    while K > 1 and len(pos) > 1:
        K -= 2
        ans *= pos.pop()
        ans %= mod
        ans *= pos.pop()
        ans %= mod
    while K > 1 and len(neg) > 1:
        K -= 2
        ans *= neg.pop()
        ans %= mod
        ans *= neg.pop()
        ans %= mod
    return ans


if __name__ == "__main__":
    print(main())

Submission status: Runtime Error

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
mod=10**9+7
A.sort(reverse=True,key=lambda x:abs(x))

if min(A)>0:
  ans=1
  for i in range(k):
    ans=(ans*A[i])%mod
  print(ans)
elif max(A)<0:
  ans=1
  if k%2==0:
    for i in range(k):
      ans=(ans*A[i])%mod
    print(ans)
  else:
    for i in range(k):
      ans=(ans*A[n-1-i])%mod
    print(ans)
else:
  L1,L2,R1,R2=[],[],[],[]
  ct=0
  for a in A:
    if a==0:
      continue
    if ct<k:
      if a>0:
        L1.append(a)
      elif a<0:
        L2.append(a)
      ct+=1
    else:
      if a>0:
        R1.append(a)
      elif a<0:
        R2.append(a)
  if ct<k:
    print(0)
  else:
    if not L1:
      if k%2==1:
        c=R1[0]
        ans=1
        for i in range(len(L2)-1):
          ans=(ans*L2[i])%mod
        ans=(ans*c)%mod
        print(ans)
      else:
        ans=1
        for i in range(len(L2)):
          ans=(ans*L2[i])%mod
        print(ans)
    elif not L2:
      ans=1
      for i in range(len(L1)):
        ans=(ans*L1[i])%mod
      print(ans)
    else:
      if len(L2)%2==0:
        ans=1
        for a in L1:
          ans=(ans*a)%mod
        for a in L2:
          ans=(ans*a)%mod
        print(ans)
      else:
        if not R1:
          if not R2:
            if 0 in A:
              print(0)
            else:
              ans=1
              ans=1
              for a in L1:
                ans=(ans*a)%mod
              for a in L2:
                ans=(ans*a)%mod
              print(ans)
          else:
            d=-R2[0]
            ans=d
            for i in range(len(L1)-1):
              ans=(ans*L1[i])%mod
            for i in range(len(L2)):
              ans=(ans*L2[i])%mod
            print(ans)
        else:
          c=R1[0]
          a=L1[-1]
          b=L2[-1]
          if R2 and R2[0]*b>a*c:
            ans=R2[0]
            for i in range(len(L1)-1):
              ans=(ans*L1[i])%mod
            for i in range(len(L2)):
              ans=(ans*L2[i])%mod
            print(ans)
          else:
            ans=c
            for i in range(len(L1)):
              ans=(ans*L1[i])%mod
            for i in range(len(L2)-1):
              ans=(ans*L2[i])%mod
            print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 1
mod = 10**9 + 7
c = 0
z = 0
for i in a:
    if i < 0:
        c += 1
    elif i == 0:
        z += 1
if c == n and k & 1:
    a.reverse()
    for i in range(k):
        ans *= -a[i]
        ans %= mod
    print(-ans % mod)
elif c == n:
    for i in range(k):
        ans *= -a[i]
        ans %= mod
    print(ans)
else:
    plus = [i for i in a if i > 0]
    minus = [i for i in a if i <= 0]
    plus.sort(reverse=1)
    minus.sort()
    x = len(plus)
    y = len(minus)
    plus += [0] * z
    p, m = 0, 0
    for i in range(k // 2):
        if x - 1 <= p:
            ans *= minus[m] * minus[m + 1]
            m += 2
        elif y - 1 <= m:
            ans *= plus[p] * plus[p + 1]
            p += 2
        else:
            if minus[m] * minus[m + 1] >= plus[p] * plus[p + 1]:
                ans *= minus[m] * minus[m + 1]
                m += 2
            else:
                ans *= plus[p] * plus[p + 1]
                p += 2
        ans %= mod
    if k & 1:
        if p < x:
            ans *= plus[p]
        else:
            ans *= minus[-1]
        ans %= mod

    print(ans % mod)

Submission status: Runtime Error

Solution code:
def max_product(arr, n, k):
    max_p=1
    for i in range(0, k):
        max_p = max_p * arr[i]
    prev = max_p
    for i in range(1, n - k + 1):
        curr = (prev//arr[i-1])*arr[i+k-1]
        max_p = max(max_p, curr)
        prev = curr
    return max_p

n,k=[int(x) for x in input().split()]
arr=[int(x) for x in input().split()]
print(max_product(arr,n,k)%1000000007)

Submission status: Runtime Error

Solution code:
import heapq
from functools import reduce

MOD = 10**9+7
n, k = map(int, input().split())
a = list(map(int, input().split()))
plus = [i for i in a if i > 0]
plus.sort(reverse=True)
minus = [i for i in a if i < 0]
minus.sort(reverse=True)
zero = [i for i in a if i == 0]

res = 1
if len(plus) + len(minus) < k:
    res = 0
    print(res % MOD)
    exit()
elif len(minus) == 0:
    res = reduce(lambda a,b: a*b, plus[:k])
    print(res%MOD)
    exit()
elif len(plus) == 0:
    if k % 2 == 0:
        res = reduce(lambda a, b: a*b, minus[-k:])
        print(res%MOD)
        exit()
    else:
        if len(zero) > 0:
            res = 0
        else:
            res = reduce(lambda a,b: a*b, minus[:k])
        print(res%MOD)
        exit()
else:
    plus = [-i for i in plus]
    heapq.heapify(plus)
    heapq.heapify(minus)
    c_p = []
    c_m = []
    last_p = False
    while len(c_p)+len(c_m) < k:
        can_p = heapq.heappop(plus)
        can_m = heapq.heappop(minus)
        if can_p < can_m:
            heapq.heappush(c_p, -can_p)
            last_p = True
        else:
            heapq.heappush(c_m, -can_m)
            last_p = False
    if len(c_m) % 2 == 0:
        res = reduce(lambda a, b: a * b, c_p, 1) * reduce(lambda a, b: a * b, c_m, 1)
        print(res % MOD)
        exit()
    if last_p:
        # 最大の負を入れる/一番小さい負を除いて最大の正を入れる
        if len(minus) > 0:
            heapq.heappop(c_p)
            can_m = heapq.heappop(minus)
            heapq.heappush(c_m, -can_m)
        else:
            heapq.heappop(c_m)
            can_p = heapq.heappop(plus)
            heapq.heappush(c_p, -can_p)
    else:
        # 最大の正を入れる/一番小さい正を除いて最大の負を入れる
        if len(plus) > 0:
            heapq.heappop(c_m)
            can_p = heapq.heappop(plus)
            heapq.heappush(c_p, -can_p)
        else:
            heapq.heappop(c_p)
            can_m = heapq.heappop(minus)
            heapq.heappush(c_m, -can_m)
    res = reduce(lambda a, b: a * b, c_p, 1) * reduce(lambda a, b: a * b, c_m, 1)
    print(res % MOD)

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7


class modint():
    """
    MODはクラスの上で宣言しておく
    """

    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    posi = [a for a in A if a > 0]
    nega = [a for a in A if a < 0]
    posi.sort(reverse=True)
    nega.sort(reverse=True)
    A.sort(reverse=True, key=abs)
    if len(posi) + len(nega) < K:
        # 0を含まなければいけないとき
        return print(0)

    ans = modint(1)
    if K % 2 == 1 and len(posi) < K:
        # 結果が負数
        # 絶対値が小さいやつをK個取ってくる
        A.sort(key=abs)
        for a in A[:K]:
            ans *= a
    else:
        # 結果が正になるように注意しなければいけない
        # skipしてかけるものがなくなったらこわい
        # 負数がK以下の奇数個しかないとハマる
        if sum(a < 0 for a in A[:K]) % 2 == 0:
            for a in A[:K]:
                ans *= a
        else:
            ans1 = modint(1)
            ans2 = modint(1)
            p_remove = False
            for a in A[:K][::-1]:
                if a > 0 and not p_remove:
                    p_remove = True
                    continue
                ans1 *= a
            n_remove = False
            for a in A[:K][::-1]:
                if a > 0 and not n_remove:
                    n_remove = True
                    continue
                ans2 *= a
                break
            mul1 = 0
            mul2 = 0
            for a in A[K:]:
                if mul1 == 0 and a > 0:
                    mul1 = a
                if mul2 == 0 and a < 0:
                    mul2 = a
                if mul1 != 0 and mul2 != 0:
                    break
            ans1 *= mul1
            ans2 *= mul2
            ans = max(ans1, ans2)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = tuple(sorted(map(int, input().split()), key=abs, reverse=True))
P = tuple(i for i in A if i >= 0)
result = 1
for i in range(K):
  result *= A[i]
if result < 0:
  if P:
    result //= A[K-1]
    result *= P[K-1]
  else:
    result = 1
    RA = sorted(A, reverse=True)
    for i in range(K):
      result *= RA[i]
print(result % (10**9 + 7))

Submission status: Runtime Error

Solution code:
import sys
N,K=[int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]

plus=[]
minus=[]
for a in A:
    if a>0:
        plus.append(a)
    elif a<0:
        minus.append(a)

if len(plus)+len(minus)<K:
    print(0)
    sys.exit(0)

if len(plus)==0:
    minus=sorted(minus,reverse=True)
    retval=1
    for i in minus[:K]:
        retval*=i
    print(retval%(10**9+7))
    sys.exit(0)


plus=sorted(plus,reverse=True)
minus=sorted(minus)

A=sorted(A,key=lambda w:abs(w),reverse=True)

retval=1
use_minus=0
for i in range(K):
    a=A[i]
    if a<0:
        use_minus+=1
    retval*=a
    retval=retval%(10**9+7)

if use_minus%2==0:
    print(retval%(10**9+7))
else:
    inv=pow(minus[use_minus-1],10**9+5,10**9+7)
    retval*=inv
    use_plus=K-use_minus
    retval=retval*plus[use_plus]
    print(retval%(10**9+7))

Submission status: Runtime Error

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

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

Mi = []
for a in A:
    if a != 0:
        Mi.append((abs(a), a//abs(a)))

Mi.sort(reverse=True)

if len(Mi) < K:
    ans = 0
else:
    ans = 1
    seg = 1
    lastinv = -1
    lastpu = -1
    for i in range(K):
        a, iv = Mi[i]
        seg *= iv
        if iv == -1:
            lastinv = a
        else:
            lastpu = a
        ans = ans * a % mod

    if seg == -1:
        fpu = -1
        fmi = -1
        ind = K
        while ind < len(Mi):
            a, iv = Mi[ind]
            ind += 1
            if iv == -1:
                if fmi == -1:
                    fmi = a
            else:
                if fpu == -1:
                    fpu = a
        
        if lastpu == -1:
            raise Exception
            if fpu != -1:
                ans = ans * fpu * pow(lastinv, mod-2, mod) % mod
            elif 0 in A:
                ans = 0
            else:
                ans = -1
                for i in range(K):
                    ans = ans * Mi[-i-1][0] % mod
        elif fpu == -1 or fmi == -1:
            if fpu == -1 and fmi == -1:
                if 0 in A:
                    ans = 0
                else:
                    ans = -ans
            elif fpu == -1:
                ans = ans * fmi * pow(lastpu, mod-2, mod) % mod
            else:
                ans = ans * fpu * pow(lastinv, mod-2, mod) % mod
        elif lastpu * fpu > lastinv * fmi:
            ans = ans * fpu * pow(lastinv, mod-2, mod) % mod
        else:
            ans = ans * fmi * pow(lastpu, mod-2, mod) % mod
    
    print(ans % mod)

Submission status: Runtime Error

Solution code:
N,K = map(int, input().split())
A = list(map(int, input().split()))
APlus = []
AMinus = []
for i in A:
    if 0 < i:
        APlus.append(i)
    elif 0 == i:
        pass
    elif i < 0:
        AMinus.append(i)
APlusBackup = APlus = sorted(APlus)
AMinusBackup = AMinus = sorted(AMinus)
count = 0
answer = 1
while count < K:
    if count + 1 < K and 1 < len(APlus) and 1 < len(AMinus):
        if AMinus[0] * AMinus[1] < APlus[0] * APlus[1]:
            answer = answer * APlus.pop(0)
            answer = answer * APlus.pop(0)
            count += 2
        elif APlus[0] * APlus[1] < AMinus[0] * AMinus[1]:
            answer = answer * AMinus.pop(0)
            answer = answer * AMinus.pop(0)
            count += 2
        elif AMinus[0] * AMinus[1] == APlus[0] * APlus[1]:
            if count + 2 < K:
                if AMinus[2] <= APlus[2]:
                    answer = answer * APlus.pop(0)
                    answer = answer * APlus.pop(0)
                    count += 2
                else:
                    answer = answer * AMinus.pop(0)
                    answer = answer * AMinus.pop(0)
                    count += 2
    else:
        try:
            answer = answer * APlus.pop(0)
            count += 1
        except:
            count = 0
            answer = 1
            APlus = sorted(APlusBackup, reverse = True)
            AMinus = sorted(AMinusBackup, reverse = True)
            while count < K:
                try:
                    if APlus[0] < AMinus[0]:
                        answer = answer * APlus.pop(0)
                        count += 1
                    elif AMinus[0] < APlus[0]:
                        answer = answer * AMinus.pop(0)
                        count += 1
                    elif APlus[0] == AMinus[0]:
                        if 1 < len(APlus) and 1 < len(AMinus):
                            if APlus[1] <= AMinus[1]:
                                answer = answer * APlus.pop(0)
                                count += 1
                            else:
                                answer = answer * AMinus.pop(0)
                                count += 1
                        else:
                            answer = answer * APlus.pop(0)
                            count += 1
                except:
                    answer = answer * AMinus.pop(0)
                    count += 1
answer = answer % (10 ** 9 + 7)
print(answer)

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
am = []
ap = []
for ai in a:
    if ai > 0:
        ap.append(ai)
    elif ai < 0:
        am.append(-ai)
am.sort(reverse=True)
ap.sort(reverse=True)

nm = len(am)
np = len(ap)
nz = n - np - nm
# print(am)
# print(ap)

if np + nm < k:
    ans = 0
elif np == 0:
    if k % 2 == 1:
        am.sort()
        ans = -1
        for i in range(k):
            ans *= am[i]
            ans %= MOD
    else:
        ans = 1
        for i in range(k):
            ans *= am[i]
            ans %= MOD
elif np < k:
    if (k - np) % 2 == 1:
        idx1 = np - 1
        idx2 = k - np + 1
    else:
        idx1 = np
        idx2 = k - np

    while idx1 >= 2 and idx2 + 1 < nm and \
        ap[idx1 - 1] * ap[idx1 - 2] < am[idx2] * am[idx2 + 1]:
        idx1 -= 2
        idx2 += 2
    ans = 1
    for i in range(idx1):
        ans *= ap[i]
        ans %= MOD
    for i in range(idx2):
        ans *= am[i]
        ans %= MOD
else:
    idx1 = k
    idx2 = 0
    while idx1 >= 2 and idx2 + 1 < nm and \
        ap[idx1 - 1] * ap[idx1 - 2] < am[idx2] * am[idx2 + 1]:
        idx1 -= 2
        idx2 += 2
    ans = 1
    for i in range(idx1):
        ans *= ap[i]
        ans %= MOD
    for i in range(idx2):
        ans *= am[i]
        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

p = []
m = []
for i in a:
    if i > 0:p.append(i)
    elif i < 0:p.append(i)

p.sort(reverse=True)
m.sort()
double = []

for i in range(len(p) - 1):
    if i % 2 == 0:
        temp = p[i] * p[i + 1]
        double.append([temp, 1])
for i in range(len(m) - 1):
    if i % 2 == 0:
        temp = m[i] * m[i + 1]
        double.append([temp, 2])

double.sort(reverse=True)
res = 1
flag = 0
while k:
    if double and k - 2 >= 0:
        temp, ind = double.pop(0)
        if ind == 1:
            p.pop(0)
            p.pop(0)
        else:
            m.pop(0)
            m.pop(0)
        res = (res * temp) % mod
        k -= 2
    else:
        if p:
            res = (res * p.pop(0)) % mod
        else:
            res = (res * m.pop(0)) % mod
        k -= 1
        
print(res)

Submission status: Runtime Error

Solution code:
def inv_mod(a, p=10**9+7):
    p = abs(p)
    a %= p
    stack = []
    p0 = p
    while a > 1:
        d, a, p = p//a, p%a, a
        stack.append(d)
    x, y = 1, 0
    while stack:
        d = stack.pop()
        x, y = y-d*x, x
    return x % p0
MOD = 10**9 + 7
inpl = lambda: list(map(int,input().split()))
N, K = inpl()
A = inpl()
if K % 2:
    A.sort(reverse=True)
    if A[0] < 0:
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD
        print(ans)
        exit()
    elif A[0] == 0:
        print(0)
        exit()

A.sort(key=abs, reverse=True)
lastplus = None
lastminus = None
ans = 1
sign = 1
for i in range(K):
    ans *= A[i]
    ans %= MOD
    if A[i] > 0:
        lastplus = i
    elif A[i] < 0:
        lastminus = i
        sign *= -1
    else:
        print(0)
        exit()
if sign == 1:
    print(ans)
else:
    firstplus = firstminus = N
    for i in range(K,N):
        if A[i] > 0 and firstplus > i:
            firstplus = i
            if firstminus < N:
                break
        elif A[i] < 0 and firstminus > i:
            firstminus = i
            if firstplus < N:
                break
        else:
            break
    if lastplus is not None and firstminus < N:
        ac = abs(A[lastplus]*A[firstminus])
    else:
        ac = -1
    if firstplus is not None and lastminus < N:
        bd = abs(A[firstplus]*A[lastminus])
    else:
        bd = -1
    if ac < 0 and bd < 0:
        pass
    elif bd >= ac:
        ans *= inv_mod(A[lastplus]) * A[firstminus] * (-1)
    else:
        ans *= inv_mod(A[lastminus]) * A[firstplus] * (-1)
    ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
arr = sorted(list(map(int,stdin.readline().split())),key=lambda x:abs(x))
mod = 10**9+7
pos,neg = [],[]
for i in arr:
    if i>=0:
        pos.append(i)
    else:
        neg.append(i)
if not len(pos):
    ans = 1
    if k%2:
        for i in range(k):
            ans *= neg[i]
            ans %= mod
    else:
        for i in range(k):
            ans *= neg[-1-i]
            ans %= mod
else:
    ans = 1
    i=len(pos)-1
    j=len(neg)-1
    pro = 1
    for r in range(k):
        pro *= pos[i]
        pro %= mod
        i -= 1
    ans = max(ans,pro)
    while i < len(pos)-1 and j > 0:
        if neg[j]*neg[j-1]>pos[i]*pos[i+1]:
            pro *= pow(pos[i]*pos[i+1],mod-2,mod)
            pro %= mod
            pro *= neg[j]*neg[j-1]
            pro %= mod
            ans = max(ans,pro)
            i += 2
            j -= 2
        else:
            break
print(ans)

Submission status: Runtime Error

Solution code:
Q = int(1e9 + 7)
N, K = map(int, input().split())
A = list(map(int, input().split()))

A = sorted(A)

if K == N:
    ans = 1
    for a in A:
        ans *= a
        ans %= Q
    print(ans)
    exit()
elif K == 1:
    ans = A[-1] % Q
    print(ans)
    exit()

A_mi, A_0, A_pl = [], [], []
for a in A:
    if a > 0:
        A_pl.append(a)
    elif a < 0:
        A_mi.append(a)
    else:
        A_0.append(a)

#答えが必ず0
if len(A_mi) + len(A_pl) < K:
    print(0)
    exit()

#全て正
if N == len(A_pl):
    ans, c = 1, 0
    for a in reversed(A_pl):
        ans *= a
        ans %= Q
        c += 1
        if c == K:
            break
    print(ans)
    exit()

#全て負or0
if N == len(A_mi) + len(A_0):
    if K % 2 == 0:
        ans, c = 1, 0
        for a in A_mi:
            ans *= a
            ans %= Q
            c += 1
            if c == K:
                break
        print(ans)
        exit()
    else:
        if len(A_0) > 0:
            print(0)
            exit()
        else:
            ans, c = 1, 0
            for a in reversed(A_mi):
                ans *= a
                ans %= Q
                c += 1
                if c == K:
                    break
            print(ans)
            exit()


cost_2 = []
if len(A_mi) > 1:
    for i in range(0, len(A_mi), 2):
        cost_2.append(A_mi[i] * A_mi[i + 1])

c = 0
ans = 1

while True:
    if K - c > 1:
        if len(cost_2) > 0:
            c2 = cost_2[0]
        else:
            c2 = 0
        pl2 = A_pl[-1] * A_pl[-2]
        if c2 >= pl2:
            ans *= c2
            cost_2.pop(0)
        else:
            ans *= pl2
            A_pl.pop(-1)
            A_pl.pop(-1)
        ans %= Q
        c += 2
    else:
        ans *= A_pl[-1]
        ans %= Q
        c += 1
        A_pl.pop(-1)
    if K == c:
        break

print(ans)

Submission status: Runtime Error

Solution code:
import math  # noqa: F401
from collections import deque  # noqa: F401
from functools import lru_cache
from typing import Deque, Dict, List, Optional, Tuple, Union  # noqa: F401

MOD = 10 ** 9 + 7


@lru_cache(maxsize=None)
def max_product_subarray_of_size_k(A, n, k):
    A.sort()
    product = 1

    if A[-1] == 0 and (k & 1):
        return 0

    if A[-1] <= 0 and (k & 1):
        for a in A[n - k : n]:
            product *= a
        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
            i += 2
        else:
            product *= right_product
            j -= 2

    return product


def main(N: int, K: int, A: List[int]):
    x = max_product_subarray_of_size_k(A, N, K)
    print(x % MOD)


if __name__ == "__main__":
    N, K = map(int, input().split())
    A: List[int] = list(map(int, input().split()))
    main(N, K, A)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

def main():
    N,K = map(int, readline().split())
    A = [int(i) for i in readline().split()]

    acc_A = [1]
    for a in A:
        acc_A.append(acc_A[-1] * a)
    
    ans = -10**15
    for r in range(K, N+1):
        ans = max(ans, acc_A[r] // acc_A[r-K])
    
    print(ans % MOD)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

if n == k:
    prod = 1
    for b in a:
        prod *= b
        prod %= mod
    print(prod)
    exit()

# negative prod
if k & 1 and a[-1] < 0:
    prod = 1
    for i in range(k):
        prod *= a[-1 - i]
        prod %= mod
    print(prod)
    exit()

A = []
for b in a:
    if b < 0:
        A.append((-b, True))
    else:
        A.append((b, False))
A = sorted(A)[::-1]

ans = 1
is_neg = False
last_neg = 1
last_nneg = -1

for i in range(k + 1):
    (b, neg) = A[i]
    ans *= b
    ans %= mod
    is_neg ^= neg
    if i == k - 1:
        if not is_neg:
            print(ans)
            exit()
    if i <= k - 1:
        if neg:
            last_neg = -b
        else:
            last_nneg = b
    if i == k:
        if is_neg:
            assert last_neg != 1
            ans *= pow(last_neg, mod - 2, mod)
        else:
            assert last_nneg != -1
            ans *= pow(last_nneg, mod - 2, mod)
        ans %= mod
        print(ans)
        exit()

Submission status: Runtime Error

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

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

Mi = []
for a in A:
    if a != 0:
        Mi.append((abs(a), a//abs(a)))

Mi.sort(reverse=True)

if len(Mi) < K:
    ans = 0
else:
    ans = 1
    seg = 1
    lastinv = -1
    lastpu = -1
    for i in range(K):
        a, iv = Mi[i]
        seg *= iv
        if iv == -1:
            lastinv = a
        else:
            lastpu = a
        ans = ans * a % mod

    if seg == -1:
        fpu = -1
        fmi = -1
        ind = K
        while ind < len(Mi):
            a, iv = Mi[ind]
            ind += 1
            if iv == -1:
                if fmi == -1:
                    fmi = a
            else:
                if fpu == -1:
                    fpu = a
        
        if lastpu == -1:
            if fpu != -1:
                ans = ans * fpu * pow(lastinv, mod-2, mod) % mod
            elif 0 in A:
                ans = 0
            else:
                ans = -1
                for i in range(K):
                    ans = ans * Mi[-i-1][0] % mod
        elif fpu == -1 or fmi == -1:
            if fpu == -1 and fmi == -1:
                if 0 in A:
                    ans = 0
                else:
                    raise Exception
                    ans = -ans
            elif fpu == -1:
                ans = ans * fmi * pow(lastpu, mod-2, mod) % mod
            else:
                ans = ans * fpu * pow(lastinv, mod-2, mod) % mod
        elif lastpu * fpu > lastinv * fmi:
            ans = ans * fpu * pow(lastinv, mod-2, mod) % mod
        else:
            ans = ans * fmi * pow(lastpu, mod-2, mod) % mod
    
    print(ans % mod)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
large_p = 10**9 + 7
from collections import deque
from copy import deepcopy
from operator import mul
from functools import reduce

def main():
    n, k, *a = map(int, read().split())
    if n == 1:
        print(a[0])
        sys.exit()
    elif n == 2:
        r = max(a[0], a[1], a[0] * a[1])
        print(r)
        sys.exit()
    a2 = [i for i in a if i > 0] #plus
    a3 = [-i for i in a if i < 0] #minus
    a2.sort(reverse=True)
    a3.sort(reverse=True)
    res = deepcopy(a2[:k+1])
    resd = deque(res)
    a3d = deque(a3)
    a2dd = deque()
    a3dd = deque()
    cnt = 0
    while cnt < k:
        if a3d and resd[-1] < a3d[0]:
            a2dd.append(resd.pop())
            t = a3d.popleft()
            resd.appendleft(t)
            a3dd.append(t)
            cnt += 1
        else:
            break
    r = reduce(mul, resd)
    if r < 0:
        r = r // a3dd[-1] * -1
        r *= a2dd[-1]
    print(r)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    int[] a = new int[n];
    for(int i=0;i<n;i++){
      a[i] = sc.nextInt(); 
    }
    System.out.println(maxProduct(a, n, k)%1000000007);
  }
  
  public static int maxProduct(int[] a, int n, int k){
   	Arrays.sort(a);
    int product = 1;
    if(a[n-1] == 0 && k%2 != 0){
      return 0; 
    }
    if(a[n-1] <= 0 && k%2 != 0){
      for(int i=n-1;i>=n;i--){
        product *= a[i]; 
      }
      return product;
    }
    int i = 0;
    int j = n-1;
    if(k%2 != 0){
      product *= a[j];
      j--;
      k--;
    }
    k >>= 1;
    for(int i=0;i<k;i++){
      int left = a[i]*a[i+1];
      int right = a[j]*a[j-1];
      if(left > right){
       	product *= left;
        i += 2;
      }else{
        product *= right;
        j -= 2;
      }
    }
    return product;
  }
}