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

Submission status: Accepted

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

import heapq
# print(A)
heapq.heapify(A)
# print(A)
for _ in range(M):
    a = heapq.heappop(A)
#     print( "aaa",a)
    heapq.heappush(A,-1*((-1*a)//2))
#     print("AAA",A)
    
# print("list",A)

print(-1*sum(A))

Submission status: Accepted

Solution code:
import heapq

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

for i in range(M):
  h = heapq.heappushpop(A, (h*(-1))//2*(-1))
    
print((sum(A)+h) * (-1))

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
a_list = [-float(i) for i in input().split()]
heapq.heapify(a_list)
for _ in range(M):
    _ = heapq.heapreplace(a_list, a_list[0]/2.0)
ans = sum([-int(i) for i in a_list])
print(ans)

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

print(-sum(A))

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 i in range(m):
    minprice = hq.heappop(a)
    hq.heappush(a, (-minprice // 2) * -1)
print(-sum(a))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
sum = 0
l = []
for i in A:
    heapq.heappush(l, i*-1)
for i in range(M):
    c = int(heapq.heappop(l)*-1/2)
    heapq.heappush(l, c*-1)
for a in l:
    sum += a*-1
print(sum)

Submission status: Accepted

Solution code:
def pushHeap(array, elem):
    n = len(array)
    array.append(elem)
    while n != 0:
        i = int((n - 1) / 2)
        if array[n] > array[i]:
            tmp = array[n]
            array[n] = array[i]
            array[i] = tmp
        n = i


def popHeap(array):
    n = len(array) - 1
    array[0] = array[n]
    del array[-1]
    i = 0
    while 2 * i + 1 < n:
        j = 2 * i + 1
        if j != n - 1 and array[j] < array[j + 1]:
            j += 1
        if array[i] < array[j]:
            tmp = array[j]
            array[j] = array[i]
            array[i] = tmp
        i = j


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

for a in A:
    pushHeap(heap_A, a)

for _ in range(M):
    discount_max = int(heap_A[0] / 2)
    popHeap(heap_A)
    pushHeap(heap_A, discount_max)

print(sum(heap_A))

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) * (-1)
    heapq.heappush(A, (a//2)*(-1))

print(-sum(A))

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.readline

n, m = map(int, input().split())
li = [-int(i) for i in input().split()]
li = sorted(li)

for _ in range(m):
	x = heapq.heappop(li)
	#print(x)
	if x % 2 == 0:
		heapq.heappush(li, x // 2)
	else:
		heapq.heappush(li, x // 2 + 1)
	#print(li)
print(-sum(list(li)))

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


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

Submission status: Accepted

Solution code:
import heapq
def neg(x):
	return x * (-1)

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

Submission status: Accepted

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

c=list(map(lambda x: int(x)*-1,input().split()))
#heapqでは最小値しか取り出せないので最大値をとるばあには－１をかけておく

heapq.heapify(c)  #リストを優先度付きキューに
for i in range(m):
    cmin=heapq.heappop(c)  #最小値の取り出し
    heapq.heappush(c,(-1)*(-cmin//2))#最小値を2で割った商をリストに追加

print(-sum(c))

Submission status: Accepted

Solution code:
import heapq

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

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

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

print(-sum(a))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import heapq as hp

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

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

Submission status: Accepted

Solution code:
import heapq

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

tmp = 0
for m in range(M):
    div = -heapq.heappop(A)
    div = div // 2
    heapq.heappush(A, -div)
print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

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

ans = 0

for i in range(len(a)):
    while True:
        if m <= 0:
            break

        maxV = heapq.heappop(a)
#        print('maxV: ' + str(maxV))
        heapq.heappush(a, -(-maxV // 2))
        m -= 1
        # print('m: ' + str(m))
        # print('a: ' + str(a))
ans = -sum(a)
print(ans)

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 _ in range(m):
    temp = heapq.heappop(a)
    temp = -(-temp//2)
    heapq.heappush(a, temp)

print(-sum(a))

Submission status: Accepted

Solution code:
from sys import stdin
import heapq

n,m = [int(x) for x in stdin.readline().rstrip().split()]
a_lst = [int(x) * (-1) for x in stdin.readline().rstrip().split()]
heapq.heapify(a_lst)

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

Submission status: Accepted

Solution code:
import math
import heapq
N,M = input().split()
N = int(N)
M = int(M)
A = [int(i) for i in input().split()]
A_ = []
#A = sorted(A, reverse=True)
for i in A:
  A_.append(i * -1)


heapq.heapify(A_)
for i in range(M):
  max_num = heapq.heappop(A_)
  #append_num = math.floor((max_num * -1) / 2)
  append_num = math.ceil(max_num / 2)
  heapq.heappush(A_,append_num)

  #print(A_)

print(sum(A_) * (-1))

Submission status: Accepted

Solution code:
import heapq

N,M = input().split()
N = int(N)
M = int(M)
price_list = input().split()
 
heap_list = []
for i in price_list:
  heapq.heappush(heap_list, int(i) * (-1))

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

Submission status: Accepted

Solution code:
import heapq
import math

n,m = list(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)
	tmp = (math.floor(-tmp/2)) * (-1)
	heapq.heappush(a, tmp)

print(sum(a) * -1)

Submission status: Accepted

Solution code:
import heapq as hq

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
que = []
for i, a in enumerate(A):
    hq.heappush(que, (-a, str(i))) 

for _ in range(M):    
    priority, a = hq.heappop(que)    
    if priority == 0:
        break
    priority = - priority
    priority //= 2
    hq.heappush(que, (-priority, a))

sum_ = 0
for q in que:
    sum_ += q[0]

print(-sum_)

Submission status: Accepted

Solution code:
import numpy
import heapq
import math

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

print(-sum(A))

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

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

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

n,m=map(int,input().split())
a=list(map(int_minus,input().split()))
heapq.heapify(a)
for i in range(m):
    maxa=-1 * heapq.heappop(a)
    maxa = maxa // 2
    heapq.heappush(a, -1 * maxa)
print(-1 * sum(a))

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
n, m = map(int, input().split())
al = list(map(int, input().split()))
al = [-a for a in al]
heapify(al)

while m != 0:
    tmp = heappop(al)
    tmp = int(tmp/2)
    m -= 1
    heappush(al, tmp)

al = list(al)
al = [-a for a in al]
print(sum(al))

Submission status: Accepted

Solution code:
import heapq

def calc(N, M, A):
    if (N == 1):
        return A[0] // (2 ** M)
    H = []
    for a in A:
        heapq.heappush(H, -a)
    for _ in range(M):
        a = (-heapq.heappop(H)) // 2
        heapq.heappush(H, -a)
    return -sum(H)


(N, M) = tuple([int(s) for s in input().split(' ')])
A = [int(s) for s in input().split()]
print(calc(N, M, A))

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

Submission status: Accepted

Solution code:
from heapq import heappop,heappush,heapify

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

heapify(A_minus)

for _ in range(M):
    heappush(A_minus, -((-heappop(A_minus)) // 2))
ans = -sum(A_minus)
print(int(ans))

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 i in range(m):
    tmp_min=heapq.heappop(a)
    heapq.heappush(a,(-1)*(-1*tmp_min//2))  # 計算誤差の関係で-1を2回かけてます
print(-sum(a))

Submission status: Accepted

Solution code:
from heapq import heappop,heappush

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

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

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq
N , M = map(int, input().rstrip().split())
 
pricelist = list(map(int, input().split()))
for i in range(N):
  pricelist[i] = pricelist[i] * (-1)
heapq.heapify(pricelist)

 
for i in range(M):
  minprice = heapq.heappop(pricelist)
  if minprice % 2 == 0:
    minprice = minprice // 2
  else:
    minprice = minprice // 2 + 1
  heapq.heappush(pricelist, minprice)

print(sum(pricelist)* (-1))

Submission status: Accepted

Solution code:
#abc141d
import heapq

n,m=map(int,raw_input().split())
a=map(int,raw_input().split())
l=[]
for i in xrange(n):
 l.append(-a[i])
q=[]
for i in l:
 heapq.heappush(q,i)
for i in range(m):
 temp=-heapq.heappop(q)
 heapq.heappush(q,-(temp/2))
res=-sum(q)
print res

Submission status: Accepted

Solution code:
#D heapq
import heapq
def mainasu(n):
    return n*(-1)
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(mainasu,a))
b.sort()
for i in range(m):
    c=heapq.heappop(b)
    if c%2==0:
        heapq.heappush(b,c//2)
    else:
        heapq.heappush(b,c//2+1)
print((-1)*sum(b))

Submission status: Accepted

Solution code:
# ABC141 D - Powerful Discount Tickets
from heapq import heappop,heappush,heapify

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

a_minus = [-x for x in a]

heapify(a_minus)

for _ in range(m):
    heappush(a_minus,-((-heappop(a_minus))//2))
ans = -sum(a_minus)
print(int(ans))

Submission status: Accepted

Solution code:
import math
import heapq

def minus(number):
    return (-1) * number

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


for x in range(M):
    t = math.floor(heapq.heappop(A) * (-1) / 2)
    heapq.heappush(A, t*(-1))

A = list(map(minus, A))
print(sum(A))

Submission status: Accepted

Solution code:
import heapq

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

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

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

t=0
for i in range(n):
  t -= heapq.heappop(h)

print(t)

Submission status: Accepted

Solution code:
import heapq

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

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

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq


if __name__ == '__main__':
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    q = []
    for x in a:
        heapq.heappush(q, -x)

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

    answer = 0
    for x in q:
        answer += int(-x//1)
    print(answer)

Submission status: Accepted

Solution code:
import sys
import heapq
from math import ceil


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


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

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

    ans = -sum(A)

    print(ans)


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 i in range(M):
    tmp = heapq.heappop(A)
    heapq.heappush(A, (tmp+1) // 2)
print(str(-sum(A)))

Submission status: Accepted

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

# In[8]:


# import copy
#import numpy as np
import heapq

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

def int_minus(s):
    return -int(s)

As = list(map(int_minus, input().split()))
"""
3 3
2 13 8

4 4
1 9 3 5
"""


# In[10]:


heapq.heapify(As)


# In[17]:


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


# In[19]:


#print(As)
print(-sum(As))


# In[ ]:

Submission status: Accepted

Solution code:
# coding: UTF-8

#import scipy.optimize
from math import ceil,floor
from heapq import heappush, heappop, heapify
    
##################################################################

if __name__ == "__main__":

    Input = [input() for i in range(2)]
    N,M = list(map(int,Input[0].split()))
    A = list(map(int,Input[1].split()))
    A = [-a for a in A]
    heapify(A)
    Use = 0
    while Use < M:
        temp = -1*heappop(A)
        temp = floor(temp/2)
        heappush(A, -temp)
        Use += 1
    print(sum(A)*-1)

Submission status: Accepted

Solution code:
import heapq

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

for _ in range(m):
    p = -heapq.heappop(ps)
    heapq.heappush(ps, -(p // 2))
print(-sum(ps))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
A = list(map(int, input().split()))
A = map(lambda x: x * (-1), A)
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:
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import sys
import logging
import heapq
logging.basicConfig(level=logging.DEBUG)

input = sys.stdin.readline

setrecursionlimit(1000000)

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

    heapq.heapify(A)
    for _ in range(M):
        a = -heapq.heappop(A) // 2 # 最小値取得
        heapq.heappush(A, -a)
    
    print(-sum(A))

main()

Submission status: Accepted

Solution code:
#二分ヒープ
class binaryHeap:
    def __init__(self):
        self.ls = []
    def add(self,n):
        self.ls.append(n)
        i = len(self.ls)-1
        while True:
            parent = i // 2
            if i == 0 or self.ls[parent] > self.ls[i]:break
            else:
                self.ls[parent],self.ls[i] = self.ls[i],self.ls[parent]
                i = parent
    def pop(self):
        n = self.ls.pop()
        if len(self.ls) == 0:return n
        ans = self.ls[0]
        self.ls[0] = n
        i = 0
        while True:
            child = 0
            if 2*i >= len(self.ls):return ans
            elif 2*i+1 >= len(self.ls):child = 2*i
            elif self.ls[2*i] > self.ls[2*i+1]:
                child = 2*i
            else:
                child = 2*i+1
            if self.ls[child] <= self.ls[i]:
                return ans
            else:
                self.ls[child],self.ls[i] = self.ls[i],self.ls[child]
                i = child

n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
heap = binaryHeap()
for i in a:
    heap.add(i)
for i in range(m):
    n = heap.pop()
    n //= 2
    heap.add(n)
print(sum(heap.ls))

Submission status: Accepted

Solution code:
import heapq
import math

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

heapq.heapify(A)

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

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

print(sum(A))

Submission status: Accepted

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

import sys
import copy
import math

sys.setrecursionlimit(1000000)

# input = sys.stdin.readline

# ~~~~~~~~~~~~~~~~~~~~~_(＾～＾ ｣ ∠)_~~~~~~~~~~~~~~~~~~


import heapq

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

heapq.heapify(A)

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

ans = 0
for x in A:
    ans += -x

print(ans)

Submission status: Accepted

Solution code:
import math
import heapq

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

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

sum = 0
for a_i in a:
    sum += int(-1 * a_i)
print(sum)

Submission status: Accepted

Solution code:
import heapq
import math
n, m = map(int, input().split())
src = list(map(int, input().split()))
new_src = []
for s in src:
    new_src.append(s*-1)
heapq.heapify(new_src)

def waru(heap):
    tmp = heapq.heappop(heap)
    heapq.heappush(heap, math.ceil(tmp / 2))
    return heap
for _ in range(m):
    new_src = waru(new_src)
print(sum(new_src)*-1)

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
def negint(s):
  return int(s) * -1

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

heapify(prices)

for _ in range(M):
  heappush(prices, heappop(prices) * -1 // 2 * -1)
  
print(sum(prices) * -1)

Submission status: Accepted

Solution code:
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import sys
import logging
import heapq

logging.basicConfig(level=logging.DEBUG)

input = sys.stdin.readline

setrecursionlimit(1000000)


def main():
	n,m = map(int,input().split())
	a = list(map(int,input().split()))
	priority = PriorityQueue()
	for i in a:
		priority.push(i)
	for _ in range(m):
		mx = priority.pop()
		priority.push(mx//2)
	print(priority.sum())

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(l):
	x = l.pop()
	y = l.pop()
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	l.append(min(x,y))
	return gcd(l) if len(l) > 1 else l[0]

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

class PriorityQueue():
	def __init__(self):
		self.queue = []
	def push(self,i):
		heapq.heappush(self.queue,-i)
	def pop(self):
		return -1 * heapq.heappop(self.queue)
	def sum(self):
		return -sum(self.queue)

main()

Submission status: Accepted

Solution code:
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import sys
import logging
import heapq

logging.basicConfig(level=logging.DEBUG)

input = sys.stdin.readline

setrecursionlimit(1000000)


def main():
	n,m = map(int,input().split())
	a = list(map(int,input().split()))
	priority = []
	for i in a:
		heapq.heappush(priority,-i)
	for _ in range(m):
		mx = heapq.heappop(priority)
		heapq.heappush(priority,-(-mx//2))
	print(-sum(priority))

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(l):
	x = l.pop()
	y = l.pop()
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	l.append(min(x,y))
	return gcd(l) if len(l) > 1 else l[0]

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

main()

Submission status: Accepted

Solution code:
import heapq


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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import heapq
def func(n):
    return -n

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

    heapq.heapify(A)

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

    print(-sum(A))

main()

Submission status: Accepted

Solution code:
import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from heapq import heappush, heappop
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    stuff = []
    for x in input().split():
        heappush(stuff, -int(x))

    for i in range(M):
        heappush(stuff, -math.floor(-heappop(stuff) / 2))

    print(-sum(stuff))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq


def resolve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    query = []
    for i in range(n):
        heapq.heappush(query, -a[i])
    for i in range(m):
        nexta = -1 * heapq.heappop(query) // 2
        heapq.heappush(query, -nexta)
    print(-sum(query))


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import heapq
def solve():
  n,m = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  query = []
  for i in range(n):
    heapq.heappush(query,-1*a[i])
  for i in range(m):
    nexta = -1 * heapq.heappop(query)
    nexta //= 2
    heapq.heappush(query,-1 * nexta)

  print(-1*sum(query))
solve()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import heapq
import math

def main():
    N,M = map(int,input().split())
    c = list(map(int,input().split()))
    c = list(map(lambda x:-x,c))
    heapq.heapify(c)

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

    print(-sum(c))

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

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split(" "))
liste = list(map(int, input().split(" ")))
liste = [(-1 * i) for i in liste]
heapq.heapify(liste)
for i in range(m):
    maxi = heapq.heappop(liste)
    maxi /= 2
    heapq.heappush(liste, int(maxi))
sum = 0
for i in liste:
    sum += (-1 * i)
print(sum)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

pq = []
for i in range(n):
    heappush(pq, -a[i])

for i in range(m):
    a_max = - heappop(pq)
    if a_max == 0:
        break
    a_max //= 2
    heappush(pq, -a_max)

ans = -sum(pq)
print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M=list(map(int,input().strip().split(' ')))
A=list(map(int,input().strip().split(' ')))
A=[-x for x in A]
heapq.heapify(A)
while M>0:
    temp=heapq.heappop(A)
    temp=-temp
    temp=temp//2
    temp=-temp
    heapq.heappush(A,temp)
    M-=1

print(-sum(A))

Submission status: Accepted

Solution code:
# ABC141D - Powerful Discount Tickets
from heapq import heapify, heappop, heappush


def main():
    N, M, *A = map(int, open(0).read().split())
    H = [-i for i in A]
    heapify(H)
    pop_max, push_max = lambda: -heappop(H), lambda x: heappush(H, -x)
    for _ in range(M):
        x = pop_max()
        push_max(x // 2)
    ans = -sum(H)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC141D - Powerful Discount Tickets
from heapq import heapify, heappop, heappush


def main():
    N, M, *A = map(int, open(0).read().split())
    H = [-i for i in A]
    heapify(H)
    pop_max, push_max = lambda A: -heappop(A), lambda A, x: heappush(A, -x)
    for _ in range(M):
        x = pop_max(H)
        push_max(H, x // 2)
    ans = -sum(H)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC141D - Powerful Discount Tickets
from heapq import heapify, heappop, heappush
pop_max, push_max = lambda A: -heappop(A), lambda A, x: heappush(A, -x)


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

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

Q = [-int(x) for x in input().split()]
heapify(Q)

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

ans = 0
for i in range(N):
    ans += -heappop(Q)

print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify,heappush,heappop
from math import ceil
n,m,*a=map(int,open(0).read().split())
if n==1:
	print(a[0]//(2**m))
	exit()
a=[(-1)*x for x in a]
heapify(a)
x=heappop(a)
while m:
	y=heappop(a)
	while x<=y and m:
		x=ceil(x/2)
		m-=1
	heappush(a,x)
	x=y
heappush(a,x)
print((-1)*sum(a))