AtCoder Begineers problem 141 . Editorial for D Question?

Can anyone suggest a good solution for this.

Maybe you can get the better solution in atcoder or codeforces :grinning:

Good solution :+1: :+1: :+1:

1 Like
#define ll long long int
using namespace std;
 
void solve(){
	int n,k;
	cin>>n>>k;
	priority_queue<ll>pq;
	for(int i=0;i<n;i++){
		ll a;
		cin>>a;
		pq.push(a);
	}
	while(k--){
		ll x=pq.top();
		pq.pop();
		x>>=1;
		pq.push(x);
	}
	ll ans=0;
	while(not pq.empty()){
		ans+=pq.top();
		pq.pop();
	}
	cout<<ans<<endl;
}
 
int main(){
	// int t;
	// cin>>t;
	// while(t--){
		solve();
	// }
	return 0;
} 

my solution
so what i did was use a priority queue to find max element all the time.
Reason because using linear search on an array takes linear time
it’s better to use priority queue as it only takes log(n) time :slight_smile:

1 Like

Use priority queue, loop until m becomes zero, pop the top element (i.e. the max element), reduce it by half and again push it back to the queue, then finally sum all the elements present in the queue.
The final sum will be your answer :smile:

Link to my solution : Submission #7569443 - AtCoder Beginner Contest 141

2 Likes

i did the same thing!

I didn’t read your code… when someone is asking for help it’s always better to write the logic, DS used etc in the form of words maybe attach some links for further references and then post your code.
These small things really help a lot :slight_smile: especially for a beginner.

Argee , logic is more important than code. :ok_hand:

1 Like

i was unable to get out of

this thing 

that’s why i didn’t write for then was gonna edit my reply.
Thank you for reminding me!

1 Like

updated! :slight_smile:
please check

2 Likes

Good sulution :ok_hand::+1::blush:

2 Likes