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 heapq import heapify, heappop, heappush


def negative(str):
    return -1 * int(str)


def main():
    N, M = map(int, input().split(" "))
    A = list(map(negative, input().split(" ")))
    heapify(A)
    while M > 0:
        x = heappop(A)
        heappush(A, -1 * (-1 * x // 2))
        M -= 1
    print(sum(A) * -1)


if __name__ == '__main__':
    main()

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
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 list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    a = LI()
    q = []
    for c in a:
        heapq.heappush(q,-c)
    for i in range(m):
        t = -heapq.heappop(q)
        heapq.heappush(q,-(t//2))

    return -sum(q)


print(main())

Solution (Python):

from heapq import heapify, heappop, heappush

pop_max, push_max = lambda heap: -heappop(heap), lambda heap, x: heappush(heap, -x)


def main():
    N, M = map(int, input().split())
    A = [-i for i in map(int, input().split())]
    heapify(A)
    for _ in range(M):
        x = pop_max(A)
        push_max(A, x // 2)
    ans = -sum(A)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import heapq

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

Solution (Python):
import heapq

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A = [-1 * i for i in A]

    heapq.heapify(A)

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


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


if __name__ == "__main__":
    main()

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


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 = list(map(int, input().split()))
a = list(map(lambda x: x*(-1), a))
heapq.heapify(a)

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

print(sum(a) * -1)

Solution (Python):
from _collections import deque


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)


def good(ub):
    cnt = 0
    for a in A:
        base = 1
        while (a // base) > ub:
            base *= 2
            cnt += 1
            if cnt > M:
                return False
    return True


import numpy
import scipy
from collections import deque


"""
need to consider the case that ticket is not enough to lower everything
"""
N = gi()
M = gi()
A = [0] * N

for i in range(N):
    A[i] = gi()

A.sort()
low = 0
high = A[N - 1]

while low < high:
    mid = (low + high) // 2
    if (good(mid)):
        high = mid
    else:
        low = mid + 1

after = []
remains = M
for a in A:
    base = 1
    while a // base > low:
        base *= 2
        remains -= 1

    after.append(a // base)

after.sort()

ans = 0
for i in range(N - 1, -1, -1):
    if remains:
        remains -= 1
        ans += after[i] // 2
    else:
        ans += after[i]

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
A=list(map(lambda x : int(x)*(-1),input().split()))
import heapq
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 = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: -1 * x, A))

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

Solution (Python):


import heapq

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

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





print(sum(A)*-1)

Solution (Python):
import heapq
def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    for i,aa in enumerate(a):
        a[i] = -1 * aa
    heapq.heapify(a)
    for i in range(m):
        tmp = heapq.heappop(a) * (-1) // 2
        heapq.heappush(a,tmp * (-1))
    print(sum(a) * (-1))
if __name__=='__main__':
    main()

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

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def main():
    N, M = LI()
    A = LI()
    total = sum(A)
    discount = []
    for a in A:
        while a > 0:
            disc = (a+1)//2
            discount.append(disc)
            a -= disc
    discount = sorted(discount)[::-1]
    discount = discount[:M]
    print(total - sum(discount))
main()

Solution (Python):
import heapq
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 = list(map(int,input().split()))
for i in range(N):
    A[i]*=-1

heapq.heapify(A)
for i in range(M):
    a=heapq.heappop(A)
    heapq.heappush(A,int(a/2))

print(sum(A)*-1)

Solution (Python):

import heapq

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

heapq.heapify(A)

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

print(-sum(A))

Solution (Python):

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

A.sort()
while M != 0:
    x = bisect.bisect_left(A,A[-1]//2)
    if N-x <= M:
        M -= N-x
        for i in range(x,N):
            A[i] = A[i]//2
        A.sort()
    else:
        for i in range(N-M,N):
            A[i] = A[i]//2
        M = 0
        A.sort()

print(sum(A))

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

A.sort()
while M != 0:
    x = bisect.bisect_left(A,A[-1]/2)
    if N-x <= M:
        M -= N-x
        for i in range(x,N):
            A[i] = A[i]/2
        A.sort()
    else:
        for i in range(N-M,N):
            A[i] = A[i]/2
        M = 0
        A.sort()

print(sum(map(int,A)))

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

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):
    b = heapq.heappop(A) * (-1)
    heapq.heappush(A, (b // 2) * (-1))
    

print(sum(A) * -1)

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

A.sort()
l = -1
r = A[-1] + 1


while r - l > 1:
    m = (r + l) // 2
    mc = 0
    a = 0
    for i in range(N):
        s = A[i]
        while m < s:
            s //= 2
            mc += 1
        a += s
    if mc <= M:
        r = m
        ans = a - (M - mc) * ((m // 2) + m % 2)
    else:
        l = m 
            
print(ans)

Solution (Python):


import math
import sys
import heapq
import fractions
L = list(map(int, input().split()))
A = list(map(int, input().split()))
A = [n*(-1) for n in A]
heapq.heapify(A)
for _ in range(L[1]):
    mx = heapq.heappop(A)*(-1)
    heapq.heappush(A, (mx//2)*(-1))

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

Solution (Python):
import heapq


n, m = [int(_) for _ in input().split()]
a_l = [(-1) * int(_) for _ in input().split()]



ans = 0
heapq.heapify(a_l)
for i in range(m):
    tmp = (-1) * heapq.heappop(a_l)
    heapq.heappush(a_l, (-1) * (tmp // 2))
    
for i in range(len(a_l)):
    ans -= a_l[i]
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)

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

print(sum(A) * -1)

Solution (Python):
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
neg_A = []
for a in A:
    neg_A.append(-a)
heapq.heapify(neg_A)

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

print(sum(neg_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 _ in range(m):
    p = heapq.heappop(a)
    heapq.heappush(a,(-1)*(-p//2))

print(-sum(a))

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):
    heapq.heapreplace(A, int(A[0]/2))
print(-sum(A))

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

heapq.heapify(A)
for _ in range(M):

    a = heapq.heappop(A)
    heapq.heappush(A, int(a/2))
print(-sum(A))

Solution (Python):
import math
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_max = heapq.heappop(a)
    heapq.heappush(a,-(-a_max//2))
print(-sum(a))

Solution (Python):
import heapq

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

B = []

for i in A:
    B.append(-i)

heapq.heapify(B)

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

print(-sum(B))

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

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

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

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

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y
def primes(n):
    P = [2]
    for L in range(3, n):
        isP = True
        for L2 in P:
            isP = isP and L%L2
            if not isP: break
        if isP: P.append(L)
    return P


N,M=LI()
As = LI()
Bs = list(map(lambda x: -x, As))
heapq.heapify(Bs)

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

print(-sum(Bs))

Solution (Python):
N, M = map(int, input().split())
As = list(map(int, input().split()))
ks = []
for a in As:
    ks.append(len(bin(a))-2)
K=100
d = [0]*K
for k in ks:
    d[k] += 1
s = 0
ss = 0
ri = 0
for i in range(K):
    i = K-i-1
    s += d[i]
    ss += s
    if ss >= M:
        ri = i
        break
Bs = []
qs = 0
for a in As[::-1]:
    q=max(0, len(bin(a))-2-ri)
    qs += q
    Bs.append(a//(2**q))
Bs.sort()
r = 0
c = 0
for b in Bs[::-1]:
    if c < M-qs:
        b = b//2
    c += 1
    r += b
print(r)

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

Solution (Python):
from heapq import heappush, heappop

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

for a in A:
    heappush(q, -a)

for _ in range(M):
    item = (-1 * heappop(q)) // 2
    heappush(q, -1 * item)

print(-1 * sum(q))

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):
    ma=heapq.heappop(a)
    heapq.heappush(a,(-1)*((-ma)//2))
print(-sum(a))

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

A = [a * (-1) for a in A]
import heapq
heapq.heapify(A)

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

print(abs(sum(A)))

Solution (Python):
import heapq

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

cnt = 0
while cnt < M:
  a = heapq.heappop(A)
  heapq.heappush(A,-((-a)//2))
  cnt += 1
print(-sum(A))

Solution (Python):
import heapq
from sys import stdin
n,m = map(int,stdin.readline().split())
*l, = map(lambda x:-int(x),stdin.readline().split())
heapq.heapify(l)
for i in [0]*m:
  a=heapq.heappop(l)
  heapq.heappush(l, -(-a//2))
print(-(sum(l)))

Solution (Python):
import collections
import math
import operator as op
from functools import reduce
import numpy as np
import math
import bisect
import heapq


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


def get_inputs(cast_func=int):
    return list(map(cast_func, input().split()))


def get_input(cast_func=int):
    return cast_func(input())


def main():
    N, M = get_inputs()
    A = get_inputs()

    max_heap = [-a for a in A]
    heapq.heapify(max_heap)
    while M > 0:
        a_max = -heapq.heappop(max_heap)
        a_max //= 2
        heapq.heappush(max_heap, -a_max)
        M -= 1

    ans = -sum(max_heap)
    print(ans)


if __name__ == '__main__':
    main()

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

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

print(-sum(a))

Solution (Python):
import heapq

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

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

print(-sum(a))

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

heapq.heapify(Lh)
for _ in range(m):
    x=heapq.heappop(Lh)
    heapq.heappush(Lh,(x+1)//2)
print(sum(Lh)*(-1))

Solution (Python):
import heapq
N, M = map(int, input().strip().split())
A = list(map(lambda x: int(x)*(-1), input().strip().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 math
import heapq

N,M = map(int,input().split())
A = [0]*N
A = list(map(lambda x: int(x)*(-1),input().split()))
if (N == 1):
    print((-1 * A[0])//(2**M))
else:
    """
    while (M != 0):
        A.sort(reverse=True)
        y = min(math.floor(log2(A[0]/A[1])+1),M)
        A[0] //= 2**y
        M -= y
    """
    """
    A.sort(reverse=True)
    for i in range(N):
        y = min(A[i] // 2,M)
        A[i] //= 2**y
        M -= y
        if (M <= 0):
            break
    """
    heapq.heapify(A)

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

    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 _ 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 = list(map(lambda x: -int(x),input().split()))
heapq.heapify(a)
for _ in range(m):
    tmp = (-heapq.heappop(a)) // 2
    heapq.heappush(a, -tmp)
print(-sum(a))

Solution (Python):
import heapq

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

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

heapq.heapify(A)

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

Solution (Python):

import heapq

class PriorytyQueue(object):

    def __init__(self, arr, target='min'):
        self.arr = arr
        self.target = target
        self._heapify()
    
    def _heapify(self):
        if self.target == 'max':
            self.arr = list(map(lambda x:x*(-1), self.arr))
        heapq.heapify(self.arr)
    
    def push(self, x):
        if self.target == 'max':
            x *= -1
        heapq.heappush(self.arr, x)

    def pop(self):
        res = heapq.heappop(self.arr)
        if self.target == 'max':
            return res*(-1)
        else:
            return res
    
    def get_arr(self):
        if self.target == 'max':
            return list(map(lambda x:x*(-1), self.arr))
        else:
            return self.arr
    
    def is_empty(self):
        return len(self.arr) == 0

N, M = map(int, input().split())
A = list(map(int, input().split()))
pq = PriorytyQueue(A, target='max')

for i in range(M):
    max_value = pq.pop()
    pq.push(max_value//2)

print(sum(pq.get_arr()))

Solution (Python):
N,M = map(int,input().split())
import numpy as np
A = list(map(int,input().split()))
A.sort(reverse = True)
B = list(map(int,np.floor(np.log2(np.array(A)))))
BB = B
C = [0]*len(A)
MM = M
for i in range(max(B),-1,-1):
  k = BB.count(i)
  if MM < k:
    break
  else:
    MM -= k
    for j in range(k):
      C[j]+=1
      BB[j]-=1

for i in range(N):
  if C[i]==0:
    break
  else:
    A[i] = A[i]//2**C[i]

A.sort(reverse = True)
for i in range(min(MM,len(A))):
  A[i] = A[i]//2

print(sum(A))

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from heapq import heappush,heappop,heapify
def resolve():
    n,m=map(int,input().split())
    A=list(map(lambda x:-int(x),input().split()))
    heapify(A)
    for _ in range(m):
        x=-heappop(A)
        x//=2
        heappush(A,-x)

    print(-sum(A))
resolve()

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

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


if __name__ == '__main__':
    main()

Solution (Python):
import heapq

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

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

heapq.heapify(A)

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

ans = 0

for i in range(N):
    x = heapq.heappop(A)
    ans += int(-x)

print(ans)

Solution (Python):
import heapq  

N,M = list(map(int, input().split()))
A = list(map(int, input().split()))
for i in range(len(A)):
  A[i] = A[i] * (-1)

heapq.heapify(A)  

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

Solution (Python):
import heapq  

N,M = list(map(int, input().split()))
A = list(map(int, input().split()))
for i in range(len(A)):
  A[i] = A[i] * (-1)

heapq.heapify(A)  

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

Solution (Python):

import heapq

N, M = [int(x) for x in input().split(" ")]

prices = [-int(x) for x in input().split(" ")]

heapq.heapify(prices)

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

total = 0
for x in prices:
    total += -x

print(total)

Solution (Python):

import sys
input = sys.stdin.readline

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

from heapq import heappush, heappop, heapify

heapify(a)
for i in range(m):
    tmp_min = (-1)*heappop(a)//2*(-1)
    heappush(a,tmp_min)

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

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

Solution (Python):
import heapq


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

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

    print(-sum(a_list))


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) * a[i]

heapq.heapify(a)

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

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

print(ans)

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

hq.heapify(A)

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

print(-sum(A))

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]*(-1)

heapq.heapify(A)

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

ans = 0
for a in A:
    ans += int(-a)
print(ans)

Solution (Python):
import heapq

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

ma = []
for i in a:
    ma.append(-i)

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

ans = 0
for i in ma:
    ans -= i

print(ans)

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

Solution (Python):
import heapq as H

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

for _ in range(M):
    x = H.heappop(A)
    H.heappush(A, int(x / 2))

print(-sum(A))

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [-a for a in A]
heapify(A)
for _ in range(M):
    a = heappop(A)
    heappush(A, -(-a//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)

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

Solution (Python):

from heapq import heappop,heappush,heapify
n,m = map(int,input().split())
aa = list(map(int,input().split()))
aa = list(map(lambda x:-x,aa))

heapify(aa)
for i in range(m):
  tmp = heappop(aa)  
  heappush(aa,-(-tmp//2))

print(-sum(aa))

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

Solution (Python):
import sys, heapq


def main():
    
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    value = [-int(inp) for inp in input().split()]

    heapq.heapify(value)

    for _ in range(M):
        elem = heapq.heappop(value)
        if elem == 0:
            break
        if elem % 2 == 0: 
        	elem //= 2
        else:
        	elem = elem // 2 + 1
        heapq.heappush(value, elem)

    print(- sum(value))
    
if __name__=="__main__":
    main()

Solution (Python):
import sys, heapq


def main():
    
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    value = [-int(inp) for inp in input().split()]

    heapq.heapify(value)

    for _ in range(M):
        old_elem = heapq.heappop(value)
        if old_elem == 0:
            break
        new_elem = -(- old_elem // 2)
        heapq.heappush(value, new_elem)

    print(- sum(value))
    
if __name__=="__main__":
    main()

Solution (Python):
import sys, heapq


def main():
    
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    value = []
    heapq.heapify(value)
    for inp in input().split():
        heapq.heappush(value, -int(inp))

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

    print(- sum(value))
    
if __name__=="__main__":
    main()

Solution (Python):
import sys, heapq


def main():
    
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    value = [-int(inp) for inp in input().split()]

    heapq.heapify(value)

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

    print(- sum(value))
    
if __name__=="__main__":
    main()

Solution (Python):
import heapq

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

targets = [int(value) for value in targets]
rev = [num * -1 for num in targets]
heapq.heapify(rev)
for i in range(m):
    tmp = -1 * heapq.heappop(rev) // 2
    heapq.heappush(rev,-1 * tmp)

targets = [num * -1 for num in rev]
print(sum(targets))

Solution (Python):
import heapq

n, m = map(int, input().split())
a = list(int(i)*(-1) for i in input().split())

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

print(sum(a) * (-1))

Solution (Python):
import heapq

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

nalist = [-i for i in alist]
heapq.heapify(nalist)
for _ in range(M):
    a = int((heapq.heappop(nalist)+1)//2)
    heapq.heappush(nalist, a)

print(-sum(nalist))

Solution (Python):

import heapq

N, M = map(int, input().split(' '))
A_rev = [int(n) * -1 for n in input().split(' ')]

heapq.heapify(A_rev)

for i in range(M):
    d, m = divmod(heapq.heappop(A_rev), 2)
    if m != 0: d += 1
    heapq.heappush(A_rev, d)

print(-sum(A_rev))

Solution (Python):
import heapq

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

minus_a_list = [-a for a in a_list]
heapq.heapify(minus_a_list)

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

print(-sum(minus_a_list))

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

print(sum(B)*(-1))

Solution (Python):
import heapq

N,M=map(int,input().split())
A=[-int(a) for a in input().split()]

heapq.heapify(A)

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

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

import heapq
import math

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

heapq._heapify_max(a)

for i in range(m):
  temp=math.floor(_heappop_max(a)/2)
  _heappush_max(a,temp)

print(sum(a))

Solution (Python):
import sys
import heapq

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

heapq.heapify(A)

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

print(-sum(A))

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

import heapq

q = [(-Ai, i) for i, Ai in enumerate(A)]
heapq.heapify(q)

M_tmp = M
while M_tmp > 0:
    penalty, i = heapq.heappop(q)
    
    Ai_tmp = (-penalty) // 2
    heapq.heappush(q, (-Ai_tmp, i))
    M_tmp -= 1

ans = sum([-penalty for penalty, i in q])
print(ans)

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

n,m = map(int, input().split(' '))
a_list = [-1 * int(i) for i in input().split() ]
heapq.heapify(a_list)
 
for _ in range(m):
    p = heapq.heappop(a_list)
    q = (-1*p //2) * (-1)
    heapq.heappush(a_list, q)    
    
print(-sum(a_list))

Solution (Python):
import heapq

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

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

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

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 i in range(M):
    heappush(A, -(-heappop(A) // 2))

print(-sum(A))