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()))
MOD = 10 ** 9 + 7

plus = []
minus = []
zero = []
for i in range(n):
    if a[i] < 0:
        minus.append(abs(a[i]))
    elif a[i] > 0:
        plus.append(a[i])
    else:
        zero.append(0)


len_p = len(plus)
len_m = len(minus)
len_z = len(zero)

is_z = False
is_p = False
if len_z != 0:
    is_z = True

cnt = 2 * (len_m // 2) + len_p
if cnt >= k:
    is_p = True
if len_p == 0 and k % 2 == 1:
    is_p = False

if is_p:
    minus = sorted(minus, reverse=True)
    plus = sorted(plus, reverse=True)
    ans = 1
    if k % 2 == 1:
        k -= 1
        ans = plus[0]
        del plus[0]
    tmp = []
    for i in range(len(minus) // 2):
        tmp.append(minus[2 * i] * minus[2 * i + 1] % MOD)
    for i in range(len(plus) // 2):
        tmp.append(plus[2 * i] * plus[2 * i + 1] % MOD)
    tmp = sorted(tmp, reverse=True)
    for i in range(k // 2):
        ans *= tmp[i]
        ans %= MOD
    print(ans)
    exit()

elif is_z:
    print(0)
    exit()

else:
    minus = sorted(minus)
    ans = -1
    for i in range(k):
        ans *= minus[i]
        ans %= MOD
    print(ans)
    exit()

Submission status: Runtime Error

Solution code:
from math import log2

N, K = map(int, input().split())
A = [int(i) for i in input().split()]

mod = 10 ** 9 + 7

p = []
m = []
for a in A :
  if a > 0 :
    p.append(a)
  else :
    m.append(-a)
    
p.sort(reverse=True)
m.sort(reverse=True)
pl = [0]
ml = [0]

for i in range(len(p)) :
  pl.append(log2(p[i]))
for i in range(len(m)) :
  ml.append(log2(m[i]))
for i in range(1, len(pl)) :
  pl[i] += pl[i - 1]
for i in range(1, len(ml)) :
  ml[i] += ml[i - 1]

Mi = -1
Mv = 0
for i in range(0, len(ml), 2) :
  j = K - i
  if len(pl) <= j or j < 0 : continue
  if ml[i] + pl[j] > Mv :
    Mi, Mv = i, ml[i] + pl[j]

if Mi != -1 :
  ret = 1
  for i in range(K - Mi) :
    ret *= p[i]
    ret %= mod
  for i in range(Mi) :
    ret *= m[i]
    ret %= mod
else :
  x = [abs(a) for a in A]
  x.sort()
  ret = 1
  for i in range(K) :
    ret *= x[i]
    ret %= mod
  ret = -ret % mod
  
print(ret)

Submission status: Runtime Error

Solution code:
mod = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort(key=lambda x:-abs(x))
p = []
n = []
for i in range(K):
    a = A[i]
    if a>0:
        p.append(a)
    else:
        n.append(a)

if len(n)%2==0:
    ans = 1
    for a in n:
        ans *= a
        ans %= mod
    for a in p:
        ans *= a
        ans %= mod
else:
    ap = 0
    an = 0
    for i in range(K,N):
        if ap==0 and A[i]>0:
            ap = A[i]
        if an==0 and A[i]<0:
            an = A[i]
    if len(p)*len(n)>0:
        ap_ = p[-1]
        an_ = -n[-1]
        if ap_*an_==0:
            ans = 0
        else:
            if ap*ap_>an*an_:
                n.pop()
                p.append(ap)
            else:
                p.pop()
                n.append(an)
            ans = 1
            for a in n:
                ans *= a
                ans %= mod
            for a in p:
                ans *= a
                ans %= mod
    elif len(p)>0:
        ans = 1
        for a in p:
            ans *= a
            ans %= mod
    elif len(n)>0:
        for a in n:
            ans *= a
            ans %= mod
if len(p)+len(n)<K:
    ans = 0
if len(p)==0 and len(n)==K and K%2==1:
    An = [A[i] for i in range(N) if A[i]<0]
    An.sort()
    An = An[::-1]
    ans = 1
    for i in range(K):
        ans *= An[i]
        ans %= 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(" ")]

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)

use_minus=min(K, (len(minus)//2)*2)
use_plus=K-use_minus

mul=1
for i in minus[:use_minus]:
    mul*=i
for i in plus[:use_plus]:
    mul*=i
retval=mul
while use_plus<=len(plus) and use_minus>=0:
    use_minus-=2
    mul=mul//minus[use_minus]
    mul=mul//minus[use_minus+1]
    mul*=plus[use_plus]
    mul*=plus[use_plus+1]
    use_plus+=2

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

Submission status: Runtime Error

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

if K % 2 != 0:
    list.sort(reverse=True)
    for i in range(1,K):
        n=list[0]*list[i]
    print(n%((10^9)+7))
else:
    list.sort(reverse=True)
    for i in range(1,K):
        m=list[0]*list[i]
    list.sort()
    for i in range(1,K):
        o=list[0]*list[i]
    if m > o:
        print(m)
    else:
        print(o)

Submission status: Runtime Error

Solution code:
# cook your dish here
b=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
ans=int(-1e18)
prod=1 
mod=int(1e9+7)
for i in range(0,b[1]):
    prod*=a[i]
ans=max(prod,ans)
for i in range(0,b[0]-b[1]): 
    prod//=a[i]
    prod*=a[i+b[1]]
    ans=max(prod,ans)  
if ans<0:
    ans=(ans+mod)%mod 
else:
    ans%=mod 
print(ans)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
large_p = 10**9 + 7
from collections import deque
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()
    a3 = [i for i in a if i < 0] #minus
    a2 = [i for i in a if i > 0] #plus
    a2.sort()
    a3.sort(reverse=True)
    a2d = deque(a2)
    a3d = deque(a3)
    r = 1
    cnt = 0
    minus = 0
    while cnt < k:
        if cnt == (k - 2):
            if minus % 2 == 0:
                if len(a3d) >= 2 and len(a2d) >= 2:
                    t = max(a3d[0] * a3d[1], a2d[0] * a2d[1])
                    r *= t
                    break
                elif len(a3d) >= 2:
                    r *= (a3d[0] * a3d[1])
                    break
                elif len(a2d) >= 2:
                    r *= (a2d[0] * a2d[1])
                    break
                elif a2d:
                    r *= a2d[0]
                    break
            else:
                r *= a3d[0]
                r *= a2d[0]
                break
        if a2d and a3d:
            if a2d[0] > (a3d[0] * -1):
                r *= a2d.popleft()
            else:
                if cnt == (k - 1) and minus % 2 == 0:
                    if a2d:
                        r *= a2d.popleft()
                    else:
                        break
                else:
                    r = r * (a3d.popleft() * -1)
                    minus += 1
            cnt += 1
        elif a2d:
            r *= a2d.popleft()
            cnt += 1
        elif a3d:
            if cnt == (k - 1) and minus % 2 == 0:
                break
            else:
                r = r * (a3d.popleft() * -1)
                cnt += 1
                minus += 1

    print(r)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7
it = lambda: list(map(int, input().strip().split()))

def solve():
    N, K = it()
    A = it()
    
    neg = []
    pos = []
    for i in range(N):
        if A[i] < 0:
            neg.append(A[i])
        elif A[i] > 0:
            pos.append(A[i])
    
    if not neg and not pos:
        return 0
    
    pos.sort()
    neg.sort(reverse=True)

    if not pos and K % 2 == 1:
        ans = 1
        for i in range(K):
            ans = ans * neg[i] % MOD
        return ans

    ans = 1
    i = 0
    j = 0
    for _ in range(K >> 1):
        if len(pos) >= 2 and len(neg) >= 2:
            if neg[-1] * neg[-2] >= pos[-1] * pos[-2]:
                ans = ans * neg.pop() % MOD * neg.pop() % MOD
            else:
                ans = ans * pos.pop() % MOD * pos.pop() % MOD
        elif len(pos) >= 2:
            ans = ans * pos.pop() % MOD * pos.pop() % MOD
        elif len(neg) >= 2:
            ans = ans * neg.pop() % MOD * neg.pop() % MOD
    
    if K % 2 == 1:
        if pos:
            ans = ans * pos.pop() % MOD
        else:
            ans = ans * neg.pop() % MOD
    return ans


if __name__ == '__main__':
    print(solve())

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    from bisect import bisect_left, bisect_right
    N, K = MAP()
    A = LIST()
    A.sort()
    neg = bisect_left(A, 0)
    pos = bisect_right(A, 0)
    negative = A[:neg]
    zeros = A[neg:pos]
    positive = A[pos:]
    if len(negative) + len(positive) < K:
        print(0)
        return
    if len(positive) == 0:
        if K % 2 == 1:
            if len(zeros) > 0:
                print(0)
                return
            else:
                ans = 1
                for n in negative[-K:]:
                    ans *= (-n)
                    ans %= MOD
                ans *= -1
                print(ans % MOD)
                return
        else:
            ans = 1
            for n in negative[:K]:
                ans *= (-n)
                ans %= MOD
            print(ans % MOD)
            return

    # 負の数は二個一で採用できる
    phead = 0
    nhead = 0
    k = K
    ans = 1
    while k > 1 and phead+1 < len(positive) and nhead+1 < len(negative):
        # 負上から二個
        ncand = 0
        if nhead + 1 < len(negative):
            ncand = negative[nhead]*negative[nhead+1]
        pcand = 0
        if phead + 1 < len(positive):
            pcand = positive[phead]*positive[phead+1]
        if ncand < pcand:
            k -= 2
            ans *= pcand
            ans %= MOD
            phead += 2
        else:
            k -= 2
            ans *= ncand
            ans %= MOD
            nhead += 2
    if nhead + 1 >= len(negative):
        # 残りは正から採用する
        # ここではpositiveは尽きない
        while k > 0:
            ans *= positive[phead]
            ans %= MOD
            phead += 1
            k -= 1
        print(ans)
        return
    if phead + 1 >= len(positive):
        # 残りは負から採用する。最後、調整が必要ならpositiveひとつ放出する
        while k > 1:
            ans *= negative[nhead]*negative[nhead+1]
            ans %= MOD
            nhead += 2
            k -= 2
        if k == 1:
            ans *= positive[phead]
            ans %= MOD
        print(ans)
        return
    if k == 1:
        ans *= positive[phead]
        ans %= MOD
        print(ans)
        return
    #
    # 負の個数、0の個数,正の個数
    # 負の個数+正の個数 < Kの場合、0
    # 正の個数 == 0の場合、
    #   Kが奇数なら、0か0に近いものをK個
    #   Kが偶数なら、大きい物をK個
    # 0 < 正の個数 <= K の場合、
    #   いくつ負を選ぶかという話 二個一で貪欲 最後は最大の正
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from math import log2
from itertools import accumulate

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 < 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

print(max_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()))
mod=10**9+7

B=[]
C=[]
Z=[]

for a in A:
    if a>0:
        B.append(a)
    elif a<0:
        C.append(-a)
    else:
        Z.append(0)

if K>len(B)+len(C):
    print(0)
    sys.exit()

if B==[]:
    ANS=1
    for i in range(K):
        ANS=ANS*(-C[i])%mod

    if Z==[]:
        print(ANS)
    elif ANS<0:
        print(0)
    else:
        print(ANS)

    sys.exit()

    
B.sort(reverse=True)
C.sort(reverse=True)

if K<=len(B):
    S=1
    for i in range(K):
        S=S*B[i]%mod

    ind=0
    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

else:
    S=1
    for i in range(K):
        S=S*B[i]%mod

    for j in range(K-len(B)):
        S=S*C[i]%mod

    ind=K-len(B)

    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

Submission status: Runtime Error

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

plus = []
minus = []
zero = []
for i in range(n):
    if a[i] < 0:
        minus.append(abs(a[i]))
    elif a[i] > 0:
        plus.append(a[i])
    else:
        zero.append(0)


len_p = len(plus)
len_m = len(minus)
len_z = len(zero)

is_z = False
is_p = False
if len_z != 0:
    is_z = True

cnt = len_m // 2 + len_p
if cnt >= k:
    is_p = True

if is_p:
    minus = sorted(minus, reverse=True)
    plus = sorted(plus, reverse=True)
    ans = 1
    if k % 2 == 1:
        k -= 1
        ans = plus[0]
        del plus[0]
    tmp = []
    for i in range(len(minus) // 2):
        tmp.append(minus[2 * i] * minus[2 * i + 1] % MOD)
    for i in range(len(plus) // 2):
        tmp.append(plus[2 * i] * plus[2 * i + 1] % MOD)
    tmp = sorted(tmp, reverse=True)
    for i in range(k // 2):
        ans *= tmp[i]
        ans %= MOD
    print(ans)
    exit()

elif is_z:
    print(0)
    exit()

else:
    minus = sorted(minus)
    ans = -1
    for i in range(k):
        ans *= minus[i]
        ans %= MOD
    print(ans)
    exit()

Submission status: Runtime Error

Solution code:
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
cnt_plus=0
cnt_zero=0
cnt_minus=0
arr_plus=[]
arr_minus=[]
for i in range(n):
  if arr[i]>0:
    cnt_plus+=1
    arr_plus.append(arr[i])
  elif arr[i]<0:
    cnt_minus+=1
    arr_minus.append(-arr[i])
  else:
    cnt_zero+=1
if cnt_plus+cnt_minus<k:
  print(0)
  exit()
if cnt_plus==0 and k%2==1:
  arr_minus=sorted(arr_minus)
  tmp=1
  for i in range(k):
    tmp*=arr_minus[i]
    tmp%=mod
  print((-tmp)%mod)
else:
  arr_plus=sorted(arr_plus,reverse=True)
  arr_minus=sorted(arr_minus,reverse=True)
  acum_plus=[1]
  for i in range(len(arr_plus)):
    acum_plus.append((acum_plus[-1]*arr_plus[i])%mod)
  acum_minus=[1]  
  for i in range(len(arr_minus)):
    acum_minus.append((acum_minus[-1]*arr_minus[i])%mod)  
  if k%2==0:
    ans=0
    for i in range(0,len(arr_plus)+1,2):
      j=k-i
      if len(arr_minus)<j:
        continue
      ans=max(ans,(acum_plus[i]*acum_minus[j])%mod)
    print(ans)
  else:
    ans=0
    for i in range(1,len(arr_plus)+1,2):
      j=k-i
      if len(arr_minus)<j:
        continue
      ans=max(ans,(acum_plus[i]*acum_minus[j])%mod)
    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 A and B:
    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 A:
    for i in A:
        S.append(i)
if B:
    for i in A:
        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
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,mod))%mod
if K == N:
    print(ans)
    quit()
if K != N:
    r = S[j-1]
    if f % 2 == 0:
        print(ans)
    else:
        if r < 0:
            r = -r
        ans *= r
        ans = ans % mod
        if r > 0:
            d = pow(q,mod-2,mod)
        else:
            d = pow(p,mod-2,mod)
            ans *= d
            ans = ans % mod
        print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import math
n,k = map(int, input().split())
a = list(map(int, input().split()))
a1 = [item for item in a if item>0]
a2 = [item for item in a if item<0]
n1 = sum(item>0 for item in a)
n2 = sum(item<0 for item in a)
nz = sum(item==0 for item in a)
a1.sort(reverse=True)
a2.sort()
c1 = [math.log2(item) for item in a1]
c2 = [math.log2(-item) for item in a2]
def cumsum(a):
    """l[i] = sum(a[:i]) なるlを返す
    sum(a[i:j]) == l[j+1] - l[i]
    """
    c = 0
    l = [None] * (len(a)+1)
    for i,num in enumerate(a):
        l[i] = c
        c += num
    l[-1] = c
    return l
cc1 = cumsum(c1)
cc2 = cumsum(c2)
if n1+n2<k:
    ans = 0
else:
    best = -10**12
    ind = None
    for i in range(n2//2+1):
        if 2*i>k:
            continue
        if 2*i+n1+nz<k:
            continue
        if k-2*i<=n1:
            val = cc2[2*i] + cc1[k-2*i]
            if val>best:
                ind = i
                best = val
    M = 10**9+7
    if ind is None:
        if nz>0:
            ans = 0
        else:
            # マイナスだけ
            ans = 1
            for i in range(k):
                ans *= a2[-(i+1)]
                ans %= M
    else:
        ans = 1
        for i in range(2*i):
            ans *= a2[i]
            ans %= M
        for i in range(k-2*i):
            ans *= a1[i]
            ans %= M
print(ans)

Submission status: Runtime Error

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

for i in range(1,K):
    n=list[0]*list[i]
    print(n)

print(n%((10^9)+7))

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


# mod m におけるaの逆元
def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m

    # 負の場合は m を足して正の数にする
    if u < 0:
        u += m
    return u


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

    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

    if N == K:
        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

    if next_plus is not None and prev_minus is not None:
        inv = modinv(prev_minus, MOD)
        tmp1 = inv * ans
        tmp1 %= MOD
        tmp1 *= next_plus
        tmp1 %= MOD
    else:
        tmp1 = -INF

    if next_minus is not None and prev_plus is not None:
        inv = modinv(prev_plus, MOD)
        tmp2 = inv * ans
        tmp2 %= MOD
        tmp2 *= next_plus
        tmp2 %= MOD
    else:
        tmp2 = -INF

    print(max(tmp1, tmp2))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
mod = 10**9 + 7

def sgn(v):
    return (v > 0) - (v < 0)

def compute_answer():
    v.sort(key=abs, reverse=True)
    prod = 1
    sg = 1
    for a in xrange(k):
        prod *= v[a]
        prod %= mod
        sg *= sgn(v[a])

    if sg >= 0:
        return prod

    if max(v) <= 0:
        prod = 1
        for a in xrange(-k,0):
            prod *= v[a]
            prod %= mod
        return prod

    def find_pair(comp):
        i = k-1
        while i >= 0 and comp(v[i]): i -= 1
        j = k
        while j < n and not comp(v[j]): j += 1
        if j == n: j = i
        return i, j
    i, j = find_pair(lambda w: w >= 0)
    I, J = find_pair(lambda w: w <= 0)
    if I >= 0 and v[j] * v[I] < v[i] * v[J]:
        i = I
        j = J

    prod = v[j]
    for a in xrange(k):
        if a != i:
            prod *= v[a]
            prod %= mod
    return prod

#for cas in xrange(input()):
    n, k = map(int, raw_input().strip().split())
    v = map(int, raw_input().strip().split())
    print compute_answer()

Submission status: Runtime Error

Solution code:
import math
def fun(arr, n, k) : 
    MaxProduct = 1
    for i in range(0, k) : 
        MaxProduct = (MaxProduct * arr[i] )%1000000007
          
    prev_product = MaxProduct 
    for i in range(1, n - k + 1) : 
        curr_product = ((prev_product // arr[i-1]) * arr[i+k-1])%1000000007 
        MaxProduct = max(MaxProduct, curr_product) 
        prev_product = curr_product 
    return MaxProduct
n,k=map(int,input().split())
seq=list(map(int,input().split()))
print(fun(seq,n,k)%1000000007)

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)
plus=sorted(plus,reverse=True)
minus=sorted(minus)

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)



retval=1
use_minus=0
for _ in range(K):
    if abs(minus[0])>abs(plus[0]):
        fact=minus.pop(0)
        retval*=fact
    else:
        fact=plus.pop(0)
        retval*=fact

if retval<0:
    retval=retval//fact
    if fact<0:
        retval*=plus[0]
    else:
        retval*=minus[0]
print(retval%(10**9+7))

Submission status: Runtime Error

Solution code:
from math import *
from copy import *
from string import *				# alpha = ascii_lowercase
from random import *
from sys import stdin,stdout
from sys import maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *
from collections import Counter		# d = dict(Counter(l))
import math
import math
import time
from queue import Queue
# PradeepGhosh_2017076

def seive(n):
	l=[True]
	l=l*(n+1)
	for i in range(2,int(sqrt(n))+1):
		if(l[i]==True):
			val=i*i
			while(val<len(l)):
				l[val]=False
				val+=i
	prime=[]
	for i in range(2,len(l)):
		if(l[i]==True):
			prime.append(i)
	return prime

def dp(l,i,n,val,ans):
	if(i>=n or val<0):
		return 1000000
	elif(val==0):
		return 0
	else:
		if(ans[i]==1000000):
			ans[i]=min(min(1+dp(l,i+1,n,val-l[i],ans),1+dp(l,i,n,val-l[i],ans)),dp(l,i+1,n,val,ans))
		return ans[i]
from queue import Queue
def factors(n):
	l=[]
	for i in range(1,int(sqrt(n))+1):
		if(n%i==0):
			if(n//i==i):
				l.append(i)
			else:
				l.append(i)
				l.append(n//i)
	return l
def check1(s,v,x):
	while(True):
		if(v not in s):
			return v
		else:
			v-=1
def check2(s,v,x):
	while(True):
		if(v not in s):
			return v
		else:
			v+=1

def up(n):
	j=n-1
	while(j>0):
		if(n%j==0):
			break
		j-=1
	return j		
def fac(n):
	c=1
	i=1
	while(i<=n):
		c*=i
		i+=1
	return c
def check_happy(n):
	ss=set()
	print(n)
	while(n!=1):
		val=n
		s=0
		print(val)
		while(val!=0):
			s+=(val%10)**2
			val=val//10
		print(val)
		print("hi")
		if(val in ss):
			return False
		else:
			n=val
			ss.add(n)
	return True
if __name__ == '__main__':
	n,k=map(int,input().split(" "))
	l=list(map(int,input().split(" ")))
	l.sort()
	if(k==n):
		prod=1
		for i in l:
			prod*=i
		print(prod%1000000007)
	else:
		prod=1
		for i in range(k):
			prod*=l[i]
		k-=1
		ind=n-1
		maxa=prod
		while(k>=0):
			prod=(prod//(l[k]))*l[ind]
			maxa=max(prod,maxa)
			ind-=1
			k-=1
		print(maxa%1000000007)

Submission status: Runtime Error

Solution code:
NUM=10**9+7
N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
A.sort()
check=[]
product=1
for i in range(K):
	product=(product*A[i])
check.append(product)
maxa=product
for i in range(1,N-K+1):
  j=i+K-1
  t=(check[-1])//A[i-1]
  t=t*A[j]
  check.append(t)
  maxa=max(maxa,t)
print(maxa%NUM)

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)
plus=sorted(plus,reverse=True)
minus=sorted(minus)

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)



if len(minus)%2==1:
    minus=minus[:-1]
use_minus=min(K,len(minus))
use_plus=K-use_minus

mul=1
for i in minus[:use_minus]:
        mul*=i
for i in plus[:use_plus]:
        mul*=i
retval=mul

while use_plus>=0 and use_minus>=0:
        use_minus-=2
        mul=mul//minus[use_minus]
        mul=mul//minus[use_minus+1]
        mul*=plus[use_plus]
        mul*=plus[use_plus+1]
        use_plus+=2
        retval=max(mul,retval)

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

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]

a.sort(reverse=True)
ans = 0
for i in range(n-1):
    ans += a[(i+1)//2]
    # print(ans)
print(ans)

Submission status: Runtime Error

Solution code:
import operation

n,k = map(int,input().split())
 
arr = list(map(int,input().split()))
 
arr.sort(reverse=True,key=abs)
 
print(reduce(operation.mul,arr[0:k],1))

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(-a)
pos = deque(sorted(pos))
neg = deque(sorted(neg))
mod = 10**9 + 7
ans = 1
sign = 1
if K % 2 == 1:
    if len(pos) > 0:
        ans = ans * pos.pop() % mod
    else:
        ans = ans * neg.popleft() % mod
        sign *= -1
    K -= 1
while K > 0:
    if len(pos) == 1 and len(neg) == 1:
        ans = ans * -neg.pop() * pos.pop() % mod
    if sign == 1:
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2] * pos[-1] < neg[-2] * neg[-1]):
            ans = ans * neg.pop() * neg.pop() % mod
        else:
            ans = ans * pos.pop() * pos.pop() % mod
    else:
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2] * pos[-1] < neg[-2] * neg[-1]):
            ans = ans * neg.popleft() * neg.popleft() % mod
        else:
            ans = ans * pos.popleft() * pos.popleft() % mod
    K -= 2
ans = ans * sign % mod
print(ans)

Submission status: Runtime Error

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

arr = list(map(int,input().split()))

arr.sort(reverse=True,key=abs)

sum1 = 1

for i in range(k): sum1 *= (arr[i]%((10**9) + 7))
  
print(sum1/((10**9)+7))

Submission status: Runtime Error

Solution code:
# Author: S Mahesh Raju
# Username: maheshraju2020
# Date: 05/07/2020

from sys import stdin,stdout
from math import gcd, ceil, sqrt
from collections import Counter
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
mod = 1000000007

n, k = iia()
arr = sorted(iia(), key=lambda x: abs(x), reverse=True)
neg = sum([1 for i in range(k) if arr[i] < 0])
if neg % 2 != 0:
    m = max(arr[k:])
    if m > 0:
        for i in range(k)[::-1]:
            if arr[i] < 0:
                arr[i] = m
                break
    else:
        for i in range(k):
            if arr[i] < 0:
                arr[i] = m
                break
res = arr[0]
for i in range(1, k):
    res *= arr[i]
print(res % mod)

Submission status: Runtime Error

Solution code:
import math
def fun(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
n,k=map(int,input().split())
seq=list(map(int,input().split()))
print(fun(seq,n,k)%1000000007)

Submission status: Runtime Error

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

arr = list(map(abs,list(map(int,input().split())))
           
arr.sort()
sum1 = 1
for i in range(k):
    sum1 *= (arr[-1-i]%1000000007)
print(sum1)