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:
MOD = (int) (1e9+7)

def power(a,n):
    if a == 0: return 0
    if n == 0: return 1

    res = 1
    while n > 0:
        if n % 2 == 1: res = res * a % MOD
        a = a * a % MOD
        n //= 2

    return res

def inverse(n):
    return power(n, MOD-2)

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

B = []
pos, neg = 0, 0
for a in A:
    if a > 0:
        B.append([a,1])
        pos += 1
    if a < 0:
        B.append([-a,-1])
        neg += 1
    if a == 0:
        B.append([0,0])
B.sort(reverse=True)

ans, sign  = 1, 1
if N == neg and K % 2 == 1:
    for i in range(K):
        ans *= B[N-1-i][0] 
        ans %= MOD
    print(-ans % MOD)
    exit()

for i in range(K):
    ans *= B[i][0]
    ans %= MOD
    sign *= B[i][1]

if sign < 0:
    out_neg, out_pos = 0, 0
    in_pos, in_neg = 0, 0

    for i in range(K):
        if B[K-1-i][1] < 0:
            out_neg = B[K-1-i][0]
            break
    
    for i in range(K):
        if B[K-1-i][1] > 0:
            out_pos = B[K-1-i][0]
            break
    
    for i in range(N-K):
        if B[K+i][1] > 0:
            in_pos = B[K+i][0]
            break
    
    for i in range(N-K):
        if B[K+i][1] < 0:
            in_neg = B[K+i][0]
            break

    if in_neg == 0 or out_pos == 0:
        ans = (ans * in_pos % MOD) * inverse(out_neg) % MOD
    elif in_pos == 0 or out_neg == 0:
        ans = (ans * in_neg % MOD) * inverse(out_pos) % MOD
    else:
        if out_pos * in_pos < out_neg * in_neg:
            ans = (ans * in_neg % MOD) * inverse(out_pos) % MOD
        else:
            ans = (ans * in_pos % MOD) * inverse(out_neg) % MOD
            
print(ans)

Submission status: Wrong Answer

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

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

    ans = 1
    nneg = 0
    a, b, c, d = -1, -1, -1, -1
    for k in range(K):
        ans = (ans * A[k])%MOD
        if A[k] < 0:
            nneg += 1
            b = k
        else:
            a = k
    
    if K == N or nneg%2 == 0:
        return ans
    
    for k in range(N-1, K-1, -1):
        if A[k] < 0:
            d = k
        else:
            c = k

    # b must be >= 0
    if a == -1 and c == -1: # all minus
        ans = 1
        for k in range(K):
            ans = (ans * A[-1-k])%MOD
        return ans
    
    if a == -1 or d == -1:
        outn = A[b]
        inn = A[c]
    elif c == -1:
        outn = A[a]
        inn = A[d]
    else:
        if A[a]*A[c] < A[b]*A[d]:
            outn = A[b]
            inn = A[c]
        else:
            outn = A[a]
            inn = A[d]

    ans = (ans * pow(outn, MOD-2, MOD))%MOD
    ans = (ans * inn)%MOD
    return ans

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

Submission status: Wrong Answer

Solution code:
MOD = (int) (1e9+7)

def power(a,n):
    if a == 0: return 0
    if n == 0: return 1

    res = 1
    while n > 0:
        if n % 2 == 1: res = res * a % MOD
        a = a * a % MOD
        n //= 2

    return res

def inverse(n):
    return power(n, MOD-2)

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

B = []
pos, neg = 0, 0
for a in A:
    if a > 0:
        B.append([a,1])
        pos += 1
    if a < 0:
        B.append([-a,-1])
        neg += 1
    if a == 0:
        B.append([0,0])
B.sort(reverse=True)

ans, sign  = 1, 1
if N == neg and K % 2 == 1:
    for i in range(K):
        ans *= B[N-1-i][0] 
        ans %= MOD
    print(-ans % MOD)
    exit()

for i in range(K):
    ans *= B[i][0]
    ans %= MOD
    sign *= B[i][1]

if sign < 0:
    out_neg, out_pos = 0,0
    in_pos, in_neg = 0, 0
    for i in range(K):
        if B[K-1-i][1] < 0:
            out_neg = B[K-1-i][0]
            break
    
    for i in range(K):
        if B[K-1-i][1] > 0:
            out_pos = B[K-1-i][0]
            break
    
    for i in range(N-K):
        if B[K+i][1] > 0:
            in_pos = B[K+i][0]
            break
    
    for i in range(N-K):
        if B[K+i][1] < 0:
            in_neg = B[K+i][0]
            break

    if(out_pos * in_pos < out_neg * in_neg):
        ans = (ans * in_neg % MOD) * inverse(out_pos) % MOD
    else:
        ans = (ans * in_pos % MOD) * inverse(out_neg) % MOD
            
print(ans)

Submission status: Wrong Answer

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

A.sort(key=lambda x: abs(x), reverse=True)
best = [1, -1]
k = [0, 0]
for a in A:
    if a == 0:
        break
    elif a > 0:
        if k[0] < K:
            best[0] = (best[0]*a)%MOD
            k[0] += 1
        if k[1] < K:
            if k[1] > 0:
                best[1] = (best[1]*a)%MOD
                k[1] += 1
    else:
        tbest = best.copy()
        tk = k.copy()
        if k[1] < K:
            if k[1] > 0:
                if tbest[0] < tbest[1]*a:
                    best[0] = (tbest[1]*a)%MOD
                    k[0] = tk[1]+1
        if k[0] < K:
            if tbest[1] > tbest[0]*a:
                best[1] = (tbest[0]*a)%MOD
                k[1] = tk[0]+1

if k[0] == K:
    ans = best[0]
else:
    ans = 1
    for k in range(K):
        ans = (ans*A[-1-k])%MOD
print(ans)

Submission status: Wrong Answer

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

A.sort(key=lambda x: abs(x), reverse=True)
best = [1, -1]
k = [0, 0]
for a in A:
    if a == 0:
        break
    elif a > 0:
        if k[0] < K:
            best[0] = (best[0]*a)%MOD
            k[0] += 1
        if k[1] < K:
            if k[1] > 0:
                best[1] = (best[1]*a)%MOD
                k[1] += 1
    else:
        tbest = best.copy()
        if k[1] < K:
            if k[1] > 0:
                if tbest[0] < tbest[1]*a:
                    best[0] = (tbest[1]*a)%MOD
                    k[0] = k[1]+1
        if k[0] < K:
            if tbest[1] > tbest[0]*a:
                best[1] = (tbest[0]*a)%MOD
                k[1] = k[0]+1

if k[0] == K:
    ans = best[0]
else:
    ans = 1
    for k in range(K):
        ans = (ans*A[-1-k])%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 1 ;count = 0 ;pro1 = pro2 = 1
minus = 0

n,k = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
for ai in A:
  if ai < 0: minus += 1
plus = n-minus

if (k - plus - min(k//2*2,minus//2*2)) >= 1 and (k - plus - min(k//2*2,minus//2*2)) % 2 == 1:
  for i in range(k):
    ans *= A[i]
    ans %= mod
  print(ans)
else:
  left = 0;right = n-1
  while k > 0:
    if k == 1:
      pro1 *= max(A[left],A[right])
      k -= 1
    else:
      if A[left]*A[left+1] >= A[right]*A[right-1]:
        pro1 *= A[left]*A[left+1]
        left += 2
      else:
        pro1 *= A[right]*A[right-1]
        right -= 2
      k -= 2
    pro1 %= mod
  print(pro1)

Submission status: Wrong Answer

Solution code:
n, k = [int(x) for x in input().strip().split(" ")]
p = 10**9 + 7

num_list = [int(x) for x in input().strip().split(" ")]
num_list = sorted(num_list, reverse = True)
ans = 1
l_idx = 0
r_idx = -1

if num_list[0] < 0 and k % 2 == 1:
  ans = 1
  for i in range(k):
    ans *= num_list[i]
    ans %= p
else:
  while True:
    if k >= 2:
      l_prod = num_list[l_idx] * num_list[l_idx+1]
      r_prod = num_list[r_idx] * num_list[r_idx-1]
      if l_prod >= r_prod:
        ans *= num_list[l_idx] % p
        ans %= p
        l_idx +=1
        k -= 1
      else:
        ans *= r_prod % p
        ans %= p
        r_idx +=2
        k -= 2
    elif k == 1:
      ans *= num_list[l_idx] % p
      ans %= p
      break
    else:
      break

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = [int(x) for x in input().strip().split(" ")]
p = 10**9 + 7

num_list = [int(x) for x in input().strip().split(" ")]
num_list = sorted(num_list, reverse = True)
ans = 1
l_idx = 0
r_idx = -1

while True:
  if k >= 2:
    l_prod = num_list[l_idx] * num_list[l_idx+1]
    r_prod = num_list[r_idx] * num_list[r_idx-1]
    if l_prod >= r_prod:
      ans *= l_prod % p
      ans %= p
      l_idx +=2
      k -= 2
    else:
      ans *= r_prod % p
      ans %= p
      r_idx +=2
      k -= 2
  elif k == 1:
    ans *= num_list[l_idx] % p
    ans %= p
    break
  else:
    break
        
if num_list[0] < 0 and k % 2 == 1:
  ans = 1
  for i in range(k):
    ans *= num_list[i]
    ans %= p

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = [int(x) for x in input().strip().split(" ")]
p = 10**9 + 7

num_list = [int(x) for x in input().strip().split(" ")]
num_list = sorted(num_list, reverse = True)
ans = 1
l_idx = 0
r_idx = -1
if num_list[0] < 0 and k % 2 == 1:
  for i in range(k):
    ans *= num_list[i]
    ans %= p
else:
  while True:
    if k >= 2:
      l_prod = num_list[l_idx] * num_list[l_idx+1]
      r_prod = num_list[r_idx] * num_list[r_idx-1]
      if l_prod >= r_prod:
        ans *= l_prod % p
        ans %= p
        l_idx +=2
        k -= 2
      else:
        ans *= r_prod % p
        ans %= p
        r_idx +=2
        k -= 2
    elif k == 1:
      ans *= num_list[l_idx] % p
      ans %= p
      break
    else:
      break

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]
nums = [int(i) for i in input().split()]
mod = 10**9 + 7
ans = [1] * (n - k + 1)
for i in range(n - k + 1):
    for j in range(k):
         ans[i] *= nums[i+j]
print(max(ans) % mod)

Submission status: Wrong Answer

Solution code:
MOD=1000000007
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
pos=[]
neg=[]
nzero=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        nzero+=1
if nzero+k>n:
    print(0)
elif nzero+k==n and len(pos)>0 and len(neg)>0:
    if nzero==0:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        if len(neg)%2:
            res*=-1
            res+=MOD
        print(res)
    elif len(neg)%2:
        print(0)
    else:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        print(res)
elif len(pos)==0:
    res=1
    if k%2 and nzero>0:
        print(0)
    elif k%2:
        neg.sort()
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
    else:
        neg.sort(reverse=True)
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
elif len(neg)==0:
    res=1
    pos.sort(reverse=True)
    for i in range(k):
        res*=pos[i]
        res%=MOD
    print(res)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    ruip=[1 for i in range(len(pos)+1)]
    ruin=[1 for i in range(len(neg)+1)]
    for i in range(len(pos)):
        ruip[i+1]=ruip[i]*pos[i]
        ruip[i+1]%=MOD
    for i in range(len(neg)):
        ruin[i+1]=ruin[i]*neg[i]
        ruin[i+1]%=MOD
    np=0
    if len(pos)>=k:
        np=k
    elif (k-len(pos))%2:
        np=len(pos)-1
    else:
        np=len(pos)
    while np>=2 and (pos[np-1]*pos[np-2]<neg[k-np+1]*neg[k-np]):
        np-=2
        if len(neg)-1<k-np+1:
            np+=2
            break
    print((ruip[np]*ruin[k-np])%MOD)

Submission status: Wrong Answer

Solution code:
MOD=1000000007
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
pos=[]
neg=[]
nzero=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        nzero+=1
if nzero+k>n:
    print(0)
elif nzero+k==n and len(pos)>0 and len(neg)>0:
    if nzero==0:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        if len(neg)%2:
            res*=-1
            res+=MOD
        print(res)
    elif len(neg)%2:
        print(0)
    else:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        print(res)
elif len(pos)==0:
    res=1
    if k%2 and nzero>0:
        print(0)
    elif k%2:
        neg.sort()
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
    else:
        neg.sort(reverse=True)
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
elif len(neg)==0:
    res=1
    pos.sort(reverse=True)
    for i in range(k):
        res*=pos[i]
        res%=MOD
    print(res)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    ruip=[1 for i in range(len(pos)+1)]
    ruin=[1 for i in range(len(neg)+1)]
    for i in range(len(pos)):
        ruip[i+1]=ruip[i]*pos[i]
        ruip[i+1]%=MOD
    for i in range(len(neg)):
        ruin[i+1]=ruin[i]*neg[i]
        ruin[i+1]%=MOD
    np=0
    if len(pos)>=k:
        np=k
    elif (k-len(pos))%2:
        np=len(pos)-1
    else:
        np=len(pos)
    while np>=2 and (pos[np-1]*pos[np-2]<neg[k-np-1]*neg[k-np-2]):
        np-=2
        if np+len(neg)<k:
            np+=2
            break
    print((ruip[np]*ruin[k-np])%MOD)

Submission status: Wrong Answer

Solution code:
MOD=1000000007
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
pos=[]
neg=[]
nzero=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        nzero+=1
if nzero+k>n:
    print(0)
elif nzero+k==n and len(pos)>0 and len(neg)>0:
    if nzero==0:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        if len(neg)%2:
            res*=-1
        print(res)
    elif len(neg)%2:
        print(0)
    else:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        print(res)
elif len(pos)==0:
    res=1
    if k%2 and nzero>0:
        print(0)
    elif k%2:
        neg.sort()
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
    else:
        neg.sort(reverse=True)
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
elif len(neg)==0:
    res=1
    pos.sort(reverse=True)
    for i in range(k):
        res*=pos[i]
        res%=MOD
    print(res)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    ruip=[1 for i in range(len(pos)+1)]
    ruin=[1 for i in range(len(neg)+1)]
    for i in range(len(pos)):
        ruip[i+1]=ruip[i]*pos[i]
        ruip[i+1]%=MOD
    for i in range(len(neg)):
        ruin[i+1]=ruin[i]*neg[i]
        ruin[i+1]%=MOD
    np=0
    if len(pos)>=k:
        np=k
    elif (k-len(pos))%2:
        np=len(pos)-1
    else:
        np=len(pos)
    while np>=2 and (pos[np-1]*pos[np-2]<neg[k-np-1]*neg[k-np-2]):
        np-=2
        if np+len(neg)<k:
            np+=2
            break
    print((ruip[np]*ruin[k-np])%MOD)

Submission status: Wrong Answer

Solution code:
MOD=1000000007
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
pos=[]
neg=[]
nzero=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        nzero+=1
if nzero+k>n:
    print(0)
elif nzero+k==n:
    if len(neg)%2:
        print(0)
    else:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        print(res)
elif len(pos)==0:
    res=1
    if k%2 and nzero>0:
        print(0)
    elif k%2:
        neg.sort()
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
    else:
        neg.sort(reverse=True)
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
elif len(neg)==0:
    res=1
    pos.sort(reverse=True)
    for i in range(k):
        res*=pos[i]
        res%=MOD
    print(res)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    ruip=[1 for i in range(len(pos)+1)]
    ruin=[1 for i in range(len(neg)+1)]
    for i in range(len(pos)):
        ruip[i+1]=ruip[i]*pos[i]
        ruip[i+1]%=MOD
    for i in range(len(neg)):
        ruin[i+1]=ruin[i]*neg[i]
        ruin[i+1]%=MOD
    np=0
    if len(pos)>=k:
        np=k
    elif (k-len(pos))%2:
        np=len(pos)-1
    else:
        np=len(pos)
    while np>=2 and (pos[np-1]*pos[np-2]<neg[k-np-1]*neg[k-np-2]):
        np-=2
        if np+len(neg)<k:
            np+=2
            break
    print((ruip[np]*ruin[k-np])%MOD)

Submission status: Wrong Answer

Solution code:
MOD=1000000007
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
pos=[]
neg=[]
nzero=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        nzero+=1
if nzero+k>n:
    print(0)
elif nzero+k==n:
    if len(neg)%2:
        print(0)
    else:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        print(res)
elif len(pos)==0:
    res=1
    if k%2 and nzero>0:
        print(0)
    elif k%2:
        neg.sort()
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
    else:
        neg.sort(reverse=True)
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
    print(res)
elif len(neg)==0:
    res=1
    pos.sort(reverse=True)
    for i in range(k):
        res*=pos[i]
        res%=MOD
    print(res)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    ruip=[1 for i in range(len(pos)+1)]
    ruin=[1 for i in range(len(neg)+1)]
    for i in range(len(pos)):
        ruip[i+1]=ruip[i]*pos[i]
        ruip[i+1]%=MOD
    for i in range(len(neg)):
        ruin[i+1]=ruin[i]*neg[i]
        ruin[i+1]%=MOD
    np=0
    if len(pos)>=k:
        np=k
    elif (k-len(pos))%2:
        np=len(pos)-1
    else:
        np=len(pos)
    while np>=2 and (pos[np-1]*pos[np-2]<neg[k-np-1]*neg[k-np-2]):
        np-=2
        if np+len(neg)<k:
            np+=2
            break
    print((ruip[np]*ruin[k-np])%MOD)

Submission status: Wrong Answer

Solution code:
MOD=1000000007
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
pos=[]
neg=[]
nzero=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        nzero+=1
if nzero+k>n:
    print(0)
elif nzero+k==n:
    if len(neg)%2:
        print(0)
    else:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        print(res)
elif len(pos)==0:
    res=1
    if k%2:
        neg.sort()
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
    else:
        neg.sort(reverse=True)
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
    print(res)
elif len(neg)==0:
    res=1
    pos.sort(reverse=True)
    for i in range(k):
        res*=pos[i]
        res%=MOD
    print(res)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    ruip=[1 for i in range(len(pos)+1)]
    ruin=[1 for i in range(len(neg)+1)]
    for i in range(len(pos)):
        ruip[i+1]=ruip[i]*pos[i]
        ruip[i+1]%=MOD
    for i in range(len(neg)):
        ruin[i+1]=ruin[i]*neg[i]
        ruin[i+1]%=MOD
    np=0
    if len(pos)>=k:
        np=k
    elif (k-len(pos))%2:
        np=len(pos)-1
    else:
        np=len(pos)
    while np>=2 and (pos[np-1]*pos[np-2]<neg[k-np-1]*neg[k-np-2]):
        np-=2
        if np+len(neg)<k:
            np+=2
            break
    print((ruip[np]*ruin[k-np])%MOD)

Submission status: Wrong Answer

Solution code:
MOD=1000000007
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
pos=[]
neg=[]
nzero=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        nzero+=1
if nzero+k>n:
    print(0)
elif len(pos)==0:
    res=1
    if k%2:
        neg.sort()
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
    else:
        neg.sort(reverse=True)
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
    print(res)
elif len(neg)==0:
    res=1
    pos.sort(reverse=True)
    for i in range(k):
        res*=pos[i]
        res%=MOD
    print(res)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    ruip=[1 for i in range(len(pos)+1)]
    ruin=[1 for i in range(len(neg)+1)]
    for i in range(len(pos)):
        ruip[i+1]=ruip[i]*pos[i]
    for i in range(len(neg)):
        ruin[i+1]=ruin[i]*neg[i]
    now=0
    ind=0
    if k%2:
        ind=1
    ind=max(ind,k-len(neg))
    while now<ruip[ind]*ruin[k-ind]:
        now=ruip[ind]*ruin[k-ind]
        ind+=2
        if ind>=len(pos):
            break
    print(now%MOD)

Submission status: Wrong Answer

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


def solve(N, K, A):
    ans = 1
    # K = N の場合は明らか
    if K == N:
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    # Ai の全ての数が負かつ K が奇数のとき、
    elif max(A) < 0 and K % 2 == 1:
        A.sort(reverse=True)
        # 絶対値が小さい方から K 個の積
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    # それ以外の場合、積は必ず非負
    else:
        A.sort(key=abs)
        for i in range(K):
            ans *= A[-i - 1]
            ans %= MOD
        if ans < 0:
            small_nonneg = [a for a in A[: N - K] if a >= 0]
            small_neg = [a for a in A[: N - K] if a < 0]
            large_nonneg = [a for a in A[N - K :] if a >= 0]
            large_neg = [a for a in A[N - K :] if a < 0]
            if not small_neg:
                ans *= max(small_nonneg)
                ans %= MOD
                ans *= pow(max(large_neg), MOD - 2, MOD)
                ans %= MOD
            elif not small_nonneg:
                ans *= min(small_neg)
                ans %= MOD
                ans *= pow(min(large_nonneg), MOD - 2, MOD)
                ans %= MOD
            else:
                if min(small_neg) * max(large_neg) > max(small_nonneg) * min(
                    large_nonneg
                ):
                    ans *= min(small_neg)
                    ans %= MOD
                    ans *= pow(min(large_nonneg), MOD - 2, MOD)
                    ans %= MOD
                else:
                    ans *= max(small_nonneg)
                    ans %= MOD
                    ans *= pow(max(large_neg), MOD - 2, MOD)
                    ans %= MOD
    return ans


print(solve(N, K, A))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
mod=10**9+7
ans=1
i=0
j=-1
k_1=k
while k_1>1:
  if a[i]*a[i+1]>a[j]*a[j-1]:
    ans=ans*a[i]*a[i+1]%mod
    i+=2
    k_1-=2
  else:
    ans=ans*a[j]%mod
    j-=1
    k_1-=1
if k_1==1:
  ans=ans*a[j]%mod
if a[-1]<0 and k%2==1:
  for i in a[n-k:]:
    ans=ans*i%mod
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
ans=1
if n==k:
  # 全部を選ぶ場合
  for q in a:
    ans=ans*q%mod
  print(ans)
  exit()

a.sort()
# print(a)

if a[0]>=0:
  # all pos
  for i in range(k):
    ans=ans*a.pop()%mod
  print(ans)
  exit()
if a[-1]<0:
  # all neg
  if k%2==0:
    # even
    for i in range(k):
      ans=ans*a[i]%mod
    print(ans)
    exit()
  else:
    # odd
    for i in range(k):
      ans=ans*a.pop()%mod
    print(ans)
    exit()
    
from collections import deque
a=deque(a)
# 左右から取り出したい
while k!=0:
  if a[0]>=0 or a[1]>=0:
    # 下から2つが正になっていたら、もうマイナスを取る意味はない
    for i in range(k):
      ans=ans*a.pop()%mod
    print(ans)
    exit()
  if a[0]*a[1]<a[-1]:
    ans=ans*a.pop()%mod
    k-=1
  else:    
    ans=ans*a.popleft()%mod
    ans=ans*a.popleft()%mod
    k-=2
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
ans=1
if n==k:
  # 全部を選ぶ場合
  for q in a:
    ans=ans*q%mod
  print(ans)
  exit()

a.sort()
# print(a)

if a[0]>=0:
  # all pos
  for i in range(k):
    ans=ans*a.pop()%mod
  print(ans)
  exit()
if a[-1]<0:
  # all neg
  if k%2==0:
    # even
    for i in range(k):
      ans=ans*i%mod
    print(ans)
    exit()
  else:
    # odd
    for i in range(k):
      ans=ans*a.pop()%mod
    print(ans)
    exit()
    
from collections import deque
a=deque(a)
# 左右から取り出したい
while k!=0:
  if a[0]>=0 or a[1]>=0:
    # 下から2つが正になっていたら、もうマイナスを取る意味はない
    for i in range(k):
      ans=ans*a.pop()%mod
    print(ans)
    exit()
  if a[0]*a[1]<a[-1]:
    ans=ans*a.pop()%mod
    k-=1
  else:    
    ans=ans*a.popleft()%mod
    ans=ans*a.popleft()%mod
    k-=2
print(ans)

Submission status: Wrong Answer

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools, copy, math
from bisect import *
from heapq import *
from collections import *


def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N, K = In.ints()

MOD = 10**9+7

ans = 1

negs = []
pos = []

for el in In.ints():
    if el<0:
        negs.append(el)
    else:
        pos.append(el)

pos.sort()
negs.sort()

KTemp = K
answers = []

if 0 in pos:
    answers.append(0)

neggz = False
ineg = len(negs)-1
ipos = 0    
while K>0:
    resNeg = negs[ineg] if ineg>=0 else 99999999999
    resPos = pos[ipos] if ipos<len(pos) else 99999999999
    
    if abs(resPos)<abs(resNeg):
        ans*=resPos

        ipos+=1
        K-=1        
    else:
        ans*=resNeg
        ineg-=1
        K-=1
        neggz = not neggz
    
    ans%=MOD

if not neggz:
    answers.append(ans)
else:
    answers.append(-ans)

ans = 1
K = KTemp
ineg = 0
ipos = len(pos)-1

while K>0:
    resNeg = -1
    resPos = -1

    if ineg<len(negs)-1:
        resNeg = negs[ineg]*negs[ineg+1]
    
    iposchoose = 0
    if ipos>=1 and pos[ipos]*pos[ipos-1] > pos[ipos]:            
        resPos = pos[ipos]*pos[ipos-1]
        iposchoose=2
    elif ipos>=0:
        resPos = pos[ipos]
    
    if resPos>resNeg:
        ans*=resPos

        if iposchoose==2:
            ipos-=2
            K-=2
        elif ipos>=0:
            ipos-=1
            K-=1            
    else:
        ans*=resNeg
        ineg+=2
        K-=2
    
    ans%=MOD

answers.append(ans)

Out.int(max(answers))



######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Wrong Answer

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools, copy, math
from bisect import *
from heapq import *
from collections import *


def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N, K = In.ints()

MOD = 10**9+7

ans = 1
negs = []
pos = []

for el in In.ints():
    if el<0:
        negs.append(el)
    else:
        pos.append(el)

pos.sort()
negs.sort()

takeSmallest = False

Ktemp = K
negCount = len(negs)
posCount = len(pos)

while Ktemp > 0:
    if Ktemp >= 2:
        if negCount>=2:
            negCount-=2
            Ktemp-=2
        elif posCount>=1:
            posCount-=1
            Ktemp-=1
        else:
            takeSmallest=True
            break
    else:
        if posCount>=1:
            break

        takeSmallest=True
        break

if takeSmallest: 
    if 0 in pos:
        ans = 0
    else:
        ineg = len(negs)-1
        ipos = 0    
        while K>0:
            resNeg = negs[ineg] if ineg>=0 else 99999999999
            resPos = pos[ipos] if ipos<len(pos) else 99999999999
            
            if abs(resPos)<abs(resNeg):
                ans*=resPos

                ipos+=1
                K-=1        
            else:
                ans*=resNeg
                ineg-=1
                K-=1
            
            ans%=MOD
else:
    ineg = 0
    ipos = len(pos)-1

    while K>0:
        resNeg = -1
        resPos = -1

        if ineg<len(negs)-1:
            resNeg = negs[ineg]*negs[ineg+1]
        
        iposchoose = 0
        if ipos>=1 and pos[ipos]*pos[ipos-1] > pos[ipos]:            
            resPos = pos[ipos]*pos[ipos-1]
            iposchoose=2
        elif ipos>=0:
            resPos = pos[ipos]
        
        if resPos>resNeg:
            ans*=resPos

            if iposchoose==2:
                ipos-=2
                K-=2
            elif ipos>=0:
                ipos-=1
                K-=1            
        else:
            ans*=resNeg
            ineg+=2
            K-=2
        
        ans%=MOD

Out.int(ans)



######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")