fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6.  
  7. int a[100005];
  8. int n,k;
  9.  
  10. namespace Sub3{
  11.     int dif[100005];
  12.     int ptl[100005];
  13.     int ptr[100005];
  14.     int del[100005];
  15.  
  16.     void solve(){
  17.         priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
  18.  
  19.         for(int i = 1; i < n; i++){
  20.             dif[i] = a[i+1] - a[i];
  21.             pq.push({dif[i],i});
  22.  
  23.             //cout << dif[i] << ' ' << i << endl;
  24.             ptl[i] = i-1;
  25.             ptr[i] = i+1;
  26.         }
  27.  
  28.         int ans = 0;
  29.         for(int i = 1; i <= k && pq.size(); i++){
  30.             int c = pq.top().first, u = pq.top().second;
  31.             pq.pop();
  32.             if(del[u]){
  33.                 i--;
  34.                 continue;
  35.             }
  36.  
  37.             ans += c;
  38.             c = -c;
  39.  
  40.             int flag = (ptl[u] != 0) && (ptr[u] != n);
  41.             if(ptl[u] != 0){
  42.                 c += dif[ptl[u]];
  43.                 del[ptl[u]] = 1;
  44.                 ptl[u] = ptl[ptl[u]];
  45.                 ptr[ptl[u]] = u;
  46.             }
  47.  
  48.             if(ptr[u] != n){
  49.                 c += dif[ptr[u]];
  50.                 del[ptr[u]] = 1;
  51.                 ptr[u] = ptr[ptr[u]];
  52.                 ptl[ptr[u]] = u;
  53.             }
  54.  
  55.             if(u == 1){
  56.                 del[u] = 1;
  57.                 ptl[ptr[u]] = 0;
  58.             }
  59.  
  60.             if(u == n-1){
  61.                 del[u] = 1;
  62.                 ptr[ptl[u]] = n;
  63.             }
  64.  
  65.             dif[u] = c;
  66.             if(flag){
  67.  
  68.                 pq.push({c,u});
  69.             }
  70.         }
  71.  
  72.         cout << ans;
  73.     }
  74. }
  75.  
  76. signed main(){
  77.     ios_base::sync_with_stdio(0);
  78.     cin.tie(0);
  79.     freopen("DAN.inp", "r", stdin);
  80.     freopen("DAN.out", "w", stdout);
  81.  
  82.     cin >> n >> k;
  83.     for(int i = 1; i <= n; i++) cin >> a[i];
  84.     sort(a+1,a+n+1);
  85.  
  86.     Sub3::solve();
  87.     return 0;
  88. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RTIgcT
language:
C++14 (gcc 8.3)
created:
1 day 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!