Monk and the Magical Candy Bags

Monk and the Magical Candy Bags 

Problem

Our Monk loves candy!
While taking a stroll in the park, he stumbled upon N Bags with candies. The i'th of these bags contains Ai candies.
He picks up a bag, eats all the candies in it and drops it on the ground. But as soon as he drops the bag, the number of candies in the bag increases magically! Say the bag that used to contain X candies (before eating), now contains [X/2] candies! ,where [x] is the greatest integer less than x (Greatest Integer Function).
Amazed by the magical spell, Monk can now have a lot more candies! But he has to return home in K minutes. In a single minute,Monk can consume all the candies in a single bag, regardless of the number of candies in it.
Find the maximum number of candies that Monk can consume.

Input:
First line contains an integer T. T test cases follow.
First line of each test case contains two space-separated integers N and K.
Second line of each test case contains N space-separated integers,the number of candies in the bags.

Output:
Print the answer to each test case in a new line.

Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 105
0 ≤ K ≤ 105
0 ≤ Ai ≤ 1010

Sample Input

1
5 3
2 1 7 4 2

Sample Output

14

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

The state of bags is:
2 1 7 4 2
Monk eats all candies from Third bag (7). The state of bags becomes:
2 1 3 4 2
Monk eats all candies from Fourth bag (4). The state of bags becomes:
2 1 3 2 2
Monk eats all candies from Third bag (3). The state of bags becomes:
2 1 1 2 2
Hence, the Monk eats 7+4+3= 14

The solution to the above question in C++ is

We can make a multiset here and then find our answer, let us see how we can do it. So we will use multiset because we have to use arranged order of the given number of candies. We will simply get the largest value in the multiset and then add it to our answer, then add half of it to the multiset and then delete that value. We will do it until K operations or k minutes as given in the question.

#include<bits/stdc++.h>

using namespace std;

// #define vv vector<int> v;

int main(){

    #ifndef ONLINE_JUDGE

    // for getting input from input.txt

    freopen("input.txt", "r", stdin);

    // for writing output to output.txt

    freopen("output.txt", "w", stdout);

#endif

    int t;

    cin>>t;

    while(t--){

        int n,k;

        cin>>n>>k;

        multiset<long long>v;

        for(int i=0; i<n; i++){

            long long temp;

            cin>>temp;

            v.insert(temp);

        }

        long long ans=0;

        while(k--){

            auto it=v.end();

            --it;

            long long t=*it;

            v.erase(it);

            ans+=t;

            v.insert(t/2);

        }

        cout<<ans<<endl;

        

    }

    return 0;

}