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



Sample input:
3 3
2 13 8


Sample output:
9

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
import heapq

N,M = map(int,input().split(' '))
l = list(map(int, input().split()))
h = []
for i in range(N):
    heapq.heappush(h, -l[i])
for i in range(M):
    p = heapq.heappop(h)
    if p==0:
        print(0)
        exit()
    p = p / 2
    heapq.heappush(h, p)
cnt = 0
for i in range(N):
    cnt += int(-h[i])
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n1, n2 = [int(i) for i in input().split()]
n3 = [int(i) for i in input().split()]

n3.sort(reverse = True)

c1 = 0
while True:
    n3[0] = n3[0] // 2
    c1 += 1
    if c1 >= n2:
        break
    t2 = 1
    while len(n3) != 1:
        if n3[t2] >= n3[0]:
            n3[t2] = n3[t2] // 2
            t2 += 1
            c1 += 1
            if c1 >= n2 or t2 >= len(n3):
                break
        else:
            break

    if c1 >= n2:
        break

    n3.sort(reverse = True)

r1 = 0
for i2 in range(n1):
    r1 += n3[i2]

print(r1)

Submission status: Accepted

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

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

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

print(-sum(h))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N,M = map(int, input().split())
hq = []
a = [int(i) for i in input().split()]
for i in range(N):
    heappush(hq, -a[i])

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

print(-sum(hq))

Submission status: Accepted

Solution code:
N, M = [int(v) for v in input().split(' ')]
A = [int(v) for v in input().split(' ')]

from heapq import heappush, heappop

h = []

for a in A:
    heappush(h, -a);

for i in range(0, M):
    p = (-heappop(h)) // 2
    heappush(h, -p)

s = 0
for p in h:
    s += p
    
print(-s)

Submission status: Accepted

Solution code:
import logging
import heapq

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)

def calc_(s):
    return int(s) * (-1)

def main():
    N, M = map(int, input().split())
    L_1 = list(map(calc_, input().split()))
    logging.info("Hello!")

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

    print(sum(list(L_1)) * (-1))
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(lambda x: -int(x), input().split()))
import heapq
import math
value = -sum(a)
heapq.heapify(a)

for i in range(m):
  use = heapq.heappop(a)
  value += math.floor(use/2)
  heapq.heappush(a, math.ceil(use/2))
  
print(value)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    from collections import deque


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

    aa = list(map(int, input().split()))
    aa.sort(reverse=True)
    aa = deque(aa)

    if n == 1:
        a = aa.popleft()
        for _ in range(m):
            a = a // 2
        print(a)
        exit()

    top = aa.popleft()

    deque_list = [aa, deque()]
    top_list = [deque_list[0].popleft(), top//2]


    for _ in range(m-1):
        max_num = max(top_list)
        max_index = top_list.index(max_num)
        try:
            deque_list[max_index+1].append(max_num//2)
        except IndexError:
            deque_list.append(deque())
            top_list.append(max_num//2)
        if top_list[max_index+1] == -1:
            top_list[max_index+1] = deque_list[max_index+1].popleft()
        try:
            top_list[max_index] = deque_list[max_index].popleft()
        except IndexError:
            top_list[max_index] = -1

    ans = 0
    for num in top_list:
        ans += max(0, num)
    for one_deque in deque_list:
        ans += sum(one_deque)
    print(ans)

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(a)

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

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq

def f(x):
    return -int(x)

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

A.sort()

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

Submission status: Accepted

Solution code:
import heapq

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

A = list(map(int, input().split()))
A.sort()
A = A[::-1]
if N == 1 or M == 1:
    A[0] = A[0]//(2**M)
    print(sum(A))
    exit()



for i in range(N):
    A[i] *= -1

heapq.heapify(A)
m_b = M
for i in range(M):
    a = heapq.heappop(A)
    b = A[0]
    buff = a
    # mai = M-(i+1)
    c = 0
    # flag = True
    for j in range(1,m_b+1):
        c += 1
        # print('-----')
        # print(a)
        a = a / (2**(j))
        a = a*-1
        a = int(a)*-1
        # print(a, j, b)
        if a >= b:
            heapq.heappush(A, a)
            # heapq.heapify(A)
            # print(A)
            # flag = False
            break
    m_b -= c
    if m_b < 1:
        # print(A)
        # print(sum(A))
        print(sum(A)*-1)
        # print(A)
        exit()

Submission status: Accepted

Solution code:
import sys
from math import floor
from heapq import heappush, heappop, heappushpop
input = sys.stdin.readline
sys.setrecursionlimit(10**7)


# 10**5
n, m = map(int, input().split())
# 10**9
a = sorted(map(lambda s: -int(s), input().split()))


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

print(sum(map(lambda x: floor(-x), a)))

Submission status: Accepted

Solution code:
import sys
import math
input=sys.stdin.readline
from heapq import heappop, heappush, heapreplace

n,m=map(int,input().split())
a=list(map(int,input().split()))
hq=[]
for i in a:
    heappush(hq,-i)    
for j in range(m):
    b=math.ceil(heappop(hq)/2)
    heappush(hq,b)
ans=0
for k in hq:
    ans-=k
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq

input = sys.stdin.readline


def solve(N, M, A):
    A = [-a for a in A]
    heapq.heapify(A)
    for _ in range(M):
        max_a = heapq.heappop(A)
        max_a /= 2
        heapq.heappush(A, max_a)
    result = 0
    for a in A:
        result += int(-a)
    return result


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    answer = solve(N, M, A)
    print(answer)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import heapq
n, m = map(int, sys.stdin.readline().split())
A = list(map(lambda x:-int(x), sys.stdin.readline().split()))
heapq.heapify(A)

for j in range(m):
    heapq.heappush(A ,int(A[0]/2))
    heapq.heappop(A)

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

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

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

heapq._heapify_max(p)

for i in range(M):
    a = _heappop_max(p)
    a //= 2
    _heappush_max(p, a)

print(sum(p))

Submission status: Accepted

Solution code:
import heapq

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
b = []
heapq.heappush(b,0)
for _ in range(m):
    bm = -b[0]
    if len(a) != 0 and a[-1] > bm:
        am = a.pop()
        am = am // 2
        heapq.heappush(b,-am)
    else:
        bm = -heapq.heappop(b)
        bm = bm // 2
        heapq.heappush(b,-bm)
        
    
print(sum(a)-sum(b))

Submission status: Accepted

Solution code:
import heapq

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

def calc(m):
    if m % 2 == 0:
        return m//2
    else:
        return m//2 + 1

m = heapq.heappop(A)
for _ in range(M-1):
    m = heapq.heappushpop(A, calc(m))

print(-sum(A)-calc(m))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq as hq
n, m = map(int, input().split())

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

acc = []
for i in a:
    hq.heappush(acc, [-i, i, 0])

for _ in range(m):
    price, org, disnum = hq.heappop(acc)
    if price == 0:
        break

    new_disnum = disnum + 1
    new_price = org // (2 ** new_disnum)

    hq.heappush(acc, [-new_price, org, new_disnum])

total = 0
for price, _, _ in acc:
    total -= price

print(total)

Submission status: Accepted

Solution code:
import heapq
import math

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

    heapq.heapify(L)

    for _ in range(M):
        max = heapq.heappop(L) * -1
        discounted = max / 2
        heapq.heappush(L, discounted*-1)
    
    floor_L = [math.floor(-i) for i in L]
    print(sum(floor_L))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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*=-1
    #print(a)
    a//=2
    #print(a)
    heapq.heappush(A,-a)
ans=0
#print(A)
for a in A:
    ans-=a
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())), reverse=True)

b = arr[0] // 2
i = 0
while True:
    if m == 0:
        break
    if b <= arr[i]:
        arr[i] = arr[i] // 2
        m -= 1
    else:
        arr = sorted(arr, reverse=True)
        i = 0
        b = arr[0] // 2
        continue
    if i < n-1:
        i += 1
    else:
        i = 0

print(sum(arr))

Submission status: Accepted

Solution code:
import heapq

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

class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        return heapq.heappop(self.hq) * self.sign
 
    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)
 
    def top(self):
        return self.hq[0] * self.sign
    
    def qsum(self):
        return -sum(self.hq)

q = Heapq(items, True)

for i in range(m):
    max_price = q.pop()
    max_price = max_price // 2
    q.push(max_price)

print(q.qsum())

Submission status: Accepted

Solution code:
import heapq
import math
def heapqmax(n):
    return n * -1

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

heapq.heapify(A)
for i in range(M):
    heapq.heappush(A,math.ceil(heapq.heappop(A)/2))
    # print(A)

print(sum(A)*-1)

Submission status: Accepted

Solution code:
import heapq

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

pq = []
for price in a:
    heapq.heappush(pq, -price)

while tickets:
    biggest = heapq.heappop(pq)
    biggest = (-biggest) // 2
    tickets -= 1
    heapq.heappush(pq, -biggest)

print(-sum(pq))

Submission status: Accepted

Solution code:
import math
n, m = map(int, input().split())
a = list(float(x) for x in input().split())
a.sort(reverse=True)
while m > 0:
    for i in range(n):
        if a[i] >= a[0]:
            a[i] = a[i] / 2
            m -= 1
            if m == 0:
                break
        else:
            a.sort(reverse=True)
            break
ans = 0
for i in range(n):
    ans += int(math.floor(a[i]))
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
while True:
    x = A[N-1]/2
    if x < 0.5:
        break
    for i in range(N-1, -1, -1):
        if A[i] < x:
            break
        A[i] /= 2
        M -= 1
        if M == 0:
            break
    A.sort()
    if M == 0:
        break

sum = 0
for a in A:
    sum += a//1
print(int(sum))

Submission status: Accepted

Solution code:
# 190915 D
import heapq
if __name__ == "__main__":
    N = list(map(int,input().split()))
    M = N[1]
    N = N[0]
    A = list(map(int,input().split()))
    for i in range(len(A)):
        A[i] = (-1) * A[i]
    heapq.heapify(A)
    for i in range(M):
        tmpa = heapq.heappop(A)
        heapq.heappush(A,int(tmpa / 2))
    print(-1*sum(A))

Submission status: Accepted

Solution code:
def maxHeapfy(a, h, i):
    l = 2 * i
    r = 2 * i + 1

    if l <= h and a[l] > a[i]:
        largest = l
    else:
        largest = i
    if r <= h and a[r] > a[largest]:
        largest = r

    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        maxHeapfy(a, h, largest)


n, m = [int(v) for v in input().split()]
a = [-1]
a.extend([int(v) for v in input().split()])

for i in range(n//2, 0, -1):
    maxHeapfy(a, n, i)

for i in range(m):
    a[1] //= 2
    maxHeapfy(a, n, 1)

print(sum(a[1:]))

Submission status: Accepted

Solution code:
import heapq

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
A = [i * -1 for i in A]
heapq.heapify(A)
for i in range(M):
    maxA = -1 * heapq.heappop(A)
    heapq.heappush(A,-1*(maxA//2))
print(-sum(A))

Submission status: Accepted

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

import heapq

heapq.heapify(a)

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

print(sum(a) * -1)

Submission status: Accepted

Solution code:
import math
import heapq
n, ticket = map(int, input().split())
L = list(map(int, input().split()))
h = []
for num in L:
    heapq.heappush(h, -num)
for _ in range(ticket):
    top = heapq.heappop(h)
    top /= 2
    heapq.heappush(h, top)
print(sum(map(lambda x: math.floor(-x), h)))

Submission status: Accepted

Solution code:
import bisect

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


while m > 0:
    a.sort()
    m -= 1
    a[-1] = a[-1] // 2
    for i in range(n-1)[::-1]:
        if m == 0:
            break
        if a[i] > a[-1]:
            m -= 1
            a[i] = a[i] // 2
        else:
            break

ans = sum(a)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
import math
n, m = map(int,input().split())
a = list(map(int, input().split()))
item = []
ans = 0

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

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

for i in range(n):
  ans += math.floor(-item[i])
  
print(ans)

Submission status: Accepted

Solution code:
import math
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):
    tmp = heapq.heappop(A) * (-1) / 2
    heapq.heappush(A,tmp * (-1))
A = list(map( lambda x : x * (-1) , A ))
A = list(map( lambda x : math.floor(x) , A ))
print(sum(A))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import bisect 
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
count=0
while True:
    a.sort(reverse=True)
    a0=a[0]//2
    for i in range(n):
        a[i]=a[i]//2
        count+=1
        if count==m:
            print(sum(a))
            exit()
        if i==n-1:break
        if a[i+1]<a0:
            break

Submission status: Accepted

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

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

print(sum([i[1] for i in A]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq
import math


class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign


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

my_heap = Heapq(a_list, True)

for i in range(m):
    value = my_heap.pop()
    value = value / 2
    my_heap.push(value)

ret = 0
for i in range(n):
    ret += math.floor(my_heap.pop())

print(ret)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

# coding: utf-8
# Your code here!
import sys

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

while True:
    al.sort(reverse=True)
    for idx, i in enumerate(al):
        if al[0] == 0:
            print("0")
            sys.exit()
        if al[0] // i >= 2:
            for j in range(idx):
                al[j] = al[j] // 2
            m = m - idx
            break
        if idx + 1 == m:
            for j in range(idx + 1):
                al[j] = al[j] // 2
            print(sum(al))
            sys.exit()
    else:
        for j in range(n):
            al[j] = al[j] // 2
        m = m - n

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
from math import ceil, floor


def p_d():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    H = []

    for a in A:
        heappush(H, a * -1)

    for _ in range(M):
        x = heappop(H)

        heappush(H, ceil(x / 2))

    ans = 0

    for a in H:
        ans -= a

    print(ans)


if __name__ == '__main__':
    p_d()

Submission status: Accepted

Solution code:
import sys
import bisect
input = sys.stdin.readline
 
def main():
    n,m = map(int,input().split())
    a = list(map(int,input().split()))
    cnt=0
    while(cnt<m):
        a.sort()
        a[n-1]=a[n-1]//2
        cnt+=1
        if(cnt==m):
            break
        for i in range(n-1):
            if(a[n-1]<=a[n-i-2]):
                a[n-i-2]=a[n-i-2]//2
                cnt+=1
                if(cnt==m):
                    break
    print(sum(a))


main()

Submission status: Accepted

Solution code:
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n,m = MAP()
a = MAP()
a = [-i for i in a]
heapify(a)
for i in range(m):
    tmp = -heappop(a)
    heappush(a,-(tmp//2))
print(-sum(a))

Submission status: Accepted

Solution code:
def solve():
  import sys
  import math
  import heapq

  sys.setrecursionlimit(10**7)
  readline=sys.stdin.readline

  n,m = map(int,input().split())
  a = [-int(i) for i in input().split()]
  heapq.heapify(a)
  
  t = heapq.heappop(a)
  for i in range(m-1):
    t = heapq.heappushpop(a,t/2)
  heapq.heappush(a,t/2)
  
  print(sum(int(-i) for i in a))

if __name__ == '__main__':
  solve()

Submission status: Accepted

Solution code:
import heapq


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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

a.sort(reverse=True)

a.append(0)
b = 0

if n > 1:
    for i in range(m):
        a[b] //= 2

        if a[b] < a[0] or a[b] < a[b + 1]:
            if a[0] > a[b + 1]:
                b = 0
                a.sort(reverse=True)
            else:
                b += 1

else:
    for i in range(m):
        a[0] //= 2





print(sum(a))

Submission status: Accepted

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

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

for i in range(N):
  ans += -heapq.heappop(q)

print(ans)

Submission status: Accepted

Solution code:
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):
    h = heapq.heappop(a)
    h = - h
    h = h // 2
    h = - h
    heapq.heappush(a,h)
g = 0
for j in range(n):
    g += heapq.heappop(a)
print(0-g)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
aL = list(map(int, input().split()))
heap = []
ans = 0
for j in aL:
    heapq.heappush(heap, -j)
for i in range(m):
    max_ = heapq.heappop(heap)
    max_ = -(-max_ // 2)
    heapq.heappush(heap, max_)
while heap:
    a = heapq.heappop(heap)
    ans -= a
print(ans)

Submission status: Accepted

Solution code:
import heapq
import math
N,M = map(int,input().split())
A = list(map(int,input().split()))
A = [-A[_] for _ in range(N)]
heapq.heapify(A)
for i in range(M):
    B = math.ceil(heapq.heappop(A)/2)
    heapq.heappush(A,B)
print(-sum(A))

Submission status: Accepted

Solution code:
import heapq as hq

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

# dp = [[0 for i in range(N)] for _ in range(M)]

# sortedA = sorted(A,reverse=True)

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

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

print(abs(sum(A)))

Submission status: Accepted

Solution code:
N,M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
import heapq
heapA = []
for a in A:
    heapq.heappush(heapA,-a)
for m in range(M):
    tmp = -heapq.heappop(heapA)
    tmp = tmp//2
    tmp = -1 * tmp
    heapq.heappush(heapA,tmp)
print(-sum(heapA))

Submission status: Accepted

Solution code:
import heapq

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

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

# a.sort(reverse=True)
heapq.heapify(a)

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

Submission status: Accepted

Solution code:
import heapq


class Reverse:
    def __init__(self, val):
        self.val = val

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

    def __repr__(self):
        return repr(self.val)


class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            for i in range(len(arr)):
                arr[i] = Reverse(arr[i])
        self.desc = desc
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        if len(self.hq) == 0:
            return None
        if self.desc:
            return heapq.heappop(self.hq).val
        else:
            return heapq.heappop(self.hq)

    def push(self, a):
        if self.desc:
            heapq.heappush(self.hq, Reverse(a))
        else:
            heapq.heappush(self.hq, a)


N, M = map(int, input().split())
q = Heapq(list(map(int, input().split())), desc=True)

while M > 0:
    a = q.pop() // 2
    q.push(a)
    M -= 1

tmp = 0
while True:
    try:
        a = q.pop()
        tmp += a
    except:
        break
print(tmp)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
aa = list(map(int, input().split()))
aa = [-b for b in aa]
heapq.heapify(aa)

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

print((-1) * sum(aa))

Submission status: Accepted

Solution code:
import heapq

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

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

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

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

Submission status: Accepted

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

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

for i in range(M):
    target = que[0]
    if target % 2 == 1:
        target = target + 1
    heapq.heapreplace(que, target // 2)

print(sum(que) * -1)

Submission status: Accepted

Solution code:
import heapq

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

    heapq.heapify(A)

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

    print(-1 * sum([int(x) for x in A]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque

import heapq
import math


class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign

    def sum(self):
        return -sum(self.hq)


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

    for _ in range(M):
        a = heap.pop()
        heap.push(math.floor(a / 2))

    print(heap.sum())


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
il = list(map(int, input().split()))
q = []
for idx, price in enumerate(il):
    heapq.heappush(q, (-price, idx))

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

sum = 0
for t in q:
    price, idx = t
    sum += -price
print(sum)

Submission status: Accepted

Solution code:
import heapq
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [(-x, x) for x in A]
heapq.heapify(A)
for i in range(M):
    P = heapq.heappop(A)
    p = P[1] // 2
    heapq.heappush(A, (-p, p))
s = 0
for i in range(N):
    s += A[i][1]
print(s)

Submission status: Accepted

Solution code:
import heapq
import math

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

heapq.heapify(B)
for i in range(M):
    b = heapq.heappop(B)
    heapq.heappush(B,math.ceil(b/2))
print(-1*sum(B))

Submission status: Accepted

Solution code:
import heapq

def main():
    [N, M] = [int(num) for num in input().split()]
    A = [int(num) for num in input().split()]
    hp = []

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

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

    hp = [int(- a // 1) for a in hp]
    print(sum(hp))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
a = list(map(int,input().split()))
for i in range(len(a)):
    a[i] = a[i]*(-1)
import heapq
heapq.heapify(a)
for _ in range(M):
    x = (-1)*heapq.heappop(a)
    y = x//2
    heapq.heappush(a,-y)
print((-1)*sum(a))

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
a = list(map(int, input().split()))
a = [-ai for ai in a]
a.sort()
for i in range(M):
    tmp = heapq.heappop(a)
    tmp = (tmp+1)//2
    heapq.heappush(a, tmp)

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq
import math

def main():
    N,M = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]
    count = 0
    heap = []
    for i in range(len(A)):
        heapq.heappush(heap,(A[i] * -1))
    for i in range(M):
        a = heapq.heappop(heap)
        a = int(a / 2)
        heapq.heappush(heap, a)
    for i in range(len(heap)):
        count += heapq.heappop(heap) * -1
    print(count)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(goods)

for i in range(m):
    highest = heapq.heappop(goods)
    if highest % 2 == 0:
        discount_price = highest//2
    else:
        discount_price = (highest//2) + 1
    heapq.heappush(goods, discount_price)
    
ans = 0
for p in goods:
    ans += p * (-1)
    
print(ans)

Submission status: Accepted

Solution code:
import heapq

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