In this HackerEarth Monk and the Magical Candy Bags problem solution 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.


HackerEarth Monk and the Magical Candy Bags problem solution


HackerEarth Monk and the Magical Candy Bags problem solution.

#include<bits/stdc++.h>
using namespace std;
 
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define elif else if
#define ff first
#define ss second
#define pii pair<ll int,ll int>
#define mp make_pair
#define pb push_back
#define CLEAR(array, value) memset(ptr, value, sizeof(array));
#define si(a)     scanf("%d", &a)
#define sl(a)     scanf("%lld", &a)
#define pi(a)     printf("%d", a)
#define pl(a)     printf("%lld", a)
#define pn        printf("\n")
#define inf 100000000

int main()
{
   freopen("in.txt","r",stdin);
   freopen("out","w",stdout);
   int t;
   cin>>t;
   assert(1<=t && t<=10);
   while(t--)
   {
    int i,j,n,k;
    cin>>n>>k;
    priority_queue<ll int>pq;
    assert(1<=n && n<=100000);
    assert(0<=k && k<=100000);
    vector< ll int> v(n);
    ll int ans=0;
    rep(i,n)
    {
      cin>>v[i];
      pq.push(v[i]);
    }
    while(k--)
    {
      ll int tmp=pq.top();
      pq.pop();
      ans+=tmp;
      pq.push(tmp/2);
    }
    cout<<ans<<"\n";
   }
  return 0;
}

Second solution

#include<bits/stdc++.h>

using namespace std;

#define vi vector < int >
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define foreach(it,v) for( __typeof((v).begin())it = (v).begin() ; it != (v).end() ; it++ )
#define ll long long
#define llu unsigned long long
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define dbg(x) { cout<< #x << ": " << (x) << endl; }
#define dbg2(x,y) { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) << endl; }
#define all(x) x.begin(),x.end()
#define mset(x,v) memset(x, v, sizeof(x))
#define sz(x) (int)x.size()

ll a[100005];

int main()
{
    int t;
    scanf("%d",&t);
    assert(1 <= t && t <= 10);
    while(t--)
    {
        int n,k,i;
        scanf("%d%d",&n,&k);
        assert(1 <= n && n <= 100000);
        assert(0 <= k && k <= 100000);
        priority_queue < ll > pq;
        for(i=0;i<n;i++)
        {
            scanf("%lld",&a[i]);
            pq.push(a[i]);
            assert(0 <= a[i] && a[i] <= (ll)1e10);
        }
        ll ans = 0;
        while(k--)
        {
            ll x = pq.top();
            pq.pop();
            ans += x;
            pq.push(x/2);
        }
        printf("%lld\n",ans);
    }
    return 0;
}