ABC181 E - Transformable Teacher (500)
$ Hは昇順にソートしておく
ペアを作る場合、明らかに隣同士で差を取るのが最小になる
上の条件から先生が組むのは偶数番目の児童が良い
左と右からペアを作っていったときの差の累積和を求めておく
m個の変身形態について、それぞれで以下を行う
$ w_i以上の値を持つ最低の値の位置を探す
奇数番目なら一つ前の偶数番目を選ぶ
その児童をペアとしたときの差分の和を求める
他のペアについては左右の累積和から$ O(1)で求まる
m個の結果の中で最小の値が答え
$ O((N+M) \log N