Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

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

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

Constraints

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

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

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

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

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

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

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

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

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

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

Sample Input 4

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

Sample Output 4

999983200

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



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, XS):
    "void()"

    posi = [x for x in XS if x >= 0]
    nega = [x for x in XS if x < 0]

    nega.sort(reverse=True)
    posi.sort()

    if K == N:
        # no choice
        ret = 1
        for i in range(N):
            ret *= XS[i]
            ret %= MOD
        return ret

    if not posi and K % 2:
        # negative answer
        # find smallest abs
        ret = 1
        for i in range(K):
            ret *= nega[i]
            ret %= MOD
        return ret

    ret = 1
    while K:
        # debug(": K, nega, posi", K, nega, posi)
        if K >= 2:
            if len(posi) >= 2:
                v = posi[-1] * posi[-2]
                w = nega[-1] * nega[-2]
                if v > w:
                    posi.pop()
                    posi.pop()
                    ret *= v
                    ret %= MOD
                else:
                    nega.pop()
                    nega.pop()
                    ret *= w
                    ret %= MOD

            else:
                v = nega.pop()
                v *= nega.pop()
                ret *= v
                ret %= MOD

            K -= 2
        else:
            if posi:
                ret *= posi[-1]
            else:
                ret *= nega[0]
            K -= 1
    return ret


def main():
    N, K = map(int, input().split())
    XS = list(map(int, input().split()))
    print(solve(N, K, XS))


T1 = """
4 2
1 2 -3 -4
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    12
    """


T2 = """
4 3
-1 -2 -3 -4
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    1000000001
    """


T3 = """
2 1
-1 1000000000
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    1000000000
    """


T4 = """
10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    999983200
    """


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Runtime Error

Solution code:
n , k = map(int, input().split())
a = list(map(int, input().split()))
neg = []
pos = []
mod = 10**9+7
for i in range(n):
    if a[i] >= 0:
        pos.append(a[i])
    else:
        neg.append(a[i])
neg.sort()
pos.sort(reverse = True)
min_num = -1
good_num = -1
if k % 2 == 1 and len(pos) == 0:
    ans = 1
    neg.sort(reverse = True)
    for i in range(k):
        ans *= neg[i]
        ans %= mod
    print(ans)
else:
    #最大化するとき
    for i in range(0,k+1,2):
        #i個だけnegから取る。
        if i > len(neg) or k - i > len(pos):
            continue
        m = 0
        if i != 0:
            m = abs(neg[i-1])
        m = min(m, pos[k-i-1])
        if m > min_num:
            min_num = m
            good_num = i
    ans = 1
    for i in range(good_num):
        ans *= neg[i]
        ans %= mod
    for i in range(k - good_num):
        ans*= pos[i]
        ans %= mod
    print(ans % mod)

Submission status: Runtime Error

Solution code:
n = int(input())
def add(x,y): return x+y%1000000007
arr = list(map(int,input().split()))
arr.sort()
print(reduce(add,arr[1:])%1000000007)

Submission status: Runtime Error

Solution code:
MOD=10**9+7
import bisect
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ans=set()
if 0 in ls:
  ans.add(0)

als=sorted(ls, key=lambda x: -abs(x))
mul=1
for i in range(K):
  mul*=als[i]
if mul>0:
  print(mul%MOD)
else:
  ls2=als[:K]
  ls3=als[K:]
  M2=max(ls2)
  m2=min(ls2)
  M3=max(ls3)
  m3=max(ls3)
  ans=set()
  ans.add(mul*m3//M2)
  ans.add(mul*m3//m2)
  ans.add(mul*M3//M2)
  ans.add(mul*M3//m2)
  print(max(ans)%MOD)

Submission status: Runtime Error

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k = MAP()

a = LIST()

pos = []
neg = []
zero = []

for el in a:
    if(el<0):
        neg.append(el)
    elif(el>0):
        pos.append(el)
    else:
        zero.append(el)

pos = sorted(pos)[::-1]
neg = sorted(neg)[::-1]

ans = 1

if(len(pos)==0):
    if(k%2==0):
        temp = 0
        for i in range(len(neg)-1, -1, -1):
            if(temp==k):
                break
            ans = (ans%mod*neg[i]%mod)%mod
            temp+=1
        if(temp>k):
            ans = 0
    else:
        temp = 0
        for i in range(len(neg) - 1):
            if (temp == k):
                break
            ans = (ans%mod * neg[i]%mod) % mod
            temp += 1
        if (temp > k):
            ans = 0
else:
    if(k==n):
        for el in a:
            ans = (ans%mod*el%mod)%mod
    else:
        left = k

        i,j = 0, len(neg)-1

        while(left>1):
            temp, temp1 = 0, 0
            if(i<len(pos)-2):
                temp = pos[i]*pos[i+1]
                # i+=2
            if(j>=1):
                temp1 = neg[j]*neg[j-1]
                # j-=2
            if(temp==0 and temp1==0):
                break
            if(temp1>temp):
                ans = (ans*(temp1%mod))%mod
                j-=2
            else:
                ans = (ans*(temp%mod))%mod
                i+=2
            left -= 2

        if(left>1):
            ans = 0
        elif(left==1):
            ans = ((ans%mod)*pos[i])%mod
        if(k%2!=0):
            ans1 = 1
            if(i-2>=0 and j-2<len(neg)-1):
                for b in range(i-1):
                    ans1 = (ans1%mod*(pos[b]))%mod
                for c in range(len(neg)-1, j-2,-1):
                    ans1 = (ans1%mod*neg[c])%mod
            # print(ans, ans1)
            ans = max(ans, ans1)
print(ans)

Submission status: Runtime Error

Solution code:
#create date: 2020-07-05 21:39

import sys
stdin = sys.stdin
mod = 10**9 + 7

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def calc(pos, neg):
    res = 1
    if pos:
        for p in pos:
            res *= p
            res %= mod
    if neg:
        for n in neg:
            res *= (-n)
            res %= mod
    return res

def main():
    n, k = na()
    a = na()
    po = list(); ne = list()
    for ai in a:
        if ai > 0:
            po.append(ai)
        if ai < 0:
            ne.append(ai)
    po.sort(reverse=True)
    ne.sort()
    if len(po) >= k:
        ans = calc(po[:k], None)
        print(ans)
        quit()
    if len(po) == 0 and k % 2 == 1:
        if 0 in a:
            print(0)
            quit()
        else:
            ans = -calc(None, ne[(n-k):]) % mod
            print(ans)
            quit()
    if len(po) + len(ne) < k:
        print(0)
        quit()
    else:
        poi = len(po)
        nei = k - poi
        if nei % 2 == 1:
            poi -= 1
            nei += 1
        poi_pre = poi; nei_pre = nei
        while poi >= 0:
            poi -= 2
            nei += 2
            if poi < 0:
                break
            positive = po[poi] * po[poi+1]
            negative = ne[nei-2] * ne[nei-1]
            if positive < negative:
                poi_pre = poi; nei_pre = nei
            else:
                ans = calc(po[:poi_pre], ne[(n-nei_pre):])
                print(ans)
                quit()
        ans = calc(po[:poi], ne[(n-nei):])
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,k = 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:
n, k = map(int, input().split())
a = list(map(int, input().split()))

mul = 1
mod = 1000000007
aa = sorted(a, reverse=True, key=abs)
for i in range(k):
    mul *= aa[i]


res = mul
for i in range(k, n):
    mul = mul*aa[i]//aa[i-k]
    res = max(res, mul)

print(res%mod)

Submission status: Runtime Error

Solution code:
N,K = (int(x) for x in input().split())
A = [int(x) for x in input().split()]

B = sorted(A, key=lambda x: abs(x), reverse=True)
C = [0]*N

for i in range(N):
    if A[i] > 0:
        C[i] = 1
    elif A[i] < 0:
        B[i] = A[i] * (-1)
        C[i] = -1

sei = 0
hi = 0
score = 1

for j in range(K):
    score *= B[j]
    if C[j] == 1:
        sei += 1
    elif C[j] == -1:
        hi += 1
        x = B[j]

if hi % 2 == 1:
    flg = 0
    for j in range(K,N):
        if C[j] == 1:
            score = score / x * B[j]
            flg = 1
            break
    if flg == 0:
        score = 1
        A = sorted(A, key=lambda x: abs(x))
        for j in range(K):
            score *= A[j]

print(int(score % (10**9 + 7)))

Submission status: Runtime Error

Solution code:

def inverse(a): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

import sys
N,K = map(int,input().split())
A = list(map(int,input().split()))

B = []
zero = 0
pl = 0
mi = 0
for i in A:
    if i == 0:
        zero += 1
    else:
        B.append( ( abs(i) , i // abs(i) ) )
        if i < 0:
            mi += 1
        else:
            pl += 1

last_pl = None

B.sort()
B.reverse()
mod = 10**9+7

if N - zero < K:
    print (0)
    sys.exit()

if pl == 0:

    if K % 2 == 0:
        now = 1
        for i in range(K):
            now *= B[i][0]
            now = mod
        print (now % mod)
        sys.exit()
    else:
        now = 1
        if zero > 0:
            print (0)
            sys.exit()
        
        for i in range(K):
            now *= B[N-i-1][0] * B[N-i-1][1]
            now %= mod
        print (now % mod)
        sys.exit()


lasp = None
lasm = None

now = 1
for i in range(K):
    now *= B[i][0] * B[i][1]

    if now >= 0:
        now %= mod
    else:
        now = now % mod - mod

    if B[i][1] > 0:
        lasp = B[i][0]
    else:
        lasm = -1 * B[i][0]

if now > 0:
    print (now % mod)
    sys.exit()

else:

    if lasp == None:
        change2 = float("-inf")
        a2 = 0
    else:
        a2 = ans * inverse(lasp)
        change2 = 1 / lasp
        for i in range(K+1,len(B)):
            if B[i][1] > 0:
                a2 *= B[i][0]
                change2 *= B[i][0]
                break
        else:
            change2 = float("-inf")

    if lasm == None:
        change3 = float("-inf")
        a3 = 0
    else:
    
        a3 = ans * inverse(lasm % mod)
        change3 = 1 / lasm
        for i in range(K+1,len(B)):
            if B[i][1] < 0:
                a3 *= -1 * B[i][0]
                change3 *= -1 * B[i][0]
                break
        else:
            change3 = float("-inf")

    if change2 > change3:
        print (a2 % mod)
    else:
        print (a3 % mod)

Submission status: Runtime Error

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

def checkio(numbers_array):
    return sorted(numbers_array, key=lambda x: abs(x))

INF = 10 ** 9 + 7

B = sorted(A)[::-1]
ans1 = 1
for i in range(K):
    ans1 *= B[i]
    ans1 %= INF
    
ans2 = 1
C = checkio(A)[::-1]
hu = []
for i in range(N):
    if C[i] < 0:
        hu.append(C[i])

i = 0
while(i < K):
    if C[i] >= 0:
        ans2 *= C[i]
        ans2 %= INF
    else:
        if i != K - 1 and C[i] in hu:
            ans2 *= C[i]
            ans2 %= INF
            del hu[0]
            if len(hu) > 0:
                ans2 *= C[hu[0]]
                ans2 %= INF
                del hu[0]
            else:
                break
            i += 1
    i += 1
            
print(max(ans1, ans2))

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:
import sys

N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))[::-1]
mod=10**9+7
score=1

if K%2==1:  #これでKは偶数として扱えるようになった
    score*=A[0]
    A.pop(0)
    K-=1

#print(A)

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

M=M[::-1]
t=0
p,m=0,0
while t<=K:
    if score<0:  #負であることが確定しているなら小さくなるようにする
        P=P[::-1]
        M=M[::-1]
        if 0 in M:
            print(0)
            sys.exit()
    if t+2<=K:
        if 2*p+1<len(P) and 2*m+1<len(M):
            if P[2*p]*P[2*p+1] >= M[2*m]*M[2*m+1]:
                score*=P[2*p]*P[2*p+1]
                p+=1
                t+=2
            else:
                score*=M[2*m]*M[2*m+1]
                m+=1
                t+=2
        elif 2*p+1<len(P):
            score*=P[2*p]*P[2*p+1]
            p+=1
            t+=2
        else:
            score*=M[2*m]*M[2*m+1]
            m+=1
            t+=2
    elif t+1<=K:
        if 2*p<len(P):
            score*=P[2*p]
        else:
            score*=M[2*m]
        break
    else:
        break
    score%=mod

print(score%mod)

Submission status: Runtime Error

Solution code:
def solmax(a,i,j):
    if j==0:
        return 1
    if i==j:
        return p[i]
    u=solmax(a,i-1,j)
    if a[i-1]>0:
        u=max(u,solmax(a,i-1,j-1)*a[i-1])
    elif a[i-1]<0:
        u=max(u,solmin(a,i-1,j-1)*a[i-1])
    else:
        u=max(u,0)
    return u
def solmin(a,i,j):
    if j==0:
        return 1
    if i==j:
        return p[i]    
    u=solmin(a,i-1,j)
    if a[i-1]>0:
        u=min(u,solmin(a,i-1,j-1)*a[i-1])
    elif a[i-1]<0:
        u=min(u,solmax(a,i-1,j-1)*a[i-1])
    else:
        u=min(u,0)
    return u
n=int(input())
k=int(input())
a=[]
p=[1]
for i in range(n):
    t=int(input())
    a.append(t)
    p.append(p[-1]*t)
print(solmax(a,n,k)%1000000007)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
P = sum(x>0 for x in a)
Z = sum(x==0 for x in a)
M = sum(x<0 for x in a)
ans = 1
mod = 10**9+7
pal = 1
if (P == 0 and K%2 == 1) or (M%2 == 1 and K == N):
  if Z != 0:
    #print('here')
    print(0)
  else:
    aabs = sorted([abs(x) for x in a])
    #print('HERE')
    #print(aabs)
    for i in aabs[:K]:
      ans *= i
      #print(ans)
      ans %= mod
      #print(ans)
    print(-1*ans+mod)
elif M%2 == 1 and P+M == K:
  if Z != 0:
    #print('here')
    print(0)
  else:
    aabs = sorted([abs(x) for x in a])
    #print('HERE')
    #print(aabs)
    for i in aabs[:K]:
      ans *= i
      #print(ans)
      ans %= mod
      #print(ans)
    print(-1*ans+mod)
else:
  if P+M < K:
    print(0)
  else:
    aabs = sorted([(abs(x),x/abs(x)) for x in a],reverse=True)
    for i in range(K-2):
      ans *= aabs[i][0]
      ans %= mod
      pal *= aabs[i][1]
    if pal == 1:
      count = 0
      tempp = 1
      tempm = 1
      for i in range(K-2,N):
        if aabs[i][1] == 1:
          tempp *= aabs[i][0]
          count += 1
          if count == 2:
            break
      count = 0
      for i in range(K-2,N):
        if aabs[i][1] == -1:
          tempm *= aabs[i][0]
          count += 1
          if count == 2:
            break
      ans*= max(tempp,tempm)
      ans %= mod
    if pal == -1:
      for i in range(K-2,N):
        if aabs[i][1] == -1:
          ans *= aabs[i][0]
          ans %= mod
          break
      for i in range(K-2,N):
        if aabs[i][1] == 1:
          ans *= aabs[i][0]
          ans %= mod
          break
  print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
def add(x,y): return x+y%1000000007
arr = list(map(int,input().split()))
arr.sort()
print(reduce(add,arr[1:]))

Submission status: Runtime Error

Solution code:
rule=input().split()
N=int(rule[0])
K=int(rule[1])
data_pre=input().split()
data_pre_2=[int(s) for s in data_pre]
data_pre_2.sort()
data=[]
import math
for i in range(N):
    num=math.fabs(data_pre_2[i])
    data.append(num)
data.sort()
data.reverse()
ind=0
for i in range(K):
    if data[i] in data_pre_2:
        pass
    else:
        ind+=1
for i in range(K+1,N):
    if data[i] in data_pre_2:
        spa=data[i]
        break
    else:
        pass
x=0
for i in range(K):
    if data[i] in data_pre_2:
        pass
    else:
        x=data[i]
ans=1
if ind%2==0:
    for i in range(K):
        ans*=data[i]
else:
    for i in range(K):
        ans*=data[i]
    ans*=spa
    ans=ans/x
print(int(ans%(10**9+7)))

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
    if K%2==1:
        for i in range(1,K+1):
            ans=(ans*n[i*(-1)])%MOD
    else:
        for i in range(K):
            ans=(ans*n[i])%MOD
elif N==K:
    ans=1
    for i in range(N):
        ans=(ans*A[i])%MOD
else:
    if numplus>=K:
        x=numplus
    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+2):
            break
        if n[K-x]*n[K-x+1]<p[x-1]*p[x-2]:
            break
        temp=(temp*n[K-x]*n[K-x+1])%MOD
        temp=(temp*pow(p[x-1]*p[x-2],MOD-2,MOD))%MOD
        ans=temp
        x-=2
print(ans)

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 *= p[itrp]
                    ans %= MOD
                    itrp += 1
                    K -= 1
            print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

def solve():
    N, K = mapint()
    As = list(mapint())
    mod = 10**9+7
    pos = []
    neg = []
    for a in As:
        if a>=0:
            pos.append(a)
        else:
            neg.append(a)
    
    pos.sort(reverse=True)
    neg.sort()
    lenp = len(pos)
    lenn = len(neg)
    if not pos and K%2==1:
        ans = 1
        for i, n in enumerate(neg[::-1]):
            ans *= n
            ans %= mod
            if i==K-1:
                break
        return ans
    if lenp+lenn==K and (K-lenp)%2==1:
        ans = 1
        pos.extend(neg)
        pos.sort(reverse=True)
        for i, p in enumerate(pos):
            ans *= p
            ans %= mod
            if i==K-1:
                break
        return ans
    ans = 1
    pcnt = 0
    ncnt = 0
    for i in range(K//2):
        if pcnt+2>=lenp:
            ans *= neg[ncnt*2]*neg[ncnt*2+1]
            ans %= mod
            ncnt += 1
        elif ncnt+2>=lenn:
            ans *= pos[pcnt*2]*pos[pcnt*2+1]
            ans %= mod
            pcnt += 1
        elif pos[pcnt*2]*pos[pcnt*2+1]>neg[ncnt*2]*neg[ncnt*2+1]:
            ans *= pos[pcnt*2]*pos[pcnt*2+1]
            ans %= mod
            pcnt += 1
        else:
            ans *= neg[ncnt*2]*neg[ncnt*2+1]
            ans %= mod
            ncnt += 1
    if K%2==1:
        ans *= pos[pcnt]
        ans %= mod
    return ans

print(solve())

Submission status: Runtime Error

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

chkp,chkm=1,1
for i in range(n):
    if ax[i]>0: a.append([abs(ax[i]),1]);chkm=0
    elif ax[i]<0: a.append([abs(ax[i]),-1]);chkp=0
    else: a.append([0,0])
a=sorted(a,reverse=True)

if chkp==1:
    ans=1
    for i in range(k):
        ans=ans*a[i][0]%mod
    print(ans)
    sys.exit()

if chkm==1:
    ans=1
    for i in range(n-1,n-k-1,-1):
        ans=ans*a[i][0]%mod
    print(mod-ans)
    sys.exit()


lp,lm=[],[]
cntm=0;ans=1
for i in range(k):
    [p,sgn]=a[i]
    ans=ans*p%mod
    if sgn==1: lp.append(p)
    elif sgn==-1:
        lm.append(p)
        cntm=cntm^1
    else: ans=0

if cntm==0 or ans==0:
    print(ans%mod)
    sys.exit()

newp,newm=-1,-1
for i in range(k+1,n):
    if a[i][1]==-1: newm=a[i][0];break
for i in range(k+1,n):
    if a[i][1]>=0: newp=a[i][0];break

x=1 if (lp and newm!=-1) else 0
y=1 if (lm and newp!=-1) else 0

if x==1 and y==1:
    if newp*lp[-1]>=newm*lm[-1]:
        ans=ans*inv(lm[-1],mod)*newp
    else:
        ans=ans*inv(lp[-1],mod)*newm

elif x==-1 and y==1: ans=ans*inv(lm[-1],mod)*newp
elif x==1 and y==-1: ans=ans*inv(lp[-1],mod)*newm
else: ans=0
print(ans%mod)



def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

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:
    if 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
    else:
        ans = 1
        for i in range(k):
            ans *= am[i]
            ans %= MOD
elif np < k:
    if (k - np) % 2 == 1:
        idx1 = np - 1
        idx2 = k - np + 1
    else:
        idx1 = np
        idx2 = k - np

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

print(ans)

Submission status: Runtime Error

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

if N - A.count(0) < K:
    print(0)
    exit(0)

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


if K % 2 == 1 and len(plus) == 0:
    minus.sort(reverse=True)
    ans = 1
    for i in range(K):
        ans *= minus[i]
        ans %= MOD
    print(ans)
    exit(0)

plus.sort(reverse=True)
minus.sort()

i = 0
j = 0

ans = 1
if K % 2 == 1:
    ans = plus[0]
    K -= 1
    plus = plus[1:]

for _ in range(K//2):
    if i+1 >= len(plus):
        ans *= (minus[j] * minus[j+1])
        ans %= MOD
        j += 2
        continue
    elif j+1 >= len(minus):
        ans *= (plus[i] * plus[i+1])
        ans %= MOD
        i += 2
        continue

    a = plus[i] * plus[i+1]
    b = minus[j] * minus[j+1]
    if a > b:
        ans *= a
        i += 2
    else:
        ans *= b
        j += 2
    ans %= MOD

print(ans)

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
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
      
print(Max%(10**9+7))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
MOD = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, (input().split())))
ap = []
neg_cnt = 0
zero_cnt = 0
for a in A:
    if a<0:
        ap.append((-a, 1))     # sortで先に来るようマイナスを1にする
        neg_cnt += 1
    elif a==0:
        ap.append((0, 0))
        zero_cnt += 1
    else:
        ap.append((a, -1))
ap.sort(reverse=True)
# print(ap)
ans = 1
if neg_cnt==N and K%2:      # 全てが負で奇数個選ぶので、答えは負
    for i in range(K):
        ans *= ap[N-i-1][0] * ap[N-i-1][1] * -1
        ans %= MOD
else:                       # 答えは正
    neg_num = 0
    for i in range(K):
        if ap[i][1] == 1:
            neg_num += 1
    if neg_num % 2:     # 負の数が奇数だったら、-1して偶数回にし、正が出るまで見る
        neg_num -= 1
        K += 1
    i = 0
    cnt = 0
    while cnt < K:
    # for i in range(K):
        if ap[i][1] == 1:  # 負の数だったら、neg_num回まで
            if neg_num == 0:
                i += 1
                continue
            else:
                neg_num -= 1
        ans *= ap[i][0] * ap[i][1] * -1
        ans %= MOD
        cnt += 1
        i += 1

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
def add(x,y): 
  return x+y
arr = list(map(int,input().split()))
arr.sort()
print(reduce(add,arr[1:])%1000000007)