fork download
copy 
  1. #ifdef LOCAL
  2.     cout<<"\nTime Elapsed: " << 1.0*clock() / CLOCKS_PER_SEC << " sec\n";
  3. #endif
  4.  
  5. #include "bits/stdc++.h"
  6.  
  7. using namespace std;
  8.  
  9.  
  10. #define ll long long
  11. #define pii pair<ll,ll>
  12. #define endl "\n"
  13. #define pb push_back
  14. #define all(a) a.begin(),a.end()
  15.  
  16.  
  17. ll  mod=998244353;
  18.  
  19. ll rec(ll i, vector<ll>& vp, ll k){
  20.     if(k<=1 || i==vp.size()){
  21.         if(k==0) return 0;
  22.         vector<ll> temp;
  23.         for(ll j=0;j<vp.size();j++){
  24.             if(vp[j]==0) continue;
  25.             ll idx=j;
  26.             ll cntr=0;
  27.             while(idx<vp.size() && vp[idx]==1){
  28.                 idx+=1;
  29.                 cntr+=1;
  30.             }
  31.             j=idx-1;
  32.             temp.pb(cntr);
  33.         }
  34.         if(!temp.empty()) sort(all(temp)), reverse(all(temp));
  35.         ll ans=0, fk=k;
  36.         for(ll j=0;j<k;j++){
  37.             if(temp.size()==j || fk==0) break;
  38.             ans+=(temp[j]);
  39.             fk-=1;
  40.         }
  41.         return ans+fk;
  42.     }
  43.     if(vp[i]==1) return rec(i+1,vp,k);
  44.     ll nxt=i, cntr=0;
  45.     while(nxt<vp.size() && vp[nxt] == 0){
  46.         nxt+=1;
  47.         cntr+=1;
  48.     }
  49.     if(cntr>k) return rec(nxt,vp,k);
  50.     ll fk=rec(nxt,vp,k);
  51.     for(ll j=i;j<nxt;j++){
  52.         vp[j]=1;
  53.     }
  54.     ll fk1=rec(nxt,vp,k-cntr);
  55.     for(ll j=i;j<nxt;j++){
  56.         vp[j]=0;
  57.     }
  58.     return max(fk,fk1);
  59. }
  60.  
  61. void solve(){
  62.     ll a,b,c,k,l,r,q,d,n,m,z,w,h,x,y;
  63.     cin>>n>>k;
  64.     if(k==0){
  65.         cout<<0<<endl;
  66.         return;
  67.     }
  68.     vector<ll> vp;
  69.     ll cntr=0;
  70.     while(n>0){
  71.         vp.pb(n%2);
  72.         cntr+=(n%2==0);
  73.         n/=2;
  74.     }
  75.     if(cntr<k){
  76.         ll sz=vp.size();
  77.         cout<<sz+(k-cntr-1)<<endl;
  78.         return;
  79.     }
  80.     ll ans=rec(0,vp,k);
  81.     cout<<ans<<endl;
  82.     return;
  83. }
  84.  
  85. int main(){
  86.     // freopen("input.txt", "r", stdin);
  87.     // freopen("output.txt", "w", stdout);
  88.     ios::sync_with_stdio(false);
  89.     cin.tie(nullptr);
  90.     ll a,b,c,n,tt,d,m,k,x,y;
  91. 	tt = 1;
  92.     cin >> tt;
  93.     while(tt--){
  94.         solve();
  95.     }
  96.     return 0;
  97. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/fq6kpM
language:
C++14 (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!