Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Constraints

1 \leq K \leq N \leq 2\times 10^5

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

The possible products of the three chosen elements are -24, -12, -8, and -6, so the maximum product is -6.

We print this value modulo (10^9+7), that is, 1000000001.

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

The possible products of the one chosen element are -1 and 1000000000, so the maximum product is 1000000000.

Sample Input 4

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

Sample Output 4

999983200

Be sure to print the product modulo (10^9+7).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Runtime Error

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

A.sort(reverse=True)

P = []
M = []
Ans = []
p = 0
m = 0

for i in range(N):
    if 0 <= A[i]:
        P.append(A[i])
    else:
        M.append(A[i])

M.sort()

if K % 2 == 1 and len(P) != 0:
    Ans.append(P[p])
    p += 1

while len(Ans) < K:

    #Mのストックがもうない時
    if m+1 >= len(M):
        Ans.append(P[p])
        if len(Ans) == K:
            break
        Ans.append(P[p + 1])
        p += 2
    elif p+1 >= len(P):
        Ans.append(M[m])
        if len(Ans) == K:
            break
        Ans.append(M[m + 1])
        m += 2
    else:
        if P[p]*P[p+1] < M[m]*M[m+1]:
            Ans.append(M[m])
            Ans.append(M[m+1])
            m += 2
        else:
            Ans.append(P[p])
            Ans.append(P[p + 1])
            p += 2

answer = 1
for i in range(K):
    answer = (answer * Ans[i]) % 1000000007

print(answer)

Submission status: Runtime Error

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

mod = 10**9 + 7

import copy
import bisect
index = bisect.bisect_right(A, 0)

plus_list = copy.copy(A[index:])
minus_list = copy.copy(A[:index])

count = 0
ans = 1

plus_num = len(plus_list) - 1
minus_num = 0
while count < K:
    if K - count == 1:
        ans *= plus_list.pop() % mod
        count += 1
    else:
        if not plus_list:
            if ans > 0 and (K - count) % 2 == 0:
                for i in range(K - count):
                    ans *= minus_list[minus_num + i] % mod
                    count += 1
            else:
                for i in range(K - count):
                    ans *= minus_list[i*(-1)-1] % mod
                    count += 1
            continue

        if len(minus_list) < 2:
            for i in range(K - count):
                ans *= plus_list[plus_num - i] % mod
                count += 1
            continue

        if plus_list[plus_num] >= minus_list[minus_num] * minus_list[minus_num+1]:
            ans *= plus_list[plus_num] % mod
            plus_num -= 1
            count += 1
        else:
            ans *= minus_list[minus_num] * minus_list[minus_num+1] % mod
            minus_num += 2
            count += 2
print(ans % mod)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
MOD = 1000000007  # type: int


def solve(N: int, K: int, A: "List[int]"):
    mp = sum([int(a<=0) for a in A])
    pl = True
    if (N == K):
        if mp%2 == 0:     pl = True
        else:     pl = False
    if (mp == N):
        if K%2 == 0: pl = True
        else: pl = False

    absA = sorted(A, key=abs)
    sA = deque(absA)
    ans = 1
    if pl:
        for i in range(K):
            ans*= sA.pop()
            # print(ans)
        if ans<0:
            pre=absA[i]
            prei = i
            while((i!=N) or (absA[i] * pre)>0 ): i+=1
            if i==N:
                pre = avsA[prei+1]
                i = prei-1
                while( (i!=N) or (absA[i]*pre)>0 ): i-=1
            ans//= absA[i]
            ans*= pre

        print(ans%MOD)



    else:
        for i in range(K):
            ans*= sA.popleft()
        print(ans%MOD)


    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

out = 0
for v in itertools.combinations(inList, 2):
    tmp = 1
    for i in range(len(v)):
        tmp = tmp*v[i]
    if tmp > out: out = tmp
print(tmp)

Submission status: Runtime Error

Solution code:

def main():
    MOD = 10**9+7
    n,k = map(int, input().split())
    al = list(map(int, input().split()))
    al_abs = []
    al_nl = []
    for a in al: 
        if a > 0: sig = 1
        elif a < 0 : 
            sig = -1
            al_nl.append(a)
        else: sig = 0
        al_abs.append((abs(a), sig))

    al_abs.sort(reverse=True)
    n_cnt = 0
    last_p = -1
    last_n = -1
    for i in range(k):
        a, sig = al_abs[i]
        if sig == -1:
            n_cnt+=1
            last_n = i
        elif sig == 1:
            last_p = i
    
    ans = 1
    if n_cnt%2 == 0:
        for i in range(k):
            a, sig = al_abs[i]
            ans *= a
            ans %= MOD
        print(ans)
        exit()


    next_p = -1
    next_n = -1 
    for i in range(k,n):
        a, sig = al_abs[i]
        if sig == 1 and next_p == -1:
            next_p = i
        elif sig == -1 and next_n == -1:
            next_n = i
        if next_n != -1 and next_p != -1:
            break

    comp_np = 0
    if next_p != -1:
        last_n_val = al_abs[last_n][0]
        next_p_val = al_abs[next_p][0]
        comp_np = next_p_val*(1.0)/last_n_val

    comp_pn = 0
    if next_n != -1 and last_p != -1:
        last_p_val = al_abs[last_p][0]
        next_n_val = al_abs[next_n][0]
        comp_pn = next_n_val*(1.0)/last_p_val

    if comp_np == 0 and comp_pn > 0:
        np_or_pn = False
    elif comp_pn == 0 and comp_np > 0:
        np_or_pn = True
    elif comp_np > 0 and comp_pn > 0:
        if next_p_val*last_p_val > next_n_val*last_n_val:
            np_or_pn = True
        else:
            np_or_pn = False

    elif comp_np == 0 and comp_pn == 0:
        if 0 in al:
            print(0)
            exit()
        else:
            al_nl.sort(reverse=True)
            for i in range(k):
                a = al_nl[i]
                ans *= (a)
                ans %= MOD
            print(ans)
            exit()


    # print(next_p, next_n, comp_np, comp_pn)

    for i in range(k):
        if np_or_pn and i == last_n:
            continue
        if (not np_or_pn) and i == last_p:
            continue
        a, sig = al_abs[i]
        ans *= a
        ans %= MOD

    if np_or_pn:
        ans *= next_p_val
        ans %= MOD
    else:
        ans *= next_n_val
        ans %= MOD

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

ans = 1

p_list, m_list = [], []
for i in a:
    if i<0: m_list.append(i)
    elif i>0: p_list.append(i)
    else: zero_flag = True

n = len(p_list)+len(m_list)

if len(p_list)+len(m_list)<k:
    print(0)
    sys.exit()
if k==n:
    ans = a[0]
    for i in range(1, k):
        ans *= a[i]
        ans %= mod
    print(ans)
    sys.exit()
if n==len(m_list):
    if zero_flag:
        print(0)
        sys.exit()
    else:
        ans = m_list[-1]
        for i in range(1, k):
            ans *= m_list[n-i-1]
            ans %= mod
        print(ans)
        sys.exit()


p_num, m_num = len(p_list)-1, 0

while k>0:
    p_mul, m_mul = 0, 0
    
    if k==3:
        if m_mul+1<len(m_list) and p_mul+1==2:
            m_mul = m_list[m_num]*m_list[m_num+1]*p_list[p_num]
            p_mul = p_list[p_num]*p_list[p_num-1]*m_list[m_num]
            if p_mul>m_mul:
                ans *= p_mul
                ans %= mod 
            else:
                ans *= m_mul
                ans %= mod
        elif m_mul+1<len(m_list) and p_mul+1<len(p_list):
            m_mul = m_list[m_num]*m_list[m_num+1]*p_list[p_num]
            p_mul = p_list[p_num]*p_list[p_num-1]*m_list[m_num]
            mm_mul = p_list[p_num]*p_list[p_num-1]*p_list[p_num-2]
            if p_mul>m_mul and p_mul>mm_mul:
                ans *= p_mul
                ans %= mod 
            elif m_mul>p_mul and m_mul>mm_mul:
                ans *= m_mul
                ans %= mod
            else:
                ans *= mm_mul
                ans %= mod
            break
    if k==1:
        if p_num<0:
            if zero_flag:
                print(0)
                sys.exit()
        ans *= p_list[p_num]
        ans %= mod
        break
    if m_mul+1<len(m_list):
        m_mul = m_list[m_num]*m_list[m_num+1]
    if p_mul+1<len(p_list):
        p_mul = p_list[p_num]*p_list[p_num-1]
    if p_mul>m_mul:
        ans *= p_mul
        ans %= mod
        p_num -= 2
    else:
        ans *= m_mul
        ans %= mod
        m_num += 2
    k -= 2
print(ans)

Submission status: Runtime Error

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
mod=10**9+7
 
def do():
    n,k=INTM()
    a=LIST()
    p=[]
    m=[]
    z=[]
    for i in a:
        if i>0:
            p.append(i)
        elif i<0:
            m.append(i)
        else:
            z.append(i)
    
    p=sorted(p)
    m=sorted(m)
    mr=sorted(m,reverse=True)
    lp=len(p)
    lm=len(m)
    lz=len(z)
    
    if n-k<lz:
        ans=0
    else:
        if (lp==0 and k%2==1):
            if lz!=0:
                ans=0
            else:
                ans=1
                for i in range(k):
                    ans*=abs(mr[i])%mod
                ans=(ans*(-1))%mod
            
        elif (lp+lm==k and lm%2==1):
            if lz!=0:
                ans=0
            else:
                ans=1
                for i in range(k):
                    ans*=abs(a[i])%mod
                ans=(ans*(-1))%mod
                
        else:
            ans=1
            pc=0
            mc=0
            for i in range(k-1):
                if p[pc]>=abs(m[mc]):
                    ans*=p[pc]%mod
                    pc+=1
                else:
                    ans*=abs(m[mc])%mod
                    mc+=1
            
            if mc%2==1:
                ans*=abs(m[mc])%mod
            else:
                ans*=p[pc]%mod
    
    print(ans) 
if __name__ == '__main__':
    do()

Submission status: Runtime Error

Solution code:
#E
N,K = map(int,input().split())
an = list(map(int,input().split()))
s = []
ans = 1

under  = len([s for s in an if s<0])

if K>=N-under:
    s = sorted(an,reverse=True)
    for i in range(K):
        ans *= s[i]
        ans %=  10**9+7
elif (under - k)%2 == 0:
    s = sorted(an,reverse=True)
    for i in range(K):
        ans *= s[i]
        ans %=  10**9+7
else:
    s = sorted(an)
    for i in range(K):
        ans *= s[i]
        ans %=  10**9+7
    

print(ans)

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split()))
N = int(a[0])
K = int(a[1])
A_i = list(map(int, input().split()))
A_pos = [i for i in A_i if i > 0]
A_neg = [i for i in A_i if i < 0]
A_zer = [i for i in A_i if i == 0]

A_pos = sorted(A_pos)
A_neg = sorted(A_neg)
A_neg.reverse()
# zettaiti tiisai jun

ret = 1

if len(A_pos) == 0:
    if len(A_zer) > 0:
        ret = 0
    for i in range(K):
        ret = ret * A_neg[i]
        ret = ret % (10**9+7)
    if ret < 0:
        ret += 10**9+7
else:
    if K % 2 == 1:
        ret *= A_pos[-1]
        A_pos = A_pos[:-1]

    for i in range(K//2):
        if len(A_pos) == 0 and len(A_neg) == 2:
            ret = ret * A_neg[0] * A_neg[1]
            continue
        if len(A_pos) == 1 and len(A_neg) == 1:
            ret = ret * A_neg[0] * A_pos[0]
            continue
        if len(A_pos) == 2 and len(A_pos) == 0:
            ret = ret * A_pos[0] * A_pos[1]
            continue
        if len(A_pos) < 2:
            c1 = 0
        else:
            c1 = A_pos[-1] * A_pos[-2]

        if len(A_neg) >= 2:
            c2 = A_neg[-1] * A_neg[-2]
        else:
            c2 = 0

        if c1 > c2:
            ret = ret * A_pos[-1] * A_pos[-2]
            A_pos = A_pos[:-2]
        else:
            ret = ret * A_neg[-1] * A_neg[-2]
            A_neg = A_neg[:-2]
        ret = ret % (10**9+7)
        if ret < 0:
            ret += 10**9+7
print(ret)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)
MOD = 10 ** 9 + 7

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, K = ZZ()
    A = ZZ()
    p = []
    z = []
    m = []
    for a in A:
        if a > 0: p.append(a)
        elif a == 0: z.append(a)
        else: m.append(a)

    if len(p) == 0 and len(z) == 0 and K%2 == 1: #答えが負
        m = sort(m)[::-1]
        ans = 1
        for i in range(K):
            ans *= m[i]
            ans %= MOD
        print(ans)
        return
    else:
        if K - len(p) - len(m) > 0:
            print(0)
            return
        else:
            p.sort(reverse=True)
            m.sort()
            ans = 1
            itr = itrp = 0
            while K > 0:
                if itr+1 < len(m): c1 = (m[itr] * m[itr+1])
                else: c1 = 0
                if itrp+1 < len(p): c2 = (p[itrp] * p[itrp+1])
                else: c2 = 0

                if c1 > c2 and K >= 2:
                    ans *= c1
                    ans %= MOD
                    itr += 2
                    K -= 2
                else:
                    ans *= c2
                    ans %= MOD
                    itrp += 1
                    K -= 1
            print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,k=map(int, input().split())
a = list(map(int, input().split()))
mod=10**9+7
if n==k:
    ans=1
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()

minus=[i for i in a if i<0]
plus=[i for i in a if i>=0]

minus=sorted(minus)
plus=sorted(plus,reverse=True)
if k%2==1 and len(plus)==0:
    ans=1
    for i in range(k):
        ans*=abs(minus[-i-1])
        ans%=mod
    print((mod-ans)%mod)
    exit()

n_minus=len(minus)
n_plus=len(plus)

m_saiyo=0
for i in range(0, n_minus+1, 2): # i個minusから採用
    if i==0:
        continue
    if 0<=k-i<n_plus-1 and (minus[i-1]*minus[i-2])>=(plus[k-i]*plus[k-i+1]):
        m_saiyo=i

ans=1

if set(plus)=={0}:
    if m_saiyo==0:
        print(0)
        exit()

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

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))

mod = 10**9+7

#全部使う
if n == k:
    ans = 1
    for i in lst1:
        ans *= i
        ans %= mod
    print(ans)
    exit() 

lst1.sort()
i = 0
minus = []
m = 0
while i < n and lst1[i] < 0:
    minus.append(lst1[i])
    m += 1
    i += 1
zero = 0
while i < n and lst1[i] == 0:
    zero += 1
    i += 1
plus = []
p = 0
while i < n:
    plus.append(lst1[i])
    p += 1
    i += 1

#必ず0を使う
if n-zero < k:
    print(0)
    exit()

#少なくともans<=0になる(負数にしかならない場合、0を掛けた方が良い場合)
if p==0 and not even(k):
    if zero:
        print(0)
        exit()
    else:
        ans = 1
        for i in range(k):
            ans *= minus[-1-i]
            ans %= mod
        print(ans)
        exit()

#0を使わないようにすると、ちょうど負数が奇数個になってしまう場合
if n-zero == k and not even(m):
    print(0)
    exit()

#以下、必ず正の数にできる
#まだなんか見落としあるかも…

#負数はこの時点で上位からペアとして良い
pair = []
for i in range(0,m-1,2): #絶対値が大きい順
    pair.append(minus[i]*minus[i+1])

ans = 1
midx = 0 #cost2
pidx = 0 #cost1
plus.reverse() #降順
while k:
    if k == 1:
        if pidx <= len(plus):
            ans *= plus[pidx]
            ans %= mod
            k -= 1
            pidx += 1
        else:
            print(0)
            exit()
    elif k == 2:
        if midx <= len(pair) and pidx+1 <= len(plus):
            if pair[midx] >= plus[pidx]*plus[pidx+1]:
                ans *= pair[midx]
                ans %= mod
            else:
                ans *= plus[pidx]*plus[pidx+1]
                ans %= mod

        elif midx <= len(pair):
            ans *= pair[midx]
            ans %= mod
        else:
            ans *= plus[pidx]*plus[pidx+1]
            ans %= mod
        
        break
    elif k >= 3:
        if midx <= len(pair):
            if pidx+2 <= len(plus): #max-2がある
                if pair[midx] >= plus[pidx+1]*plus[pidx+2]:
                    ans *= pair[midx]
                    ans %= mod
                    midx += 1
                    k -= 2
                else:
                    ans *= plus[pidx]
                    ans %= mod
                    pidx += 1
                    k -= 1
            elif pidx+1 <= len(plus): #max-1がある
                if pair[midx] >= plus[pidx]*plus[pidx+1]:
                    ans *= pair[midx]
                    ans %= mod
                    midx += 1
                    k -= 2
                else:
                    ans *= plus[pidx]
                    ans %= mod
                    pidx += 1
                    k -= 1
            elif pidx <= len(plus): #maxしかない
                if pair[midx] >= plus[pidx]:
                    ans *= pair[midx]
                    ans %= mod
                    midx += 1
                    k -= 2
                else:
                    ans *= plus[pidx]
                    ans %= mod
                    pidx += 1
                    k -= 1
            else: #plusにない
                ans *= pair[midx]
                ans %= mod
                midx += 1
                k -= 2

                
        else:
            ans *= plus[pidx]
            ans %= mod
            pidx += 1
            k -= 1

print(ans)

Submission status: Runtime Error

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  l=LI()

  zero_contain=False
  if l.count(1):
    zero_contain=True

  al=[]
  for x in l:
    al.append((abs(x),x))

  al=sorted(al,key=lambda x:x[0],reverse=True)

  zero=False
  minus=0

  ansl=[]
  for ax,x in al[:k]:
    if x==0:
      zero=True
    if x<0:
      minus+=1
    ansl.append(x)

  ans=1
  for x in ansl:
    if x==0:
      ans=0
      break
    elif x>0:
      pass
    else:
      ans*=-1

  if ans>0:
    ans=1
    for x in ansl:
      ans*=x
      ans%=mod
    return ans
  elif ans<0:
    for x in ansl[::-1]:
      if x<0:
        t=x
        ansl2=copy.deepcopy(ansl)
        ansl2.remove(t)
        break
    ff=False
    for ax,x in al[k:]:
      if x>=0:
        ans2*=x
        ff=True
        break
    if not ff:
      ansl2=[]
      for ax,x in al[::-1][:k]:
        ansl2.append(x)

    ans2=1
    for x in ansl2:
      ans2*=x
      ans2%=mod

    # print(ans,ans2)

    ans=1
    for x in ansl:
      ans*=x
      ans%=mod

    return max(ans,ans2)
  else:
    return 0

# main()
print(main())

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right

mod = 10 ** 9 + 7
n, k = map(int, input().split())
A = list(map(int, input().split()))
# dp = [[[0] * (2) for _ in range(k+1)]for _ in range(n+1)]
# # dp[桁][数][負数の数=1,0]

A.sort()
n_minus = bisect_left(A, 0)
n_zero = bisect_right(A, 0) - n_minus
n_plus = n - n_minus - n_zero

possible_max = min(k, n_minus)
possible_min = max(k - (n_plus + n_zero), 0)
ans = 1
if possible_max == possible_min and possible_min % 2 == 1:
    a = A[n + 100]
    if k - (possible_min) > 0 and n_zero > 0:
        print(0)
        exit()
    A_plus = A[n - (n_plus) :]
    A_minus = A[:n_minus]
    A_minus.sort(reverse=True)
    # 負の数は奇数個小さい方から選ぶ
    for i in range(possible_min):
        ans *= A_minus[i]
        ans %= mod
    for i in range(k - possible_min):
        ans *= A_plus[i]
        ans %= mod
else:
    # 正の数に成る→大きいものがほしい
    # 負の数は偶数個、これの数を決め打つ
    # 計算すると大変だから大小を考える

    A_plus = A[n - (n_plus) :]
    A_plus.sort(reverse=True)
    A_minus = A[:n_minus]

    # 負の数を使う数を決め打つ
    # 最終的に正にできるパターン
    minus_num_max = min(n_minus // 2, k // 2)
    select = k - 2 * minus_num_max
    if n_plus < select:
        print(0)
        exit()
    # 負の数にしかできないパターン
    # 遊びがない時に奇数個の負の数を選ばざるを得ない
    # その時に0があるかどうかパターン
    plus_shortage = 0
    minus_shortage = 0
    for i in range(minus_num_max + 1):
        # 各々使う個数
        p = k - 2 * i
        m = 2 * i
        if p - 2 < 0:
            plus_shortage = 1
            break
        if p > n_plus:
            continue
        plus_kouho = A_plus[p - 1] * A_plus[p - 2]
        if m + 1 >= n_minus:
            minus_shortage = 1
            break
        minus_kouho = A_minus[2 * i] * A_minus[2 * i + 1]
        if minus_kouho > plus_kouho:
            ans *= minus_kouho
            ans %= mod
        else:
            break

    for j in range(k - 2 * i):
        ans *= A_plus[j]
        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 + MOD
            for i in range(k):
                ans *= am[i]
                ans %= MOD
    else:
        ans = 1
        for i in range(k):
            ans *= am[i]
            ans %= MOD
elif nm == 0:
    ans = 1
    for i in range(k):
        ans *= ap[i]
        ans %= MOD
elif nm == 1 and np + nm == k:
    if nz > 0:
        ans = 0
    else:
        ans = -1 + MOD
        for i in range(np):
            ans *= ap[i]
            ans %= MOD
        for i in range(nm):
            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:
PRIME = 10 ** 9 + 7

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

_a = sorted(a,key=abs,reverse=True)

ans = 1
if n == k:
  for i in range(k):
    ans = (ans * _a[i]) % PRIME
else:
  minus_n = 0
  minus_k = 0
  zero = 0
  min_minus = -1
  min_plus = -1
  max_minus = -1
  min_plus = -1
  
  for i in range(n):
    if _a[i] < 0:
      minus_n += 1
      if i < k:
        minus_k += 1
        min_minus = i
      else:
        max_minus = i
    elif _a[i] == 0:
      zero += 1
    elif i < k:
      min_plus = i
    else:
      max_plus = i
  
  if minus_n + zero == n and k % 2 == 1:
    for i in range(1, k + 1):
      ans = (ans * _a[-i]) % PRIME
  elif minus_k % 2 == 0:
    for i in range(k):
      ans = (ans * _a[i]) % PRIME
  elif max_plus >= 0 and (max_minus < 0 or abs(a[max_minus] / a[min_plus]) < abs(a[max_plus] / a[min_minus])):
    for i in range(k):
      if i != min_minus:
        ans = (ans * _a[i]) % PRIME
    ans = (ans * _a[max_plus]) % PRIME
  else:
    for i in range(k):
      if i != min_plus:
        ans = (ans * _a[i]) % PRIME
    ans = (ans * _a[max_minus]) % PRIME
    
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
    if lenZ != 0 and lenM % 2 == 1: #必要ないと思うけど頭の中がこんがらがって居るので一応
        print(0)
        exit()
    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 and j+2<=lenM:
        ans.append(M[j]*M[j+1])
        j+=2
        count+=1
        continue
    if j+2>lenM and i+2<=lenP:
        ans.append(P[i]*P[i+1])
        i+=2
        count+=1
        continue
    if i+2>lenP and j+2 > lenM:
        print(0)
        exit()
    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(len(ans)):
    intans*=ans[i]
    intans%=MOD
print(intans)

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(1)

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]
    if neg:
        ans *= -b
    else:
        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:
            if last_nneg != -1:
                ans *= pow(last_nneg, mod - 2, mod)
            else:
                ans *= pow(last_neg, mod - 2, mod)
                ans *= pow(-b, mod - 2, mod)
                for j in range(k + 1, n):
                    if not A[j][1]:
                        ans *= A[j][0]
                        break
        ans %= mod
        print(ans)
        exit()

Submission status: Runtime Error

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
As = list(map(int, input().split()))
MOD = 10 ** 9 + 7

def multiReduce(array):
    ret = 1
    for a, s in array:
        if s == 0:
            ret = ret * a % MOD
        else:
            ret = ret * (-a) % MOD
    return ret

arr = []
for a in As:
    if a >= 0:
        arr.append((a, 0))
    else:
        arr.append((-a, 1))

arr.sort(reverse=True)

if arr[K-1][0] == 0:
    print(0)
    exit()

lastPlus = None
lastPlusIdx = None
lastMinus = None
lastMinusIdx = None
numMinus = 0
for i in range(K):
    a = arr[i]
    if a[1] == 0:
        lastPlus = a[0]
        lastPlusIdx = i
    else:
        lastMinus = -a[0]
        lastMinusIdx = i
        numMinus += 1

if numMinus % 2 == 0:
    print(multiReduce(arr[:K]))
    exit()

nextPlus = None
nextMinus = None
for i in range(K, N):
    a = arr[i]
    if a[1] == 0 and nextPlus is None:
        nextPlus = a[0]
    elif a[1] == 1 and nextMinus is None:
        nextMinus = -a[0]

BD = None
if lastMinus and nextPlus:
    BD = lastMinus * nextPlus
AC = None
if lastPlus and nextMinus:
    AC = lastPlus * nextMinus

if BD and (AC is None or BD >= AC):
    arr[lastMinusIdx] = nextPlus
    print(multiReduce(arr[:K]))
    exit()
elif AC and (BD is None or BD < AC):
    arr[lastPlusIdx] = nextMinus
    print(multiReduce(arr[:K]))
    exit()

print(multiReduce(arr[N-K:]))

Submission status: Runtime Error

Solution code:
import sys
import functools
import operator

n, k = map(int, input().split())
l = list(map(int, input().split()))
if 0 in l:
  if n-l.count(0) >= k:
    l.remove(0)
  else:
    print(0)
    sys.exit()

l = sorted(l)
j = 0
num = 0
Max = functools.reduce(operator.mul, l[:k])
Max_ = Max
for i in range(k-1, -1, -1):
  x = int(Max_*(l[n-j-1]/l[i]))
  j += 1
  Max_ = x
  if Max < x:
    Max = x
    num = 0
  else:
    num += 1
  
  if num == 2:
    break
      
print(Max%(10**9+7))