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):
import heapq
n,m=map(int,input().split())
A=list(map(int,input().split()))
B=[]
for i in range(n):
    heapq.heappush(B,-A[i])
for j in range(m):
    x=heapq.heappop(B)
    if x//2==0:
        heapq.heappush(B,x//2)
    else:
        heapq.heappush(B,(x+1)//2)
print(-sum(B))

Solution (Python):
import sys
import heapq

input = sys.stdin.readline

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

A = map(int, input().split())
pq = []
heappush = heapq.heappush
for a in A:
    heappush(pq, -a)

heappushpop = heapq.heappushpop
now_t = heapq.heappop(pq)

for i in range(M):
    now_t = heapq.heappushpop(pq, -(-now_t//2))

ans = now_t + sum(pq)

print(-ans)

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

Solution (Python):
import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return((list(sys.stdin.readline()))[:-1])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def main():
    N,M = LI()
    A = [-1*int(x) for x in sys.stdin.readline().split()]


    heapq.heapify(A)

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

    return(-1 * sum(A))



if __name__ == "__main__":
    print(main())

Solution (Python):
import heapq
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
A = inpl()
q = []
for a in A:
    heapq.heappush(q,-a)
for _ in range(M):
    a = -heapq.heappop(q)
    a //= 2
    heapq.heappush(q,-a)
print(-sum(q))

Solution (Python):
import heapq
n,m = map(int,input().split())
d = [0] * m
a = list(map(int,input().split()))
s = sum(a)
for i in range(n):
  c = a[i]
  while True:
    c,p = c//2,c
    if p-c > d[0]:
      heapq.heappushpop(d,p-c)
    else:
      break
print(s-sum(d))

Solution (Python):
N,M=map(int,input().split())
A=list(map(int,input().split()))
from heapq import heappop,heappush
q=[]
for a in A:
    heappush(q,(-a,a,0))
while M>0:
    _,X,n=heappop(q)
    n+=1
    heappush(q,(-(X//2**n),X,n))
    M-=1
r=0
for _,X,n in q:
    r+=X//2**n
print(r)

Solution (Python):
import heapq
import math

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

h = []

for i in range(0, N):
    heapq.heappush(h, -A[i])

for i in range(0, M):
    v = heapq.heappop(h)
    discounted = v / 2
    heapq.heappush(h, discounted)

res = 0
for i in range(0, N):
    res = res + math.floor(-h[i])

print(res)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import heapq

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

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

print(-sum(Q))

Solution (Python):
import heapq

N, M = map(int, input().split())
a = [(-1)*int(i) for i in input().split()]
heapq.heapify(a)

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

Solution (Python):
import heapq
N, M = [int(i) for i in input().split()]
A = [-int(i) for i in input().split()]
heapq.heapify(A)
for i in range(M):
    a = heapq.heappop(A)
    a = -a//2
    heapq.heappush(A, -a)

print(-sum(A))

Solution (Python):
import heapq as hq

N, M = [int(_) for _ in input().split()]
A = []
for a in [int(_) for _ in input().split()]:
    hq.heappush(A, -a)

for _ in range(M):
    v = hq.heappop(A)
    hq.heappush(A, v / 2)
print(-sum([int(a) for a in A]))

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

for i in range(M):
    a = heapq.heappop(h)[1]//2
    heapq.heappush(h, (-a, a))

ans = 0
for i in range(N):
    ans += heapq.heappop(h)[1]

print(ans)

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):
    tmp = heapq.heappop(A)
    tmp = -tmp // 2
    heapq.heappush(A,-tmp)
print(-sum(A))

Solution (Python):

"""
Created on Sun Sep 15 20:38:23 2019

@author: Yamazaki Kenichi
"""
import heapq

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

q = []
for a in A:
    heapq.heappush(q,-a)

for i in range(M):
    tmp = heapq.heappop(q)
    tmp /= 2
    heapq.heappush(q,tmp)

ans = 0
for c in q:
    ans += int(-c)
print(ans)

Solution (Python):

import sys, heapq


def solve(N: int, M: int, A: "List[int]"):
    H = [(-a, a) for a in A]
    heapq.heapify(H)
    for i in range(M):
        mx = heapq.heappop(H)
        mx = mx[1] >> 1
        heapq.heappush(H, (-mx, mx))
    print(sum([e[1] for e in heapq.nlargest(N, H)]))
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, M, A)

if __name__ == '__main__':
    main()

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

Solution (Python):
from math import floor
from heapq import heappush, heappop
n, m = map(int, input().split())
a = []
for i in map(int, input().split()):
    heappush(a, -i)
dis = lambda x,y: x // 2**y

for _ in range(m):
    heappush(a, -dis(-heappop(a), 1))
print(-sum(a))

Solution (Python):
import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))

hq = []
for a in A:
  heapq.heappush(hq, -a)
  
for i in range(M):
  curr = -heapq.heappop(hq)
  heapq.heappush(hq, -(curr//2))
  
print(-sum(hq))

Solution (Python):
import heapq

n, m = list(map(int, input().split()))
nums = [-x for x in list(map(int, input().split()))]

heapq.heapify(nums)

for _ in range(m):
	x = heapq.heappop(nums)
	heapq.heappush(nums, ((-1 * x) // 2) * -1)

print(-sum(nums))

Solution (Python):
import heapq

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

h=[]

for i in range(n):
  heapq.heappush(h,-1*a[i])

for i in range(m):
  t=heapq.heappop(h)
  heapq.heappush(h,(t+1)//2)

print(-1*sum(h))

Solution (Python):
import heapq as hq 
n,m = map(int,input().split())
arr = list(map(int,input().split()))
arr = list(map(lambda x:x*(-1),arr))
hq.heapify(arr)
for i in range(m):
    tmp = -hq.heappop(arr)
    tmp //= 2
    hq.heappush(arr,-tmp)
print(-sum(arr))

Solution (Python):
from math import floor
import heapq
def main():
    n,m = map(int,input().split())
    a  = [ -int(x) for x in input().split()]
    heapq.heapify(a)
    for i in range(m):
        now = -heapq.heappop(a)
        now = floor(now/2)
        heapq.heappush(a,-now)
    print(-sum(a))
if __name__ == "__main__":
    main()

Solution (Python):
import heapq

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

for s in S:
	heapq.heappush(A, s * -1)
	
for _ in range(M):
	tmp = heapq.heappop(A)
	if tmp > 0:
		tmp //= 2
	else:
		tmp *= -1
		tmp //= 2
		tmp *= -1
	heapq.heappush(A, tmp)
	
print(sum(A) * -1)

Solution (Python):
from heapq import heapify,heappop,heappush
N,M = map(int,input().split())
A = list(map(lambda x:-int(x),input().split()))
heapify(A)



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



print(-sum(A))

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

N, M = map(int, input().split())
A = [-int(i) for i in input().split()]
heapify(A)
for i in range(M):
  x = -heappop(A)
  x //= 2
  heappush(A,-x)
ans = (-sum(A))
print(ans)

Solution (Python):
from heapq import heappush, heappop
n,m=map(int,input().split())
a=list(map(int,input().split()))
h=[]
for x in a:
    heappush(h,-x)
for _ in [0]*m:
    k=-heappop(h)
    heappush(h,-(k//2))
ans=0
for _ in [0]*n:
    ans+=-heappop(h)
print(ans)

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

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

for i in range(n):
    ans -= int(a[i])
print(ans)

Solution (Python):
import heapq
n, m = map(int, input().split())
aa = list(map(int, input().split()))
h = []
for a in aa:
    heapq.heappush(h, -a)
for mm in range(m):
    heapq.heappush(h, heapq.heappop(h) / 2)

s = sum([int(-v) for v in h])
print(s)

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

Solution (Python):

import sys
from heapq import heappop, heappush

sys.setrecursionlimit(10 ** 7)


def solve(N: int, M: int, A: "List[int]"):
    pool = []
    for a in A:
        heappush(pool, -a)
    for _ in range(M):
        v = heappop(pool)
        heappush(pool, v / 2)
    result = 0
    for i in pool:
        result += int(i)
    print(-result)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, M, A)

if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

import heapq
from math import floor, ceil

def main():
    n, m = LI()
    a_s = LI()
    minus_as = [-i for i in a_s]
    heapq.heapify(minus_as)
    ans = 0
    for i in range(m):
        v = heapq.heappop(minus_as)
        v = ceil(v / 2)
        heapq.heappush(minus_as, v)
    print(-1 * int(sum(minus_as)))





if __name__ == '__main__':
    main()

Solution (Python):
from collections import *
import sys
inp = raw_input

def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]


N, M = nl()
A = nl()

from heapq import *

pq = []
for a in A:
    heappush(pq, -a)

for _ in range(M):
    v = heappop(pq)
    a = -v
    heappush(pq, -(a//2))

tot = 0
for _ in range(N):
    v = heappop(pq)
    tot += -v
print(tot)

Solution (Python):
import heapq
N,M=map(int,input().split())
a=list(map(int,input().split()))

A=[]
for i in range(N):
    A.append(a[i]*(-1))
heapq.heapify(A)

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

Solution (Python):
import heapq
import math

N,M=map(int,input().split())
h=[]

for i in input().split():
	heapq.heappush(h, -int(i))

for i in range(M):
	t=heapq.heappop(h)
	heapq.heappush(h, math.ceil(t/2))

print(-sum(h))

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

for _ in range(M):
    b = heapq.heappop(A)[1]
    b = b // 2
    heapq.heappush(A, (-b, b))

ans = 0
for i in range(N):
    ans += A[i][1]
print(ans)

Solution (Python):
from heapq import heappush, heappop

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

hq = []
for a in A:
  heappush(hq, -a)
for i in range(M):
  price = heappop(hq)
  heappush(hq, -(-price//2))
print(-sum(hq))

Solution (Python):
import sys
from heapq import heappop as hpp, heappush as hp
readline = sys.stdin.readline
N, M = map(int, readline().split())
A = list(map(int, readline().split()))
mA = [(-a, -a, 0) for a in A]
mA.sort()
for _ in range(M):
  k, j, l = hpp(mA)
  hp(mA, (-(-j//pow(2, l+1)), j, l+1))
print(-sum(ai[0] for ai in mA))

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

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

if __name__ == '__main__':
    main()

Solution (Python):
import heapq
n,m=map(int,input().split())
a=[]
for i in input().split():
    heapq.heappush(a, -int(i))

for _ in range(m):
    x=-heapq.heappop(a)//2
    
    heapq.heappush(a, -x)

print(-sum(a))

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 heapq
n, m = [ int(v) for v in input().split() ]
a_list = [ -int(v) for v in input().split() ]
a_list = sorted(a_list)

for i in range(m):
    b = heapq.heappop(a_list)
    b = -b
    b //= 2
    heapq.heappush(a_list,-b)

print(-sum(a_list))

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

Solution (Python):
import heapq

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

q = []

for v in a:
    heapq.heappush(q, -v)

for i in range(m):
    v = heapq.heappop(q)
    v = (-v) // 2
    heapq.heappush(q, -v)

ans = 0
for i in range(len(q)):
    ans -= q[i]

print(ans)

Solution (Python):

import heapq
N,K=  list(map(int,input().split(" ")))
nums = list(map(int,input().split(" ")))
nums = list(map(lambda x:-x , nums))
heapq.heapify(nums)
for _ in range(K):
    temp = heapq.heappop(nums)
    temp *= -1
    temp //= 2
    temp *= -1
    heapq.heappush(nums,temp)
nums = list(map(lambda x:-x , nums))
print(sum(nums))

Solution (Python):
import heapq
N, M = map(int, input().split())
A = [[-int(x), i] for i, x in enumerate(input().split())]
heapq.heapify(A)
for _ in range(M):
  a, i = heapq.heappop(A)
  _a = (-a) // 2
  heapq.heappush(A, [-_a, i])
print(sum([-a[0] for a in A]))

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

for i in range(M):
    a = heapq.heappop(A)
    if a == 0:
        heapq.heappush(A, 0)
    else:
        heapq.heappush(A, a/2)
A = [int(-A[i]) for i in range(N)]
print(sum(A))

Solution (Python):

import sys
sys.setrecursionlimit(12345678)
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop, heapify


def main():
    n, m = map(int, input().split())
    al = list(map(int, input().split()))
    for i in range(len(al)):
        al[i] = -al[i]

    heapify(al)

    for _ in range(m):
        val = heappop(al)
        val *= -1
        val //= 2
        val *= -1

        heappush(al, val)

    print(-sum(al))


if __name__ == '__main__':
    main()

Solution (Python):
import heapq


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

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

Q = []


for i in range(N):

    heapq.heappush(Q,-1 * A[i])


for i in range(M):

    now = heapq.heappop(Q)
    now *= -1

    heapq.heappush(Q,-1 * (now // 2))

ans = 0

for i in Q:
    ans -= i
print (ans)

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

for i in range(m):
    x=heapq.heappop(a)
    x=((-1)*x)//2
    heapq.heappush(a, (-1)*x)
ans=0
for i in range(n):
    y=heapq.heappop(a)
    ans+=(-1)*y
print(ans)

Solution (Python):
import heapq as hq

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

p=[]
for i in range(N):
  hq.heappush(p,-A[i])


for i in range(M):
  tmp=-hq.heappop(p)//2
  hq.heappush(p,-tmp)

p=list(map(lambda x:-x, p))
print(sum(p))

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

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, A):
    q = [-v for v in A]
    heapq.heapify(q)
    for _ in range(M):
        v = -heapq.heappop(q)
        v /= 2
        heapq.heappush(q, -v)
    
    return -sum(map(int, q))


def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M, A))


if __name__ == '__main__':
    main()

Solution (Python):
import heapq
import math

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

negA = list(map(lambda x: -x, A))

heapq.heapify(negA)

for _ in range(M):
    nedan = -heapq.heappop(negA)
    nedan = nedan // 2
    heapq.heappush(negA, -nedan)

print(-sum(negA))

Solution (Python):
from heapq import heappush, heappop
import queue
import re
import math
import functools

def s_raw():
    return input().rstrip("\r")

def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return list(map(int, ss_raw()))


INF = 1 << 29


def make1d_arr(n, val=INF):
    return [val for i in range(n)]


def make2d_arr(h, w, val=INF):
    return [[val for i in range(w)]for i in range(h)]


def gcd(a, b):
    if(b == 0):
        return a
    return gcd(b, a % b)


def BFord(n,es):
    v_cost = [INF]*n
    v_cost[0] = 0
    for v in range(n*2):
        for e in es:
            frm = e[0]
            to = e[1]
            if v_cost[to] > v_cost[frm]+e[2]:
                v_cost[to] = v_cost[frm]+e[2]
                if v >= n:
                    v_cost[to] = -INF
        if v == n-1:
            prev = v_cost[:]
    v_cost = [-INF if prev[idx]!=v_cost[idx] else v_cost[idx] for idx in range(n)]
    return v_cost
    

def main():
    N,M = ints_raw()
    As = ints_raw()
    As = [-a for a in As]
    As.sort()
    for i in range(M):
        a = heappop(As)
        heappush(As,-((-a)//2))
    return -sum(As)

    


if __name__ == "__main__":
    print(main())

Solution (Python):
import heapq

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

h = []
for i in range(n):
    heapq.heappush(h, -a[i])

for i in range(m):
    b = -heapq.heappop(h)
    c = b // 2
    heapq.heappush(h, -c)

print(-sum(h))

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))

a_new = []
for _a in a:
    a_new.append(-1 * _a)

a = sorted(a_new)
import heapq
heapq.heapify(a)



for i in range(k):
    tmp = heapq.heappop(a)
    
    tmp = tmp / 2
    heapq.heappush(a, tmp)
    

ans = 0
for i in range(n):
    ans += int(a[i] * -1)
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()
  l=LI()

  q=[]
  for x in l:
    heapq.heappush(q,-x)

  for _ in range(m):
    x=-heapq.heappop(q)
    heapq.heappush(q,-(x//2))

  return -sum(q)


print(main())

Solution (Python):
N,M = map(int, input().split())
As = list(map(int, input().split()))
import heapq
q = []
heapq.heapify(q)
for a in As:
    heapq.heappush(q,-a)
for i in range(M):
    a = heapq.heappop(q)
    a = (-a)//2*-1
    
    heapq.heappush(q,a)

print(-1*sum(list(q)))

Solution (Python):
import heapq
N,M = [int(x) for x in input().split()]
A = [-int(x) for x in input().split()]
heapq.heapify(A)
for i in range(M):
    x = heapq.heappop(A)
    x = -x//2
    heapq.heappush(A,-x)
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 i in range(m):
    mx=heapq.heappop(a)*-1
    heapq.heappush(a,mx//2*-1)
print(sum(a)*-1)

Solution (Python):


import heapq
def main():
    N, M = map( int, input().split())
    A = list( map( lambda x:-x, map( int, input().split())))
    heapq.heapify(A)
    for _ in range(M):
        a = heapq.heappop(A)
        a = -((-a)//2)
        heapq.heappush(A, a)
    print( -sum(A))
if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush, heappop

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

for t in tmp:
    heappush(A, -t)

for m in range(M):
    p = -heappop(A)
    p //= 2
    heappush(A, -p)

print(-sum(A))

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

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

PQ = [-A for A in As]
heapify(PQ)

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

ans = 0
while PQ:
    A = -heappop(PQ)
    ans += int(A)

print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a_list=list(map(int,input().split()))
import heapq
A=[]
for i in a_list:
    heapq.heappush(A,-i)
for i in range(m):
    now=heapq.heappop(A)
    now=-now
    now=now//2
    now=-now
    heapq.heappush(A,now)
ans=0
for i in range(n):
    now=heapq.heappop(A)
    ans-=now
print(ans)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop, heapify
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M = MI()
    A = LI()
    for i,a in enumerate( A):
        A[i] = - a

    heapify(A)
    for _ in range(M):
        a = heappop(A)
        heappush(A,a/2)
    
    ans = 0
    for h in A:
        ans += int(-h)
    print(ans)
if __name__ == '__main__':
    main()

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


heapq.heapify(A)  



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

print(-sum(A))

Solution (Python):
from heapq import heappop, heappush

def getlist():
	return list(map(int, input().split()))

N, M = getlist()
A = getlist()

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

for i in range(M):
	val = heappop(Q)
	if val % 2 == 0:
		heappush(Q, val // 2)
	else:
		heappush(Q, (val + 1) // 2)

print(-sum(Q))

Solution (Python):
import math
import heapq
from bisect import bisect_right, bisect_left
from collections import defaultdict, Counter
import itertools
import sys
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7
INF = float("inf")


def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    aa = []
    for i in range(n):
        aa.append(-a[i])
    heapq.heapify(aa)
    ans = 0
    for i in range(m):
        t = heapq.heappop(aa)
        t = math.ceil(t / 2)
        heapq.heappush(aa, t)
    print(-sum(aa))


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 m in range(M):
    a = -heapq.heappop(A)
    heapq.heappush(A, -(a//2))
print(-sum(A))

Solution (Python):
from heapq import heappush, heappop
N, M = map(int, input().split())
a = [int(i) for i in input().split()]
ls = []
ans = [0]*N
for i in range(N):
  heappush(ls, (-a[i], i))
for i in range(M):
  x, j = heappop(ls)
  x = -1*x
  heappush(ls, (-x/2,j))
  ans[j] += 1

total = 0
for i in range(N):
  total += a[i]//(2**ans[i])
print(total)

Solution (Python):

from heapq import heappop, heappush, heapify
import sys

def inpl(): return list(map(int, input().split()))

N, M = inpl()
A = inpl()
Q = [[-A[i], A[i], 0] for i in range(N)]
F = 2
heapify(Q)

for _ in range(M):
    b, a, x = heappop(Q)
    if b:
        b = a//(2**(x+1))
    heappush(Q, [-b, a, x+1])

ans = 0
for i in range(N):
    ans -= Q[i][0]

print(ans)

Solution (Python):
from heapq import *

N, M = map(int, input().split())
*A, = map(int, input().split())
minusA = [-a for a in A]
heapify(minusA)
while M:
    maxA = - heappop(minusA)
    heappush(minusA, - (maxA >> 1))
    M -= 1
print(sum(-a for a in minusA))

Solution (Python):


import heapq


def minimize_money(n, m, xs):
    pq = [-x for x in xs]
    heapq.heapify(pq)
    for _ in range(m):
        x = -heapq.heappop(pq)
        new_x = -(x // 2)
        heapq.heappush(pq, new_x)
    res = sum(-y for y in pq)
    return res


def main():
    n, m = (int(z) for z in input().split())
    xs = [int(z) for z in input().split()]
    res = minimize_money(n, m, xs)
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
import heapq as hq
N,M = map(int,input().split())
A = None
if N > 1:
	A = list(map(int,input().split()))
else:
	A = [int(input())]
A = [a*-1 for a in A]
hq.heapify(A)
for i in range(M):
	a = hq.heappop(A) * -1
	hq.heappush(A, (a//2) * -1)
print(-sum(A))

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

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

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

print(sum([int(-a) for a in A]))

Solution (Python):
from heapq import heappush, heappop
import math
N, M = map(int, input().split())
As = list(map(int, input().split()))
q = []
for a in As:
  heappush(q, -a)
for _ in range(M):
  a = heappop(q)
  heappush(q, math.ceil(a / 2))
print(-sum(q))

Solution (Python):
import heapq

def main():

    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    hq = []
    for a in A:
        heapq.heappush(hq, -a)
    for _ in range(M):
        a = heapq.heappop(hq)
        a = -a/2
        heapq.heappush(hq, -a)
    ans = 0
    for a in hq:
        ans += int(-a)
    return ans

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

Solution (Python):
from heapq import heappop, heappush
N, M = map(int, input().split())
A = list(map(int, input().split()))
H = []
for a in A:
    heappush(H, -a)

cnt = 0
while cnt < M:
    a = heappop(H)
    heappush(H, -((-a)//2))
    cnt += 1

print(-sum(H))

Solution (Python):

import sys
import heapq


def solve(N: int, M: int, A: "List[int]"):
    a_heap = []

    for a in A:
        heapq.heappush(a_heap,(-a,a))

    for i in range(M):
        item = heapq.heappop(a_heap)
        new_p = item[1] // 2
        heapq.heappush(a_heap,(-new_p,new_p))

    print(sum(map(lambda x: x[1],a_heap)))

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    A = [ int(next(tokens)) for _ in range(N) ]  
    solve(N, M, A)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
import heapq
INF = float("inf")


def solve(N: int, M: int, A: "List[int]"):
    h = []
    tot = 0
    for a in A:
        heapq.heappush(h, (-a, 0))
        tot += a
    
    for i in range(M):
        p, kaisu = heapq.heappop(h)
        tot -= -p
        p = -p // 2
        tot += p
        heapq.heappush(h, (-p, kaisu+1))
        
    print(tot)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, M, A)


if __name__ == '__main__':
    main()

Solution (Python):
def slove():
    import sys
    import heapq
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    a = list(map(int, input().rstrip('\n').split()))
    for i in range(len(a)):
        a[i] = a[i] * - 1
    heapq.heapify(a)
    for i in range(m):
        p = heapq.heappop(a)
        p /= 2
        heapq.heappush(a, p)
    t = 0
    for i in range(len(a)):
        t += int(a[i])
    print(-t)


if __name__ == '__main__':
    slove()