Problem:
 Score : 400 points    Problem Statement Takahashi is going to buy N items one by one.  The price of the i -th item he buys is A_i yen (the currency of Japan).  He has M discount tickets, and he can use any number of them when buying an item.  If Y tickets are used when buying an item priced X yen, he can get the item for \frac{X}{2^Y} (rounded down to the nearest integer) yen.  What is the minimum amount of money required to buy all the items?      Constraints  All values in input are integers.  1 \leq N, M \leq 10^5  1 \leq A_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  M  A_1  A_2  ...  A_N       Output Print the minimum amount of money required to buy all the items.        Sample Input 1 3 3
2 13 8      Sample Output 1 9  We can buy all the items for 9 yen, as follows:   Buy the 1 -st item for 2 yen without tickets.  Buy the 2 -nd item for 3 yen with 2 tickets.  Buy the 3 -rd item for 4 yen with 1 ticket.        Sample Input 2 4 4
1 9 3 5      Sample Output 2 6       Sample Input 3 1 100000
1000000000      Sample Output 3 0  We can buy the item priced 1000000000 yen for 0 yen with 100000 tickets.       Sample Input 4 10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000      Sample Output 4 9500000000

Solution (Python):
from sys import stdin

n, m = [int(x) for x in stdin.readline().rstrip().split()]
a = [int(x) for x in stdin.readline().rstrip().split()]

lb = -1
ub = 1e+09 + 3
total_money = sum(a)

while ub - lb > 1:
    mid = (lb + ub) // 2
    count = 0
    ac = a[:]
    for i in range(len(ac)):
        while ac[i] > mid:
            if ac[i] == 0:
                break
            ac[i] //= 2
            count += 1
        if count > m:
            break
    if count > m:
        lb = mid
    else:
        ub = mid
        ac.sort(reverse=True)
        if count < m:
            for i in range(m-count):
                if i >= n:
                    break
                ac[i] //= 2
        total_money = sum(ac)


print(total_money)

Solution (Python):
import heapq

n, m = map(int, input().split())
A = list(map(lambda x: -int(x), input().split()))

heapq.heapify(A)
for i in range(m):
    item = heapq.heappop(A)
    heapq.heappush(A, (-1) * (-item // 2))

print(-sum(A))

Solution (Python):
from heapq import *
N,M = map(int,input().split())
A = list(map(lambda x: -int(x),input().split()))
heapify(A)
for i in range(M):
    heappush(A,-(-heappop(A)//2))
print(-sum(A))

Solution (Python):
import heapq
N, M = map(int, input().split())
a = list(map(int, input().split()))
a = list(map(lambda x: x*(-1), a))
heapq.heapify(a)

for _ in range(M):
  X = heapq.heappop(a)
  heapq.heappush(a, X/2)

print(sum(int(-x) for x in a))

Solution (Python):
import heapq
N,M = map(int,input().split())
list_A = list(map(int,input().split()))	
list_A = list(map(lambda x: int(x)*(-1),list_A))




heapq.heapify(list_A) 
for i in range(M):
  
  target = heapq.heappop(list_A)
  
  
  '''負の要素の切り捨て除算は切り捨てがマイナスの方に
  行くため少しだけややこしい。'''
  target = (-1)*((-target) // 2)
  heapq.heappush(list_A, target)  
  

print((-1)*sum(list_A))

Solution (Python):
import heapq
N,M = map(int,input().split())
list_A = list(map(lambda x: int(x)*(-1),input().split()))	


heapq.heapify(list_A)
for i in range(M):
  
  target = heapq.heappop(list_A)
  
  
  '''負の要素の切り捨て除算は切り捨てがマイナスの方に
  行くため少しだけややこしい。'''
  heapq.heappush(list_A, (-1)*((-target) // 2))  
  

print(-sum(list_A))

Solution (Python):
from heapq import heappush,heappop
n,k=map(int,input().split())
a=list(map(int,input().split()))
q=[]
for i in a:
  heappush(q,-i)
for _ in range(k):
  i=heappop(q)
  i=-i//2
  heappush(q,-i)
print(-sum(q))

Solution (Python):
import heapq
 
N,M = map(int,input().split())
Price_List = list(map(lambda x:x*(-1),map(int,input().split())))
heapq.heapify(Price_List)
for i in range(M):
    val = heapq.heappop(Price_List)* -1 // 2 * -1
    heapq.heappush(Price_List,val)
print(-sum(Price_List))

Solution (Python):
import heapq
 
N,M = map(int,input().split())
Price_List = list(map(lambda x:x*(-1),map(int,input().split())))
heapq.heapify(Price_List)
for i in range(M):
    val = heapq.heappop(Price_List)* -1 // 2 * -1
    heapq.heappush(Price_List,val)
print(-sum(Price_List))

Solution (Python):
import bisect
 
N,M = map(int,input().split())
Price_List = list(map(int,input().split()))
Price_List.sort()
for i in range(M):
    New_Price = Price_List.pop(-1)//2
    Price_List.insert(bisect.bisect(Price_List,New_Price),New_Price)
print(sum(Price_List))

Solution (Python):
import heapq as hp
n,m=map(int,input().split())
a=[-int(x) for x in input().rstrip().split()]

hp.heapify(a)
for i in range(m):
    
    now=hp.heappop(a)
    now=-now//2
    hp.heappush(a,-now)

print(-sum(a))

Solution (Python):

import heapq


def main():
    item_no, discount_no = [int(x) for x in input().split()]
    prices = [int(x) * -1 for x in input().split()]
    heapq.heapify(prices)

    for _ in range(discount_no):
        current_max = heapq.heappop(prices)
        current_max = current_max * -1 // 2 * -1
        heapq.heappush(prices, current_max)

    print(- sum(prices))


if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect

N,M = map(int,input().split())
Ali = list(map(int,input().split()))

Ali.sort()
for i in range(M):
  a = Ali.pop(-1)
  a //= 2
  Ali.insert(bisect(Ali,a), a)

print(sum(Ali))

Solution (Python):
n, m = map(int, input().split())

A = list(map(int, input().split()))

import heapq

A = list(map(lambda x: x*(-1), A))

heapq.heapify(A)

for i in range(m):
    val = heapq.heappop(A)
    val = (-1 * val)//2 * (-1)
    heapq.heappush(A, val)

print(sum(list(map(lambda x: x*(-1), A))))

Solution (Python):
import heapq
n, m = map(int, input().split())
a = list(map(lambda x: -int(x), input().split()))
heapq.heapify(a)
num = 0
while num < m:
    maximum = -1 * heapq.heappop(a)
    maximum //= 2
    heapq.heappush(a, -maximum)
    num += 1
print(-sum(a))

Solution (Python):
import heapq
import math
n,m=map(int, input().split())
hp=list(map(lambda x:-1*int(x), input().split()))
heapq.heapify(hp)
for _ in range(m):
  item=heapq.heappop(hp)
  heapq.heappush(hp, math.ceil(item/2))
  
print(sum(hp)*-1)

Solution (Python):
n, m = map(int, input().split())
A = list(map(int, input().split()))

tmp_list = []

for i in range(n):
    tmp = A[i]
    now = tmp
    while True:
        if tmp != 0:
            tmp = tmp // (2)
            tmp_list.append(now - tmp)
            now = tmp
        else:
            break

tmp_list.sort(reverse=True)
print(sum(A) - sum(tmp_list[:m]))

Solution (Python):
import heapq
t = 1


def max(a,b):
	if a > b:
		return a
	return b
while t > 0:
	t -= 1
	
	
	
	
	
	
	
	
	
	n,m = map(int,input().split())	
	v = list(map(int,input().strip().split()))[0:n]
	for i in range(n):
		v[i] = -v[i]
	heapq.heapify(v)
	for i in range(m):
		x = heapq.heappop(v)
		x = -x
		x = x//2
		heapq.heappush(v,-x)
	ans = 0
	for i in range(n):
		ans += (-heapq.heappop(v))
	print(ans)

Solution (Python):
import heapq
NM,a=open(0).read().rstrip().split('\n')
N,M=map(int,NM.split())
A=list(map(int,a.split()))
A=[-1*i for i in A]
heapq.heapify(A)
for i in range(M):
    sample=heapq.heappop(A)
    sample=-1*sample//2
    heapq.heappush(A,-1*sample)
print(-sum(A))

Solution (Python):
import heapq
N,M=map(int,input().split())
A=list(map(lambda x: int(x)*(-1),input().split()))
heapq.heapify(A)
for x in range(M):
  t=(-1)*heapq.heappop(A)
  heapq.heappush(A,(-1)*(t//2))
print(-1*sum(A))

Solution (Python):
import heapq
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for y in a:
  b.append(y*(-1))

heapq.heapify(b)
for x in range(m):
  c=heapq.heappop(b)*(-1)
  d=(c//2)*(-1)
  heapq.heappush(b,d)
  
sum1=sum(b)*(-1)
print(sum1)

Solution (Python):
import heapq

N, M = [int(x) for x in input().split()]
A = list([int(x) * - 1 for x in input().split()])
heapq.heapify(A)

for _ in range(M):
    target = heapq.heappop(A) * -1
    heapq.heappush(A, (target // 2) * -1)

print(sum(A) * -1)

Solution (Python):
import heapq
N,M = map(int, input().split())
A = list(map(lambda x:-int(x), input().split()))
heapq.heapify(A)
for i in range(M):
    a = heapq.heappop(A)
    heapq.heappush(A,-(-a//2))
print(-sum(A))

Solution (Python):
import bisect
N,M = map(int, input().split())
A = sorted(map(int, input().split()))
for i in range(M):
    bisect.insort(A, A.pop()//2)
print(sum(A))

Solution (Python):
import heapq

N,M= map(int,input().split())
A = list(map(lambda x: int(x)*-1,input().split()))
heapq.heapify(A)
while M:
    tmp=heapq.heappop(A)*-1
    heapq.heappush(A,tmp//2*-1)
    M -=1
print(sum(A)*-1)

Solution (Python):
N,M = map(int,input().split())
A = list(map(lambda x:-int(x), input().split()))

import heapq
heapq.heapify(A)

for i in range(M):
  price = heapq.heappop(A)
  price *= -1
  price //= 2
  heapq.heappush(A, -price)

print(sum(A) * (-1))

Solution (Python):
from heapq import heappop, heappush

N,M=map(int,input().split())
A=list(map(int,input().split()))

B = []
for i in range(N):
  heappush(B,-A[i])

for i in range(M):
  a = heappop(B)
  a /= 2
  heappush(B,a)

print(sum([int(-B[i]) for i in range(N)]))

Solution (Python):
import heapq
def solve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a = list(map(lambda x: x*(-1), a))

    heapq.heapify(a)
    cnt = 0
    while cnt < m:
        x = heapq.heappop(a)
        heapq.heappush(a, -(-x//2))
        cnt += 1
        if x == 0: break

    return sum(a)*(-1)

print(solve())

Solution (Python):
from heapq import heappushpop, heapify

N, M = map(int, input().split(' '))
A = list(map(int, input().split(' ')))

heap = [-a for a in A]
heapify(heap)

for _ in range(M):
    heappushpop(heap, (-1 * heap[0] // 2) * -1)

print(-1 * sum(heap))

Solution (Python):
from heapq import heappush, heappop, heapify
N, M = map(int, input().split())
aaa = list(map(lambda x: -x , map(int, input().split())))
heapify(aaa)
for _ in range(M):
    a = heappop(aaa)
    if a < 0:
        a *= -1
        a //= 2
        a *= -1
    heappush(aaa, a)
print(-sum(aaa))

Solution (Python):
def resolve():
    import heapq
    import sys
    input = sys.stdin.readline
    _, M = [int(i) for i in input().split()]
    A = [-int(i) for i in input().split()]
    heapq.heapify(A)
    for _ in range(M):
        heapq.heappush(A, -(-heapq.heappop(A) // 2))
    print(-sum(A))

resolve()

Solution (Python):
import math
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for _ in range(M):
    x=math.floor(A.pop(N-1)/2)
    bisect.insort(A,x)
print(sum(A))

Solution (Python):
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext

def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    n, m = i_map()
    num_list = i_list()

    for i in range(n):
        num_list[i] *= -1

    heapify(num_list)

    for _ in range(m):
        pop_num = heappop(num_list) * -1
        heappush(num_list, pop_num//2 * -1)

    print(sum(num_list)*-1)

if __name__ == '__main__':
    main()

Solution (Python):
import heapq

N, M = map(int, input().split())
A = list(map(lambda x: -int(x), input().split()))

heapq.heapify(A)

for i in range(M):
    min_a = heapq.heappop(A)
    heapq.heappush(A, -(-min_a//2))

print(-sum(A))

Solution (Python):
import sys
input=sys.stdin.readline

N,M = (int(x) for x in input().rstrip('\n').split())
As = [int(x) for x in input().rstrip('\n').split()]
As = sorted(As,reverse = True)
rest = M
for _ in range(M):
  if rest == 0:
    break
  d = As[0]
  b = d//2 - d//4
  for i in range(N):
    a = As[i]
    check = 0
    if a-a//2<b:
      if rest > i:
        ad = [x//2 for x in As[:i]]
        As = As[i:]
        As.extend(ad)
        rest -= i
        check += 1
        As = sorted(As,reverse = True)
        break
      else:
        ad = [x//2 for x in As[:rest]]
        As = As[rest:]
        As.extend(ad)
        check += 1
        rest = 0
        break
    if i == N-1:
      if check == 0:
        if rest > N:
          As = [x//2 for x in As]
          rest -= N
        else:
          ad = [x//2 for x in As[:rest]]
          As = As[rest:]
          As.extend(ad)
          rest = 0
          break
print(sum(As))

Solution (Python):
n, m = map(int, input().split())
aas = list(map(int, input().split()))
import heapq
hq = []
for i in aas:
    heapq.heappush(hq,-i)
for i in range(m):
    tmp = heapq.heappop(hq)
    heapq.heappush(hq,-((-tmp)//2))
print(-sum(hq))

Solution (Python):
n, m = map(int, input().split())
aas = list(map(int, input().split()))
import heapq
hq = []
for i in aas:
    heapq.heappush(hq,-i)
for i in range(m):
    tmp = heapq.heappop(hq)
    heapq.heappush(hq,-((-tmp)//2))
print(-sum(hq))

Solution (Python):
from heapq import (
    heapify,  
    heappop,
    heappush,
    heappushpop,
    heapreplace
    )

N, M = map(int, input().split())


A = [-i for i in map(int,input().split())]
heapify(A)

for _ in range(M):
    s = -heappop(A)
    s //= 2
    heappush(A, -s)

print(-sum(A))

Solution (Python):
n,k=list(map(int,input().split()))
m=list(map(int,input().split()))
for i in range(n):
    m[i]*=(-1)

import heapq
heapq.heapify(m)
for i in range(k):
    p=heapq.heappop(m)
    heapq.heappush(m,p/2)
s=0
for i in range(n):
    s+=int(abs(m[i]))
print(s)

Solution (Python):
from collections import defaultdict
from collections import deque
from collections import OrderedDict
import itertools
import heapq
from sys import stdin
input = stdin.readline


class MaxHeapObj(object):
  def __init__(self, val):
    self.val = val

  def __lt__(self, other):
    return self.val > other.val

  def __eq__(self, other):
    return self.val == other.val

  def __str__(self):
    return str(self.val)


class MinHeap(object):
  def __init__(self, L=None):
    if L is None:
      self.h = []
    else:
      heapq.heapify(L)
      self.h = L

  def heappush(self, x):
    heapq.heappush(self.h, x)

  def heappop(self):
    return heapq.heappop(self.h)

  def __getitem__(self, i):
    return self.h[i]

  def __len__(self):
    return len(self.h)


class MaxHeap(MinHeap):
  def __init__(self, L=None):
    super(MaxHeap, self).__init__(list(map(lambda x: MaxHeapObj(x), L)))

  def heappush(self, x):
    heapq.heappush(self.h, MaxHeapObj(x))

  def heappop(self):
    return heapq.heappop(self.h).val

  def __getitem__(self, i):
    return self.h[i].val


def main():
  N, M = list(map(int, input().split()))
  A = list(map(int, input().split()))

  PQ = MaxHeap(A)

  while M:
    now = PQ.heappop()
    PQ.heappush(int(now/2))
    M -= 1

  sum_ = 0
  for x in PQ.h:
    sum_ += x.val
  print(sum_)


if(__name__ == '__main__'):
  main()

Solution (Python):


import bisect





def solve(N, M, As):
    prices = sorted(As, reverse=True) + [0]
    halfed_idx = []
    n = 0
    idx = 0
    for _ in range(M):
        if len(halfed_idx) == 0:
            prices[n] //= 2
            halfed_idx.append(n)
            n += 1
        else:
            if prices[n] > prices[halfed_idx[idx]]:
                prices[n] //= 2
                halfed_idx.append(n)
                n += 1
            else:
                prices[halfed_idx[idx]] //= 2
                halfed_idx.append(halfed_idx[idx])
                idx += 1
    print(sum(prices))


def solve2(N, M, As):
    """later (ave 2.3 second)"""
    As.sort()
    for i in range(M):
        p = As.pop() // 2
        As.insert(bisect.bisect_right(As, p), p)
    print(sum(As))


if __name__ == '__main__':
    N, M = map(int, input().split())
    As = [int(i) for i in input().split()]

    
    
    
    solve(N, M, As)

Solution (Python):
def resolve():
    N, M = list(map(int, input().split()))
    A = list(map(lambda x: -int(x), input().split()))
    import heapq
    heapq.heapify(A)
    for i in range(M):
        v = heapq.heappop(A)
        heapq.heappush(A, v/2)
    import math
    A = list(map(lambda x: math.floor(-x), A))
    print(sum(A))
    


if '__main__' == __name__:
    resolve()

Solution (Python):
from heapq import heappush, heappop, heapify

def neg_int(n):
    return -int(n)
    
N, M = map(int, input().split())
a_list = list(map(neg_int, input().split()))
heapify(a_list)
for _ in range(M):
    a = -heappop(a_list)
    a //= 2
    heappush(a_list, -a)
print(-sum(a_list))

Solution (Python):
import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
for i in range(N):
    A[i] = -A[i]
heapq.heapify(A)

for i in range(M):
    trgt = -heapq.heappop(A)//2
    heapq.heappush(A,-trgt)
print(-sum(A))

Solution (Python):
N,M=map(int,input().split())
A=list(map(lambda x: -int(x),input().split()))
import heapq
heapq.heapify(A)
for _ in range(M):
  a = heapq.heappop(A)
  a /= 2
  heapq.heappush(A,a)
ans = 0
for a in A:
  ans += int((-1)*a)
print(ans)

Solution (Python):
import heapq
import sys
from io import StringIO
import unittest

n, m = map(int, input().split())
a = list(map(lambda x: int(x) * (-1), input().split()))
heapq.heapify(a)

for _ in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1) * (-tmp_min // 2))
print(-sum(a))

Solution (Python):

import heapq

n, m = map(int, input().split())

a = [int(i) * -1 for i in input().split()]

heapq.heapify(a)

for i in range(m):
    minPrice = heapq.heappop(a)
    
    minPrice = -(abs(minPrice) // 2)
    heapq.heappush(a, minPrice)

print(-sum(a))

Solution (Python):

import heapq

n, m = map(int, input().split())

a = [int(i) * -1 for i in input().split()]

heapq.heapify(a)

for i in range(m):
    minPrice = heapq.heappop(a)
    
    minPrice = -(abs(minPrice) // 2)
    heapq.heappush(a, minPrice)

sum = 0
for i in a:
    sum += -i

print(sum)

Solution (Python):
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
c=0
while c<m:
  d=a[0]/2
  for i in range(n):
    if a[0]==0:
      c=m
    if a[i]>d:
      a[i]//=2
      c+=1
      if c==m:
        break  
    else:
      a.sort(reverse=True)
      break
print(sum(a))

Solution (Python):
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: x*(-1), A))
heapq.heapify(A)

for _ in range(M):
    a = ((heapq.heappop(A)*-1)//2)*-1
    if a != 0:
        heapq.heappush(A, a)

    if len(A) == 0:
        break

print(sum(A)*-1)

Solution (Python):

import heapq
n, m = map(int, input().split())
a= list(map(lambda x: int(x) * (- 1), input().split()))
heapq.heapify(a)  

for i in range(m):
    tmp=heapq.heappop(a) * -1  
    tmp //= 2
    heapq.heappush(a, -1 * tmp) 
print(sum(a)*-1)

Solution (Python):
import heapq
n, m = map(int, input().split())
lst = list(map(lambda x: -(int(x)), input().split()))
heapq.heapify(lst)
for i in range(m):
  a = heapq.heappop(lst)
  heapq.heappush(lst, a / 2)
res = 0
for i in range(n):
  res += int(-lst[i])
print(res)

Solution (Python):
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: x*(-1), A))

heapq.heapify(A)

for _ in range(M):
  Max = heapq.heappop(A) * -1
  heapq.heappush(A, Max//2 * -1)
  
ans = 0
for i in range(N):
  ans += -1 * A[i]
  
print(ans)

Solution (Python):
import heapq as hq
n,m=input().split()
hq.heapify(a:=[-int(x) for x in input().split()])
for i in range(int(m)):hq.heappush(a,-(-hq.heappop(a)//2))
print(-sum(a))

Solution (Python):
import heapq as hq
n,m=input().split()
hq.heapify(a:=[-int(x) for x in input().split()])
for i in range(int(m)):hq.heappush(a,-(v:=-hq.heappop(a)//2))
print(-sum(a))

Solution (Python):
import bisect
import math

n,m = map(int,input().split())
a = list(map(int,input().split()))

a.sort()

ans = sum(a)
for i in range(m):
    tmp = a.pop()
    ans -= tmp
    cost = math.floor(tmp/2)
    ans += cost
    idx = bisect.bisect_left(a,cost)
    a.insert(idx,cost)

print(ans)

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)







import math
class segtree:
    def __init__(self, n, init_val = None, init = 0):
        self.n = n
        self.init_val = init_val
        self.init = init
        self.k = math.ceil(math.log2(n))

        try:init_val[0]
        except:raise ValueError('init_val should be list')

        self.bins = [self.init] * (1<<(self.k+1))
        for idx, i in enumerate(range(1<<self.k, 1<<(self.k+1))):
            if len(self.init_val)>idx:
                self.bins[i] = init_val[idx]

        self.caliculate()

    def compare(self, l, r):
        
        
        return max(l, r, key = lambda x:x[0])

    def caliculate(self):
        k = self.k
        while k:
            for i in range(1<<k, 1<<(k+1)):
                if not i%2:
                    self.bins[i//2] = self.compare(self.bins[i], self.bins[i+1])
                else:continue
            k -= 1

    def update(self, idx, val):
        '''idx : 0-started index'''
        k = (1<<self.k) + idx
        self.bins[k] = val
        while k>1:
            self.bins[k // 2] = self.compare(self.bins[k // 2 * 2], self.bins[k // 2 * 2 + 1])
            k = k//2


    def eval(self, l, r):
        ret = self.init
        l = (1 << self.k) + l
        r = (1 << self.k) + r
        
        while True:
            
            if r - l == 1:
                ret = self.compare(ret, self.bins[l])
                ret = self.compare(ret, self.bins[r])
                break
            elif l == r:
                ret = self.compare(ret, self.bins[l])
                break
            else:
                done = False
                if l % 2:
                    ret = self.compare(ret, self.bins[l])
                    l += 1
                    done = True
                if not r % 2:
                    ret = self.compare(ret, self.bins[r])
                    r -= 1
                    done = True
                if not done:
                    l = l // 2
                    r = r // 2
        
        return ret

    def value(self, ind):
        return self.bins[(1<<self.k) + ind]


def run():
    N,M = map(int, sysread().split())
    A = list(map(int, sysread().split()))
    A_with_idx = [(a, i) for i, a in enumerate(A)]
    st = segtree(len(A_with_idx), init_val = A_with_idx, init = (0, -1))
    for i in range(M):
        a, idx = st.bins[1]
        st.update(idx, (a // 2, idx))

    ret = 0
    for i in range(N):
        ret += st.value(i)[0]
    print(ret)



if __name__ == "__main__":
    run()

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)







import math
class segtree:
    def __init__(self, n, init_val = None, init = 0):
        self.n = n
        self.init_val = init_val
        self.init = init
        self.k = math.ceil(math.log2(n))

        try:init_val[0]
        except:raise ValueError('init_val should be list')

        self.bins = [self.init] * (1<<(self.k+1))
        for idx, i in enumerate(range(1<<self.k, 1<<(self.k+1))):
            if len(self.init_val)>idx:
                self.bins[i] = init_val[idx]

        self.caliculate()

    def compare(self, l, r):
        
        
        return max(l, r, key = lambda x:x[0])

    def caliculate(self):
        k = self.k
        while k:
            for i in range(1<<k, 1<<(k+1)):
                if not i%2:
                    self.bins[i//2] = self.compare(self.bins[i], self.bins[i+1])
                else:continue
            k -= 1

    def update(self, idx, val):
        '''idx : 0-started index'''
        k = (1<<self.k) + idx
        self.bins[k] = val
        while k>1:
            self.bins[k // 2] = self.compare(self.bins[k // 2 * 2], self.bins[k // 2 * 2 + 1])
            k = k//2


    def eval(self, l, r):
        ret = self.init
        l = (1 << self.k) + l
        r = (1 << self.k) + r
        
        while True:
            
            if r - l == 1:
                ret = self.compare(ret, self.bins[l])
                ret = self.compare(ret, self.bins[r])
                break
            elif l == r:
                ret = self.compare(ret, self.bins[l])
                break
            else:
                done = False
                if l % 2:
                    ret = self.compare(ret, self.bins[l])
                    l += 1
                    done = True
                if not r % 2:
                    ret = self.compare(ret, self.bins[r])
                    r -= 1
                    done = True
                if not done:
                    l = l // 2
                    r = r // 2
        
        return ret

    def value(self, ind):
        return self.bins[(1<<self.k) + ind]


def run():
    N,M = map(int, sysread().split())
    A = list(map(int, sysread().split()))
    A_with_idx = [(a, i) for i, a in enumerate(A)]
    st = segtree(len(A_with_idx), init_val = A_with_idx, init = (0, -1))
    for i in range(M):
        a, idx = st.bins[1]
        st.update(idx, (a // 2, idx))

    ret = 0
    for i in range(N):
        ret += st.value(i)[0]
    print(ret)



if __name__ == "__main__":
    run()