abc186_d - Sum Of Difference

Two observations:

• $

  x - y

  =

  y - x

  $.

• Each $a_i$ is paired with all other elements $a_j$, $i!=j$.

This allows us to reorder the elements, both in position and in the operand.

Sort the array non-decreasingly. In this way we won’t have to worry about possible negative values:

Time complexity: $O(n)$

Memory complexity: $O(n)$

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vector<ll> a(n), pa(n);
    read_n(begin(a), n);
    sort(begin(a), end(a));
    partial_sum(begin(a), end(a), begin(pa));
    ll ans = 0;
    for (int i = n - 1; i >= 1; --i)
        ans += i * a[i] - pa[i - 1];
    cout << ans << endl;
    return 0;
}