問題
与えられた $n$ 個の整数 $A _ {1}, \ldots, A _ {n}$ から $k$ 個選ぶとき、選んだ要素の積としてありえる値の最大値を求めよ（$1 \leq k \leq n \leq 2 \times 10 ^ 5$）
解説
$A$ をあらかじめ昇順にソートしておく。$A$ のすべての数が $0$ 以下かつ $k$ が奇数ならば、大きい順に $k$ 個とった積が最大である。それ以外の場合について考える。$k$ が偶数の場合、隣り合う $2$ つをセットで扱うことで、答えを必ず $0$ 以上にできる。積を最大にするには、$i=0,j=n-1$ から始めて、$A _ i \times A _ {i + 1}$ と $A _ {j - 1} \times A _ {j}$ のうち積が大きい方を採用し、採用されたら $i$ は $+2$、$j$ は $-2$ することを $k/2$ 回繰り返せばよい。また、$k$ が奇数の場合は $A$ の最大値が正になるので必ず採用することで、$k$ が偶数の場合に帰着する。
実装
n, k = map(int, input().split()) *A, = map(int, input().split()) p = 10**9 + 7 A.sort() ans = 1 if A[n - 1] <= 0 and k % 2 == 1: for i in range(k): ans *= A[n - 1 - i] ans %= p print(ans) exit() i = 0 j = n - 1 if k % 2 == 1: ans *= A[j] ans %= p j -= 1 k -= 1 for _ in range(k // 2): left = A[i] * A[i + 1] right = A[j] * A[j - 1] if (left > right): ans *= left ans %= p i += 2 else: ans *= right ans %= p j -= 2 print(ans)
