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, = map(int, input().split())

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

while M>0:
    a = heapq.heappop(A)*(-1)
    heapq.heappush(A, -int(a/2))
    M -= 1

print(-sum(A))

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):
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time,heapq
start_time = time.time()



def solve():
    n,m = invr()
    a = inlt()
    a = list(map(lambda x : x * (-1),a))
    heapq.heapify(a)
    for i in range(m):
      heapq.heappush(a,-(-heapq.heappop(a) // 2))
    print(-sum(a))
    


 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 

def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1],1
    return(q)
 
def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)

def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))

def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))

ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

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

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

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

Solution (Python):
import heapq

def readinput():
    n,m=list(map(int,input().split()))
    a=list(map(int,input().split()))
    return n,m,a

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

    sum=0
    for i in hq:
        sum+=i
    
    return -sum

if __name__=='__main__':
    n,m,a=readinput()
    ans=main(n,m,a)
    print(ans)

Solution (Python):
import queue

n, m = [int(_) for _ in input().split(' ')]
a = [int(_) for _ in input().split(' ')]

q = queue.PriorityQueue()
for i in a:
    q.put(-i)

for _ in range(m):
    i = -(q.get())
    q.put(-(i >> 1))

answer = 0
for _ in range(n):
    answer -= q.get()

print(answer)

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

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

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

n,m = map(int,input().split())
l = list(map(int,input().split()))
s = sum(l)
for i in range(n):
    l[i] *= (-1)

heapq.heapify(l)

discount = 0

for i in range(m):
    x = (-heapq.heappop(l))
    heapq.heappush(l,-(x//2))
    discount += (x-x//2)

print(s-discount)

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

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

Solution (Python):
N ,M = map(int, input().split())
A_list = [int(i) * (-1) for i in input().split()]


import heapq

heapq.heapify(A_list)
for i in range(M):
    x = heapq.heappop(A_list)
    heapq.heappush(A_list, (-1)*(-x//2))

print(-sum(A_list))

Solution (Python):
from fractions import Fraction
from math import log, ceil
import heapq

(n, m), aa = [list(map(int, s.split())) for s in open(0)]
aa = [-Fraction(a) for a in aa]

heapq.heapify(aa)

while m:
    m1 = heapq.heappop(aa)

    if len(aa):
        m2 = aa[0]
        use = min(max(ceil(log(m1/m2)/log(2)), 1), m)

    else:
        use = min(max(ceil(log(-m1)/log(2)), 1), m)



    heapq.heappush(aa, m1 / Fraction(2**use))
    m -= use
    if -(aa[0]) < 1:
        break

aa = [int(-a) for a in aa]

print(sum(aa))

Solution (Python):
import heapq
class HeapQ:
    def __init__(self, L, desc=False):
        if desc:
            L = [-l for l in L]
        self.sign = -1 if desc else 1
        self.HQ = L
        heapq.heapify(self.HQ)
    def pop(self):
        return heapq.heappop(self.HQ) * self.sign
    def push(self, x):
        heapq.heappush(self.HQ, x * self.sign)
    def get_list(self):
        return list([-hq for hq in self.HQ]) if self.sign == -1 else list(self.HQ)

n, m = map(int, input().split())
A = list(map(int, input().split()))
hq = HeapQ(A, desc=True)
for _ in range(m):
    hq.push(hq.pop() // 2)

print(sum(hq.get_list()))

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

def main():
    n, m = map(int, input().split())
    a = [int(x)*-1 for x in input().split()]
    ans = sum(a)*-1
    diff = 0
    
    heapify(a)
    for _ in range(1, m+1):
        _h_a = heappop(a) * -1
        diff += _h_a - _h_a // 2
        heappush(a, (_h_a // 2)*-1)
    ans -= diff
    print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):
import heapq
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


n, m = LI()
a = LI()
a = list(map(lambda x: -1 * x, a))
heapq.heapify(a)
for _ in range(m):
    price = -1 * heapq.heappop(a)  
    heapq.heappush(a,  -1 * (price // 2))
print(-1 * sum(a))

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

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *A = map(int, read().split())

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

    for _ in range(M):
        a = heappop(hq)
        a = int(a / 2)
        heappush(hq, a)

    print(-sum(hq))
    return


if __name__ == '__main__':
    main()

Solution (Python):
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

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

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

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

if __name__ == '__main__':
    main()

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):
    top = heappop(a)
    top = -top // 2
    heappush(a, -top)

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):
  tmp = heappop(A)
  heappush(A,-((-tmp)//2))
A = list(A)

print(-sum(A))

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

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

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

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        lower, upper = [], []
        i = 1
        while i * i <= n:
            if n % i == 0:
                lower.append(i)
                if i != n // i:
                    upper.append(n // i)
            i += 1
        return lower + upper[::-1]

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    N, M = Scanner.map_int()
    A = Scanner.map_int()
    A = [-a for a in A]
    heapq.heapify(A)
    for _ in range(M):
        x = -heapq.heappop(A)
        x //= 2
        heapq.heappush(A, -x)
    print(-sum(A))


def main():
    
    
    
    
    
    
    solve()


if __name__ == "__main__":
    main()

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 i in range(M):
    price = heapq.heappop(A)*(-1)//2
    heapq.heappush(A, -price)

print(-sum(A))

Solution (Python):
from heapq import heappush as hpush
from heapq import heappop as hpop

class Descending_HeapQueue:
    def __init__(self, hq=[]):
        self.hq = []
        for i in hq:
            self.push(i)
    def push(self, n):
        hpush(self.hq, -n)
    def pop(self):
        return -hpop(self.hq)
    def sum(self):
        return -sum(self.hq)
    def __str__(self):
        return [-i for i in self.hq].__str__()

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    dhq = Descending_HeapQueue(A)
    for _ in range(M):
        dhq.push(dhq.pop() // 2)
    print(dhq.sum())
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 i in range(m):
    mx=heapq.heappop(a)
    heapq.heappush(a, (-1)*(-mx//2))

print(-sum(a))

Solution (Python):
import heapq
n, m = map(int, 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())
p = list(map(int,input().split()))
price = [x*(-1) for x in p]
heapq.heapify(price)
while m != 0:
    max_price = heapq.heappop(price)*(-1)
    heapq.heappush(price,(max_price//2)*(-1))
    m -= 1
print(sum(price)*(-1))

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

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

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

Solution (Python):
import heapq

N, M = map(int, input().split())
A = [-int(x) for x in input().split()]
heapq.heapify(A)
for _ in range(M):
    pop = heapq.heappop(A)
    if pop % 2 == 0:
        num = pop//2
    else:
        num = (pop+1)//2
    heapq.heappush(A, num)

print(-sum(A))

Solution (Python):
import heapq
import sys

def input():
    return sys.stdin.readline().strip()

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

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

if __name__ == "__main__":
    main()

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

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

print(-sum(a))

Solution (Python):



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





A = [-a for a in A]
import heapq
heapq.heapify(A)
import bisect
for i in range(M):
    a = heapq.heappop(A)
    new = a/2
    
    
    heapq.heappush(A,new)
import numpy as np
A = np.array(A,dtype=np.int64)
print(-A.sum())

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

N, M = map(int, input().split())
A = []
for i in input().split():
    A.append(-int(i))
heapify(A)
for _ in range(M):
    a = -heappop(A)
    heappush(A, (a // 2) * -1)

ans = -sum(A)
print(ans)

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

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    A = list(map(lambda x: int(x) * (-1), input().split()))
    heapify(A)
    for _ in range(m):
        a = (heappop(A) * (-1)) // 2
        heappush(A, a * (-1))

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


if __name__ == '__main__':
    resolve()

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

Solution (Python):
from heapq import heappop, heapify, heappush
def main():
    n, m = list(map(int, input().split()))
    A = list(map(lambda x: -int(x), input().split()))
    heapify(A)
    for _ in range(m):
        a = heappop(A)
        if a == 0:
            break
        a = -int(-a // 2)
        heappush(A, a)
    print(sum([-a for a in A]))

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

print(-sum(a))

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

heapq.heapify(a)

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

print(-sum(a))

Solution (Python):
from heapq import heappush, heappop,heapify
n,m = map(int,input().split())
def minusint(x):
  return -int(x)
a = list(map(minusint,input().split()))
heapify(a)
for _ in range(m):
  ai = heappop(a)*(-1)
  heappush(a,-(ai//2))
print(-sum(a))

Solution (Python):
import heapq

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def main():
    N, M = mi()
    A = list(map(lambda x: -int(x), input().split()))
    heapq.heapify(A)
    for i in range(M):
        t = heapq.heappop(A)
        heapq.heappush(A, -(-t//2))
    print(-sum(A))

if __name__ == '__main__':
    main()

Solution (Python):
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b=mi()
l=list(mi())
l=list(map(lambda x: x*-1 , l))
heapq.heapify(l)
for i in range(b):
  s=heapq.heappop(l)
  s=(-1)*(((-1)*s)//2)
  heapq.heappush(l,s)
ans=0
for i in range(a):
  d=heapq.heappop(l)
  ans+=(-1)*d
print(ans)

Solution (Python):
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [-v for v in a]
heapq.heapify(a)

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

print(-sum(a))

Solution (Python):
from heapq import heappush, heappop

N, M = map(int, input().split())
*A, = map(int, input().split())
q = []
for i in A:
    heappush(q, -i)

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

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


N, M = map(int, input().split())
A = list(map(lambda x: -int(x), input().split()))
if N == 1:
    print(N >> M)
    exit()
heapify(A)
while M > 0:
    a = -heappop(A)
    while M > 0 and a >= -A[0]:
        a >>= 1
        M -= 1
    heappush(A, -a)
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 _ in range(M):
    n = - heappop(a)
    n //= 2
    heappush(a, -n)
print(-sum(a))

Solution (Python):



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

import heapq
heapq.heapify(a)
for i in range(m):
  min_a=heapq.heappop(a)*(-1)
  heapq.heappush(a,min_a//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 _ in range(m):
    temp = -heapq.heappop(a)
    temp//=2
    heapq.heappush(a,-temp)
ans = 0
for _ in range(n):
    ans -= heapq.heappop(a)
print(ans)

Solution (Python):
def tickets(a, t):
  
  ret = 0
  for x in a:
    while (x > t):
      x //= 2
      ret += 1
  return ret

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

  lb = -1
  ub = 1000000000
  while (ub - lb > 1):
    mid = lb + (ub - lb) // 2
    t = tickets(a, mid)
    if t < m:
      ub = mid
    else:
      lb = mid

  t = 0
  for i in range(n):
    while (a[i] > ub):
      a[i] //= 2
      t += 1

  a.sort(reverse=True)

  for i in range(min(n, m-t)):
    a[i] //= 2

  print(sum(a))

  return

if __name__ == "__main__":
  resolve()

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
A = map(int, readline().split())

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

while M > 0:
    a = -heapq.heappop(q)
    a //= 2
    heapq.heappush(q, -a)
    M -= 1

ans = 0
while len(q) > 0:
    ans += abs(heapq.heappop(q))
print(ans)

Solution (Python):
n,m = map(int,input().split())
a = list(map(int,input().split()))
M = max(a)
a = sorted(a,reverse=True)
t = 0
while M > 1:
    M = -(-M//2)
    t += 1
z = [[] for i in range(t+2)]
for i in range(n):
    s = 0
    b = a[i]
    while b > 1:
        b = -(-b//2)
        s += 1
    z[t-s].append(a[i])
count = 0
for i in range(t+1):
    z[i] = sorted(z[i])
    if count > m:
        break
    while z[i]:
        if count >= m:
            break
        c = z[i].pop()
        z[i+1].append(c//2)
        count += 1
ans = 0
for A in z:
    ans += sum(A)
print(ans)

Solution (Python):
import heapq
N,M = map(int, input().split())
A = list(map(lambda x: -int(x), input().split()))
heapq.heapify(A)
ans = 0
for i in range(M):
    most_expensive = -heapq.heappop(A)
    most_expensive //= 2
    heapq.heappush(A, -most_expensive)
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):
    minimum=heapq.heappop(a)
    mini=((minimum*(-1))//2)*(-1)
    heapq.heappush(a,mini)
    
print(-sum(a))

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

print(-1*sum(a))

Solution (Python):
import heapq

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

ans = 0

heapq.heapify(a)

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

print(-1*sum(a))

Solution (Python):
import heapq

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

for x in range(M):
    maxA = heapq.heappop(A)
    heapq.heappush(A, -1 * ((-1 * maxA) // 2))
A = list(map(lambda x: x * (-1), A))

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)

while m > 0:
    x = heapq.heappop(A)*(-1)
    x //= 2
    A.append(-x)
    m -= 1
print(abs(sum(list(A))))

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

def insertHeap(array, val):
    array.append(val)
    n = len(array)-1
    while n != 0:
        parent = int((n - 1) / 2)
        if array[n] > array[parent]:
            tmp = array[n]
            array[n] = array[parent]
            array[parent] = tmp
            n = parent
        else:
            break
    return array

def desertHeap(array):
    if array == []:
      return None
    array[0], array[-1] = array[-1], array[0]
    res = array.pop(-1)
    n = len(array)
    if n == 0 or n == 1:
      return res
    parent = 0
    while True:
        child = 2 * parent + 1
        if child >= n: break
        if (child + 1 < n) and array[child] < array[child + 1]:
            child += 1
        if array[parent] < array[child]:
            array[child], array[parent] = array[parent], array[child]
            parent = child;
        else:
            break
    return res
 

li = []
a.sort()
for aa in a:
  li = insertHeap(li, aa)

for i in range(m):
  val = desertHeap(li)
  li = insertHeap(li, val//2)

print(sum(li))

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

Solution (Python):



import sys
from collections import defaultdict, deque
from heapq import heappush, heappop, heapify
import math
import bisect
input = sys.stdin.readline




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

q = []
for t in a:
    
    heappush(q, -t)


for m in range(M):
    val = heappop(q)
    val = (-val)//2
    heappush(q, -val)

print(-sum(q))

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

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

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

heapq.heapify(malist)

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

print(-sum(malist))

Solution (Python):
from heapq import heappush, heappop

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

    for i in range(m):
        num, x, cnt = heappop(heap)
        heappush(heap, [num / 2, x, cnt + 1])

    ans = 0
    for i in range(n):
        num, x, cnt = heappop(heap)
        ans += int(num)
    print(-ans)


if __name__ == "__main__":
    resolve()

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 sys
input = sys.stdin.readline
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
A_dic = {} 
for i in range(N):
    if A[i] not in A_dic:
        A_dic[A[i]] = []
    A_dic[A[i]].append(i)


total = 0
rest = M
if N == 1:
    while rest > 0:
        rest -= 1
        A[0] //= 2
    total = A[0]
elif N == 2:
    while rest > 0:
        rest -= 1
        if A[0] >= A[1]:
            A[0] //= 2
        else:
            A[1] //= 2
    total = A[0] + A[1]
else:
    hq = [-A[i] for i in range(N)]
    heapq.heapify(hq)
    while rest > 0:
    
    
    
    
    
    
    
    
    
    
    
    
    
    
        
        max_v = heapq.heappop(hq) * (-1)
        max_idx = A_dic[max_v].pop()
        A[max_idx] //= 2
        if max_v//2 not in A_dic:
            A_dic[max_v//2] = []
        A_dic[max_v//2].append(max_idx)
        heapq.heappush(hq, (max_v//2) * (-1))
        rest -= 1
    total = sum(A)
    


print(total)

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

for i in range(M):
    expe = heapq.heappop(q)
    expe = -expe // 2
    heapq.heappush(q, -expe)
print(-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)

while m > 0 :
  m -= 1
  heapq.heappush(a, -(-heapq.heappop(a) // 2))

print(-sum(a))

Solution (Python):
import heapq

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

an = [-1 * i for i in an]

heapq.heapify(an)

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

print(-1 * sum(an))

Solution (Python):
N,M=list(map(int,input().split()))
import sys
A= list(map(int,sys.stdin.readline().split()))
A=[i*-1 for i in A]
import heapq
heapq.heapify(A)
for i in range(M):
    X=heapq.heappop(A)
    X=abs(X)//2*-1
    heapq.heappush(A,X)
print(abs(sum(A)))

Solution (Python):
import heapq

def solve():
    N, M = map(int, input().split())
    A = list(map(lambda x: int(x) * -1, input().split()))
    
    heapq.heapify(A)
    
    for _ in range(M):
      t = heapq.heappop(A)
      heapq.heappush(A, -1*(-t//2))
    
    return -sum(A)

print(solve())

Solution (Python):
import heapq
def main():
    n, m = list(map(int, input().split()))
    t = list(map(int, input().split()))
    t = list(map(lambda x: x*(-1), t))
    heapq.heapify(t)
    while m > 0:
        v = heapq.heappop(t) * -1
        heapq.heappush(t, (v // 2)* -1)
        m -= 1

    print(sum(t)*-1)


if __name__ == '__main__':
    main()

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