fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. 	// your code goes here;
  6. 	int n,k;
  7. 	cin>>n>>k;
  8. 	vector<int> p(n);
  9. 	for(int i=0;i<n;i++){
  10. 		cin>>p[i];
  11. 	}
  12. 	int sum=0,count=0;
  13. 	 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  14.      unordered_map<int,int> mp;
  15.     for(int i=0;i<n;i++){
  16.     	pq.push({0,p[i]});
  17.     	// mp[p[i]]=0;
  18.     }
  19.     while(count<k+n&&!pq.empty()){
  20.     	auto it = pq.top();
  21.     	pq.pop();
  22.     	int dis = it.first;
  23.     	int loc = it.second;
  24.  
  25.     	if(mp[loc]==0){
  26.     		sum+=dis;
  27.     		if(mp[loc+1]==0){
  28.     			pq.push({dis+1,loc+1});
  29.     		}
  30.     		if(mp[loc-1]==0){
  31.     			pq.push({dis+1,loc-1});
  32.     		}
  33.     	count++;
  34.     	mp[loc]=1;
  35.     	}
  36.  
  37.     }
  38.     cout<<sum;
  39. 	return 0;
  40. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
2 4
7 8
stdout
copy 
6
https://ideone.com/rWJ6sE
language:
C++14 (gcc 8.3)
created:
3 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!