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: Time Limit Exceeded

Solution code:
from itertools import combinations
n, k = map(int, input().split())
ln = list(map(int, input().split()))
l = list(combinations(ln, k))
MOD = 10**9+7
lans = []
for i in l:
    mul = 1
    for j in range(k):
        mul *= i[j]
    lans.append(mul)
print(max(lans)%MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def kmaxprod_v2(data, k):
    if len(data) < k:
        return np.nan
    data = np.asanyarray(data)
    # for integer dtypes convert to python ints to have unlimited range for the
    # final product
    dfp = data.astype(object) if data.dtype in (
        int, np.int64, np.int32, np.int16, np.int8) else data
    # np.argpartition raises an exception if len(data) == k, therefore
    if len(data) == k:
        return np.prod(dfp)
    neg = data <= 0
    # if k is odd and there are no positive elements we must settle for the
    # least negative
    if k % 2 == 1 and np.count_nonzero(neg) == len(data):
        return np.prod(-np.partition(-data, k)[:k].astype(dfp.dtype))
    # now n > k and we have at least one positive element
    ap = np.argpartition(-np.absolute(data), k)
    low, high = ap[k:], ap[:k]
    # try multiplying the k with highest absolute value
    greedy = np.prod(dfp[high])
    if greedy >= 0:
        return greedy
    # there are two possible ways of fixing the sign:
    # either swap the worst negative inside for the best positive outside
    # or swap the worst positive inside for the best negative outside
    # compute both and compare
    # bpo in, wni out
    bpo = np.max(dfp[low])
    if bpo <= 0:
        spfn = 0
    else:
        neg_high = np.where(neg[high])[0]
        wni_ind = np.argmax(data[high[neg_high]])
        # translate to index in high
        wni_ind = neg_high[wni_ind]
        spfn = bpo*np.prod(dfp[high[:wni_ind]])*np.prod(dfp[high[wni_ind+1:]])
    # bno in, wno out
    pos_high = np.where(~neg[high])[0]
    if len(pos_high) == 0:
        snfp = 0
    else:
        wpi_ind = np.argmin(data[high[pos_high]])
        wpi_ind = pos_high[wpi_ind]
        bno = np.min(dfp[low])
        snfp = bno*np.prod(dfp[high[:wpi_ind]])*np.prod(dfp[high[wpi_ind+1:]])
    return max(spfn, snfp)


n,k=map(int,input().split())
data=list(map(int,input().split()))
md=10**9+7
print(kmaxprod_v2(data,k)%md)

Submission status: Time Limit Exceeded

Solution code:
from sys  import stdin,stdout

import bisect
import math
def st():
    return list(stdin.readline().strip())

def inp():
    return int(stdin.readline())

def li():
    return list(map(int,stdin.readline().split()))

def mp():
    return map(int,stdin.readline().split())

def pr(n):
    stdout.write(str(n)+"\n")

def soe(limit):
    l=[1]*(limit+1)
    prime=[]
    for i in range(2,limit+1):
        if l[i]:
            for j in range(i*i,limit+1,i):
                l[j]=0

    for i in range(2,limit+1):
        if l[i]:
            prime.append(i)
    return prime

def segsoe(low,high):
    limit=int(high**0.5)+1
    prime=soe(limit)
    n=high-low+1
    l=[0]*(n+1)
    for i in range(len(prime)):
        lowlimit=(low//prime[i])*prime[i]
        if lowlimit<low:
            lowlimit+=prime[i]
        if lowlimit==prime[i]:
            lowlimit+=prime[i]
        for j in range(lowlimit,high+1,prime[i]):
            l[j-low]=1
    for i in range(low,high+1):
        if not l[i-low]:
            if i!=1:
                print(i)

def power(a,n):
    r=1
    while n:
        if n&1:
            r=(r*a)
            n=n-1
        else:
            a=(a*a)
            n=n>>1
    return r

m=(10**9 +7) 
def solve():
    n,k=mp()
    l=li()
    l.sort()
    c=1
    if l[-1]==0 and k&1:
        return 0
    if l[-1]<=0 and k&1:
        for i in reversed(range(n-k,n)):
            c*=l[i]

        return c%m
    i=0
    j=n-1
    if k&1:
        c*=l[j]
        j-=1
        k-=1

    k//=2
    for x in range(k):

        a=l[i]*l[i+1]
        b=l[j]*l[j-1]

        if a>b:
            c*=a
            i+=2
        else:
            c*=b
            j-=2
    return c%m
    
            
        
    


print(solve())

Submission status: Time Limit Exceeded

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

for m in range(0,K+1,2):
    mul=1
    for i in minus[:m]:
        mul*=i
    for i in plus[:K-m]:
        mul*=i
    retval=max(mul,retval)

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

Submission status: Accepted

Solution code:
from collections import deque
rand = False
verbose = False

if rand:
    import random
    N, K = 200000, 10000
    A = random.choices(range(-10**9, 10**9), k=N)
else:
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

MOD = 10**9 + 7

def mul(A):
    ret = 1
    for i in range(len(A)):
        ret = (ret * A[i]) % MOD
#        print (ret)
    return ret

if K==N:
    print(mul(A))
    exit()

POS, NEG = list(), list()
for i in range(len(A)):
    if A[i] < 0:
        NEG.append(A[i])
    else:
        POS.append(A[i])

POS.sort(reverse=True)
NEG.sort()

if len(POS)==0 and K%2==1: # must go negative
    print(mul(NEG[-K:]))
    exit()

POS = deque(POS)
NEG = deque(NEG)

ans = list()
while len(ans)<K:
    if len(NEG) <= 1:
        if verbose: print('no more neg numbers')
        ans.append(POS.popleft()) # no negative numbers to add
    elif len(POS) <= 1:
        if verbose: print('no more pos numbers')
        if K-len(ans)>=2:
            ans.append(NEG.popleft())
            ans.append(NEG.popleft())
        else:
            ans.append(POS.popleft())
    elif POS[0]*POS[1] > NEG[0]*NEG[1] or K-len(ans)==1:
        if verbose: print('pos bigger')
        ans.append(POS.popleft())
    else:
        if verbose: print('neg biger')
        ans.append(NEG.popleft())
        ans.append(NEG.popleft())

print(mul(ans))

Submission status: Accepted

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

def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    l, r = 0, N-1
    MOD = 10**9+7
    if K == N:
        ans = 1
        for num in A:
            ans *= num
            ans %= MOD
        print(ans)
        exit()
    elif A[-1] < 0 and K%2 == 1:
        ans = 1
        for i in range(K):
            ans *= A[-i-1]
            ans %= MOD
        print(ans)
        exit()
    ans = 1
    if K%2 == 1:
        ans *= A[-1]
        r -= 1
    for _ in range(K//2):
        nl = A[l]*A[l+1]
        nr = A[r]*A[r-1]
        if nl > nr:
            ans *= nl
            l += 2
        else:
            ans *= nr
            r -= 2
        ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7
res = 1
a.sort(reverse=True)
if a[0]<0 and k%2==1:
    for i in range(k):
        res = (res*a[i])%mod
else:
    right = n-1
    left = 0
    while k > 1:
        if a[right]*a[right-1] < a[left]*a[left+1]:
            res = (res*a[left])%mod
            left += 1
            k -= 1
        else:
            res = (res*a[right]*a[right-1])%mod
            right -= 2
            k -= 2
    if k == 1:
        res = (res*a[left])%mod

print(res)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
import random
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


N, K = read_values()
def main():
    A = read_list()
    # A = [random.randint(-10 ** 9, 10 ** 9) for _ in range(N)]

    A.sort(reverse=True)
    if N == K or (A[0] < 0 and K % 2 == 1):
        res = 1
        for a in A[:K]:
            res *= a
            res %= mod
        print(res)
        return

    A.sort(key=lambda a: abs(a), reverse=True)

    P1 = list(filter(lambda a: a >= 0, A[:K]))
    P2 = list(filter(lambda a: a >= 0, A[K:]))
    N1 = list(filter(lambda a: a < 0, A[:K]))
    N2 = list(filter(lambda a: a < 0, A[K:]))

    if len(N1) % 2 == 1:
        # if N1[-1] * N2[0] : P1[-1] * P2[0]
        if len(P1) == 0 or len(N2) == 0:
            N1[-1] = P2[0]
        elif len(P2) == 0:
            P1[-1] = N2[0]
        else:
            if P1[-1] * P2[0] >= N1[-1] * N2[0]:
                N1[-1] = P2[0]
            else:
                P1[-1] = N2[0]
    
    res = 1
    for p in P1:
        res *= p
        res %= mod

    for n in N1:
        res *= n
        res %= mod
    
    print(res % mod)
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import io
import os
from heapq import merge

input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

MOD = 10 ** 9 + 7


def solve(N, K, A):
    assert 1 <= K <= len(A)
    A.sort()
    neg = [-x for x in A if x < 0][::-1]  # abs value only
    nonneg = [x for x in A if x >= 0]

    # Get product of the K smallest by absolute value
    # If there are no achievable nonneg products, then this will be the smallest negative product
    bestNeg = 1
    for i, x in enumerate(merge(neg, nonneg)):
        bestNeg *= x
        bestNeg %= MOD
        if i >= K - 1:
            break
    bestNeg = -bestNeg % MOD

    def getBestNonNeg(K):
        ans = 1
        if K % 2 == 1:
            # Num neg must be even, so we need an odd number of nonneg. Always take the highest nonneg
            if not nonneg:
                return None
            ans = nonneg.pop() % MOD
            K -= 1
        while K >= 2 and len(nonneg) >= 2 and len(neg) >= 2:
            if nonneg[-1] * nonneg[-2] < neg[-1] * neg[-2]:  # Take larger
                ans = (ans * neg.pop() * neg.pop()) % MOD
            else:
                ans = (ans * nonneg.pop() * nonneg.pop()) % MOD
            K -= 2
        while K >= 2 and len(neg) >= 2:
            ans = (ans * neg.pop() * neg.pop()) % MOD
            K -= 2
        while K >= 2 and len(nonneg) >= 2:
            ans = (ans * nonneg.pop() * nonneg.pop()) % MOD
            K -= 2
        if K == 0:
            return ans
        return None

    # Make largest nonnegative
    ans = getBestNonNeg(K)
    if ans is not None:
        return ans
    # Answer is negative
    return bestNeg


if False:
    from itertools import combinations
    import random

    random.seed(0)
    for t in range(10000000):
        N = random.randint(1, 10)
        A = [random.randint(-N, N) for i in range(N)]
        K = random.randint(1, N)
        ans = solve(N, K, A)
        expected = float("-inf")
        for combo in combinations(A, r=K):
            prod = 1
            for x in combo:
                prod *= x
            expected = max(expected, prod)
        print(N, K, A, ans, expected)
        assert ans == (expected % MOD)

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
print(solve(N, K, A))

Submission status: Accepted

Solution code:

"""

https://atcoder.jp/contests/abc173/tasks/abc173_e

クソだけどやろう

正負・0を分割

0がある場合は、最大を0に更新
0がN-K個より多い場合は即終了

残りの場合は、0を取らなくても構成できる場合のみ


"""

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

pl = []
mi = []
znum = 0

if K == 1:
    print (max(A))
    sys.exit()

for i in A:
    if i > 0:
        pl.append(i)
    elif i == 0:
        znum += 1
    else:
        mi.append(i)

ans = float("-inf")
if znum > 0:
    ans = 0

#0にならざるを得ない場合を処理
if znum > N-K:
    print (ans)
    sys.exit()

#答えが負になる場合も処理する
#大きいほうからかけていけばいい
#N個の場合 or 正がない場合は負になりえない
mod = 10**9+7
pl.sort()
mi.sort()

if K == N:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
    print (ans)
    sys.exit()

if K % 2 == 1 and len(pl) == 0:
    if znum > 0:
        ans = 0
    else:
        ans = 1
    mi.reverse()
    for i in range(K):
        ans *= mi[i]
        ans %= mod
    print (ans)
    sys.exit()

#まず、2個づつセットにすることを考える
#正負でセットにしていって、あまり同士も合成する

if K % 2 == 1:
    K -= 1
    ans = pl[-1]
    del pl[-1]
else:
    ans = 1

pl2 = []
pl.reverse()
if len(pl) % 2 == 1:
    pl.append(0)
if len(mi) % 2 == 1:
    mi.append(0)
for i in range(0,len(pl),2):
    pl2.append(pl[i] * pl[i+1])
for i in range(0,len(mi),2):
    pl2.append(mi[i] * mi[i+1])


pl2.sort()
pl2.reverse()
for i in range(K//2):
    ans *= pl2[i]
    ans %= mod
print (ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, K = getNM()
X = getList()

pos = sorted(v for v in X if v >= 0)
neg = sorted(-v for v in X if v < 0)

# 全てのXの要素を使うなら答えは自明
if N == K:
    ans = 1
    for x in X:
        ans *= x
        ans %= mod
    print(ans % mod)
    exit()

ok = False  # True: ans>=0, False: ans<0
if pos:
    #正の数があるとき
    ok = True
else:
    #全部負-> Kが奇数なら負にならざるをえない。
    ok = (K % 2 == 0)

ans = 1
if ok:
    # ans >= 0
    if K % 2 == 1:
        #Kが奇数の場合初めに1つ正の数を掛けておく
        #こうすれば後に非負でも負でも2つずつのペアで
        #考えられる
        ans = ans * pos.pop() % mod

    # 答えは非負になる→二つの数の積は必ず非負になる．
    cand = []
    while len(pos) >= 2:
        x = pos.pop() * pos.pop()
        cand.append(x)

    while len(neg) >= 2:
        x = neg.pop() * neg.pop()
        cand.append(x)

    cand.sort(reverse = True) # ペアの積が格納されているので必ず非負
    # ペア毎に掛けていく
    for i in range(K // 2):
        ans = ans * cand[i] % mod
else:
    # ans <= 0
    cand = sorted(X, key=lambda x: abs(x))
    for i in range(K):
        ans = ans * cand[i] % mod

print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect
from functools import reduce

def main():
    mod = 10 ** 9 + 7
    N, K = MI()
    A = LI()
    flag = 0
    for a in A:
        if a >= 0:
            flag = 1
            break

    A.sort(key=lambda x: abs(x), reverse=True)

    if K == N:
        ans = 1
        for a in A:
            ans *= a
            ans %= mod
        print(ans % mod)
        exit()
    elif flag == 0 and K % 2 != 0:
        B = A[::-1]
        ans = 1
        for i in range(K):
            ans *= B[i]
            ans %= mod
        ans %= mod
        print(ans)
        exit()
    else:
        ans = 1
        now_p = 0
        now_n = 0
        cnt_n = 0
        for i in range(K):
            a = A[i]
            ans *= a
            ans %= mod
            if a > 0:
                now_p = a
            elif a < 0:
                now_n = a
                cnt_n += 1
            else:
                print(0)
                exit()
        if cnt_n % 2 == 0:
            print(ans)
            exit()
        else:
            next_p = 0
            next_n = 0
            flag_p = 0
            flag_n = 0
            for i in range(K, N):
                a = A[i]
                if a > 0 and flag_p == 0:
                    next_p = a
                    flag_p = 1
                elif a < 0 and flag_n == 0:
                    next_n = a
                    flag_n = 1
                if flag_n == 1 and flag_p == 1:
                    break
                if a == 0:
                    break
        if now_p == 0:
            ans *= (pow(now_n, mod - 2, mod) * next_p) % mod
            ans %= mod
        elif next_p != 0 and next_n != 0:
            if now_p * next_p <= now_n * next_n:
                ans *= (pow(now_p, mod - 2, mod) * next_n) % mod
                ans %= mod
            else:
                ans *= (pow(now_n, mod - 2, mod) * next_p) % mod
                ans %= mod
        elif next_p == 0:
            ans *= (pow(now_p, mod - 2, mod) * next_n) % mod
            ans %= mod
        elif next_n == 0:
            ans *= (pow(now_n, mod - 2, mod) * next_p) % mod
            ans %= mod


        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import log
mod = int(1e9) + 7
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()

def sign(v):
    if v == 0:
        return 0
    return 1 if v > 0 else -1

pref = [(0, 1)] * (n + 1)
suf = [(0, 1)] * (n + 1)

c = 1
sm = 0
sgn = 1
for j in range(n):
    c = c * a[j] % mod
    sgn *= sign(a[j])
    if a[j] != 0:
        sm += log(abs(a[j]))
    pref[j + 1] = (sgn * sm, c, sgn)

c = 1
sm = 0
sgn = 1
for j in range(n):
    c = c * a[n - j - 1] % mod
    sgn *= sign(a[n - j - 1])
    if a[n - j - 1] != 0:
        sm += log(abs(a[n - j - 1]))
    suf[j + 1] = (sgn * sm, c, sgn)

m = max(pref[k], suf[k])
for i in range(1, k):
    sgn = pref[i][2] * suf[k - i][2]
    pm = pref[i][1] * suf[k - i][1] % mod
    sm = abs(pref[i][0]) + abs(suf[k - i][0])
    m = max(m, (sgn * sm, pm, sgn))

    
print(m[1])

Submission status: Accepted

Solution code:
def make_set_list(array,valid):
    new_array = []
    for i in range(len(array)//2):
        new_array.append(array[2*i]*array[2*i+1])
    if len(array)%2 == 1 and valid == 1:
        new_array.append(array[len(array)-1])
    return new_array

N, K = list(map(int,input().split()))
As = list(map(int,input().split()))
p_nums = []
n_nums = []
for i in range(N):
    n = As[i]
    if n < 0:
        n_nums.append(n)
    else:
        p_nums.append(n)
As.sort(key = abs)
n_nums.sort()
p_nums.sort(reverse = True)
if len(p_nums) > 0:
    if N > K:
        ok = True
    elif len(n_nums) % 2 == 0:
        ok = True
    else:
        ok = False
elif K % 2 == 0:
    ok = True
else:
    ok = False

ans = 1

if ok:
    if K % 2 == 0:
        set_p_num = make_set_list(p_nums,1)
        set_n_num = make_set_list(n_nums,0)
        set_num = set_p_num + set_n_num
        set_num.sort(reverse = True)
        for i in range(K//2):
            ans = (ans*(set_num[i]%(10**9+7)))%(10**9+7)
    else:
        ans = p_nums.pop(0)
        set_p_num = make_set_list(p_nums,1)
        set_n_num = make_set_list(n_nums,0)
        set_num = set_p_num + set_n_num
        set_num.sort(reverse = True)
        for i in range(K//2):
            ans = (ans*(set_num[i]%(10**9+7)))%(10**9+7)
else:
    for i in range(K):
        ans = (ans*(As[i]%(10**9+7)))%(10**9+7)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7
if N==K:
  ans0 = 1
  for a in A:
    ans0 = ans0*a%MOD
  print(ans0)
  exit()

A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 = ans1*a%MOD
  print(ans1)
  exit()

A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]
 
ansA = 1
for a in A[0:K]:
  ansA = ansA*a%MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()

B1=A[0:K]
C1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]

if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
if not Bp:Bp.insert(0,B1[-1])
if not Bm:Bm.insert(0,B1[0])
  
B1.remove(Bp[-1])
B1.append(min(B2[0],0))

ansB = 1
for a in B1[0:K]:
  ansB = ansB*a%MOD

C1.remove(Bm[-1])
C1.append(max(B2[-1],0))
 
ansC = 1
for a in C1[0:K]:
  ansC = ansC*a%MOD

BB1=[np.sign(i) for i in B1]
ansBB1 = BB1[0:K].count(-1)%2
BB2=[np.sign(i) for i in C1]
ansBB2 = BB2[0:K].count(-1)%2
if ansBB1==1:
  print(ansC)
  exit()
if ansBB2==1:
  print(ansB)
  exit()

if abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0])>=0:
  print(ansC)
else: print(ansB)

Submission status: Accepted

Solution code:
import numpy as np
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7
if N==K:
  ans0 = 1
  for a in A:
    ans0 = ans0*a%MOD
  print(ans0)
  exit()

A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 = ans1*a%MOD
  print(ans1)
  exit()

A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]
 
ansA = 1
for a in A[0:K]:
  ansA *= a
  ansA %= MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()

B1=A[0:K]
C1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]

if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
if not Bp:Bp.insert(0,B1[-1])
if not Bm:Bm.insert(0,B1[0])
  
B1.remove(Bp[-1])
B1.append(min(B2[0],0))

ansB = 1
for a in B1[0:K]:
  ansB *= a
  ansB %= MOD

C1.remove(Bm[-1])
C1.append(max(B2[-1],0))
 
ansC = 1
for a in C1[0:K]:
  ansC *= a
  ansC %= MOD

BB1=[np.sign(i) for i in B1]
ansBB1 = BB1[0:K].count(-1)%2
BB2=[np.sign(i) for i in C1]
ansBB2 = BB2[0:K].count(-1)%2
if ansBB1==1:
  print(ansC)
  exit()
if ansBB2==1:
  print(ansB)
  exit()

if abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0])>=0:
  print(ansC)
else: print(ansB)

Submission status: Accepted

Solution code:
import numpy as np
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7
if N==K:
  ans0 = 1
  for a in A[0:N]:
    ans0 *= a
    ans0 %= MOD
  print(ans0)
  exit()

A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 *= a
    ans1 %= MOD
  print(ans1)
  exit()

A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]
 
ansA = 1
for a in A[0:K]:
  ansA *= a
  ansA %= MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()

B1=A[0:K]
C1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]

if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
if not Bp:Bp.insert(0,B1[-1])
if not Bm:Bm.insert(0,B1[0])
  
B1.remove(Bp[-1])
B1.append(min(B2[0],0))

ansB = 1
for a in B1[0:K]:
  ansB *= a
  ansB %= MOD

C1.remove(Bm[-1])
C1.append(max(B2[-1],0))
 
ansC = 1
for a in C1[0:K]:
  ansC *= a
  ansC %= MOD

BB1=[np.sign(i) for i in B1]
ansBB1 = BB1[0:K].count(-1)%2
BB2=[np.sign(i) for i in C1]
ansBB2 = BB2[0:K].count(-1)%2
if ansBB1==1:
  print(ansC)
  exit()
if ansBB2==1:
  print(ansB)
  exit()

if abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0])>=0:
  print(ansC)
else: print(ansB)

Submission status: Accepted

Solution code:
import numpy as np
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7
if N==K:
  ans0 = 1
  for a in A[0:N]:
    ans0 *= a
    ans0 %= MOD
  print(ans0)
  exit()
A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 *= a
    ans1 %= MOD
  print(ans1)
  exit()

A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]
 
ansA = 1
for a in A[0:K]:
  ansA *= a
  ansA %= MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()

#while ansA>0:
#  ansA-=MOD

B1=A[0:K]
C1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]
 
if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
if not Bp:Bp.insert(0,B1[-1])
if not Bm:Bm.insert(0,B1[0])
  
B1.remove(Bp[-1])
B1.append(min(B2[0],0))

ansB = 1
for a in B1[0:K]:
  ansB *= a
  ansB %= MOD

C1.remove(Bm[-1])
C1.append(max(B2[-1],0))
 
ansC = 1
for a in C1[0:K]:
  ansC *= a
  ansC %= MOD

BB1=[np.sign(i) for i in B1]
ansBB1 = BB1[0:K].count(-1)%2
BB2=[np.sign(i) for i in C1]
ansBB2 = BB2[0:K].count(-1)%2

if ansBB1==1:
  print(ansC)
  exit()
if ansBB2==1:
  print(ansB)
  exit()

if abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0])>=0:
  print(ansC)
else: print(ansB)

Submission status: Accepted

Solution code:
import numpy as np
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7
if N==K:
  ans0 = 1
  for a in A[0:N]:
    ans0 *= a
    ans0 %= MOD
  print(ans0)
  exit()
A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 *= a
    ans1 %= MOD
  print(ans1)
  exit()
 
A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]
 
ansA = 1
for a in A[0:K]:
  ansA *= a
  ansA %= MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()

while ansA>0:
  ansA-=MOD

B1=A[0:K]
C1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]
 
if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
if not Bp:Bp.insert(0,B1[-1])
if not Bm:Bm.insert(0,B1[0])
  
#print(Bp,Bm,B2)
#print(Bp[-1],B2[0])
B1.remove(Bp[-1])
B1.append(min(B2[0],0))
#print(B1)
ansB = 1
for a in B1[0:K]:
  ansB *= a
  ansB %= MOD
#print(Bm[-1],B2[-1])
C1.remove(Bm[-1])
C1.append(max(B2[-1],0))
 
ansC = 1
for a in C1[0:K]:
  ansC *= a
  ansC %= MOD
#print(B1,C1)
#print(ansB,ansC)
BB1=[np.sign(i) for i in B1]
ansBB1 = BB1[0:K].count(-1)%2
BB2=[np.sign(i) for i in C1]
ansBB2 = BB2[0:K].count(-1)%2
#print(ansBB1,ansBB2)
if ansBB1==1:
  print(ansC)
  exit()
if ansBB2==1:
  print(ansB)
  exit()
#print(B2[0]/Bp[-1],B2[-1]/Bm[-1])
#print(Bp[-1]*B2[-1],Bm[0]*B2[0])

#print(abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0]))
#print(ansB,ansC)
if abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0])>=0:
  print(ansC)
else: print(ansB)

Submission status: Accepted

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

    A.sort(reverse=True)  # 符号付きの大きい順
    B = sorted(A, key=lambda x: abs(x), reverse=True)  # 絶対値の大きい順
    C = []

    if k == n:
        C = A  # 全部使う
    elif k % 2 == 1 and A[0] < 0:
        C = A[:k]  # 絶対値小さい順にk個
    else:
        plus = []
        minus = []
        for b in B[:k]:
            if b >= 0: plus.append(b)
            else: minus.append(b)

        if len(minus) % 2 == 1:
            # 積が負になるので入れ替え検討
            rem1, add1, rem2, add2 = None, None, None, None

            rem1 = minus[-1]  # 負値の絶対値最小
            add1 = max(B[k:])  # 残りものの正値の絶対値最大
            valid1 = (add1 >= 0)

            valid2 = False
            if plus:
                rem2 = plus[-1]
                add2 = min(B[k:])  # 負値の絶対値最大
                valid2 = (add2 < 0)

            if valid1 and valid2:
                if add1 * rem2 > rem1 * add2:
                    minus[-1] = add1
                else:
                    plus[-1] = add2
            elif valid1:
                minus[-1] = add1
            elif valid2:
                plus[-1] = add2

        C = plus + minus

    ans = 1
    for c in C:
        ans *= c
        if ans < 0: ans += mod
        ans %= mod
    print(ans)

if __name__ == '__main__':
    abc173_e()

Submission status: Accepted

Solution code:
from collections import deque

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

MOD = 10**9 + 7

# 0以上の数
X = []
# 負の数
Y = []

# 左の方が絶対値が大きくなるようにそれぞれソート
for a in A:
    if a >= 0:
        X.append(a)
    else:
        Y.append(a)
X.sort(reverse=True)
X = deque(X)
Y.sort()
Y = deque(Y)
# print(X)
# print(Y)

nums = []
# 全部選ぶしかない場合
if K == N:
    nums = A
# どうやっても負にしかならない場合（Aが全て負 and Kが奇数）
# 絶対値が小さくなるように取っていく
elif len(Y) == N and K % 2 == 1:
    for _ in range(K):
        nums.append(Y.pop())
# 上記以外の場合、結果を0以上（負ではない）にすることが出来る
# 絶対値が大きくなるように and 負にならないように 取っていく
# X,Yについて、「2個以上ある場合」、「1個の場合」、「0個の場合」の3*3=9通りに分けられる
# Yが1個、0個の場合はまとめることが出来たので、結局3*2=6通り

# 残り1個しか追加出来ない時に注意

else:
    while len(nums) < K:
        if len(X) >= 2 and len(Y) >= 2:
            if X[0] * X[1] >= Y[0] * Y[1] or len(nums) == K - 1:
                nums.append(X.popleft())
            else:
                nums.append(Y.popleft())
                nums.append(Y.popleft())
        elif len(X) >= 2 and len(Y) <= 1:
            nums.append(X.popleft())

        elif len(X) == 1 and len(Y) >= 2:
            if X[0] >= Y[0] * Y[1] or len(nums) == K - 1:
                nums.append(X.popleft())
            else:
                nums.append(Y.popleft())
                nums.append(Y.popleft())
        elif len(X) == 1 and len(Y) <= 1:
            nums.append(X.popleft())

        elif len(X) == 0 and len(Y) >= 2:
            if len(nums) == K - 1:
                # 負にならざるを得ない場合、絶対値が小さい方の負の数を追加する(ここだけpopleftではなくpop)
                # 絶対に0以上に出来るという前提に矛盾しているが、形式上記述しておく
                nums.append(Y.pop())
            else:
                nums.append(Y.popleft())
                nums.append(Y.popleft())
        # K<=Nなので、共に0になることは起こり得ない
        elif len(X) == 0 and len(Y) <= 1:
            num.append(Y.pop())

ans = 1
for num in nums:
    ans *= num
    ans %= MOD
print(ans)