Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

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

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

Constraints

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

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

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

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

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

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

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

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

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

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

Sample Input 4

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

Sample Output 4

999983200

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



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Runtime Error

Solution code:
N,K = map(int, input().split())
A = list(map(int, input().split()))
APlus = []
AMinus = []
for i in A:
    if 0 < i:
        APlus.append(i)
    elif 0 == i:
        pass
    elif i < 0:
        AMinus.append(i)
APlusBackup = APlus = sorted(APlus)
AMinusBackup = AMinus = sorted(AMinus)
count = 0
answer = 1
while count < K:
    #リストに2つ以上要素がある場合
    if count + 1 < K and 1 < len(APlus) and 1 < len(AMinus):
        if AMinus[0] * AMinus[1] < APlus[0] * APlus[1]:
            answer = answer * APlus.pop(0)
            answer = answer * APlus.pop(0)
            count += 2
        elif APlus[0] * APlus[1] < AMinus[0] * AMinus[1]:
            answer = answer * AMinus.pop(0)
            answer = answer * AMinus.pop(0)
            count += 2
        elif AMinus[0] * AMinus[1] == APlus[0] * APlus[1]:
            if count + 2 < K:
                if AMinus[2] <= APlus[2]:
                    answer = answer * APlus.pop(0)
                    answer = answer * APlus.pop(0)
                    count += 2
                else:
                    answer = answer * AMinus.pop(0)
                    answer = answer * AMinus.pop(0)
                    count += 2
    #リストに1つの要素がある場合
    else:
        try:
            answer = answer * APlus.pop(0)
            count += 1
        except:
            count = 0
            answer = 1
            APlus = sorted(APlusBackup, reverse = True)
            AMinus = sorted(AMinusBackup, reverse = True)
            while count < K:
                try:
                    if APlus[0] < AMinus[0]:
                        answer = answer * APlus.pop(0)
                        count += 1
                    elif AMinus[0] < APlus[0]:
                        answer = answer * AMinus.pop(0)
                        count += 1
                    elif APlus[0] == AMinus[0]:
                        if 1 < len(APlus) and 1 < len(AMinus):
                            if APlus[1] <= AMinus[1]:
                                answer = answer * APlus.pop(0)
                                count += 1
                            else:
                                answer = answer * AMinus.pop(0)
                                count += 1
                        else:
                            answer = answer * APlus.pop(0)
                            count += 1
                except:
                    try:
                        answer = answer * AMinus.pop(0)
                        count += 1
                    except:
                        break
            break
print(answer % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
import collections, heapq, itertools, bisect
import math, fractions
from functools import reduce, lru_cache
import sys, copy


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

    def inverse(self):
        return pow(self.x, MOD - 2, MOD)

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N, K = LI()
    A = LI()

    if K == N:
        print(reduce(lambda x, y: x * y, A, ModInt(1)))
        exit()

    plus = sorted([ai for ai in A if ai >= 0], reverse=True)
    minus = sorted([ai for ai in A if ai < 0])

    if len(plus) == 0:
        if K % 2 == 1:
            print(reduce(lambda x, y: x * y, minus[-K:], ModInt(1)))
        else:
            print(reduce(lambda x, y: x * y, minus[:K], ModInt(1)))
        exit()

    ip, im = 0, 0
    ans = ModInt(1)

    j = 0

    while True:
        if j == K:
            break
        if j == K - 1:
            ans *= plus[ip]
            break

        # K - j >= 2
        if len(plus) - ip >= 2 and len(minus) - im >= 2:
            p = plus[ip] * plus[ip+1]
            m = minus[im] * minus[im+1]
            if p > m:
                ans *= p
                ip += 2
            else:
                ans *= m
                im += 2
            j += 2
        elif len(plus) - ip >= 2:
            ans *= p
            ip += 2
            j += 2
        elif len(minus) - im >= 2:
            ans *= m
            im += 2
            j += 2

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    A=list(map(int,sys.stdin.readline().split()))

    Ap=[x for x in A if x>=0 ]
    Am=[abs(x) for x in A if x<0]

    if K==N:
        out=1
        for a in A:
            out*=a
            out%=10**9+7
        print(out)
        return


    if K%2==1 and len(Ap)==0:
        Am.sort()
        out=1
        for i in range(K):
            out*=Am[i]
            out%=10**9+7
        print((-out)%(10**9+7))
        return

    Ap.sort(reverse=True)
    Am.sort(reverse=True)
    
    ap_idx=0
    am_idx=0
    result=1
    for _ in range(0,K,2):
        kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk
        if K%2==0 and ap_idx+1<len(Ap):
            pmax=Ap[ap_idx]*Ap[ap_idx+1]
        elif K%2==1 and ap_idx+2<len(Ap):
            pmax=Ap[ap_idx]*Ap[ap_idx+1]
        else:
            pmax=-1

        if am_idx+1<len(Am):
            mmax=Am[am_idx]*Am[am_idx+1]
        else:
            mmax=-1

        if pmax==-1 and mmax==-1:
            break

        if pmax>mmax:
            result*=pmax
            ap_idx+=2
        else:
            result*=mmax
            am_idx+=2

        result%=(10**9+7)
    
    if K%2==1:
        result*=Ap[ap_idx]

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

main()

Submission status: Runtime Error

Solution code:
import bisect
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]

rrn = lambda n: [ rr() for _ in xrange(n)]

N, K = rrm()
arr = rrm()
def solve(N, K, arr):
    if K==N:
        ans = arr[0]
        for i in range(1, N):
            ans*=arr[i]
        return ans
    neg, pos = [], []
    has = False
    for num in arr:
        if num<0:
            bisect.insort(neg, num)
        elif num>0:
            bisect.insort(pos, num)
        else:
            has = True
    pos_prefix = [1]
    for i in range(len(pos)-1, -1, -1):
        pos_prefix.append(pos_prefix[-1]*pos[i])
    neg_prefix = [1]
    for i in range(len(neg)):
        neg_prefix.append(neg_prefix[-1]*neg[i])
    if has:
        ans = 0
    else:
        ans = float('-inf')
    if len(pos)>=K:
        cur = pos_prefix[K]
        ans = max(ans, cur)
        for i in range(2, min(K, len(neg))+2, 2):
            if i>len(neg):
                continue
            pre = neg_prefix[i]
            post = pos_prefix[K-i]
            ans  = max(ans, pre*post)
        return ans
    else:
        neg_len = min(K-K%2, len(neg)-len(neg)%2)
        for i in range(2, neg_len+2, 2):
            pre = neg_prefix[i]
            need = K-i
            if need<=len(pos):
                after = pos_prefix[need]
                ans = max(ans, pre*after)
    if ans < float('-inf'):
        return ans
    else:
        ans = neg[0]
        for i in range(1,K):
            ans*=neg[-i]
        return ans
        
print(solve(N,K, arr) % (10**9+7))

Submission status: Runtime Error

Solution code:
import sys
from operator import mul
from functools import reduce
n, k = map(int, input().split())
arr = list(map(int, input().split()))


MOD = 10**9 + 7

# negを奇数個選ばないといけないシチュエーションかどうか
neg = [x < 0 for x in arr]

if all(neg) and k % 2 == 1:
    arr.sort(reverse=True)
    print(reduce(mul, arr[:k]) % MOD)
    sys.exit()

arr_p = [x for x in arr if x >= 0]
arr_n = [x for x in arr if x < 0]

arr_p.sort(reverse=True)
arr_n.sort()

ans = 0
for i in range(0, min(k, len(arr_n)) + 1, 2):
    neg = reduce(mul, arr_n[:i]) if i != 0 else 1
    pos = reduce(mul, arr_p[:k - i]) if k - i != 0 else 1
    ans = max(ans, neg * pos)

print(ans % MOD)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
zero=a.count(0)
a=[x for x in a if x!=0]
a.sort()
res=1
cnt=0
p=1000000007
while 1:
  #print(a,res)
  if cnt==k:
    break
  if len(a)==1:
    if cnt == k-1:
      res =res*a[0] % p
      cnt+=1
    break
  if a[-1] < 0:
    res *= a[-1]
    res%=p
    cnt += 1
    a.pop(-1)
    continue
  tmp_a = res * a[0]*a[1] % p
  tmp_b = res * a[-1] % p
  if tmp_a > tmp_b and cnt < k-1:
    res = tmp_a
    cnt += 2
    a.pop(0)
    a.pop(0)
  else:
    res = tmp_b
    cnt += 1
    a.pop(-1)
if cnt < k and zero >0:
  res=0
print(res%p)

Submission status: Runtime Error

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

mod = 10**9 + 7
p = []
m = []
z_cnt = 0

for i in range(N):
    if A[i] < 0:
        m.append(-A[i])
    elif A[i] > 0:
        p.append(A[i])
    else:
        z_cnt += 1

p.sort(reverse=True)
m.sort(reverse=True)

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

tmp = K
while(tmp > len(p)):
    tmp -= 2

max_sum = -1
ans = None
while(tmp >= 0 and K - tmp <= len(m)):
    tmp_sum = sum(p[:tmp]) + sum(m[:K-tmp])
    if tmp_sum > max_sum:
        ans = 1
        tmp_list = p[:tmp] + m[:K-tmp]
        for i in tmp_list:
            ans = (ans * i) % mod
        max_sum = tmp_sum
    tmp -= 2

if ans != None:
    print(ans)
else:
    tmp = K - 1
    while(tmp > len(p)):
        tmp -= 2

    min_sum = 10 ** 20
    while(tmp >= 0 and K - tmp <= len(m)):
        tmp_sum = sum(p[len(p)-tmp:]) + sum(m[len(m)-K-tmp:])
        if tmp_sum < min_sum:
            ans = 1
            tmp_list = p[len(p)-tmp:] + m[len(m)-K-tmp:]
            for i in tmp_list:
                ans = (ans * i) % mod
            min_sum = tmp_sum
        tmp -= 2
        
    print((-ans)%mod)

Submission status: Runtime Error

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

zero=0
a=list(map(int,input().split()))
for i in range(n):
    if a[i]>0:
        A.append([a[i],0])
    elif a[i]<0:
        A.append([-a[i],1])
    else:
        zero+=1        
if k>n-zero:
    print(0)
    sys.exit()

A=list(reversed(sorted(A)))
cnt=0
for i in range(k):
    cnt+=A[i][1]
chk=0
for i in range(n-zero):
    chk+=A[i][1]
    
if cnt%2==0:
    ans=1
    for i in range(k):
        ans=ans*A[i][0]%mod
    print(ans)
elif chk==n-zero:
    if zero>0:
        print(0)
        sys.exit()
    ans=1
    for i in range(k):
        ans=ans*A[n-i-1][0]%mod
    print((-ans)%mod)
else:
    if A[k][1]==0:
        p=A[k][0]
        m=0
        for i in range(k+1,n-zero):
            if A[i][1]==1:
                m=A[i][0]
                break
    else:
        m=A[k][0]
        p=0
        for i in range(k+1,n-zero):
            if A[i][1]==1:
                p=A[i][0]
                break
    if A[k-1][1]==0:
        l=0
        for i in range(k-1):
            if A[k-i-2][1]==1:
                l=A[k-i-2][0]
                Xl=k-i-2
        if m*l>p*k:
            ans=1
            for i in range(k-1):
                ans=ans*A[i][0]%mod
            ans=ans*m%mod
            print(ans)
        else:
            ans=1
            for i in range(k-1):
                if i==Xl:
                    continue
                ans=ans*A[i][0]%mod 
            ans=ans*p%mod
            print(ans)
    else:
        l=0
        for i in range(k-1):
            if A[k-i-2][1]==0:
                l=A[k-i-2][0]
                Xl=k-i-2
        if p*l>m*k:
            ans=1
            for i in range(k-1):
                ans=ans*A[i][0]%mod
            ans=ans*p%mod
            print(ans)
        else:
            ans=1
            for i in range(k-1):
                if i==Xl:
                    continue
                ans=ans*A[i][0]%mod 
            ans=ans*m%mod
            print(ans)

Submission status: Runtime Error

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

a.sort()

pro = 1
for i in range(k):
    pro *= a[i]

ans = pro
if n > k:
    for i in range(k):
        pro = pro // a[k - i - 1] * a[n - i - 1]
        ans = max(ans, pro)

MOD = 1000000000 + 7

while ans < 0:
    ans += MOD

print(ans % MOD)

Submission status: Runtime Error

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

ans = 1

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

n = len(p_list)+len(m_list)

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


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

while k>0:
    p_mul, m_mul = 0, 0
    if k==1:
        ans *= p_list[p_num]
        ans %= mod
        break
    if m_mul+1<len(m_list):
        m_mul = m_list[m_num]*m_list[m_num+1]
    if p_mul+1<len(p_list):
        p_mul = p_list[p_num]*p_list[p_num-1]
    if p_mul>m_mul:
        ans *= p_mul
        ans %= mod
        p_num -= 2
    else:
        ans *= m_mul
        ans %= mod
        m_num += 2
    k -= 2
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
listA = list(map(int, input().split()))
zeroFlag = 0
if 0 in listA:
    zeroFlag = 1
    listA.remove(0)
listA.sort()

hidariI = 0
migiI = len(listA)-1

hidatiKouho = 1
migiKouho = 1

for i in range(k):
    hidatiKouho*=listA[hidariI]
    migiKouho*=listA[migiI]
    if hidatiKouho > 0:
        hidatiKouho %= 10**9 + 7
    if migiKouho > 0:
        migiKouho %= 10**9 + 7
    hidariI+=1
    migiI-=1

if zeroFlag:
    print(max(hidatiKouho, migiKouho, 0)%(10**9 + 7))
else:
    print(max(hidatiKouho, migiKouho) % (10**9 + 7))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
p=[]
m=[]
z=0
a.sort(reverse=True)
for i in range(n):
    if a[i]>0:
        p.append(a[i])
    elif a[i]==0:
        z+=1
    else:
        m.append(a[i])
nump=len(p)
numm=len(m)
ans=1
if nump+numm<k and z!=0:
    print(0)
elif numm<2 and nump>=k:
    for i in range(k):
        ans*=p[i]
        ans%=10**9+7
    print(ans)
elif 2*(numm//2)+nump<k:
    if z!=0:
        print(0)
    else:
        a.sort()
        for i in range(k):
            ans*=a[i]
            ans%=10**9+7
        print(ans)
elif  nump==0:
    if z!=0:
        print(0)
    else:
        for i in range(k):
            ans*=m[i]
            ans%=10**9+7
        print(ans)
else:
    if k%2==1:
        ans*=p[0]
    m.sort()
    nump=(nump-1)//2
    numm=numm//2
    nump1=0
    nump2=0
    numm1=0
    numm2=0
    for i in range(k//2):
        if nump2==nump:
            nump1=0
        else:
            nump1=p[nump2*2]*p[nump*2+1]
        if numm2==numm:
            numm1=0
        else:
            numm1=m[numm2*2]*m[numm2*2+1]
        if numm1>nump1:
            num=numm1
            numm2+=1
        else:
            num=nump1
            nump2+=1
        ans*=num
        ans%=10**9+7
    print(ans)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
all_minus = True
for i in range(n):
  if a[i] >= 0:
    all_minus = False
    break
if all_minus:
  a.sort(key = lambda x: abs(x))
  ans = 1
  for i in range(k):
    ans *= a[i]
  ans %= mod
  print(ans)
  exit()
a.sort(key = lambda x: abs(x))
a.reverse()
ans = 1
mcnt = 0
zcnt = 0
for i in range(n):
  if a[i] == 0:
    zcnt += 1
if zcnt > n - k:
  print(0)
  exit()
b = []
for i in range(n):
  if a[i] == 0:
    continue
  b.append(a[i])
m = len(b)
for i in range(k):
  ans *= b[i]
  if b[i] < 0:
    mcnt += 1
if mcnt % 2 == 0:
  ans = max(0, ans) % mod
  print(ans)
  exit()
lp = 0
lm = 0
for i in reversed(range(k)):
  if b[i] > 0:
    lp = b[i]
    break
for i in reversed(range(k)):
  if b[i] < 0:
    lm = b[i]
    break
base = ans
for i in range(k, m):
  temp = base
  if b[i] > 0:
    temp //= lm
    temp *= b[i]
    ans = max(ans, temp)
  else:
    temp //= lp
    temp *= b[i]
    ans = max(ans, temp)
ans = max(0, ans) % mod
print(ans)

Submission status: Runtime Error

Solution code:
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a = sorted(a)
mod = 1000000007

if n == k:
    prod = 1
    for b in a:
        prod *= b
        prod %= mod
    print(prod)
    exit()

# negative prod
if k & 1 and a[-1] < 0:
    prod = 1
    for i in range(k):
        prod *= a[-1 - i]
        prod %= mod
    print(prod)
    exit()

A = []
for b in a:
    if b < 0:
        A.append((-b, True))
    else:
        A.append((b, False))
A = sorted(A)[::-1]

ans = 1
is_neg = False
last_neg = 1
last_nneg = -1

for i in range(k + 1):
    (b, neg) = A[i]
    if neg:
        ans *= -b
    else:
        ans *= b
    ans %= mod
    is_neg ^= neg
    if i == k - 1:
        if not is_neg:
            print(ans)
            exit()
    if i <= k - 1:
        if neg:
            last_neg = -b
        else:
            last_nneg = b
    if i == k:
        if is_neg:
            assert last_neg != 1
            ans *= pow(last_neg, mod - 2, mod)
        else:
            assert last_nneg != -1
            ans *= pow(last_nneg, mod - 2, mod)
        ans %= mod
        print(ans)
        exit()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right

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

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

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

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

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

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
MOD = pow(10,9)+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
P = []; M = []
for i in range(N):
  if A[i] >0:
    P.append(A[i])
  else:
    M.append(A[i])
P.sort(reverse=True)
M.sort(reverse=True)
ans = 1
if K == 1:
  print(P[0]%MOD)
  exit()
if len(M) == 0: #全て正の場合:
  for i in range(K):
    ans = ans*P[i]%MOD
  print(ans)
  exit()
if len(P) == 0: #全て負の場合
  for i in range(K):
    ans = ans*M[i]%MOD
  print(ans)
  exit()
L = [[],[]]
M.sort()
P = deque(P); M = deque(M)
pm = [0,0] #正負の数を保存
pnow = 0; mnow = 0
#print(P,M)

for i in range(K):
  if not P:
    temp = M.popleft()
    pm[1] +=1
    L[1].append(temp)
  elif not M:
    temp = P.popleft()
    pm[0] +=1
    L[0].append(temp)
  elif P and M:
    if P[0] >= abs(M[0]):
      temp = P.popleft()
      pm[0] += 1
      L[0].append(temp)
    else:
      temp = M.popleft()
      pm[1] += 1
      L[1].append(temp)
#一個ずらす
#print(L)

if pm[1]%2 == 1 and (P or M):
  if not M:
    L[1].pop()
    L[0].append(P[0])
  elif not P:
    L[0].pop()
    L[1].append(M[0])
  elif M and P:
    if L[0][-1]*P[0] >= L[1][-1]*M[0]:
      L[1].pop()
      L[0].append(P[0])
    else:
      L[0].pop()
      L[1].append(M[0])
#print(L)    
for num in range(2):
  for s in L[num]:
    ans = ans*s%MOD
print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
zero=a.count(0)
a=[x for x in a if x!=0]
a.sort()
res=1
cnt=0
p=1000000007
while 1:
  print(a,res)
  if cnt==k:
    break
  if len(a)==1:
    if cnt == k-1:
      res =res*a[0] % p
      cnt+=1
    break
  if a[-1] < 0:
    res *= a[-1]
    res%=p
    cnt += 1
    a.pop(-1)
    continue
  tmp_a = res * a[0]*a[1] % p
  tmp_b = res * a[-1] % p
  if tmp_a > tmp_b and cnt < k-1:
    res = tmp_a
    cnt += 2
    a.pop(0)
    a.pop(0)
  else:
    res = tmp_b
    cnt += 1
    a.pop(-1)
if cnt < k and zero >0:
  res=0
print(res%p)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))[::-1]
mod=10**9+7
score=1
ans=0
if K%2==1:  #これでKは偶数として扱えるようになった
    score*=A[0]
    A.pop(0)
    K-=1
P,M=[],[]
N=len(A)
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 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:
MOD = 10**9+7
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
if all(ai < 0 for ai in a):
    ans = 1
    if k & 1:
        for ai in a[-k:]:
            ans = ans * ai % MOD
    else:
        for ai in a[:k]:
            ans = ans * ai % MOD
elif n == k:
    ans = 1
    for ai in a:
        ans = ans * ai % MOD
else:
    ans = 1
    a.sort(key=abs, reverse=True)
    cneg = sum(ai < 0 for ai in a[:k])
    if cneg & 1 == 0:
        for ai in a[:k]:
            ans = ans * ai % MOD
    else:
        left = []
        cnt = 0
        for i in range(len(a)):
            if cneg == 1:
                if i < k - 1 and a[i] >= 0:
                    ans = ans * ai % MOD
                    cnt += 1
                else:
                    left.append(a[i])
            else:
                ans = ans * a[i] % MOD
                cnt += 1
                if a[i] < 0:
                    cneg -= 1
        r = k - cnt
        if r == 1:
            ans = ans * [ai for ai in left if ai >= 0][0] % MOD
        else:
            ngs = [ai for ai in left if ai < 0]
            pss = [ai for ai in left if ai >= 0]
            t = -1001001001001001001001
            if len(ngs) >= 2:
                t = ngs[0] * ngs[1]
            if len(pss) >= 2:
                t = max(t, pss[0] * pss[1])
            ans = ans * t % MOD
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9+7
sei = []
hu = []
zero = []
for i in range(N):
    a = A[i]
    if a > 0:
        sei.append(a)
    elif a < 0:
        hu.append(a)
    else:
        zero.append(0)
sei.sort(reverse = True)
if len(zero) > N - K:
    print(0)
else:
    ans = 1
    p = len(sei)
    q = len(hu)
    if p == 0:
        hu.sort(reverse = True)
        for i in range(K):
            ans *= hu[i]
            ans %= MOD
        print(ans)
    elif q == 0:
        for i in range(K):
            ans *= sei[i]
            ans %= MOD
        print(ans)
    else:
        hu.sort()
        flag = 0
        pin = 0
        qin = 0
        r = K
        while r > 0:
            if pin == -1 and qin == -1:
                break
            elif pin == -1:
                qin += 1
                if qin == q:
                    qin = -1
                flag = abs(flag-1)
            elif qin == -1:
                pin += 1
                if pin == p:
                    pin = -1
            else:
                if abs(sei[pin])>abs(hu[qin]):
                    pin += 1
                    if pin == p:
                        pin = -1
                else:
                    qin += 1
                    if qin == q:
                        qin = -1
                    flag = abs(flag-1)
            r -= 1
        if pin == -1:
            pin = p
        if qin == -1:
            qin = q
        if p+q == K:
            for i in range(p):
                ans *= sei[i]
                ans %= MOD
            for i in range(q):
                ans *= hu[q]
                ans %= MOD
            print(ans%MOD)
        else:
            if flag == 0:
                for i in range(pin):
                    ans *= sei[i]
                    ans %= MOD
                for j in range(qin):
                    ans *= hu[j]
                    ans %= MOD
                print(ans%MOD)
            else:
                if pin == p:
                    for i in range(pin-1):
                        ans *= sei[i]
                        ans %= MOD
                    for j in range(qin+1):
                        ans *= hu[j]
                        ans %= MOD
                    print(ans%MOD)
                else:
                    for i in range(pin+1):
                        ans *= sei[i]
                        ans %= MOD
                    for j in range(qin-1):
                        ans *= hu[j]
                        ans %= MOD
                    print(ans%MOD)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
S = []
for i in range(N):
    if A[i] > 0:
        p = i
        break
D = A[:p]
B = []
for i in D:
    B.append(i)
B.sort()
C = A[p:]
for i in range(p):
    S.append(-A[i])
for i in range(p,N):
    S.append(A[i])
S.sort()
i = 0
while B:
    if S[i] == B[0]:
        S[i] = -S[i]
        B.pop(0)
    i += 1
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
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)