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

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

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

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

ans = -sum(hq)
print(ans)

Submission status: Accepted

Solution code:
n, m, *a = map(int, open(0).read().split())

a.sort(reverse=True)

if n == 1:
  for i in range (0,m):
    a[0] = a[0]//2
    if a[0] == 0:
      break
else:
  a.append(0)
  biggest = a[0]
  now = 0
  while m > 0:
    a[now] = a[now]//2
    m = m - 1
    biggest = a[0]
    for i in range (n-1):
      if a [i+1] >= biggest and m>0:
        a[i+1] = a[i+1]//2
        m = m -1
      else:
        a.sort(reverse = True)
        break

print(sum(a))

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(price)

for i in range(M):
    max_price = -(heapq.heappop(price))
    new_price = max_price // 2
    heapq.heappush(price, -(max_price // 2))

print(-(sum(price)))

Submission status: Accepted

Solution code:
def d_powerful_discount_tickets():
    from heapq import heapify, heappop, heappush
    N, M = [int(i) for i in input().split()]
    A = [-int(i) for i in input().split()]

    heapify(A)
    for _ in range(M):
        heappush(A, -(-heappop(A) // 2))
    return -sum(A)

print(d_powerful_discount_tickets())

Submission status: Accepted

Solution code:
def d_powerful_discount_tickets():
    import heapq
    N, M = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]

    # 参考: https://juppy.hatenablog.com/entry/2019/04/05/蟻本_Python_プライオリティキュー_2_heapq_競技プログラミン
    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()    # raises appropriate IndexError if heap is empty
        if heap:
            returnitem = heap[0]
            heap[0] = lastelt
            heapq._siftup_max(heap, 0)
            return returnitem
        return lastelt

    heapq._heapify_max(A)
    for _ in range(M):
        _heappush_max(A, _heappop_max(A) // 2)
    return sum(A)

print(d_powerful_discount_tickets())

Submission status: Accepted

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

from heapq import *

heapify(q)

while m:
    a = heappop(q)
    a = -(-a // 2)
    heappush(q, a)
    m -= 1

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import heapq


def solve(N: int, M: int, A: "List[int]"):
    heapq.heapify(A)
    while M > 0:
        d = heapq.heappop(A)
        d = -(-d//2)
        heapq.heappush(A, d)
        M -= 1
    print(-sum(A))
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [-int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

A.sort(reverse = True)
i = 0
for j in range(M):
	A[i] = A[i]//2
	if i <= N-2 and A[i] < A[i+1] and A[0] < A[i+1]:
		i += 1
	else :
		A.sort(reverse=True)
		i = 0
print(str(sum(A)))

Submission status: Accepted

Solution code:
import heapq as hq

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

#ヒープキューのために符号逆転
A=list(map(lambda x: x * (-1), A))
hq.heapify(A)

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

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

Submission status: Accepted

Solution code:
import heapq

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

vQ = []
for a in vA:
    heapq.heappush(vQ, -a)

res = 0
for _ in range(M):
    if not vQ:
        break
    # heappop は 最小値を取得する
    ma = heapq.heappop(vQ)
    ma = -ma//2
    heapq.heappush(vQ, -ma)

print(-sum(vQ))

Submission status: Accepted

Solution code:
import heapq as hq
import math

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

for _ in range(M):
    a = math.ceil(hq.heappop(A) / 2)
    hq.heappush(A,a)

print(sum(A)* -1)

Submission status: Accepted

Solution code:
import heapq as hq
import math

def discount(price):
    return math.ceil(price / 2)

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

for _ in range(M):
    a = discount(hq.heappop(A))
    hq.heappush(A,a)

print(sum(A)* -1)

Submission status: Accepted

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

print(d_powerful_discount_tickets())

Submission status: Accepted

Solution code:
import heapq

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

for i in range(N):
    heapq.heappush(hq, A[i]*(-1))

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

Submission status: Accepted

Solution code:
import heapq
import math

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

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

Submission status: Accepted

Solution code:
import heapq

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

hq = []
A = list(map(int, input().split()))
for x in A:
    heapq.heappush(hq, -x)
    
# print(hq)

for i in range(M):
    x = heapq.heappop(hq)
    x = int(x / 2)
    # print(x)
    heapq.heappush(hq, x)

# print(hq)
ans = 0
for x in hq:
    ans += -x
print(ans)

Submission status: Accepted

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

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

pop = lambda: -heappop(a_minus)
push = lambda x: heappush(a_minus,-x)

for _ in range(m):
    x = pop()
    push(x//2)

print(-sum(a_minus))

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

print(-sum(A))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify

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

    heapify(hq)

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

    print(-sum(hq))    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import os
import heapq
import math


def main():
    N, M = (int(x) for x in input().split())
    cost = [-a for a in map(int, input().split())]
    # print(cost)
    heapq.heapify(cost)
    # print(cost)
    for _ in range(0, M):
        x = heapq.heappop(cost)
        # print(x)
        heapq.heappush(cost, x/2)
        # print(cost)
    res = 0
    for i in range(0, N):
        # res += math.floor(cost[i]*-1)
        res += int(cost[i]*-1)

    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

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

print(-sum(hq))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify

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

heapify(hq)

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

print(-sum(hq))

Submission status: Accepted

Solution code:
import os
import heapq
import math

N, M = (int(x) for x in input().split())
cost = [-a for a in map(int, input().split())]
heapq.heapify(cost)

for _ in range(0,M):
    x = heapq.heappop(cost)
    heapq.heappush(cost, x/2)
res = 0
for i in range(0, N):
    res += math.floor(cost[i]*-1)

print(res)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
L = [int(v) * -1 for v in input().split()]

heapify(L)

for i in range(M):
    a = heappop(L) * -1

    heappush(L, a // 2 * -1)

print(sum(L) * -1)

Submission status: Accepted

Solution code:
import heapq
from sys import stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
A = [(-1)*int(_) for _ in stdin.readline().rstrip().split()]
heapq.heapify(A)
for i in range(M):
    tmp = heapq.heappop(A)
    heapq.heappush(A, (-1)*(-tmp//2))
print(-sum(A))

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

sn = lambda : stdin.readline().rstrip()
an = lambda : map(int, stdin.readline().split())
ni = lambda : int(sn())

import heapq

def main():
  n, m = an()
  a = [-int(x) for x in stdin.readline().split()]
  heapq.heapify(a)
  ans = 0
  for _ in range(m):
    x = heapq.heappop(a)
    heapq.heappush(a, x / 2)
  print(-sum(int(x) for x in a))

main()

Submission status: Accepted

Solution code:
import heapq

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

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

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

Submission status: Accepted

Solution code:
import heapq
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 size(self):
        return len(self.hq)


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

q = Heapq(A, desc=True)
for i in range(M) :
    tmp = q.pop()
    tmp //= 2
    q.push(tmp)

ans = 0
for i in range(N) :
    ans += q.pop()
print(ans)

Submission status: Accepted

Solution code:
import heapq

N,M = map(int,input().split())
original_value = list(map(int,input().split()))
value = []

for v in original_value:
  heapq.heappush(value,v*(-1))

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

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

Submission status: Accepted

Solution code:
import heapq as hp
n, m = map(int, input().split())
list_A = list(map(int, input().split()))
 
a_q = []
for i in list_A:
    hp.heappush(a_q, -1*i)
    
for i in range(m):
    tmp = hp.heappop(a_q)
    tmp = hp.heappush(a_q, int(tmp/2))
    
print(-sum(a_q))

Submission status: Accepted

Solution code:
import heapq as hp
n, m = map(int, input().split())
list_A = list(map(int, input().split()))
# list_A = sorted(list_A)

a_q = []
for i in list_A:
    hp.heappush(a_q, -1*i)

for i in range(m):
    tmp = hp.heappop(a_q)
    tmp = hp.heappush(a_q, int(tmp/2))

print(-sum(a_q))

Submission status: Accepted

Solution code:
import heapq

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

q = []
for i in range(N):
    # 最も大きい値を取り出して1/2したいので、ここで反転させておき、最終的に足す時に戻す
    heapq.heappush(q, -a[i])
for i in range(M):
    l = heapq.heappop(q)
    heapq.heappush(q, -(-l//2))
print(-sum(q))

Submission status: Accepted

Solution code:
import bisect

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

cnt = 1
while cnt <= M:
    x = bisect.bisect(A, A[0]/2)
    for i in range(x):
        A[i] /= 2
        cnt += 1
        if cnt > M:
            break
    if x != 0 or x != len(A):
        A.sort()
print(sum(map(lambda x: int(-x), A)))

Submission status: Accepted

Solution code:
#! /usr/bin/env python3
# -*- coding:utf-8 -*-

def discount(M, A):
    from heapq import heappush, heappop
    hq = []
    for x in A:
        heappush(hq, (-x, x))
    for _ in range(M):
        _, price = heappop(hq)
        dprice = int(price/2)
        heappush(hq, (-dprice, dprice))
    return sum([x for _, x in hq])

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

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

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

Submission status: Accepted

Solution code:
import heapq

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

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

    print(-1 * sum(h))


if __name__ == '__main__':
    d()

Submission status: Accepted

Solution code:
import os
import heapq

N,M = (int(x) for x in input().split())
list = [-int(i) for i in input().split()]

heapq.heapify(list)
ans = 0
for i in range(0,M):
    a = heapq.heappop(list)
    heapq.heappush(list,-((-a)//2))
for j in list:
    ans += j*(-1)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import heapq
N,M=map(int,input().split())
a_list=[int(x) for x in input().split()]

A=list([-1*x for x in a_list])
heapq.heapify(A)

for m in range(M):
    max_a=heapq.heappop(A)
    half=max_a/2
    heapq.heappush(A,half)

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

Submission status: Accepted

Solution code:
import heapq
import itertools


def rev(x):
    return int(x) * -1


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

heapq.heapify(a)

for i in itertools.repeat(None, m):
    k = heapq.heappop(a)
    heapq.heappush(a, int(k / 2))

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq

n, m = (int(x) for x in input().split())
A = [int(x) * (-1) for x in input().split()]
heapq.heapify(A)

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

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

Submission status: Accepted

Solution code:
import heapq as hq

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
from heapq import *
from itertools import *
import math
import random
import re
import string
import sys

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

h = []
for a in As:
    heappush(h, -a)

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

print(-sum(h))

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
n,m = (int(i) for i in input().split())
a = [-int(i) for i in input().split()]
x = []
for i in a: heappush(x,i)
for i in range(m):
    p = heappop(x)+1
    heappush(x,p//2)
print(-sum(x))

Submission status: Accepted

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

for _ in range(M):
  i = - heapq.heappop(As)
  i = i >> 1
  heapq.heappush(As,-i)

print(-sum(As))

Submission status: Accepted

Solution code:
import sys
import math
import heapq
n, m = [int(i) for i in sys.stdin.readline().split()]
a_ls = [-int(i) for i in sys.stdin.readline().split()]
heapq.heapify(a_ls)
for i in range(m):
    _max = - heapq.heappop(a_ls)
    heapq.heappush(a_ls, - _max / 2)
a_ls = [math.floor(-i) for i in a_ls]
print(sum(a_ls))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
A = [-int(a) for a in input().split()]
A = sorted(A)

from heapq import heappush, heappop

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

print(-sum(A))

Submission status: Accepted

Solution code:
import sys
import math
import numpy as np
from heapq import heappush, heappop
pos=input()
pos=pos.split()
N=int(pos[0])
M=int(pos[1])
sum=0

item=input()
item=item.split()
item=list(map(float,item))

hq=[]
for i in item:
  heappush(hq,-i)
  
for j in range(1,M+1):
  temp=heappop(hq)
  heappush(hq,math.ceil(temp/2.0))
  
for k in range(0,N):
  sum-=heappop(hq)
print(int(sum))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import heapq

N,M=map(int,sys.stdin.readline().split())
AList=list(map(int,sys.stdin.readline().split()))
h = []
for a in AList:
    heapq.heappush(h, -1*a)
for i in range (M):
  maxNum=heapq.heappop(h)
  heapq.heappush(h, ((maxNum*-1)//2)*-1)
print(sum(h)*-1)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
a = []
[heapq.heappush(a, -x) for x in map(int, input().split())] 
while m > 0:
    t = heapq.heappop(a)
    t /= 2
    m -= 1
    heapq.heappush(a, int(t))
print(sum([abs(x) for x in a]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
A = [int(x) for x in input().split()]
import heapq
heap = []
for value in A:
    heapq.heappush(heap, -value)
for i in range(M):
    disc = heapq.heappop(heap)
    disc = -disc //2
    heapq.heappush(heap, -disc)
print(-sum(heap))

Submission status: Accepted

Solution code:
import heapq
import math
I = list(map(int,input().split()))
N = I[0]
M = I[1]
A = list(map(lambda x:-x,map(int,input().split())))
heapq.heapify(A)
for i in range(M):
    num = heapq.heappop(A)
    num = math.ceil(num / 2)
    heapq.heappush(A,num)

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
hq=list(map(float,input().split()))
hq=[-n for n in hq]
heapq.heapify(hq)
for i in range(M):
    heapq.heappush(hq,heapq.heappop(hq)/2)
hq=[int(a) for a in hq]
print(-sum(hq))

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
A = inpl()
A.sort(reverse=True)
L = list(map(lambda a: len(bin(a))-2,A))
L.append(0)
l = L[0]
P = []
D = []
for i in range(N+1):
    if L[i] == l:
        continue
    elif i > M:
        break
    else:
        d = l - L[i]
        l = L[i]
        r = M // i
        if d < r:
            P.append(i)
            D.append(d)
            M -= d*i
        else:
            P.append(i)
            D.append(r)
            M -= r*i
            break
E = [0]
for dd in D[::-1]:
    E.append(E[-1]+dd)
i = 0
for n in range(len(P)):
    while i < P[n]:
        A[i] >>= E[-n-1]
        i += 1
A.sort(reverse=True)
for m in range(min(M,N)):
    A[m] >>= 1

print(sum(A))

Submission status: Accepted

Solution code:
import heapq

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

A_minus = [-int(a) for a in A]
heapq.heapify(A_minus)

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

Submission status: Accepted

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

# q(m) = q(m-1) - max(A) / 2

# 優先度付きキューをつかう
# 逆ヒープとか? => 要素全部に-1かけてやれば楽

import heapq
heapq.heapify(A)

for i in range(M):
  m = A[0]
  heapq.heappushpop(A, (-1) * ((m * (-1))  // 2))

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
import math

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

item_price_list = list(map(lambda x: x*(-1), item_price_list))
heapify(item_price_list)
for i in range(m):
    a = heappop(item_price_list)
    heappush(item_price_list, math.ceil(a/2))
    
print((-1)*sum(item_price_list))

Submission status: Accepted

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

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

print(-sum(H))

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7
import heapq

def main():
    N, M = MAP()
    A = [-int(i) for i in input().split()]
    heapq.heapify(A)
    for mm in range(M):
        minv = heapq.heappop(A)
        heapq.heappush(A, minv / 2)
    print(sum([int(x) for x in A]) * -1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
N,M=[int(thing) for thing in input().split(" ")]
A_list=[int(thing)*(-1) for thing in input().split(" ")]
heapq.heapify(A_list)
for aaaaa in range(M):
    thing =heapq.heappop(A_list)/2
    heapq.heappush(A_list,thing)
print(int(sum([thing*-1//1 for thing in A_list])))

Submission status: Accepted

Solution code:
import heapq
import math

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

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

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

print(-sum(A))

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
li = [-int(x) for x in input().split()]
import heapq
heapq.heapify(li)
for i in range(b):
    c = heapq.heappop(li)
    heapq.heappush(li,c/2)
li = [int(x) for x in li]
print(-sum(li))

Submission status: Accepted

Solution code:
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):
  num = heapq.heappop(A)
  num = ((-1)*num) //2 
  #単純にnum = num//2とすると
  #num = -9のとき num//2 = -5になってしまう
  #(cf)num == 9のときは num//2 = 4
  num = -num
  heapq.heappush(A,num)
  
ans = -sum(A)
print(ans)

Submission status: Accepted

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

ans = -sum(A)
print(ans)

Submission status: Accepted

Solution code:
import heapq
import math

n, m = map(int, input().split())
A = list(map(lambda x: -x, map(int, input().split())))
heapq.heapify(A)
for _ in range(m):
    tmp = heapq.heappop(A)
    tmp = math.ceil(tmp / 2)
    heapq.heappush(A, tmp)
print(-sum(A))

Submission status: Accepted

Solution code:
import  heapq

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

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

for i in range(0,M):
    a = - (-heapq.heappop(Alist) // 2)
    heapq.heappush(Alist,a)

ans = 0
for j in Alist:
    ans += j * (-1)

print(ans)

Submission status: Accepted

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

# N: 買う品物の個数
# M: 持っている割引券の数
N, M = list(map(int, input().split()))

# X 円の品物を買う際に Y 枚の割引券を使った場合、その品物を (X/2^Y) 円(小数点以下切り捨て)で買うことができます。
# 最小で何円あれば全ての品物を買うことができるのか?

# アイディア
# 単に高い商品から順に割引券を使えればよい...
# プライオリティキューを使って最大のものから順次割引していけばよさそう
# Python のプライオリティキューは最小値しか取れないため、すべての値を (* -1) して考える (出力時にまた (* -1) して戻す)
A = [-x for x in map(int, input().split())]
heapq.heapify(A)


for i in range(M):
    # M 回割引券を適用する
    minimal = heapq.heappop(A)
    heapq.heappush(A, minimal / 2)

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

Submission status: Accepted

Solution code:
import heapq
import math

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

heapq.heapify(a)

for _ in range(m):
	l = heapq.heappop(a)
	l = math.ceil(l/2)
	heapq.heappush(a,l)

print(abs(sum(list(a))))

Submission status: Accepted

Solution code:
import heapq


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

heapq.heapify(a)

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

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq
import math
n, m = map(int, input().split())
a = list(int(x) for x in input().split())
h = []
for value in a:
    heapq.heappush(h, value*(-1))
for i in range(m):
    a = heapq.heappop(h)
    heapq.heappush(h, a/2)
ans = 0
for i in range(n):
    ans += math.floor(h[i]*(-1))
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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)
tmp = 0

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

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)
for m in range(M):
  a = -heapq.heappop(A)
  heapq.heappush(A,-(a>>1))
print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

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

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

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.readline
 
n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] *= -1
heapq.heapify(a)
 
for cnt in range(m):
    temp = heapq.heappop(a)*(-1)
    if temp == 0:
        break
    heapq.heappush(a, (temp//2)*(-1))
    
print(sum(a)*(-1))

Submission status: Accepted

Solution code:
import heapq
import math

mnum, gnum = map(int, input().split())
array = list(map(lambda a: -int(a), input().split()))

array.sort()
heapq.heapify(array)

for i in range(gnum):
	temp = heapq.heappop(array)
	temp /= 2.0
	heapq.heappush(array, temp)
    
amount = 0
for a in array:
  amount += math.floor(-a)
print(amount)

Submission status: Accepted

Solution code:
import math
import heapq

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

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

amount = 0
for a in A:
  amount += math.floor(-a)
print(amount)

Submission status: Accepted

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

from heapq import heappush, heappop
hq=[]

for a_val in a:
    # heappopで最も小さい値が取り出されるため、(-1)をかけて入れる
    heappush(hq, -a_val)
for _ in range(m):
    heappush(hq, -(heappop(hq)//(-2)))
print(-sum(hq))

Submission status: Accepted

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

for i in range(M):
  maxA = heapq.heappop(Ai)*(-1)
  waribiki = maxA // 2
  heapq.heappush(Ai,waribiki * (-1))
  #print(Ai)
  
print(sum(Ai) * (-1))

Submission status: Accepted

Solution code:
def main():
    import sys
    import heapq
    input=sys.stdin.readline
    N,M=map(int,input().split())
    A=list(map(lambda x:-1*int(x),input().split()))
    heapq.heapify(A)
    for i in range(M):
        if i==0:
            temp = -(heapq.heappop(A))//2
        else:
            heapq.heappush(A,-temp)
            temp = -(heapq.heappop(A))//2
    print(-sum(A)+temp)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
item=list(map(lambda x: -int(x),input().split()))
heapq.heapify(item)
for i in range(m):
    top=-heapq.heappop(item)
    top //=2
    heapq.heappush(item,-top)

print(-sum(item))