D - Sum diff

キーワード

数式処理，累積和，二分探索

解説

愚直に組 $(i,j)$ を全探索しようとすると，計算量は $O(NM)$ となり間に合いません。
考察をして計算量を改善する必要があります。

$A$ の要素の順番は答えに影響しないので，$A$ を昇順にソートして単調性を持たせます。
答えに $B_k$ が寄与する部分は，$\sum_{i=1}^{N}|A_i-B_k|$ です。
もし，$A_j < B_k \leq A_{j+1}$ となる $j$ が存在するならば，
$\sum_{i=1}^{N}|A_i-B_k|$
$=\sum_{i=1}^{j}(B_k-A_i)+\sum_{i=j+1}^{N}(A_i-B_k)$
$=jB_k-\sum_{i=1}^{j}A_i+\sum_{i=j+1}^{N}A_i-(N-j)B_k$
$=(2j-N)B_k-\sum_{i=1}^{j}A_i+\sum_{i=j+1}^{N}A_i$
と分解できます。
また，$B_k \leq A_1$ の場合は，$\sum_{i=1}^{N}|A_i-B_k|=\sum_{i=1}^{N}A_i-NB_k$ であり，$A_N < B_k$ の場合は，$\sum_{i=1}^{N}|A_i-B_k|=NB_k-\sum_{i=1}^{N}A_i$ となります。
$jB_k, (N-j)B_k$ は $O(1)$ で求めることができ，$\sum_{i=1}^{j}A_i, \sum_{i=j+1}^{N}A_i, \sum_{i=1}^{N}A_i$ は事前に $O(N)$ で累積和を取っておけば $O(1)$ で値を求めることができます。

$A$ の要素と $B_k$ の大小関係がどの場合に該当するのかは二分探索によって $O(\log N)$ で調べられるので，結局，答えに $B_k$ が寄与する部分は $O(\log N)$ で値を求めることができます。
これを $1 \leq k \leq M$ を満たすすべての $k$ に対して求めた値の総和が答えになります。
計算量は $O((N+M)\log N)$ で，十分高速です。

なお，$A$, $B$ のうち要素数が大きくない方をソートすることで，計算量は $O((N+M)\log \min (N,M))$ になります。

実装例(C++)