ABC173 E - Multiplication 4 (500)
ひたすら場合分けする
正の数、負の数、0の個数をそれぞれ数え上げる
それぞれpl, mi, zとする
$ z + k > nなら0が必ず入るので答えは0
$ k = pl + miなら0以外の要素が全部含まれる場合を作れる
その場合に結果が負になる場合、0が$ Aに含まれている場合はその方が答えが良くなるので0
それ以外は0以外の要素を全部かけるだけ
正の数が無い場合
負の数しか作れない場合に0が$ Aに含まれている場合はその方が答えが良くなるので0
kが奇数の場合は答えが負になるので絶対値が小さい順に取っていく
kが偶数の場合は答えが正になるので絶対値が大きい順に取っていく
以降は取ってくる負の数の量を調整することで答えを非負整数にできる
正の数、負の数の配列をそれぞれ作って絶対値の大きい順にソートする
kが奇数の場合、正の数の先頭から一つ取って答えにかけておく
k個選択されるまで以下を繰り返す
正の数の先頭二つの積と、負の数の先頭二つの積で大きい方を選ぶ
選んだ二つを答えにかける
ソートがボトルネックで$ O(N \log N)