➤ Problem Link : 1111C. Creative Snap
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int n,k,a,b;
map<ll,ll> mp;
ll minPower(ll arr[],ll i,ll j)
{
if(i==j)
{
auto it = mp.find(i);
if(it==mp.end())
return a;
else
{
ll t=it->second;
it--;
t-=it->second;
return b*(t);
}
}
auto rt = mp.upper_bound(j);
rt--;
auto lt = mp.lower_bound(i);
lt--;
ll val = rt->second - lt->second;
if(val==0)
return a;
ll first = minPower(arr,i,(i+j)/2)+minPower(arr,(i+j)/2 + 1,j);
ll second = b*val*(j-i+1);
return min(first,second);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>k>>a>>b;
ll arr[k];
mp.clear();
mp[0]=0;
for(int i=0;i<k;i++)
{
cin>>arr[i];
mp[arr[i]]++;
}
auto temp=mp.begin();
auto it = mp.begin();
it++;
for(;it!=mp.end();it++)
{
it->second+=temp->second;
temp++;
}
cout<<minPower(arr,1,pow(2,n));
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.