ARC074 D - 3N Numbers
長さ3Nの数列a[i]が与えられる。この中から2N個を選び「前半N個の総和 - 後半N個の総和」を最大化せよ。
前半N要素が全て入っている範囲を[0, k), 後半N要素が全て入っている範囲を[k, N)として、N<=k<N*2 の範囲で最大値を求めればよい。ナイーブにやるには毎回ソートして前半であれば最大値からN番目までの和を求めれば良いが、これでは計算量がO(N^2)なので間に合わない。
そこで、PriorityQueueを使ってある時点kでの総和の最大値から、k+1での総和の最大値をO(logN)で計算する。具体的にはa[k]をQueueに追加し、最小値minを取り出す。するとdp[k + 1] = dp[k] - min + a[k] となる。これを前半後半両方で2個dpすると、その差の最大値が答え。O(N logN)。
