fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = 200005;
  6. const long long INF = 1e15;
  7.  
  8. int n;
  9. long long a[MAXN];
  10. long long D[MAXN];
  11. int L[MAXN], R[MAXN];
  12. bool used[MAXN];
  13. long long ans[MAXN];
  14.  
  15. int main() {
  16.     ios_base::sync_with_stdio(0); 
  17.     cin.tie(0); 
  18.     cout.tie(0);
  19.  
  20.     if (!(cin >> n)) return 0;
  21.  
  22.     for (int i = 1; i <= n; i++) {
  23.         cin >> a[i];
  24.     }
  25.  
  26.     sort(a + 1, a + 1 + n);
  27.  
  28.     D[0] = INF;
  29.     D[n] = INF;
  30.     for (int i = 1; i < n; i++) {
  31.         D[i] = a[i+1] - a[i];
  32.         L[i] = i - 1;
  33.         R[i] = i + 1;
  34.     }
  35.     L[0] = -1; 
  36.     R[n] = n + 1;
  37.  
  38.     priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  39.  
  40.     for (int i = 1; i < n; i++) {
  41.         pq.push({D[i], i});
  42.     }
  43.  
  44.     long long current_cost = 0;
  45.     for (int k = 1; k <= n / 2; k++) {
  46.         while (used[pq.top().second]) {
  47.             pq.pop();
  48.         }
  49.  
  50.         long long v = pq.top().first;
  51.         int id = pq.top().second;
  52.         pq.pop();
  53.  
  54.         current_cost += v;
  55.         ans[k] = current_cost;
  56.  
  57.         int l = L[id];
  58.         int r = R[id];
  59.  
  60.         used[l] = true;
  61.         used[r] = true;
  62.  
  63.         D[id] = D[l] + D[r] - D[id];
  64.         pq.push({D[id], id});
  65.  
  66.         L[id] = L[l];
  67.         R[id] = R[r];
  68.  
  69.         if (L[id] >= 0) R[L[id]] = id;
  70.         if (R[id] <= n) L[R[id]] = id;
  71.     }
  72.  
  73.     for (int k = 1; k <= n / 2; k++) {
  74.         cout << ans[k] << (k == n / 2 ? "" : " ");
  75.     }
  76.     cout << "\n";
  77.  
  78.     return 0;
  79. }
  80.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pFHhCQ
language:
C++14 (clang 8.0)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!