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:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    if n == k:
        ans = a[0]
        for i in a[1:]:
            ans *= i
            ans %= mod
        print(ans)
        return
    mi = []
    ma = []
    a.sort()
    for ai in a:
        if ai <= 0:
            heappush(mi, ai)
        else:
            heappush(ma, -ai)
    if not ma:
        ans = 1
        if k & 1:
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
        else:
            for i in range(k):
                ans *= a[i]
                ans %= mod
        print(ans)
        return
    if len(mi) >= k:
        ans = 1
        A = []
        if k & 1:
            k -= 1
            ans *= -heappop(ma)
        for _ in range(k):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        while len(ma) >= 2 and len(A) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            if g1 * g2 < h1 * h2:
                print(ans)
                return
            ans *= pow(h1 * h2, mod - 2, mod)
            ans %= mod
            ans *= g1 * g2
            ans %= mod
        print(ans)
    else:
        L = len(mi)
        A = []
        X = k - L
        if len(mi) & 1:
            L -= 1
            X -= 1
            ans *= -heappop(ma)
        for i in range(L):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        for i in range(X):
            x = -heappop(ma)
            ans *= x
            ans %= mod
        while len(ma) >= 2 and len(A) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            if g1 * g2 < h1 * h2:
                print(ans)
                return
            ans *= pow(h1 * h2, mod - 2, mod)
            ans %= mod
            ans *= g1 * g2
            ans %= mod
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
P=[]
Z=[]
N=[]
for i in range(n):
  if a[i]>0:
    P.append(a[i])
  elif a[i]==0:
    Z.append(a[i])
  else:
    N.append(-a[i])
P.sort()
P3=[1]
for i in range(len(P)):
  P3.append(P3[-1]*P[i]%mod)
P.reverse()
P2=[1]
for i in range(len(P)):
  P2.append(P2[-1]*P[i]%mod)
N.sort()
N3=[1]
for i in range(len(N)):
  N3.append(N3[-1]*N[i]%mod)
N.reverse()
N2=[1]
for i in range(len(N)):
  N2.append(N2[-1]*N[i]%mod)

if len(P)+len(N)<k:
  print(0)
  exit()

if len(N)==0:
  print(P2[k])
  exit()

ans=[]

for i in range(len(N)//2+1):
  if i*2<=k and k-i*2<=len(P):
    ans.append(N2[i*2]*P2[k-i*2]%mod)

if len(ans)!=0:
  print(max(ans))
  exit()

for i in range(k+1):
  if k-i<=len(P):
    ans.append(N3[i]*P3[k-i])

print(-min(ans)%mod)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
b,c,d = 0,0,0
mod = 10**9+7
B = []
C = []
D = []
for a in A:
    if a < 0:
        b += 1
        B.append(a)
    elif a == 0:
        c += 1
        C.append(a)
    else:
        d += 1
        D.append(a)
if B:
    B.sort()
if D:
    D.sort(reverse = True)
if K > b+d:
    print(0)
elif K == b+d and K< N and b%2 == 1:
    print(0)
elif K == N:
    ans = 1
    for i in range(N):
        ans = ans * A[i] % mod
    print(ans)
elif b == N and K % 2 == 1:
    ans = 1
    for i in range(1,K+1):
        ans = ans*B[-i]%mod
    print(ans)
else:
    bi = 0
    di = 0
    ans = 1
    while(K>1):
        if (bi >= b) or (di+1< d and D[di]*D[di+1] > B[bi]*B[bi+1]):
            ans = ans*D[di]%mod
            ans = ans*D[di+1]%mod
            di += 2
        else:
            ans = ans*B[bi]%mod
            ans = ans*B[bi+1]%mod
            bi += 2
        K -= 2
    if K == 1:
        ans = ans * D[di] % mod
    print(ans)

Submission status: Runtime Error

Solution code:
def maxProduct(a, n, k):
  a.sort()
  product = 1
  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]
    return product
  i = 0
  j = n-1
  if(k&1):
    product *= a[j]
    j -= 1
    k -= 1
  k >>= 1
  for i in range(k):
    left = a[i]*a[i+1]
    right = a[j]*a[j-1]
    if(left > right):
      product *= left
      i += 2
    else:
      product *= right
      j -= 2
  return product

if __name__ == "__main__":
  n = int(input())
  k = int(input())
  a = list(map(int, input().strip().split()))
  print(maxProduct(a, n, k)%1000000007)

Submission status: Runtime Error

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

b = [(abs(i), 1 if i >= 0 else -1) for i in a]

b = sorted(b)
b = list(reversed(b))

p = 1
for i in range(k):
	p *= b[i][0] * b[i][1]

mod = int(1e9 + 7)

if p >= 0:
	print(p % mod)
else:
	# choice between replacing the last positive by the next negative
	# and replacing the last negative by the next positive
	lastP, nextP, lastN, nextN = -1, -1, -1, -1
	for i in range(k):
		if b[i][0] * b[i][1] >= 0:
			lastP = i
		if b[i][0] * b[i][1] <= 0:
			lastN = i
	for i in range(k, n):
		if b[i][0] * b[i][1] >= 0:
			nextP = i
		if b[i][0] * b[i][1] <= 0:
			nextN = i
	ans = -1e50
	if lastP != -1 and nextN != -1:
		ans = max(ans, -(p // b[lastP][0]) * b[nextN][0])
	if lastN != -1 and nextP != -1:
		ans = max(Ans, -(p // b[lastN][0]) * b[nextP][0])
	
	if ans >= 0:
		print(ans % mod)
	else:
		# tout le monde est negatif
		a = list(reversed(sorted(a)))
		p = 1
		for i in range(k):
			p *= a[i]
		print(p % mod)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True, key = lambda x: abs(x))
mod = 10**9+7
nega = 0
posi = 0
zero = 0
for i in range(n):
    if a[i] > 0:
        posi += 1
    elif a[i] == 0:
        zero += 1
    else:
        nega += 1

if n == k:
    ans = 1
    for i in range(n):
        ans *= a[i]
        ans %= mod

elif posi == 0:
    if k % 2 == 0:
        pass
    else:
        if a.count(0) > 0:
            ans = 0
        else:
            a.reverse()
            ans = 1
            for i in range(k):
                ans *= abs(a[i])
                ans %= mod

            ans *= -1


else:
    posi = 0
    nega = 0
    zero = 0
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod

    for i in range(k):
        if a[i] > 0:
            posi += 1
        elif a[i] < 0:
            nega += 1
        else:
            zero += 1
    if zero > 0:
        ans = 0

    elif nega % 2 != 0:
        minposi = 0
        minnega = 0
        for i in range(k-1, -1, -1):
            if a[i] > 0:
                if minposi == 0:
                    minposi = a[i]
            else:
                if minnega == 0:
                    minnega = a[i]

        maxposi = 0
        maxnega = 0
        for i in range(k, n):
            if a[i] > 0:
                if maxposi == 0:
                    maxposi = a[i]
            else:
                if maxnega == 0:
                    maxnega = a[i]

        if abs(minposi*maxposi) > abs(minnega*minnega):
            ans *= pow(abs(maxnega), mod-2, mod)
            ans *= minposi
        else:
            ans *= pow(abs(maxposi), mod-2, mod)
            ans *= abs(minnega)

print(ans % mod)

Submission status: Runtime Error

Solution code:
import heapq
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:
        heapq.heappush(m,i)
    else:
        heapq.heappush(p,-i)
heapq.heappush(m,0)
heapq.heappush(m,0)
heapq.heappush(p,0)
heapq.heappush(p,0)
m1 = heapq.heappop(m)
m2 = heapq.heappop(m)
p1 = -heapq.heappop(p)
p2 = -heapq.heappop(p)
while k:
    if k%2 == 1:
        ans *= p1
        p1 = p2
        p2 = -heapq.heappop(p)
        k -= 1
    elif m1 * m2 > p1 * p2:
        ans *= m1 * m2
        m1 = heapq.heappop(m)
        m2 = heapq.heappop(m)
        k -= 2
    else:
        ans *= p1
        p1 = p2
        p2 = -heapq.heappop(p)
        k -= 1
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
#

import sys
input=sys.stdin.readline
MOD=10**9+7


def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A2n=[]
    for i in range(0,N,2):
        if A[i]<=0 and A[i+1]<=0:
            A2n.append(A[i]*A[i+1])
        else:
            break

    A.sort(reverse=True)
    ans=1
    if A[0]<=0 and K%2==1:
        for i in range(K):
            ans=(ans*A[i])%MOD
        print(ans)
        exit()
    ni=0
    i=0
    while(K>0):
        if len(A2n)-ni>0 and A[i]*A[i+1]<A2n[ni] and K>=2:
            ans=(ans*A2n[ni])%MOD
            K-=2
            ni+=1
        else:
            ans=(ans*A[i])%MOD
            i+=1
            K-=1
    print(ans)
            
    
    
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
m = 10**9+7
arr = list(map(int, input().split()))
arr.sort()
p = [arr[0]]
for i in arr[1:]:
	p += [i*p[-1]]
for i in arr:
	p += [i*p[-1]]

res = p[k-1]
for i in range(1, 2 * n):
	if i + k < 2 * n:
		res = max(res, p[i+k-1]//p[i-1])
	else:
		break

print(res % m)

Submission status: Runtime Error

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

P = []
M = []
for i in A:
  if i < 0:
    M.append(abs(i))
  if i > 0:
    P.append(i)

if len(M) + len(P) < K:
  print(0)
  exit()
elif len(M) + len(P) == K:
  ans = 1
  for i in M:
    ans = ans * i % MOD
  for i in P:
    ans = ans * i % MOD
  if len(M) % 2 == 1:
    ans *= -1
    ans += MOD
  print(ans)
  exit()

M.sort(reverse = True)
P.sort(reverse = True)

if len(P) == 0:
  x = 1 / 0
  ans = 1
  if K % 2 == 0:
    for i in range(K):
      ans = ans * M[i] % MOD
  else:
    for i in range(K):
      ans = ans * M[-1 -i] % MOD
    ans *= -1
    while ans < 0:
      ans += MOD
  print(ans)
else:
  ans = 1
  pn = 0
  mn = 0
  if K % 2 == 1:
    K -= 1
    ans *= P[0]
    pn = 1
  for i in range(K // 2):
    if pn + 2 > len(P):
      ans = ans * M[mn] * M[mn + 1] % MOD
      mn += 2
    elif mn + 2 > len(M):
      ans = ans * P[pn] * P[pn + 1] % MOD
      pn += 2
    else:
      p = P[pn] * P[pn + 1]
      m = M[mn] * M[mn + 1]
      if p > m:
        ans = ans * p % MOD
        pn += 2
      else:
        ans = ans * m % MOD
        mn += 2
  print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
a_n=[]#aのうち負の数のlist
a_p=[]#aのうち正の数のlist
b=[]
for i in range(len(a)):
  if a[i]<=0:
    a_n.append(a[i])
  if a[-(i+1)]>=0:
    a_p.append(a[-(i+1)])

if len(a_p)==0:
  ans=1
  for i in range(k):
    ans=(ans*a_n[i])%1000000007
else:
  ans=1
  j=0
  jn=0
  jp=0
  while j<k-2:
    if (jn>=len(a_n)-1):
      ans=(ans*a_p[jp])%1000000007
      jp=jp+1
      j=j+1
    elif (jp>=len(a_p)):
      ans=(ans*a_n[jn]*a_n[jn+1])%1000000007
      jn=jn+2
      j=j+2
    elif a_n[jn]*a_n[jn+1]>=a_p[jp]*a_p[jp+1]:
      ans=(ans*a_n[jn]*a_n[jn+1])%1000000007
      jn=jn+2
      j=j+2
    else:
      ans=(ans*a_p[jp])%1000000007
      jp=jp+1
      j=j+1
  if j==k-2:
    if(jp>=len(a_p)):
      ans=(ans*a_n[jn]*a_n[jn+1])%1000000007
    elif(jn>=len(a_n)):
      ans=(ans*a_p[jp]*a_p[jp+1])%1000000007
    else:
      ans=(ans*max(a_n[jn]*a_n[jn+1],a_p[jp]*a_p[jp+1]))%1000000007
  else:
    if(jp>=len(a_p)):
      ans=(ans*a_n[jn])%1000000007
    else:
      ans=(ans*a_p[jp])%1000000007

print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
B = []
C = []
for i in range(N):
    a = A[i]
    if a < 0:
        b = -a
        B.append(b)
    else:
        b = a
        C.append(a)
S = []
while B and C:
    a = B[0]
    b = C[0]
    p = 0
    if a <= b:
        S.append(-a)
        B.pop(0)
    else:
        S.append(b)
        C.pop(0)
if B:
    for i in B:
        S.append(-i)
if C:
    for i in C:
        S.append(i)
f = 0
p = 0
q = 0
mod = 10**9+7
ans = 1
for i in range(K):
    j = N - i - 1
    if S[j] < 0:
        q = S[j]
        f += 1
    else:
        p = S[j]
    ans *= max(S[j],-S[j])
    ans = ans % mod
r = 0
s = 0
for i in range(K,N):
    j = N - i - 1
    if S[j] < 0:
        r = min(S[j],r)
    else:
        s = max(S[j],s)
        
def pow(a,b,mod):
    if b == 0:
        return 1
    else:
        if b % 2 == 0:
            return (pow(a,b//2,mod))**2%mod
        else:
            return (a*(pow(a,(b-1)//2,mod))**2)%mod
if K == N:
    print(ans)
if K != N:
    if f % 2 == 0:
        print(ans)
    else:
        ans1 *= r
        ans1 = ans1 % mod
        d = pow(p,mod-2,mod)
        ans1 *= d
        ans1 = ans2 % mod
        ans2 *= s
        ans2 = ans2 % mod
        d = pow(q,mod-2,mod)
        ans2 *= d
        ans2 = ans2 % mod
        if r*q > s*q:
            ans = ans1
        else:
            ans = ans2
        print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

def f(A, N, K):
    A.sort()
    I = (np.abs(A)).argsort()
    A = A[I][::-1]
    if N == K:
        return A
    # 全部負
    if np.all(A < 0):
        if K % 2 == 0:
            return A[:K]
        else:
            return A[-K:]
    # これ以外の場合は、必ず正を実現できる
    pos = A[A >= 0]
    neg = A[A < 0]
    nums = [1]
    if K & 1:
        nums = [pos[0]]
        pos = pos[1:]
        K -= 1
    # K は偶数
    # pos, neg から偶数個ずつセットにする
    pos = pos[::2] * pos[1::2]
    neg = neg[::2] * neg[1::2]
    A = np.concatenate([pos, neg])
    A.sort()
    A = A[::-1]
    return np.concatenate([nums, A[:K // 2]])

MOD = 10**9 + 7
B = f(A, N, K).tolist()
ans = 1
for x in B:
    ans = ans * x % MOD
print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

    def __add__(self, other):
        return ModInt(self.x + other.x) if isinstance(other, ModInt) else ModInt(self.x + other)

    def __sub__(self, other):
        return ModInt(self.x - other.x) if isinstance(other, ModInt) else ModInt(self.x - other)

    def __mul__(self, other):
        return ModInt(self.x * other.x) if isinstance(other, ModInt) else ModInt(self.x * other)

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

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD))
            if isinstance(other, ModInt)
            else ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return ModInt(other.x - self.x) if isinstance(other, ModInt) else ModInt(other - self.x)

    __rmul__ = __mul__

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

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD))
            if isinstance(other, ModInt)
            else ModInt(pow(other, self.x, MOD))
        )


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
        print(ans)
        return

    B = []
    n_plus = 0
    for a in A:
        if a >= 0:
            B.append((a, True))
            n_plus += 1
        else:
            B.append((-a, False))

    if n_plus == 0:
        A.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD
        print(ans)
        return

    B.sort(key=lambda x: x[0], reverse=True)
    cnt = 0
    prev_minus = None
    prev_plus = None
    ans = 1
    for i in range(K):
        b, flag = B[i]

        ans *= b
        ans %= MOD

        if flag:
            prev_plus = b
        else:
            cnt += 1
            prev_minus = b

    if cnt % 2 == 0 or ans == 0:
        print(ans)
        return

    next_minus = None
    next_plus = None
    for i in range(K, N):
        b, flag = B[i]
        if flag:
            if next_plus is None:
                next_plus = b
        else:
            if next_minus is None:
                next_minus = b

    ans = ModInt(ans)

    if next_plus is not None and prev_minus is not None:
        tmp1 = ans / ModInt(prev_minus)
        tmp1 *= ModInt(next_plus)
        tmp1 %= MOD
    else:
        tmp1 = -INF

    if next_minus is not None and prev_plus is not None:
        tmp2 = ans / ModInt(prev_plus)
        tmp2 *= ModInt(next_minus)
        tmp2 %= MOD
    else:
        tmp2 = -INF

    print(max(tmp1, tmp2))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from math import log2
from itertools import accumulate

epsilon = 10 ** -5

MOD = 10 ** 9 + 7

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

negs = []
poss = []
for A in As:
    if A > 0:
        poss.append(A)
    elif A < 0:
        negs.append(-A)

poss.sort(reverse = True)
negs.sort(reverse = True)

if len(poss) + len(negs) < K:
    print(0)
    exit()

if len(poss) == 0:
    if N > len(negs):
        if K % 2 == 1:
            print(0)
        else:
            ans = 1
            for n in negs[:K]:
                ans *= n
                ans %= MOD
            print(ans)
    else:
        if K % 2 == 1:
            ans = 1
            for n in negs[-K:]:
                ans *= n
                ans %= MOD
            print(-ans%MOD)
        else:
            ans = 1
            for n in negs[:K]:
                ans *= n
                ans %= MOD
            print(ans)
    exit()

def mulmod(a, b):
    return a * b % MOD

logs_poss = [0.0] + [log2(p) for p in poss] 
logs_poss_csum = list(accumulate(logs_poss))

poss_mod_csum = [1] + list(accumulate(poss, mulmod))

logs_negs = [0.0] + [log2(n) for n in negs] 
logs_negs_csum = list(accumulate(logs_negs))

negs_mod_csum = [1] + list(accumulate(negs, mulmod))

max_log = -1
for minus in range(0, K+1, 2):
    plus = K - minus
    if plus <= len(poss) and minus <= len(negs):
        if max_log + epsilon < logs_poss_csum[plus] + logs_negs_csum[minus]:
            max_log = logs_poss_csum[plus] + logs_negs_csum[minus]
            max_mod = poss_mod_csum[plus] * negs_mod_csum[minus] % MOD
        elif max_log <= logs_poss_csum[plus] + logs_negs_csum[minus]:
            mod = poss_mod_csum[plus] * negs_mod_csum[minus] % MOD
            if mod > max_mod:
                max_log = logs_poss_csum[plus] + logs_negs_csum[minus]
                max_mod = poss_mod_csum[plus] * negs_mod_csum[minus] % MOD

print(max_mod)

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:
    pass
    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:
        x = np - 1
        idx = k - np + 1
    else:
        x = np
        idx = k - np

    while idx + 2 <= x and idx + 1 < nm and ap[x - idx - 1] * ap[
            x - idx - 2] < am[idx] * am[idx + 1]:
        idx += 2
    ans = 1
    for i in range(x - idx):
        ans *= ap[i]
        ans %= MOD
    for i in range(idx):
        ans *= am[i]
        ans %= MOD
else:
    idx = 0
    while idx + 2 <= k and idx + 1 < nm and ap[k - idx - 1] * ap[
            k - idx - 2] < am[idx] * am[idx + 1]:
        idx += 2
    ans = 1
    for i in range(np - idx):
        ans *= ap[i]
        ans %= MOD
    for i in range(idx):
        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()))
a.sort()
res=1
cnt=0
p=1000000007
while 1:
  #print(a,res)
  if cnt==k or len(a)==0:
    break
  if len(a)==1 & a[0] > 0 & cnt < k:
    res *= a[0]
    break
  if a[-1] < 0:
    res *= a[-1]
    res%=p
    cnt += 1
    a.pop(-1)
    continue
  tmp_a = res * a[0]*a[1]
  tmp_b = res * a[-1]
  if tmp_a > tmp_b and cnt < k-1:
    res = tmp_a
    res%=p
    cnt += 2
    a = a[2:]
  else:
    res = tmp_b
    res %= p
    cnt += 1
    a = a[:-1]
print(res%p)

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
    val = 0
    if k%2:
        ans *= pos[i]
        i -= 1
        val += 1
    while val != k:
        if i<1:
            ans *= neg[j]*neg[j-1]
            ans %= mod
            j -= 2
        elif j<1:
            ans *= pos[i]*pos[i-1]
            ans %= mod
            i -= 2
        else:
            if pos[i]*pos[i-1]>neg[i]*neg[i-1]:
                ans *= pos[i]*pos[i-1]
                ans %= mod
                i -= 2
            else:
                ans *= neg[j] *neg[j-1]
                ans %= mod
                j -= 2
        k -= 2
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 7 + 10**9
    if N == K:
        r = 1
        for i in A:
            r *= i
            r %= mod
        return r % mod
    if max(A) == 0 and K % 2 == 1:
        return 0
    if max(A) < 0 and K % 2 == 1:
        A.sort(reverse=True)
        r = 1
        for i in range(K):
            r *= A[i]
            r %= mod
        return r % mod
    a = []
    for i in A:
        a.append((abs(i), i))
    a.sort(reverse=True)
    cm = 0
    lp = None
    lm = None
    for i in range(K):
        if a[i][1] >= 0:
            lp = i
        else:
            lm = i
            cm += 1
    if cm % 2 == 0:
        r = 1
        for i in range(K):
            r *= a[i][1]
            r %= mod
        return r
    if not lp:
        r = 1
        for i in range(K-1):
            r *= a[i][1]
            r %= mod
        for i in range(K+1, N):
            if a[i][1] > 0:
                r *= a[i][1]
                r %= mod
                return r
    np = None
    nm = None
    for i in range(K+1, N):
        if a[i][1] >= 0 and not np:
            np = i
        if a[i][1] < 0 and not nm:
            nm = i
        if np and nm:
            break
    if not np:
        r = 1
        for i in range(K):
            if i != lp:
                r *= a[i][1]
                r %= mod
        r *= a[nm][1]
        return r % mod
    if not nm:
        r = 1
        for i in range(K):
            if i != lm:
                r *= a[i][1]
                r %= mod
        r *= a[np][1]
        return r % mod
    r = 1
    for i in range(K):
        if i not in (lp, lm):
            r *= a[i][1]
    r *= max(a[np][1] * a[lp][1], a[lm][1] * a[nm][1])
    return r % mod
print(main())

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:
    pass
    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:
        x = np - 1
        idx = k - np + 1
    else:
        x = np
        idx = k - np

    while idx + 2 <= x and idx + 1 < nm and ap[x - idx - 1] * ap[
            x - idx - 2] < am[idx] * am[idx + 1]:
        idx += 2
    ans = 1
    for i in range(np - idx):
        ans *= ap[i]
        ans %= MOD
    for i in range(idx):
        ans *= am[i]
        ans %= MOD
else:
    idx = 0
    while idx + 2 <= k and idx + 1 < nm and ap[k - idx - 1] * ap[
            k - idx - 2] < am[idx] * am[idx + 1]:
        idx += 2
    ans = 1
    for i in range(np - idx):
        ans *= ap[i]
        ans %= MOD
    for i in range(idx):
        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()))
A_plus = []
A_minus = []
for A_ in A:
    if A_ > 0:
        A_plus.append(A_)
    else:
        A_minus.append(-A_)
if len(A_plus) > 0 and len(A_minus) > 0:
    A_plus.sort(reverse = True)
    A_minus.sort(reverse = True)

    index_plus = 0
    index_minus = 0

    counter_ = 0

    times_list = []
    while counter_ < K:
        if A_plus[index_plus] >= A_minus[index_minus]:
            times_list.append(A_plus[index_plus])
            index_plus += 1
        else:
            times_list.append(A_minus[index_minus])
            index_minus += 1
        counter_ += 1

    if index_minus % 2 == 0:
        pass
    else:
        if index_plus == 0:
            times_list.remove(A_minus[index_minus - 1])
            times_list.append(A_plus[index_plus])
        else:
            if A_plus[index_plus] * A_plus[index_plus - 1] > A_minus[index_minus] * A_minus[index_minus - 1]:
                times_list.remove(A_minus[index_minus - 1])
                times_list.append(A_plus[index_plus])
            else:
                times_list.remove(A_plus[index_plus - 1])
                times_list.append(A_minus[index_minus])
    ans_ = 1
    for time_ in times_list:
        ans_ *= time_
        ans_ = ans_ % (10 ** 9 + 7)

elif len(A_plus) > 0:
    A_plus.sort(reverse = True)
    ans_ = 1
    for i in range(K):
        ans_ *= A_plus[i]
        ans_ = ans_ % (10 ** 9 + 7)
else:
    if K % 2 == 0:
        A_minus.sort(reverse = True)
        ans_ = 1
        for i in range(K):
            ans_ *= A_minus[i]
            ans_ = ans_ % (10 ** 9 + 7)
    else:
        A_minus.sort(reverse = False)
        ans_ = 1
        for i in range(K):
            ans_ *= A_minus[i]
        ans_ = -1 * ans_
        ans_ = ans_ % (10 ** 9 + 7)
        
print(ans_)