No.062 D

$a^{\prime}$ の前半を $a_1, a_2, \dots, a_{N+i}$ から選び, 後半を $a_{N+i+1}, a_{N+i+2}, \dots, a_{3N}$ から選ぶとする. $i$ は $0 \leq i \leq N$ となる.

前半はなるべく大きい数を選び, 後半はなるべく小さい数を選ぶようにすればいい.

これを愚直に実装すると $O(N^2\log N)$ となり, 部分点がもらえるはずである.

$a_1, a_2, \dots, a_{N+i}$ の上位 $N$ 個の和を求める方法であるが, 優先度付きキューを使う.

まず $a_1, a_2, \dots, a_N$ の和を計算し, 同時に最小値を返す優先度付きキューに入れておく.

次に $a_{N+1}$ とキューの最小値を比べ, $a_{N+1}$ の方が大きければ和は $a_{N+1}$ とキューの最小値の差分だけ大きくなる. そしてキューの最小値を $a_{N+1}$ に置き換える. $a_{N+1}$ の方が小さければ何もしない.

以下これを繰り返すことで $0 \leq i \leq N$ の範囲の計算を $O(N\log N)$ で行うことができるので, 満点をもらえる.

後半部も同様に求めて, 最後に前後半の差の最大値を求める.