Untitled
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; }