Untitled

mail@pastecode.io avatar
unknown
plain_text
8 months ago
3.1 kB
3
Indexable
Never
// Author- Aryan Pundir
#include<bits/stdc++.h>
using namespace std;
#define ll          long long
#define lli         long long int
#define vl          vector<ll>
#define vi          vector<int>
#define vs          vector<string>
#define vpi          vector<pair<int,int>>
#define vpl          vector<pair<ll,ll>>
#define pi          pair<int,int>
#define pl          pair<ll,ll>
#define all(a)      a.begin(),a.end()
#define mem(a,x)    memset(a,x,sizeof(a))
#define pb          push_back
#define mpi          map<int,int>
#define si          set<int>
#define sl          set<ll>
#define mpl          map<ll,ll>
#define mpcl          map<char,ll>
#define pqi          priority_queue<int>
#define pql          priority_queue<ll>
#define mpql          priority_queue <ll,vl ,greater<ll>>
#define mod          1000000007
const ll maxn = 2e5+5 ;
// Sieve of Eratosthenes
// const int N=1300000;
// const int nax=1e9+1;
// bool isPrime[N];
// vector<int> primes;
// void sieve(int n=N) {
// fill(isPrime + 2, isPrime + n, true);
// primes.pb(2);
// for (ll i=3;i*i<=nax;i++) {
// bool isPrime =true;
// for (auto p : primes) {
// if (i % p == 0) {
// isPrime = false;
// break;
// }
// }
// if (isPrime) {
// primes.push_back(i);
// }
// }
// }
// ll factorial[maxn];
// void calcfact()
// {
// factorial[0] = 1;
// for (ll i = 1; i < maxn; i++) 
// factorial[i] = (factorial[i - 1] * i) % mod; 
// }
// ll power(ll x, ll y)
// {
// ll res = 1;
//  x = x % mod;
// if (x == 0)
// return 0;
// while (y > 0)
//  {
// if (y & 1ll)
// res = (res * x) % mod;
//  y = y >> 1ll;
//  x = (x * x) % mod;
// }
// return res;
// }
// ll power(ll x, ll y, ll p)
// {
// ll res = 1; // Initialize result
// x = x % p; // Update x if it is more than or equal to p
// while (y > 0)
// {
// // If y is odd, multiply x with result
// if (y & 1)
// res = (res * x) % p;
// // y must be even now
// y = y >> 1; // y = y/2
// x = (x * x) % p;
// }
// return res;
// }
// // Returns n^(-1) mod p
// ll modInverse(ll n, ll p)
// {
// return power(n, p - 2, p);
// }
// ll nCrModPFermat(ll n,ll r, ll p)
// {
// if (n < r)
// return 0;
// if (r == 0)
// return 1;
// ll fac[n + 1];
// fac[0] = 1;
// for (int i = 1; i <= n; i++)
// fac[i] = (fac[i - 1] * i) % p;
// return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p)% p;
// }
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        ll n,k;
        cin>>n>>k;
        vl nums(n);
        for(ll i=0;i<n;i++)cin>>nums[i];
        vl dp(n,0);
        ll lst=(nums[n-1]/2);
        dp[n-1]=max(nums[n-1]-k,lst);
        ll cone=0;
        ll divby=1;
        for(ll i=n-2;i>=0;i--){
            ll maxi;
            for(int i=0;i<cone;i++){
                divby*=2;
            }
            nums[i]/=divby;
            maxi=max(nums[i]/2,nums[i]-k);
            if(maxi==nums[i]/2){
                cone++;
            }
            dp[i]=dp[i+1]+maxi;
        }
        cout<<dp[0]<<endl;

    }
    return 0;
}