Can anyone suggest a good solution for this.
Maybe you can get the better solution in atcoder or codeforces
Good solution
#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
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
Link to my solution : Submission #7569443 - AtCoder Beginner Contest 141
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 especially for a beginner.
Argee , logic is more important than code.
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!
updated!
please check
Good sulution