D - Sum of difference Editorial by en_translator


We can assume that \(A_1\leq\ldots\leq A_N\) by sorting the input. Then, for each \(i<j\), \(|A_i-A_j| = A_j-A_i\).

For each \(i\), \(\sum_{j=i+1}^{N}|A_i-A_j|=(\sum_{j=i+1}^{N}A_j)-(N-i)A_i\), and this can be calculated in a \(O(1)\) time each by calculating the cumulative sums beforehand. Therefore, the problem could be solved in a total of \(O(N\log N)\) time.

posted:
last update: