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 math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    n,k,*A = get_all_int()
    A = list(A)

    # 答えが負である条件
    # ・Aが全て負で、Kが奇数
    # ・Aの負数が奇数個かつ0が存在せず、K=N

    # 答えが0である条件
    # ・N-(Aの0の個数) < K

    positives = 0
    zeros = 0
    negatives = 0

    for a in A:
        if a > 0:
            positives += 1
        elif a == 0:
            zeros += 1
        else:
            negatives += 1
    

    if k == 1:
        # 1個だけの場合はたんに最大値を出力する
        A.sort(reverse=True)
        print(A[0])
        exit()

    if (n-zeros) < k:
        # 答えが0
        print(0)
        exit()
    
    elif (k==n and negatives%2==1  or  n==negatives and k%2==1):
        # 答えが負
        # 絶対値小さい順にK個掛ける
        A.sort(key=lambda a: abs(a))
        # log(A)
        ans = 1
        for i in range(k):
            ans =  (ans * A[i]) % MOD
        print(ans%MOD)
        exit()

    else:
        # 答えが正
        # 絶対値大きい順にK個掛ける
        A.sort(reverse=True, key=lambda a: abs(a))
        # log(A)
        ans = 1
        n_count = 0
        last_n = 0
        last_p = 0
        for i in range(k):
            a = A[i]
            ans =  (ans * a) % MOD
            if a < 0:
                n_count += 1
                last_n = a
            elif a > 0:
                last_p = a
                # log(i, last_n)

        # log(ans, n_count, last_n)
        
        # 負数を奇数個選んでいる場合は調整する
        if n_count%2 == 1:
            x = None
            y = None
            for i in range(k,n):
                a = A[i]
                if a > 0 :
                    ans_a = ans*inv(last_n, MOD) * a
                    x = a
                    break
            if last_p != 0:
                for i in range(k,n):
                    if a < 0 and last_p!=0:
                        ans_b = ans*inv(last_p, MOD) * a
                        y = a
                        break
                if x is not None:
                    xx = abs(x) / abs(last_n)
                    yy = abs(y) / abs(last_p)
                    if yy > xx:
                        ans_a = ans_b
                else:
                    ans_a = ans_b
            ans = ans_a
        
        print(ans%MOD)
        exit()

main()

Submission status: Runtime Error

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

if max(a) < 0:
    a.sort()
    ans = 1
    if k % 2 == 0:
        for e in a[:k]:
            ans *= e
            ans %= mod
    else:
        for e in a[-k:]:
            ans *= e
            ans %= mod

    print(ans)

else:
    neg = []
    pos = []
    for e in a:
        if e < 0:
            neg.append(e)
        else:
            pos.append(e)

    neg.sort()
    pos.sort(reverse=True)

    ans = 1
    if k % 2:
        ans *= pos.pop(0)
        k -= 1

    nums = [e1 * e2 for e1, e2 in zip(neg[::2], neg[1::2])]
    nums += [e1 * e2 for e1, e2 in zip(pos[::2], pos[1::2])]
    if len(neg) % 2:
        nums += neg[-1]
    if len(pos) % 2:
        nums += pos[-1]

    nums.sort(reverse=True)
    for e in nums[:k//2]:
        ans *= e
        ans %= mod

    print(ans)

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:
        if nz > 0:
            ans = 0
        else:
            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:
import itertools, operator


def out(X):
    print(list(itertools.accumulate(X, func=lambda x, y: x * y % mod))[-1])
    exit()


N, K = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()], key=lambda x: -abs(x))
mod = 10**9 + 7
cnt = 0
ipos = ineg = -1
for i, a in enumerate(A[:K]):
    if a < 0:
        cnt += 1
        ineg = i
    else:
        ipos = i
if cnt % 2 == 0:
    out(A[:K])
else:
    for i, a in enumerate(A[K:]):
        if a < 0 and ipos != -1:
            X = A[:ipos] + A[ipos + 1:K] + A[K + i]
            out(X)
        elif a > 0 and ineg != -1:
            X = A[:ineg] + A[ineg + 1:K] + A[K + i]
            out(X)
    else:
        C = A[::-1]
        cnt = 0
        out(C[:K])

Submission status: Runtime Error

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

if sum(v == 0 for v in A) > N - K:
    print(0)
    exit()


if all(v <= 0 for v in A):
    x = sorted([v for v in A if v < 0])
    ans = 1
    if K % 2 == 0:
        for i in range(K):
            ans = ans * x[i] % MOD
    else:
        for i in range(N - K, N):
            ans = ans * x[i] % MOD
            
    print(ans)
    exit()


x = sorted([(abs(v), v // abs(v)) for v in A])
plus = []
minus = []
for i in range(K):
    v, s = x.pop()
    if s == 1:
        plus.append(v)
    else:
        minus.append(v)


if len(minus) % 2 != 0:
    p_cand = MOD
    m_cand = MOD
    while x:
        v, s = x.pop()
        if s == 1 and p_cand == MOD:
            p_cand = v
        elif s == -1 and m_cand == MOD:
            m_cand = v
    
    if p_cand == MOD and m_cand != MOD and plus:
        plus.pop()
        minus.append(m_cand)
    elif m_cand == MOD and p_cand != MOD and minus:
        minus.pop()
        plus.append(p_cand)
    elif p_cand != MOD and m_cand != MOD and plus and minus:
        p_val = plus.pop() * p_cand
        m_val = minus.pop() * m_cand
        
        if p_val > m_val:
            plus.append(p_val)
        else:
            minus.append(m_val)
            
ans = 1
for v in plus:
    ans = ans * v % MOD
for v in minus:
    ans = ans * v % MOD
print(ans)

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(" ")]
mod=10**9+7
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
        retval=retval%mod
    print(retval%mod)
    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 a in A[:K]:
    if a<0:
        use_minus+=1
    retval*=a
    retval=retval%mod

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

Submission status: Runtime Error

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

INF=10**9+7

x=False
y=False
z=False
xl=[]
yl=[]
for i in a:
    if i>0:
        x=True
        xl.append(i)
    elif i<0:
        y=True
        yl.append(i)
    else:
        z=True

if not y:
    a.sort(reverse=True)
    ans=1
    for i in range(k):
        ans=(ans*a[i])%INF

else:
    if not x:
        if z:
            if k%2==0:
                a.sort()
                ans=1
                for i in range(k):
                    ans=(ans*a[i])%INF
            else:
                ans=0
        else:
            if k%2==0:
                a.sort()
                ans=1
                for i in range(k):
                    ans=(ans*a[i])%INF
            else:
                a.sort(reverse=True)
                ans=1
                for i in range(k):
                    ans=(ans*a[i])%INF
    else:
        if z:
            if len(xl)+len(yl)>k:
                ans=0
            
            if len(xl)+len(yl)==k:
                ans=1
                for i in xl:
                    ans=(ans*i)%INF
                for i in yl:
                    ans=(ans*i)%INF
                if len(yl)%2==0:
                    pass
                else:
                    ans=0
            
            if k%2==0:
                xyl=[]
                xl.sort(reverse=True)
                yl.sort()
                for i in range(len(xl)//2):
                    xyl.append(xl[i*2]*xl[i*2+1])
                for i in range(len(yl)//2):
                    xyl.append(yl[i*2]*yl[i*2+1])
                xyl.sort(reverse=True)
                ans=1
                for i in range(k//2):
                    ans=(ans*xyl[i])%INF

            else:
                xyl = []
                xl.sort(reverse=True)
                yl.sort()
                for i in range((len(xl)-1) // 2):
                    xyl.append(xl[i * 2+1] * xl[i * 2 + 2])
                for i in range(len(yl) // 2):
                    xyl.append(yl[i * 2] * yl[i * 2 + 1])
                xyl.sort(reverse=True)
                ans = xl[0]
                for i in range((k-1) // 2):
                    ans = (ans * xyl[i]) % INF
            
        else:
            if k==n:
                ans=1
                for i in a:
                    ans=(ans*i)%INF
            
            if k%2==0:
                xyl=[]
                xl.sort(reverse=True)
                yl.sort()
                for i in range(len(xl)//2):
                    xyl.append(xl[i*2]*xl[i*2+1])
                for i in range(len(yl)//2):
                    xyl.append(yl[i*2]*yl[i*2+1])
                xyl.sort(reverse=True)
                ans=1
                for i in range(k//2):
                    ans=(ans*xyl[i])%INF

            else:
                xyl = []
                xl.sort(reverse=True)
                yl.sort()
                for i in range((len(xl)-1) // 2):
                    xyl.append(xl[i * 2+1] * xl[i * 2 + 2])
                for i in range(len(yl) // 2):
                    xyl.append(yl[i * 2] * yl[i * 2 + 1])
                xyl.sort(reverse=True)
                ans = xl[0]
                for i in range((k-1) // 2):
                    ans = (ans * xyl[i]) % INF


print(ans)

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:
        if len(plus) > 0:
            can_p = heapq.heappop(plus)
        else:
            can_p = 10**9+1
        if len(minus) > 0:
            can_m = heapq.heappop(minus)
        else:
            can_m = 10**9+1
        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
n,k=map(int,input().split())
arr=list(map(int,input().split()))
def findMaxProduct(arr, n, k) : 
    MaxProduct = 1
    for i in range(0, k) : 
        MaxProduct = MaxProduct * arr[i] 
          
    prev_product = MaxProduct 
    for i in range(1, n - k + 1) : 
        curr_product = (prev_product // arr[i-1]) * arr[i+k-1] 
        MaxProduct = max(MaxProduct, curr_product) 
        prev_product = curr_product 
    return MaxProduct 
x=findMaxProduct(arr, n, k)
print(x%mod)

Submission status: Runtime Error

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np

def main():
	n,k=MI()
	A=LI()
	p=[]
	m=[]
	mod=10**9+7

	for i in A:
		if i>=0:
			p.append(i)
		else:
			m.append(i)
	p.sort(reverse=True)
	m.sort()
	#print(p,m)

	ans=1
	if p==[] and k%2==1:
		for i in range(k):
			ans*=m[-i-1]
			ans%=mod
			#print(k,ans)
	elif n==k==2:
		print((A[0]*A[1])%mod)
		exit(0)

	else:
		i=0
		j=0
		pl=len(p)
		ml=len(m)
		while k>=2:
			if i+2<=pl and j+2<=ml:
				pp=p[i]*p[i+1]
				mm=m[j]*m[j+1]
				if pp>mm:
					ans*=pp
					ans%=mod
					i+=2
				else:
					ans*=mm
					ans%=mod
					j+=2
			elif i+2<=pl:
				pp=p[i]*p[i+1]
				ans*=pp
				ans%=mod
				i+=2
			else:
				#print(i,j)
				mm=m[j]*m[j+1]
				ans*=mm
				ans%=mod
				j+=2
			k-=2

		if k==1:
			ans*=p[i]
			ans%=mod
	print(ans)



if __name__ == "__main__":
	main()

Submission status: Runtime Error

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

A = sorted(A, key = lambda x:abs(x), reverse=True)
#print(A)

ans = []
negidx = 0
posidx = 0
neg = False
for i in range(K):
  a = A[i]
  ans.append(a)
  if a<0:
    negidx = i
    neg = not neg
  else:
    posidx = i
#print(ans, neg, negidx)
answer = 1
if neg:
  poppos = list(ans)
  pg = poppos.pop(posidx)
  popneg = list(ans)
  ng = popneg.pop(negidx)
  pgratio = None
  ngratio = None
  found = 0
  for i in range(K+1, N):
    if A[i]>=0 and ngratio is None:
      found = 1
      popneg.append(A[i])
      ngratio = -A[i]/ng
    if A[i]<0 and pgratio is None:
      found = 2
      poppos.append(A[i])
      pgratio = -A[i]/pg
    if pgratio is not None and npratio is not None:
      found = 3
      break
  if found == 1:
    for a in popnep:
      answer *= a
    print(answer%1000000007)
  elif found == 2:
    for a in poppos:
      answer *= a
    print(answer%1000000007)
  elif found == 3:
    if pgratio > ngratio:
      for a in poppos:
        answer *= a
      print(answer%1000000007)
    else:
      for a in popneg:
        answer *= a
      print(answer%1000000007)
  else:
    for i in range(K):
      answer *= A[-(i+1)]
    print(answer%1000000007)
else:
  for a in ans:
    answer *= a
  print(answer%1000000007)

Submission status: Runtime Error

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

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

# 正に出来る場合：
# ・すべて正の数を選べる
# ・選べる数が奇数個で、負の数が偶数個と正の数が1個以上存在する
# ・選べる数が偶数個で、負の数が偶数個存在する
# 負になる場合：
# ・すべて負の数で且つ、選べる数が奇数個
# ・0が存在していれば、0のほうがマシ

# 開始時点で、絶対値が少ないほうを目指すか大きいほうを目指すか決まる
# 負の数を目指す場合、大きいほうからK個掛ければOK

# 大きいほうを目指す場合、
# 正の数の大きい順リスト [2,1]
# 負の数の絶対値大きい順リスト [-4,-3]
# の先頭から、2個のペアが大きくなるほうを貪欲に取っていく。
# 取れる数が奇数の場合は、まず正のほうの一番大きいのを取っちゃえばOK

pluslist = []
minuslist = []
zerocnt = 0
for i in range(len(A)):
  if A[i] > 0:
    pluslist.append(A[i])
  elif A[i] < 0:
    minuslist.append(A[i])
  else:
    zerocnt += 1
    
# 必ずゼロを選んでしまう場合
if N - zerocnt < K:
  print(0)
  exit(0)

if K % 2 == 1 and len(pluslist) == 0:
  # 負になる場合
  if zerocnt > 0:
    print(0)
    exit(0)
  # 絶対値が小さい状態を目指す
  minuslist = sorted(minuslist, reverse = True)
  ans = 1
  for i in range(K):
    ans *= minuslist[i]
    ans %= DIV
  print(ans)
  exit(0)
  
# 正の数を目指す
pluslist = sorted(pluslist, reverse = True)
minuslist = sorted(minuslist)
from collections import deque

plusq = deque(pluslist)
minusq = deque(minuslist)

ans = 1
if K % 2 == 1 and len(plusq) > 0:
  ans *= plusq.popleft() # 一番大きいものを取っておく
  K -= 1
  
for i in range(K // 2):
  p = 0
  m = 0
  if len(plusq) >= 2:
    p1 = plusq.popleft()
    p2 = plusq.popleft()
    p = p1 * p2
  if len(minusq) >= 2:
    m1 = minusq.popleft()
    m2 = minusq.popleft()
    m = m1 * m2
  if m == 0:
    ans *= p % DIV
    ans %= DIV
    continue
  if p == 0:
    ans *= m % DIV
    ans %= DIV
    continue
  if p > m:
    ans *= (p1 * p2) % DIV
    ans %= DIV
    minuq.appendleft(m2)
    minusq.appendleft(m1)
  else:
    ans *= (m1 * m2) % DIV
    ans %= DIV
    plusq.appendleft(p2)
    plusq.appendleft(p1)

print(ans)

Submission status: Runtime Error

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

p_list = []
n_list = []
z_count = 0

for A in map(int, input().split()):
	if A < 0:
		n_list.append(A)
	elif A > 0:
		p_list.append(A)
	else:
		z_count += 1

p_list.sort()
n_list.sort()

#print(p_list)
#print(n_list)

if len(p_list) + len(n_list) < K:
	print(0)
else:
	values = []
	
#	print(len(p_list) >= K ,  (K - len(p_list)) % 2 == 0 ,  ((K - len(p_list)) % 2 == 1 and len(p_list) >= 1 and K - len(p_list) + 1 <= len(n_list)))
	if len(p_list) >= K or (K - len(p_list)) % 2 == 0 or ((K - len(p_list)) % 2 == 1 and len(p_list) >= 1 and K - len(p_list) + 1 <= len(n_list)):
		n_list.reverse()
		if len(p_list) >= K:
			for i in range(K):
				values.append(p_list.pop())
		elif (K - len(p_list)) % 2 == 0:
			for i in range(len(p_list)):
				values.append(p_list.pop())
			while len(values) < K:
				values.append(n_list.pop())
		elif K - len(p_list) + 1 <= len(n_list):
			for i in range(len(p_list) - 1):
				values.append(p_list.pop())
			while len(values) < K:
				values.append(n_list.pop())
		i = K - 1
		while i >= 1 and len(n_list) >= 2:
			if values[i] * values[i - 1] < n_list[-1] * n_list[-2]:
				values[i] = n_list.pop()
				values[i - 1] = n_list.pop()
				i -= 2
	else:
		p_list.reverse()
		if len(p_list) >= K:
			for i in range(K):
				values.append(p_list.pop())
		elif (K - len(p_list)) % 2 == 0:
			for i in range(len(p_list)):
				values.append(p_list.pop())
			while len(values) < K:
				values.append(n_list.pop())
		elif K - len(p_list) + 1 <= len(n_list):
			for i in range(len(p_list) - 1):
				values.append(p_list.pop())
			while len(values) < K:
				values.append(n_list.pop())
		i = K - 1
		while i >= 1 and len(n_list) >= 2:
			if values[i] * values[i - 1] > n_list[-1] * n_list[-2]:
				values[i] = n_list.pop()
				values[i - 1] = n_list.pop()
				i -= 2
	
#	print(values)
	total = 1
	for v in values:
		total = (total * v) % M
	print(total)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
MOD=10**9+7
p=[]
n=[]
for i in range(N):
    if A[i]<0:
        n.append(A[i])
    else:
        p.append(A[i])
p.sort(reverse=True)
n.sort()
numplus=len(p)
if numplus==0:
    ans=1
    for i in range(1,K+1):
        ans=(ans*n[i*(-1)])%MOD
else:
    if numplus>=K:
        x=K
    else:
        if (K-numplus)%2==1:
            x=numplus-1
        else:
            x=numplus
    ans=1
    for i in range(x):
        ans=(ans*p[i])%MOD
    for i in range(K-x):
        ans=(ans*n[i])%MOD
    temp=ans
    bai=1
    while x>1:
        if len(n)<(K-x+1):
            break
        bai*=(n[K-x]*n[K-x+1])/(p[x-1]*p[x-2])
        temp=(temp*n[K-x]*n[K-x+1])%MOD
        temp=(temp*pow(p[x-1]*p[x-2],MOD-2,MOD))%MOD
        if bai>1:
            ans=temp
            bai=1
        x-=2
print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
MOD = 10**9+7
M = []
P = []
Z = []
for i in a:
    if i < 0:
        M.append(i)
    elif i > 0:
        P.append(i)
    else:
        Z.append(i)
P.sort(reverse=True)
M.sort()
lenZ = len(Z)
lenM = len(M)
lenP = len(P)
if n - k < lenZ:
    print(0)
    exit()
elif lenZ != 0 and n - k == lenZ and lenM % 2 == 1:
    print(0)
    exit()
elif n - k == lenZ:
    ans = 1
    for i in P:
        ans*=i
        ans%=MOD
    for i in M:
        ans*=i
        ans%=MOD
    print(ans)
    exit()
elif lenP == 0:
    M = M[::-1]
    ans = 1
    for i in range(k):
        ans*=M[i]
        ans%=MOD
    print(ans)
    exit()
count = 0
ans = []
i = 0
j = 0
if k % 2 == 1:
    ans.append(P[0])
    i+=1
    k-=1
    if k == 0:
        print(P[0])
        exit()
k //= 2
while count < k:
    if i+2>=lenP:
        ans.append(M[j]*M[j+1])
        j+=2
        count+=1
        continue
    if j+2>=lenM:
        ans.append(P[i]*P[i+1])
        i+=2
        count+=1
        continue
    p = P[i]*P[i+1]
    m = M[i]*M[i+1]
    if p > m:
        ans.append(p)
        i+=2
        count+=1
    else:
        ans.append(m)
        j+=2
        count+=1
intans = 1
for i in range(k):
    intans*=ans[i]
    intans%=MOD
print(intans)

Submission status: Runtime Error

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

    plus = [A[i] for i in range(N) if A[i] >= 0]
    minus = [A[i] for i in range(N) if A[i] < 0]

    ans = 1

    id = 0
    id2 = 0
    P = len(plus)
    M = len(minus)
    plus.sort(reverse=True)

    mod = 10**9 + 7

    if P == 0:
        if K % 2 == 0:
            minus.sort()
            for i in range(K):
                ans *= minus[i]
                ans %= mod
        else:
            minus.sort(reverse=True)
            for i in range(K):
                ans *= minus[i]
                ans %= mod

    elif M == 0:
        for i in range(K):
            ans *= plus[i]
            ans %= mod

    else:

        p = P // 2
        m = M // 2
        if K > (p+m)*2 and (K % 2 == 1 and P % 2 == 0):  # 絶対値が小さい方から貪欲
            A.sort(key=lambda x: abs(x))
            for i in range(K):
                ans *= A[i]
                ans %= mod

        else:  # 絶対値が大きい方から貪欲
            minus.sort()
            pp = [plus[i]*plus[i+1] for i in range(M // 2)]
            mm = [minus[i] * minus[i+1] for i in range(P//2)]

            id = 0
            id2 = 0

            pp.sort(reverse=True)
            mm.sort(reverse=True)
            pp.append(1)
            mm.append(1)
            for i in range((K // 2) - 1):
                if id == p - 1:
                    ans *= mm[id2]
                    id2 += 1
                elif id2 == m:
                    ans *= pp[id]
                    id += 1
                elif pp[id] >= mm[id2]:
                    ans *= pp[id]
                    id += 1
                else:
                    ans *= mm[id2]
                    id2 += 1

                ans %= mod

            if K % 2 == 1:

                if id >= p-1:
                    ans *= mm[id2]
                    ans *= plus[id*2]
                else:
                    ans *= pp[id]
                    id += 1
                    ans *= pp[id*2]
            else:
                if id == p - 1:
                    ans *= mm[id2]
                    id2 += 1
                elif id2 == m:
                    ans *= pp[id]
                    id += 1
                elif pp[id] >= mm[id2]:
                    ans *= pp[id]
                    id += 1
                else:
                    ans *= mm[id2]
                    id2 += 1

    print(ans % mod)


main()

Submission status: Runtime Error

Solution code:
# @author 

import sys

class EMultiplication4:
    def solve(self, tc=0):
        MOD = 10 ** 9 +7

        n, k = [int(_) for _ in input().split()]
        a = [int(_) for _ in input().split()]
        a.sort()
        pos = [x for x in a if x > 0]
        neg = [x for x in a if x < 0]

        if len(pos) + len(neg) < k:
            print(0)
            return

        pre_neg = [1] * (len(neg) + 1)
        pre_pos = [1] * (len(pos) + 1)
        for i in range(1, len(neg) + 1):
            pre_neg[i] = pre_neg[i - 1] * neg[i - 1]
        for i in range(1, len(pos) + 1):
            pre_pos[i] = pre_pos[i - 1] * pos[i - 1]

        post_pos = [1] * (len(pos) + 1)
        post_neg = [1] * (len(neg) + 1)
        for i in range(1, len(pos) + 1):
            post_pos[i] = post_pos[i - 1] * pos[len(pos) - i]
        for i in range(1, len(neg) + 1):
            post_neg[i] = post_neg[i - 1] * neg[len(neg) - i]


        ans = 1
        for i in range(k):
            ans *= a[i]

        st = k - len(pos)
        st += st % 2
        # print(st, len(neg))
        for i in range(st, len(neg) + 1, 2):
            if i > k:
                break
            ans = max(ans, pre_neg[i] * post_pos[k - i])

        st = k - len(pos)
        for i in range(st, len(neg) + 1):
            if i > k:
                break
            ans = max(ans, post_neg[i] * pre_pos[k - i])

        print(ans % MOD)




solver = EMultiplication4()
input = sys.stdin.readline

solver.solve()

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(" ")]
mod=10**9+7
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
        retval=retval%mod
    print(retval%mod)
    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 a in A[:K]:
    if a<0:
        use_minus+=1
    retval*=a
    retval=retval%mod

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

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7

n, k = map(int, input().split())
alst = list(map(int, input().split()))

if n == 1:
    print(alst[0])
    exit()

alst.sort()

if alst[0] >= 0:
    ans = 1
    alst.sort(reverse = True)
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

if alst[-1] <= 0:
    ans = 1
    if k % 2 == 1:
        alst.sort(reverse = True)
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

blst = []
for num in alst:
    try:
        blst.append([abs(num), abs(num) // num])
    except ZeroDivisionError:
        blst.append([abs(num), 0])
blst.sort(reverse = True)
if blst[k - 1] == 0:
    print(0)
    exit()
    
minus = 0
last_minus = 0
last_plus = 0
ans_lst = []
for i in range(k):
    if blst[i][1] == -1:
        minus += 1
        last_minus = blst[i][0]
    else:
        last_plus = blst[i][0]
    ans_lst.append(blst[i][0])

next_minus = 0
next_plus = 0

for i in range(k, n):
    if blst[i][1] == -1:
        next_minus = blst[i][0]
    elif blst[i][1] == 1:
        next_plus = blst[i][0]

if minus % 2 == 0:
    ans = 1
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

else:
    minus_s = last_minus * next_minus
    plus_s = last_plus * next_plus
    ans = 1
    if minus_s == plus_s == 0:
        if last_minus == 0:
            ans_lst.remove(last_plus)
            ans_lst.append(next_minus)
        else:
            ans_lst.remove(last_minus)
            ans_lst.append(next_plus)
        
    elif minus_s > plus_s:
        ans_lst.remove(last_plus)
        ans_lst.append(next_minus)
    else:
        ans_lst.remove(last_minus)
        ans_lst.append(next_plus)
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)