fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define TIME (1.0*clock()/CLOCKS_PER_SEC)
  4. using namespace std;
  5.  
  6. void input(){
  7. 	#define taskname ""
  8. 	if(fopen(taskname ".inp", "r")){
  9. 		freopen(taskname ".inp", "r", stdin);
  10. 		freopen(taskname ".out","w",stdout);
  11. 	}
  12. }
  13. const int N = 2e5+1;
  14. const ll INF =1e18;
  15. const int Q =1e9+7;
  16. ll a[N];
  17. ll n,k;
  18. int main(){
  19. 	cin.tie(0)->sync_with_stdio(0);
  20. 	cout.tie(0);
  21. 	input();
  22. 	cin >> n >> k;
  23. 	for(ll i=1;i<=n;++i) cin >> a[i];
  24.     sort(a+1,a+n+1);
  25.     vector<ll>w(n+1);
  26.     for(ll i=1;i<n;++i) w[i] = (a[i+1] - a[i])*(a[i+1]-a[i]);
  27.     w[0] = INF;
  28.     w[n] = INF;
  29.     ll sz = n-1;
  30.     vector<ll>pre(sz+2),nxt(sz+2);
  31.     vector<bool>ck(sz+2,0);
  32.     for(ll i=0;i<=sz+1;++i){
  33.         pre[i] = i-1;
  34.         nxt[i] = i+1;
  35.     }
  36.     priority_queue<pair<ll,ll>>q;
  37.     for(ll i=1;i<=sz;++i) q.push({-w[i],i});
  38.     ll ans = 0;
  39.     while(k--){
  40.         while(ck[q.top().second] || -q.top().first != w [q.top().second]) q.pop();
  41.         ll val = q.top().first;
  42.         ll id = q.top().second;
  43.         q.pop();
  44.         val = -val;
  45.         ans += val;
  46.         ll l = pre[id], r = nxt[id];
  47.         w[id] = w[l] + w[r] - w[id];
  48.         ck[l] = 1;
  49.         ck[r] = 1;
  50.         if(l >= 0) pre[id] = pre[l];
  51.         else pre[id] = -1; 
  52.         if(r<=sz+1) nxt[id] = nxt[r];
  53.         else nxt[id] = sz+2;
  54.         if(pre[id] >= 0) nxt[pre[id]] = id;
  55.         if(nxt[id] <= sz+1) pre[nxt[id]] = id;
  56.         q.push({-w[id],id});
  57.     }
  58.     cout << ans << endl;
  59. 	return 0;
  60. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
5 2 
2 5 3 3 6
stdout
copy 
1
https://ideone.com/nVsL24
language:
C++ (gcc 8.3)
created:
2 days 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!