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: Wrong Answer

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)

    def check_positive(k):
        if k % 2 == 0:
            return (len(neg) // 2) * 2 + len(pos) >= k
        else:
            if pos:
                k -= len(pos) if len(pos) % 2 == 1 else len(pos) - 1
                return (len(neg) // 2) * 2 >= k
            return False
    
    
    n, k = mi()
    L = lmi()
    pos = []
    zero_cnt = 0
    neg = []
    for elm in L:
        if elm < 0:
            neg.append(elm)
        elif elm > 0:
            pos.append(elm)
        else:
            zero_cnt += 1
    
    if check_positive(k):
        # 答えは正にできる。できるだけ大きい正の値を作ろう
        abs_neg = []
        tmp = sorted([abs(elm) for elm in neg], reverse=True)
        if len(neg) % 2 == 1:
            tmp = tmp[:-1]
        i = 0
        while i + 1 < len(tmp):
            abs_neg.append(tmp[i] * tmp[i+1])
            i += 2
        abs_neg.reverse()
        neg = abs_neg
        pos.sort()
        mul = 1
        cnt = 0
        # print(pos)
        # print(neg)
        while cnt < k:
            if pos and neg:
                if cnt == k - 1:
                    mul = (mul * pos.pop()) % mod
                    cnt += 1
                elif len(pos) == 1:
                    if pos[-1] < neg[-1]:
                        mul = (mul * neg.pop()) % mod
                        cnt += 2
                    else:
                        mul = (mul * pos.pop()) % mod
                        cnt += 1
                else:
                    if pos[-1] * pos[-2] < neg[-1]:
                        mul = (mul * neg.pop()) % mod
                        cnt += 2
                    else:
                        mul = (mul * pos.pop() * pos.pop()) % mod
                        cnt += 2
            elif pos:
                mul = (mul * pos.pop()) % mod
                cnt += 1
            elif neg:
                mul = (mul * neg.pop()) % mod
                cnt += 2
            else:
                raise RuntimeError
        print(mul)

    elif zero_cnt != 0:
        # 答えは 0 にできる。0 が最善や
        print(0)

    else:
        # 答えは負にしかならぬ。できるだけ 0 に近い負の値を作ろう
        tmp = [abs(elm) for elm in L]
        tmp.sort()
        mul = 1
        # print(tmp)
        for i in range(k):
            mul = (mul * tmp[i]) % mod
        print(mod - mul)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
ps = []
ns = []
for a in map(int, input().split()):
    if a > 0:
        ps.append(a)
    elif a < 0:
        ns.append(a)

def product(l):
    t = 1
    for li in l:
        t *= li
        t %= (10**9 + 7)
    return t

if len(ps) + len(ns) == 0:
    print(0)
elif len(ps) == 0:
    if k % 2 == 0:
        ns.sort()
    else:
        ns.sort(reverse=True)
    print(product(ns[:k]))
elif len(ns) == 0:
    ps.sort(reverse=True)
    print(product(ps[:k]))
else:
    ma = 0
    ps.sort(reverse=True)
    ns.sort()
    for nc in range(k+1):
        if nc % 2 == 0:
            pc = k - nc
            ma = max(ma, product(ps[:pc] + ns[:nc]))
    print(ma)

Submission status: Wrong Answer

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

MOD = 10**9 + 7

A_abs = [abs(a) for a in A]
A_is_negative = [a < 0 for a in A]

# A_abs の大きい順にソート
A_abs, A_is_negative, A = zip(*sorted(zip(A_abs, A_is_negative, A), key=lambda x: x[0], reverse=True))

ans = 1
ans_is_negative = 0

for i in range(K-1):
    ans *= A[i]
    if A_is_negative[i]:
        # A_sign が False なら A は負なので ans_is_negative を反転
        ans_is_negative = 1 - ans_is_negative
        last_negative = i

# 最後の 1 つの判定
if ans_is_negative and A_is_negative[K-1]:
    ans *= A[K-1]
    ans %= MOD
    print(ans)
elif ans_is_negative and not A_is_negative[K-1]:
    # 基本的に 次の A_is_negative を探す
    for i in range(K, N):
        if A_is_negative[i]:
            ans *= A[K-1]
            ans %= MOD
            print(ans)
            exit()
    # 最後まで見つからない場合...
    # negative は必ず以前にあるので、直前の negative まで戻って取り除き、 positive を大きい順に 2 つ見つける
    tar = A[last_negative]
    tar_inv = pow(tar, MOD-2, MOD)
    ans *= tar_inv
    ans %= MOD
    ans *= A[K-1]
    ans %= MOD
    ans *= A[K]
    ans %= MOD
    print(ans)
elif not ans_is_negative and A_is_negative[K-1]:
    # 基本的に 次の not A_is_negative を探す
    for i in range(K, N):
        if not A_is_negative[i]:
            ans *= A[K-1]
            ans %= MOD
            print(ans)
            exit()
    # 最後まで見つからない場合....
    # どうがんばっても negative を偶数個にはできないのであきらめ、小さいほうから K こ掛けて答えとする
    ans = 1
    for i in range(1, K+1):
        ans *= A[-i]
        ans %= MOD
    print(ans)
else:
    # 現時点での ans も + で 次の要素も + なら
    ans *= A[K-1]
    ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N, K = input().split()
N, K = int(N), int(K)
li = input().split()
li = list(map(int,li))
max_num = -100000000
for pair in itertools.combinations(li, K):
    num = 1
    for i in range(K):
        num *= pair[i]
    if num >= max_num:
        max_num =  num
print(max_num % (10**9+7))

Submission status: Wrong Answer

Solution code:
'''
# Sample code to perform I/O:

name = input()                  # Reading input from STDIN
print('Hi, %s.' % name)         # Writing output to STDOUT

# Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail
'''

# Write your code here
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
m = 1
mod = 1000000007
for i in range(k):
    m = (m%mod) * (a[i]%mod)
    m = m%mod
print(m%mod)

Submission status: Wrong Answer

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

def solve():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    P = 10**9 + 7
    def mod_prod(a,b):
        return (a % P) * (b % P) % P

    def mod_fact(a):
        ret = 1
        for i in range(a):
            ret = ret * (i + 1) % P
        return ret

    def mod_pow(a, n):
        ret = 1
        while n > 0:
            if n % 2 == 1:
                ret = ret * a % P
            a = a * a % P
            n = n >> 1
        return ret

    def mod_div(a, b):
        b_inv = mod_pow(b, P - 2)
        return a * b_inv % P

    def mod_comb(a,b):
        ret = 1
        b = min(b, a - b)
        for i in range(b):
            ret *= a - i
            ret %= P
        ret = mod_div(ret, mod_fact(b))
        return ret

    A.sort(key=lambda x:-abs(x))

    topK = A[:K]
    rest = A[K:]

    if sum(1 if a < 0 else 0 for a in topK) % 2 == 0:
        ans = 1
        for a in topK:
            ans *= a
            ans %= P
        print(ans)
    else:
        default_ans = 1
        for a in topK:
            default_ans = default_ans * a % P

        ans1 = default_ans
        rest_negs = [a for a in rest if a < 0]
        topk_poss = [a for a in topK if a >= 0]
        if len(rest_negs) > 0 and len(topk_poss) > 0:
            ans1 = 1
            for a in topK:
                ans1 *= a
                ans1 %= P
            ans1 = mod_div(ans1, min(topk_poss))
            ans1 = ans1 * min(rest_negs) % P
        else:
            pass

        ans2 = default_ans
        rest_poss = [a for a in rest if a >= 0]
        topk_negs = [a for a in topK if a < 0]
        if len(rest_poss) > 0 and len(topk_negs) > 0:
            ans2 = 1
            for a in topK:
                ans2 = ans2 * a % P
            ans2 = mod_div(ans1, max(topk_negs))
            ans2 = ans2 * max(rest_poss) % P
        
        ans3 = 1
        for i in range(K):
            ans3 = ans3 * A[N - 1 - i] % P

        print(max(ans1, ans2, ans3))

solve()

Submission status: Wrong Answer

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

listA.sort()
hidariI = 0
migiI = len(listA)-1

hidatiKouho = 1
migiKouho = 1

for i in range(k):
    hidatiKouho*=listA[hidariI]
    migiKouho*=listA[migiI]
    hidariI+=1
    migiI-=1

print(max(hidatiKouho, migiKouho)%(10**9+7))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
mod=10**9+7
P=1
B=[]
C=False
for i in range(N):
  if A[i]:
    B.append(A[i])
  else:
    C=True
if len(B)<K:
  print(0)
  exit()
B.sort(reverse=True,key=lambda x:abs(x))
Y=0
for i in range(K):
  if B[i]<0:
    Y+=1
  P=P*B[i]%mod
if Y&1==0:
  print(P)
  exit()
if Y==K:
  B.sort()
  if B[-1]<0:
    if C:
      print(0)
      exit()
    P=1
    for i in range(K):
      P=P*B[-(i+1)]%mod
    print(P)
    exit()
  P=P*pow(B[0],mod-2,mod)*B[-1]%mod
  print(P)
  exit()
Y,Z=0,0
for i in range(K,len(B)):
  if B[i]<0:
    Y=B[i]
    break
for i in range(K,len(B)):
  if B[i]>0:
    Z=B[i]
    break
if Y==0:
  for i in range(K-1,-1,-1):
    if B[i]<0:
      P=P*pow(B[i],mod-2,mod)
      break
  print(P*Z%mod)
elif Z==0:
  for i in range(K-1,-1,-1):
    if B[i]>0:
      P=P*pow(B[i],mod-2,mod)
      break
  print(P*Y%mod)
if Y==0 or Z==0:
  exit()
V,W=0,0
for i in range(K-1,-1,-1):
  if B[i]<0:
    V=B[i]
    break
for i in range(K-1,-1,-1):
  if B[i]>0:
    W=B[i]
    break

if Y*V>Z*W:
  print(P*Y*pow(W,mod-2,mod)%mod)
else:
  print(P*Z*pow(V,mod-2,mod)%mod)

Submission status: Wrong Answer

Solution code:
import bisect
N ,K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
mod = 10 ** 9 + 7
# ans = 0
if A.count(0) > (N - K):
  print(0)
  quit()
  
# ans = minus
plus = bisect.bisect_right(A, 0)
minus = bisect.bisect_left(A, 0) 
if N == K:
  ans = 1
  for i in range(N):
    ans *= A[i]
    ans %= mod
  print(ans)
  quit()
  
if minus == N:
  ans = 1
  for i in range(1, K + 1):
    ans *= A[-i]
    ans %= mod
  print(ans)
  quit()
  
ans = 1

count = 0
i = 0
j = -1
while count < K:
  if K - count >= 2:
    fo = (A[i] * A[i + 1]) % mod
    re = (A[j] * A[j - 1]) % mod
    #print(fo, re)
    if fo > re:
      ans *= fo 
      ans %= mod
      i += 2
    elif (A[j - 1] < 1) or (A[j - 2] < 1):
      ans *= fo 
      ans %= mod
      i += 2      
    else:
      ans *= re
      ans %= mod
      j -= 2
    count += 2  
  else:
    count += 1
    ans *= A[j]
      
  #print(ans)
print(ans % mod)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

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

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

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

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

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

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

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

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

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

    positives = 0
    zeros = 0
    negatives = 0

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

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

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

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

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

main()

Submission status: Wrong Answer

Solution code:
def prod(llst):
	P=1
	if len(llst)==0:
		p=P*0
	else:
		for i in llst:
			P=P*i
	return P
n,k=map(int,input().split())
lst=list(map(int,input().split()))
lst.sort(reverse=True)
maxlst=[]
i=0
while i<n:
	if lst[i]<0:
		break
	maxlst.append(lst[i])
	i=i+1
minlst=lst[i:]
#minlst.sort(reverse=True)
#maxlst.sort(reverse=True)
#print(minlst,maxlst)
maxp=prod(maxlst[:k])
mp=prod(minlst[:k])
if k%2==0:
	if mp>maxp:
		print(mp%1000000007)
	else:
		print(maxp%1000000007)
else:
	if len(maxlst)==0:
		print(mp%1000000007)
	else:
		print(maxp%1000000007)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def solution():
    n, k = map(int, input().split())
    a_list = sorted(list(map(int, input().split())),
                    key=lambda a: abs(a), reverse=True)

    MOD = 10 ** 9 + 7

    if all([a<0 for a in a_list]):
        ans = 1
        a_list = reversed(a_list)
        for i, a in enumerate(a_list):
            ans *= a % MOD
            if i == k - 1:
                return ans % MOD
    else:
        ans = 1
        pn = 1
        for i, a in enumerate(a_list):
            if i>=k-1:
                if pn < 0 and a >= 0:
                    continue
                else:
                    ans *= a % MOD
                    return ans % MOD
            ans *= a % MOD
            pn *= 1 if a>0 else -1

print(solution())

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
sign = dict({-1:0,0:0,1:0})
for a in A:
    if a<0:
        sign[-1]+=1
    elif a>0:
        sign[1]+=1
    else:
        sign[0]+=1
if sign[1]==0:
    A.sort(reverse=True)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
else:
    A.sort()
    ans = 1
    i,j = 0,N-1
    while K>0:
        if K>1 and A[i]*A[i+1]>=A[j]*A[j-1]:
            ans *= A[i]*A[i+1]
            ans %= MOD
            i += 2
            K -= 2
        else:
            ans *= A[j]
            ans %= MOD
            j -= 1
            K -= 1
print(ans)

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    A=LI()
    Lp=[]
    Lm=[]
    Lz=[]
    for i in range(N):
        if A[i]==0:
            Lz.append(0)
        elif A[i]>0:
            Lp.append(A[i])
        else:
            Lm.append(A[i])
            
    Lp.sort(reverse=True)
    Lm.sort()
    
    Np=len(Lp)
    Nm=len(Lm)
    
    if len(Lp)+len(Lm)<K:#どうしても0が入る
        print(0)
        exit()
    if K==1:
        print(max(A))
        exit()
    if max(A)<=0:#正数がない
        if K%2==0:
            A.sort()
        else:
            A.sort(reverse=True)
        ans=1
        for i in range(K):
            ans=(ans*A[i])%mod
        print(ans)
        exit()
    
    Lp.append(0)
    Lp.append(0)
    Lp.append(0)
    Lm.append(0)
    Lm.append(0)
    nowp=0
    nowm=0
    
    ans=1
    if K%2==0:
        for i in range(K//2):
            a=Lp[nowp]*Lp[nowp+1]
            b=Lm[nowm]*Lm[nowm+1]
            if a>=b:
                ans=(ans*a)%mod
                nowp+=2
            else:
                ans=(ans*b)%mod
                nowm+=2
    else:
        ans=Lp[0]
        nowp+=1
        for i in range(K//2):
            a=Lp[nowp]*Lp[nowp+1]
            b=Lm[nowm]*Lm[nowm+1]
            if a>=b:
                ans=(ans*a)%mod
                nowp+=2
            else:
                ans=(ans*b)%mod
                nowm+=2
    print(ans)
        
            

        
 
    
            
            

main()

Submission status: Wrong Answer

Solution code:
'''
# Sample code to perform I/O:

name = input()                  # Reading input from STDIN
print('Hi, %s.' % name)         # Writing output to STDOUT

# Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail
'''

# Write your code here
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
m = 1
mod = 1000000007
for i in range(k):
    m = (m) * (a[i])
    m = m%mod
print(m%mod)

Submission status: Wrong Answer

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<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
            if k<=n2:
                for i in range(k):
                    ans *= a2[-(i+1)]
                    ans %= M
            else:
                for i in range(n2):
                    ans *= a2[i]
                    ans %= M
                for i in range(n1):
                    ans *= a1[i]
                    ans %= M
    else:
        ans = 1
        for i in range(2*ind):
            ans *= a2[i]
            ans %= M
        for i in range(k-2*ind):
            ans *= a1[i]
            ans %= M
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
import sys

MOD = 10**9+7

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

a_plus=[]
a_minus=[]
a_zero = 0

for ai in a:
    if ai>0:
        heapq.heappush(a_plus, -ai)
    elif ai<0:
        heapq.heappush(a_minus, ai)
    else:
        a_zero += 1
        
if a_zero > n-k:
    print(0)
    sys.exit()
elif (len(a_minus) == n and k%2 == 1) or (n==k and len(a_minus)%2 == 1):
    for _ in range(n-k):
        heapq.heappop(a_minus)
    ans = 1
    for _ in range(len(a_minus)):
        ans *= - heapq.heappop(a_minus)
        ans %= MOD
    for _ in range(len(a_plus)):
        ans *= - heapq.heappop(a_plus)
        ans %= MOD
    print(-ans % MOD)
    sys.exit()


ans = 1
last_plus = MOD
last_minus = MOD
sign = 1

for _ in range(k):
    if len(a_minus)==0 or (len(a_plus)>0 and a_plus[0] < a_minus[0]):
        last_plus = -heapq.heappop(a_plus)
        ans *= last_plus
    else:
        last_minus = -heapq.heappop(a_minus)
        ans *= last_minus
        sign *= -1
    
    ans %= MOD
    

if sign>0:
    print(ans)
else:
    heapq.heappush(a_plus,0)
    heapq.heappush(a_minus,0)
    
    if -a_plus[0] / last_minus > -a_minus[0] / last_plus:
        ans = ans * (-a_plus[0]) % MOD * pow(last_minus,MOD-2,MOD) % MOD
    else:
        ans = ans * (-a_minus[0]) % MOD * pow(last_plus,MOD-2,MOD) % MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
S = A
ls1 = S[0:k]
ls2 = S[::-1][0:k]
mod = (10**9)+7
now1 = 1
now2 = 1
c1 = 0
c2 = 0
for i in range(len(ls1)):
    if ls1[i] == 0:
        now1 *= ls1[i]
        break
    else:
        if ls1[i] < 0:
            now1 = mod -(now1*ls1[i])%mod
            c1 += 1
        else:
            now1 *= ls1[i]
            now1 %= mod
for i in range(len(ls2)):
    if ls2[i] == 0:
        now2 *= ls2[i]
        break
    else:
        if ls2[i] < 0:
            now2 = mod -(now2*ls2[i])%mod
            c2 += 1
        else:
            now2 *= ls2[i]
            now2 %= mod
if c1 %2 == 1:
    now1 = -now1
if c2 %2 == 1:
    now2 = -now2
K = max(now1,now2)
print(K%mod)

Submission status: Wrong Answer

Solution code:
def solve():
    MOD = 10**9 + 7

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

    numPos, num0, numNeg = 0, 0, 0
    for A in As:
        if A > 0:
            numPos += 1
        elif A == 0:
            num0 += 1
        else:
            numNeg += 1

    if numPos + numNeg < K:
        ans = 0
    else:
        posAs, negAs = [], []
        prod = 1
        for A in As:
            if A > 0:
                posAs.append(A)
                prod *= A
                prod %= MOD
            elif A < 0:
                negAs.append(A)
                prod *= A
                prod %= MOD
        N = numPos + numNeg

        if K == N and prod < 0:
            if num0 > 0:
                ans = 0
            else:
                ans = prod

        elif K%2 != 0 and numPos == 0:
            if num0 > 0:
                ans = 0
            else:
                negAs.sort(reverse=True)
                ans = 1
                for A in negAs[:K]:
                    ans *= A
                    ans %= MOD

        else:
            posAs.sort(reverse=True)
            negAs.sort()
            acc = 1
            accPoss = [acc]
            for A in posAs:
                acc *= A
                acc %= MOD
                accPoss.append(acc)
            acc = 1
            accNegs = [acc]
            for A in negAs:
                acc *= A
                acc %= MOD
                accNegs.append(acc)

            ans = 0
            for x in range(0, K+1, 2):
                y = K - x
                if x > numNeg or y > numPos:
                    break
                prod = accNegs[x] * accPoss[y] % MOD
                if prod > ans:
                    ans = prod

    print(ans % MOD)


solve()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

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

pos = A[bisect_left(A, 0):]
pos.reverse()
neg = A[:bisect_left(A, 0)]

mod = 10**9+7
ans = 1
if len(pos) == 0 and K % 2 == 1:
    for i in range(K):
        ans *= neg[-i-1]
        ans %= mod
else:
    p, n = 0, 0
    for i in range(0, K-1, 2):
        v1 = 0
        v2 = 0
        if K % 2 == 0:
            if len(pos) >= p + 2:
                v1 = pos[p] * pos[p+1]
        else:
            if len(pos) >= p + 3:
                v1 = pos[p] * pos[p+1]

        if len(neg) >= n + 2:
            v2 = neg[n] * neg[n+1]

        if v2 > v1:
            ans *= v2
            ans %= mod
            n += 2
        else:
            ans *= v1
            ans %= mod
            p += 2

    if K % 2 == 1:
        ans *= pos[p]
        ans %= mod

print(ans)