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 math  # noqa
import bisect  # noqa
import queue  # noqa


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

    que = queue.PriorityQueue()
    for a in A:
        que.put(-a)

    while M > 0:
        M -= 1
        a = que.get()
        que.put(-(-a // 2))

    ans = 0
    while not que.empty():
        ans += -que.get()

    print(ans)

Submission status: Accepted

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

from collections import Counter
import heapq
Ad = dict(Counter(A))
keys = [-k for k in Ad.keys()]
heapq.heapify(keys)

tk = m
while tk > 0 and len(keys) > 0:
  key = -1 * keys[0]
  n = Ad[key]

  if n > tk:
    Ad[key] -= tk
    if Ad.get(key//2) != None:
      Ad[key//2] += tk
    else:
      Ad[key//2] = tk
    tk = 0
    break

  else:
    Ad[key] = 0
    heapq.heappop(keys)
    if Ad.get(key//2) != None:
      Ad[key//2] += n
    else:
      Ad[key//2] = n
      heapq.heappush(keys, -1 * (key//2))
    tk -= n

ans = 0
for kv in Ad.items():
  ans += kv[0] * kv[1]
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):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a,-1*(-tmp_min//2))
print(-sum(a))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc141/tasks/abc141_d
from copy import deepcopy
from heapq import heappop, heappush, heapify
n, m = map(int, input().split())

items = [-int(i) for i in input().split()]
heapify(items)
while m:
    m -= 1
    item = -1 * heappop(items)
    item //= 2
    heappush(items, -1 * item)
pay = 0
for i in items:
    pay += -1 * i
print(pay)

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

Submission status: Accepted

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

import heapq
#n 買う商品数
#m 割引券の数
#a 値段
heapq.heapify(a)
while True:
   # print(a)
    tmp = (-1) * heapq.heappop(a) //2
    heapq.heappush(a,-1 * tmp)
    m -= 1
    if m == 0:
        break
print(-1*sum(a))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = list(map(int, input().split()))
import heapq
class Heapq:
    # 最大値を取り出す際は desc=True に設定
    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
    
hp = Heapq(a, desc=True)
for i in range(M):
    max_ = hp.pop() // 2
    hp.push(max_)
    
ans = 0
for i in range(N):
    #print(hp.top())
    ans += hp.pop()
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = list(map(int, input().split()))
import heapq
class Heapq:
    # 最大値を取り出す際は desc=True に設定
    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
    
hp = Heapq(a, desc=True)
for i in range(M):
    max_ = hp.pop() // 2
    hp.push(max_)
    
ans = 0
for i in range(N - 1):
    #print(hp.top())
    ans += hp.pop()
print(ans + hp.top())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
#from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
#from math import floor, ceil
#from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
#inf = 10**17
#mod = 10**9 + 7

n,m=MI()
As=LI()
for i in range(n):
    As[i]*=-1
    
#print(As)

heapify(As)
for i in range(m):
    mn=heappop(As)
    mn=(abs(mn)//2)*(-1)
    heappush(As,mn)

print(-sum(As))

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

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] *= (-1)
heapq.heapify(a)

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

Submission status: Accepted

Solution code:
import heapq
import math

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

# 各要素に1掛ける
A = list(map(lambda x: x * -1, A))
heapq.heapify(A)

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

print(sum(A) * -1)

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

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq
def main():
    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*(-tmp_min//2))
    print(-sum(a))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import heapq

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

Submission status: Accepted

Solution code:
import heapq

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

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

heapq.heapify(a)

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

print(-1 * sum(a))

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

print(sum(a)*-1)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

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

    heapify(a)
    while m:
        b = heappop(a)
        b = (-b)//2
        heappush(a, -b)
        m -= 1
    print(-sum(a))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import *
n, m = map(int,input().split())
a = list(map(int,input().split()))
a = list(map(lambda x:x * (-1), a))
heapify(a)

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

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq
from math import ceil
n,m = map(int,input().split())
A = list(map(int,input().split()))
hq = list(map(lambda x:-1*x ,A))
heapq.heapify(hq)

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

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

n, m = map(int, input().split())
A = list(map(int, input().split()))
H = []
for a in A:
    heappush(H, -a)
for i in range(m):
    b = heappop(H)
    b *= -1
    b //= 2
    heappush(H, -b)
goukei = sum(H)
print(-goukei)

Submission status: Accepted

Solution code:
def main():
  import heapq
  n,m = map(int,input().split())
  a =sorted(list(map(lambda x: int(x)*(-1),input().split())))
  heapq.heapify(a)
  for _ in range(m):
    x=heapq.heappop(a)/2
    heapq.heappush(a,x) 
  print(int(sum((-1)*i//1 for i in a)))
if __name__=='__main__':
  main()

Submission status: Accepted

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

# priority queue を使う
# 最小値を取り出す、要素を挿入する
heapify(A_minus)

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

Submission status: Accepted

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

for _ in range(M):
  a = heapq.heappop(q)
  heapq.heappush(q, a/2)
ans = 0 
for p in q:
  ans += int(-p)
print(ans)

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()))

#A = list(map(lambda x: x * (-1), A))
A = [-i for i in A]
heapq.heapify(A)

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

print(sum(A) * (-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()))

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

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

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

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
p = a.pop()
sub = deque([p//2])
for i in range (m-1):
    if (len(a) != 0):
        if (a[-1] >= sub[-1]):
            x =a.pop()
            sub.appendleft(x//2)
        else:
            x =sub.pop()
            sub.appendleft(x//2)
    else:
        x =sub.pop()
        sub.appendleft(x//2)
print(sum(a)+sum(sub))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
n,m = map(int,input().split())
a_ls = list(map(int, input().split()))

a_ls = list(map(lambda x: -x, a_ls))
hq = []
for i in range(n):
    heappush(hq,a_ls[i])
for _ in range(m):
    target = heappop(hq)
    target = -(-target//2)
    heappush(hq, target)
print(-sum(hq))

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [-1 * i for i in a]
heapq.heapify(a)
cnt = 0
while cnt < m:
    x = heapq.heappop(a) * -1
    x = x // 2
    cnt += 1
    heapq.heappush(a, x * -1)
print(sum(a) * -1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations
# from itertools import combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    N,M=map(int,input().split())
    A=list(map(int,input().split()))
    A = [-a for a in A]  # プライオリティキューで最大値を取り出す処理を実施するために正負反転
    heapify(A)  # プライオリティキューに変換

    for i in range(M):
        M=heappop(A)
        M=M/2
        heappush(A,M)
    print(sum([int(-a) for a in A]))  # 最後にまた正負反転






resolve()

Submission status: Accepted

Solution code:
from math import ceil
from heapq import heapify, heappop, heappush
N,M = map(int, input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))
heapify(A)
while M>0:
    temp = heappop(A)
    heappush(A, temp/2)
    M-=1
print(-sum(map(ceil, A)))

Submission status: Accepted

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

hp = []
for x in a:
    item = (-x, x, 0)
    heapq.heappush(hp, item)

for i in range(m):
    (neg_cost, full_price, n) = heapq.heappop(hp)
    new_cost = full_price // (2 ** (n+1))
    item = (-new_cost, full_price, n+1)
    heapq.heappush(hp, item)

print(sum([-c for (c, _, _) in hp]))

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

Submission status: Accepted

Solution code:
import heapq

N_ko, M_mai = map(int, input().split())
prices = list(map(int, input().split()))
prices = [-1 * i for i in prices]

heapq.heapify(prices)

for i in range(M_mai):
    p = abs(heapq.heappop(prices))
    
    p = -1 * (p // 2)

    heapq.heappush(prices, p)

summ = -1 * sum(prices)

print(summ)

Submission status: Accepted

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

import heapq
heapq.heapify(A)
while M:
    a = heapq.heappop(A)
    heapq.heappush(A, -1 * (-1 * a // 2))
    M -= 1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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

h = [-a for a in aa]
heapq.heapify(h)
for _ in range(m):
    x = h[0]
    heapq.heapreplace(h, -(-x // 2))

print(sum([-hh for hh in h]))

Submission status: Accepted

Solution code:
import heapq

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

h = [(-a, a) for a in aa]
heapq.heapify(h)
for _ in range(m):
    x = h[0]
    c = x[1] // 2
    x = (-c, c)

    heapq.heapreplace(h, x)

print(sum([-hh[0] for hh in h]))

Submission status: Accepted

Solution code:
import collections
import sys
import numpy as np
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
#入力
#解答
#出力
#Priority-queue
class PriorityQueue:

    def __init__(self,heap):
        self.heap = heap
        heapify(self.heap)
    
    def push(self,item):
        heappush(self.heap,item)
    
    def pop(self):
        return heappop(self.heap)
    
    def pushpop(self,item):
        return heappushpop(self.heap,item)
    
    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)

n,m = map(int,input().split())
A = sorted(list(map(int,input().split())))
heap = []
q = PriorityQueue(heap)
for i in range(n):
    q.push(-A[i])

for i in range(m):
    a = q.pop()
    a *= -1
    a //=2
    a *= -1
    q.push(a)
print(-1*sum(heap))

Submission status: Accepted

Solution code:
import heapq
pq = []

N, M = map(int, input().split())
A = list(map(int, input().split()))
for i in A:
  heapq.heappush(pq, -i)
for i in range(M):
  x = pq[0]
  heapq.heappop(pq)
  heapq.heappush(pq, -((-x)//2))
print(-sum(pq))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush, heapify
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
from functools import reduce
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm_base(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def main():
  N, M = map(int,readline().split())
  A = [0]*N
  for i, x in enumerate(map(int,readline().split())):
    A[i] = -x
  heapify(A)
  for _ in range(M):
    x = heappop(A)
    x = -((-x)//2)
    heappush(A, x)
  print(-sum(A))

  
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import heapq
import numpy as np
from math import ceil

n, m = map(int, input().split())
a = np.array(list(map(int, input().split())))
a = a * (-1)
a = list(a)
heapq.heapify(a)

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

print(-1*sum(a))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 12 00:27:20 2020

@author: Kanaru Sato
"""

import heapq

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

a = [-1*i for i in a]
heapq.heapify(a)
sum = 0

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

sum = 0
for i in range(len(a)):
    sum += -1*a[i]

print(sum)

Submission status: Accepted

Solution code:
import heapq

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

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

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq as hq
n, m = map(int, input().split())
items = [-int(i) for i in input().split()]
hq.heapify(items)
for _ in range(m):
    max_val = hq.heappop(items)
    hq.heappush(items, -(-max_val // 2))
print(-sum(items))

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
A = list(map(lambda x:-int(x), input().split()))
#print([bin(val) for val in A])

heapq.heapify(A)
#print(A)

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

Submission status: Accepted

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

import heapq
heapq.heapify(mvals)

for _ in range(M):
    price = heapq.heappop(mvals)
    heapq.heappush(mvals, price / 2)

res = sum(map(lambda x:int(-x), mvals))
print(res)

Submission status: Accepted

Solution code:
#from operator import itemgetter
#from collections import Counter
import heapq
#N = int(input())
N, M = map(int, input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))
#A = [int(input()) for i in range(N)]

heapq.heapify(A)

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

Submission status: Accepted

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

print(-1*sum(A))

Submission status: Accepted

Solution code:
import queue

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

q = queue.PriorityQueue()
for k in a:
  q.put(k)
  
for _ in range(m):
  q.put(-(-q.get()//2))
  
ans = 0
for _ in range(n):
  ans += q.get()
  
print(-ans)

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(a)

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

print(-sum(a))

Submission status: Accepted

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

Submission status: Accepted

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

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

for a_ in a:
    heappush(A,a_) 

for _ in range(M):
  maxA = ceil(heappop(A)/2)
  A.append(maxA)
print(-sum(A))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
from heapq import heappush, heappop

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

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

for i in range(m):
    a = heappop(heap)
    a = int(a / 2)
    heappush(heap,a)


print(-sum(heap))

Submission status: Accepted

Solution code:
import sys
import numpy as np
import bisect

N, M = map(int, sys.stdin.readline().split())
A = np.array(list(map(int, sys.stdin.readline().split())))
A.sort()

max = A[N - 1]

count = 0

while count < M:
    max = A[N - 1]
    c = bisect.bisect_left(A, int(max / 2))
    add = N - c
    if count + add > M:
        d = M - count
        A[-d:] = A[-d:] // 2
        break
    else:
        A[c:] = A[c:] // 2
        count += add
        if count == M:
            break
    A.sort()
    
ans = int(sum(A))

print(ans)

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#優先度付きキュー -> 最小値をO(logN)で取り出す
import heapq

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

a = [-x for x in a]

#aを優先度付きキューに変更
heapq.heapify(a)

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

Submission status: Accepted

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

List = list(map(lambda x: x*(-1), List))  # 各要素を-1倍

heapq.heapify(List)
for i in range(m):
  max = heapq.heappop(List)
  heapq.heappush(List, int(max/2))  # 要素の挿入
print(sum(List)*(-1))

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










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

Submission status: Accepted

Solution code:
import heapq
import sys

input = sys.stdin.readline


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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,M=nm()
A=nl()
h=[]
for i in A:
    heapq.heappush(h,-1*i)

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

Submission status: Accepted

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

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

total = -sum(A)
print(total)

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

Submission status: Accepted

Solution code:
import sys

N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
m = A[0]
seg = [1]

t = 1
while(True):
    t *= 2
    if t > m:
        break
    seg.append(t)

c = 0
for i in range(-1,-len(seg)-1,-1):
    for j in range(N):
        if A[j] < seg[i]:
            break
        A[j] = A[j]//2
        c += 1
        if c == M:
            print(sum(A))
            sys.exit()
    A.sort(reverse=True)

print(sum(A))

Submission status: Accepted

Solution code:
def left(i):
  return 2 * i + 1

def right(i):
  return 2 * i + 2

def parent(i):
  return (i - 1) // 2

def swap(items, i, j):
  items[i], items[j] = items[j], items[i]
  
def bubble_up(items, i):
  p = parent(i)
  while i > 0 and items[i] > items[p]:
    swap(items, i, p)
    i = p
    p = parent(i)
    
def heappush(items, item):
  items.append(item)
  bubble_up(items, len(items) - 1)
  
def tricle_down(items, i):
  while True:
    j = -1
    r = right(i)
    if r < len(items) and items[r] > items[i]:
      l = left(i)
      if items[l] > items[r]:
        j = l
      else:
        j = r
    else:
      l = left(i)
      if l < len(items) and items[l] > items[i]:
        j = l
    if j >= 0:
      swap(items, i, j)
    i = j
    if i < 0:
      break
  
def heappop(items):    
  x = items[0]
  items[0] = items[-1]
  items.pop()
  tricle_down(items, 0)
  return x

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

items = []
for x in input().split():
  heappush(items, int(x))

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

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop


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

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

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

Submission status: Accepted

Solution code:
#n=int(input())
n,m=map(int,input().split())
al=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

import math 
import heapq

hq=[(-1)*val for val in al]
heapq.heapify(hq)

for i in range(m):
    mx=(-1)*(heapq.heappop(hq))
    newval=math.floor(mx/2)
    heapq.heappush(hq,(-1)*newval)

print(-sum(hq))

Submission status: Accepted

Solution code:
from heapq import (
    heapify,  # 優先度付きキューの生成
    heappop,
    heappush,
    heappushpop,
    heapreplace
    )

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

#heapqは最小値しか取り出さないので-1倍する
A = [-i for i in map(int,input().split())]
heapify(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq
import math
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
logof2=[0]*N
mi=0
buf=0
#print(A)
for i in range(N):
    A[i]=-A[i]  #heapqは実装上最初値しか取り出さないので、数列を-1倍し、最小値が最大に当たるようにする
heapq.heapify(A)#priority_que化
for i in range(M):
    buf=heapq.heappop(A)    #最大値を取り出すことに相当
    buf=buf/2            #切り捨て(floor)の挙動は負数の時おかしくなるので一旦正値に変換して計算し
    heapq.heappush(A,buf)   #
    #print(A)
for i in range(N):
    mi=mi+math.floor(-1*A[i])  #残った要素ごとの足し算に相当する

print(mi)

Submission status: Accepted

Solution code:
import heapq
import math
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
logof2=[0]*N
mi=0
buf=0
#print(A)
for i in range(N):
    A[i]=-A[i]  #heapqは実装上最初値しか取り出さないので、数列を-1倍し、最小値が最大に当たるようにする
heapq.heapify(A)#priority_que化
for i in range(M):
    buf=heapq.heappop(A)    #最大値を取り出すことに相当
    buf=-(-buf)/2            #切り捨て(floor)の挙動は負数の時おかしくなるので一旦正値に変換して計算し
    #buf=-buf                #負数に戻す
    heapq.heappush(A,buf)   #
    #print(A)
for i in range(N):
    mi=mi+math.floor(-1*A[i])  #残った要素ごとの足し算に相当する

print(mi)