Submission #74771863

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    if (!(cin >> N)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // Sorting is the bottleneck: O(N log N)
    sort(A.begin(), A.end());

    long long total_sum = 0;
    for (int k = 0; k < N; ++k) {
        // Using 0-based indexing: k goes from 0 to N-1
        // Contribution = A[k] * (number of elements smaller) - A[k] * (number of elements larger)
        // number of elements smaller = k
        // number of elements larger = (N - 1 - k)
        total_sum += A[k] * k - A[k] * (N - 1 - k);
    }

    cout << total_sum << endl;

    return 0;
}

Submission Info

Judge Result