C. Alice and the Cake codeforces solution

C. Alice and the Cake codeforces solution

by ujjal roy

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

int main()

{

    ll t,n,i,j,a;

    cin>>t;

    while(t--)

    {

        map<ll,int> mp;

        multiset<ll> m1;

        multiset<ll> m2;

        ll sum=0;

        cin>>n;

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

        {

            cin>>a;

            m1.insert(a);

            sum+=a;

            mp[a]++;

        }

    m2.insert(sum);

    while(!m2.empty())

    {

        ll x=*--m2.end();

        if(x<*--m1.end()) break;

        m2.erase(m2.find(x));

        if(mp[x]!=0)

        {

            mp[x]--;

           m1.erase(m1.find(x));

        }

        else

        {

             m2.insert(x/2);

             m2.insert((x+1)/2);

        }

    }

      if(!m1.empty()) cout<<"NO"<<endl;

      else cout<<"YES"<<endl;

    }

    return 0;

}