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:
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
d=[]
for i in range(m):
  if len(a)>0:
    if len(d)==0:
      d.append(a[0]//2)
      a.pop(0)
    else:
      if a[0]>=d[0]:
        d.append(a[0]//2)
        a.pop(0)
      else:
        d.append(d[0]//2)
        d.pop(0)
  else:
    if len(a)==0:
      a.append(d[0]//2)
      d.pop(0)
    else:
      if d[0]>=a[0]:
        a.append(d[0]//2)
        d.pop(0)
      else:
        a.append(d[0]//2)
        a.pop(0)
print(sum(d)+sum(a))

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)

for i in range(M):
    a=((-1*heapq.heappop(A))//2)*(-1)
    heapq.heappush(A,a)
sum=0
for i in range(N):
    sum+=A[i]
print(-sum)

Submission status: Accepted

Solution code:
import heapq
import math


def main():
    N, M = list(map(int, input().split(' ')))
    neg_A = list(map(lambda x: - int(x), input().split(' ')))  # max to min
    heapq.heapify(neg_A)
    for _ in range(M):
        min_neg_a = heapq.heappop(neg_A)
        heapq.heappush(neg_A, min_neg_a / 2)
    answer = 0
    for _ in range(N):
        neg_a = heapq.heappop(neg_A)
        answer += math.floor(-neg_a)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
import numpy as np

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

A = list(-np.array(A))
    
heapq.heapify(A)  # Aをheapに変換
for _ in range(M):
    x = heapq.heappop(A)  # Aの中の最小値を取り出して返す
    heapq.heappush(A, (-x//2)*-1)
    
print(-sum(A))

Submission status: Accepted

Solution code:
import heapq
import numpy as np

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

for i in range(N):
    A[i] *= -1
    
heapq.heapify(A)  # Aをheapに変換
for _ in range(M):
    x = heapq.heappop(A)  # Aの中の最小値を取り出して返す
    heapq.heappush(A, (-x//2)*-1)
    
print(-sum(A))

Submission status: Accepted

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

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


ans = 0
for a in range(N):
  ans += math.floor(-A[a])

print(ans)

Submission status: Accepted

Solution code:
import itertools
import sys
import math
import numpy as np
import fractions
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
from bisect import insort
import heapq
sys.setrecursionlimit(10**9)

def main():
    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かけてるので本質的にはmax
        half = min * (-1) // 2
        half *= -1
        heapq.heappush(A,half)
        # print(A)
        # print(min)

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


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_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(lambda x: int(x)*(-1), input().split()))
heapq.heapify(A)

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

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

print(sum(A))

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
import heapq

n, m = [int(x) for x in stdin.readline().rstrip().split()]
a = [int(x) for x in stdin.readline().rstrip().split()]

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

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

print(-sum(a))

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May  3 18:07:38 2020

@author: Kanaru Sato
"""
import heapq

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

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

print(-1*sum(adush))

Submission status: Accepted

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

for i in range(m):
    tmp_min = heapq.heappop(lst)
    heapq.heappush(lst, (-1)*(-tmp_min//2))  # 計算誤差の関係で-1を2回かけてます
print(-sum(lst))

Submission status: Accepted

Solution code:
import sys
import heapq


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


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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

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

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

print(-sum(A))

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: x*(-1), A))  # 各要素を-1倍

heapq.heapify(A)

if N == 1:
    MAX = heapq.heappop(A)//2**M 
    if MAX < 0:
        print(0)
    else:
        print(MAX)
    exit()

cnt = 0
while M > 0:
    MAX = heapq.heappop(A)
    if MAX % 2 == 0:
        heapq.heappush(A, MAX//2)
    else:
        heapq.heappush(A, MAX//2+1)

    M -= 1

print(-sum(A))

Submission status: Accepted

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: x*(-1), A))  # 各要素を-1倍

heapq.heapify(A)

if N == 1:
    MAX = heapq.heappop(A)//2**M 
    if MAX < 0:
        print(0)
    else:
        print(MAX)
    exit()

cnt = 0
while M > 0:
    MAX = heapq.heappop(A)
    if MAX % 2 == 0:
        heapq.heappush(A, MAX//2)
    else:
        heapq.heappush(A, MAX//2+1)

    M -= 1

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

Submission status: Accepted

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

import heapq
heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify

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

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

print(-sum(list(map(int, A))))

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

for _ in range(M):
    a = heappop(A)
    if a == 0:
        break
    a = -(-a // 2)
    heappush(A, a)

ans = -sum(A)
print(ans)

Submission status: Accepted

Solution code:
#n:shinamono no kazu
#m:waribiki maisuu
import heapq

n,m=map(int,input().split())
a=list(map(lambda x:int(x)*(-1),input().split()))
#print(temp)
heapq.heapify(a)
for _ in range(m):
  minA=heapq.heappop(a)
  #print(minA)
  heapq.heappush(a,minA/2.0)
  #print(a)
#print(a)
result=0
for item in a:
  result+=item*(-1)//1
  
print(int(result))

Submission status: Accepted

Solution code:
#ABC141D
#heapq 効率的にリストの最小値を取り出す
def main():
    import sys, heapq as h
    N, M = map(int, sys.stdin.readline().split())
    A = list(map(lambda x:-int(x), sys.stdin.readline().split()))
    #print(A)
    h.heapify(A) #heap化
    #print(A)
    for m in range(M):
        a = h.heappop(A)
        #print(int(a/2))
        h.heappush(A, int(a/2))
        #print(A)
    print(-sum(A))

if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
import os
import math
import heapq

def main():
	n,m = map(int, input().split())
	a_list = list(map(lambda x: int(x)*(-1), input().split()))
	heapq.heapify(a_list)
	
	for i in range(m):
		max_num = heapq.heappop(a_list)*(-1)
		heapq.heappush(a_list, (max_num//2)*(-1))

	print((-1)*sum(a_list))

		

if __name__ == "__main__":
	main()

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

Submission status: Accepted

Solution code:
import heapq  # 優先度付きキュー
# def solve():  # TLE
#     n, m = map(int, input().split())
#     # O(nlog(n))
#     a = sorted(list(map(int, input().split())))
#     # 最大の値でチケットを使う
#     # まだ最大かどうか考慮Y：もう一度使うN:バイナリーサーチをかけてリストをソートする
#     # O(m)
#     for i in range(m):
#         a[len(a)-1] //= 2
#         if a[len(a)-1] < a[len(a)-2]:
#             # O(log2m)
#             a = binary_search(a, a[len(a)-1])
#     return sum(a)


def solve():
    n, m = map(int, input().split())
    a = list(map(lambda x: int(x)*-1, input().split()))
    heapq.heapify(a)  # aを優先度付きキューに変更
    for _ in range(m):  # _　iで注意が出ない(インスタンスを作らない)
        tmp_min = heapq.heappop(a)  # aの最大の値のpop
        heapq.heappush(a, (-1)*(-tmp_min//2))  # 計算誤差が生じるため(//2の返り値はintのため)
    return -sum(a)


def binary_search(lst, num):
    lst.pop(len(lst)-1)
    left, right = 0, len(lst)-1
    while left <= right:
        mid = (left + right)//2
        if lst[mid] < num:
            left = mid + 1
        else:
            right = mid-1
    lst.insert(mid, num)
    return lst


ans = solve()
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 = heapq.heappop(A)
    a /= 2
    heapq.heappush(A,a)
s = 0
for i in A:
    i = int(i*(-1))
    s += i
print(s)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N, M, *A = map(int, open(0).read().split())

q = []
for v in A:
    heappush(q, -v)
    
for _ in range(M):
    v = heappop(q)
    heappush(q, -(-v // 2))
    
print(-sum(q))

Submission status: Accepted

Solution code:
from sys import stdin
import heapq

[N,M] = [int(x) for x in  stdin.readline().rstrip().split()]
#heapqは最小値ヒープなので、ここで符号を逆転させる
def reverse(a):
    return -1*int(a)
As = [reverse(x) for x in  stdin.readline().rstrip().split()]


#単純に考えて、一番高いものに割引券を使うことを繰り返せばよい
#つまり、ヒープを使えば効率が良い
#M回割引券を使うわけなんだけれど、一回の操作での計算量はO(logN)なので、
#合計の計算量はO(MlogN)である。

heapq.heapify(As)

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

#値を切り捨て
As = [int(x)*-1 for x in As]
print(sum(As))

Submission status: Accepted

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

for _ in range(m):
    temp = math.ceil(heapq.heappop(A)/2)
    A.append(temp)

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

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)

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import heapq
def main():
    n,m=map(int,input().split())
    A=[int(_) for _ in input().split()]
    A=list(map(lambda x:-x,A))
    heapq.heapify(A)
    for _ in range(m):
        x=heapq.heappop(A)
        heapq.heappush(A,-(-x//2))
    print(-sum(A))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heapify,heappop,heappush

n,m=map(int,input().split())
a=[-int(a) for a in input().split()]
heapify(a)
for _ in range(m):
    heappush(a,heappop(a)/2)
print(-sum(int(x) for x in a))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(lambda x:-int(x),input().split()))
import heapq  # heapqライブラリのimport
heapq.heapify(a)
for _ in range(m):
  ai=heapq.heappop(a)
  heapq.heappush(a, (ai+2-1)//2)
print(-sum(a))
#print(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*(-1), A))

heapq.heapify(A)

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

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

Submission status: Accepted

Solution code:
import heapq
import numpy as np
N, M = map(int,input().split())

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

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

print(sum(np.array(A) * -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)         
k=m
while k>0:
  b=heapq.heappop(a)*(-1)//2  
  heapq.heappush(a, b*(-1))   
  k-=1
print(sum(a)*(-1))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify


def main():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    hq = [(-1) * i for i in A]
    heapify(hq)
    cnt = 0
    while cnt < m:
        a = (-1) * heappop(hq)
        a //= 2
        heappush(hq, (-1) * a)
        cnt += 1
    print((-1) * sum(hq))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

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

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

# ----- heapq ここから-----
import heapq
class Reverse:
    def __init__(self, val):
        self.val = val
        
    def __lt__(self, other):
        return self.val > other.val
        
    def __repr__(self):
        return repr(self.val)
    
class Heapq:
    def __init__(self, arr, desc = False):
        if desc:
            for i in range(len(arr)):
                arr[i] = Reverse(arr[i])
        self.desc = desc
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        if self.desc: return heapq.heappop(self.hq).val
        else: return heapq.heappop(self.hq)
 
    def push(self, a):
        if self.desc: heapq.heappush(self.hq, Reverse(a))
        else: heapq.heappush(self.hq, a)
 
    def top(self):
        if self.desc: self.hq[0].val
        else: return self.hq[0]
# ----- heapq ここまで-----

n,m = myinput()
a = list(myinput())

hq = Heapq(a,desc=True)

for i in range(m):
    M = hq.pop()
    hq.push(M//2)

ans = 0
for i in range(n):
    ans += hq.pop()
    
print(ans)

Submission status: Accepted

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

import heapq
heapq.heapify(a)

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

import math
c = list(map(lambda x:x*(-1),a))
print(sum(list(map(math.floor,c))))

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):
    temp=heapq.heappop(A)
    heapq.heappush(A,temp//2+temp%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
#print(A)
heapq.heapify(A)
for i in range(M):
    temp=heapq.heappop(A)
#    print(temp)
    heapq.heappush(A,temp//2+temp%2)
    
print(-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*(-1), a))
heapq.heapify(a)

count_use = 0
while count_use < m:
    max_a = heapq.heappop(a)
    max_a = -1*((-1*max_a)//2)
    #print(max_a)
    heapq.heappush(a, max_a)
    count_use += 1

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

Submission status: Accepted

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



if __name__ == "__main__":
    main()

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))
A.sort()

for _ in range(M):
  n=heapq.heappop(A)
  n=-(-n//2)
  heapq.heappush(A,n)
print(-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):
  min = heapq.heappop(a)
  heapq.heappush(a, (-min//2)*(-1))
print(-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 _ in range(M):
    discount = (-1) * heapq.heappop(A)
    discount //= 2
    heapq.heappush(A, -discount)

print(-sum(A))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from heapq import heappop, heappush
    N, M = map(int, input().split())
    A = []
    for a in input().split():
        heappush(A, (-1) * int(a))
    for _ in range(M):
        a = (-1) * heappop(A)
        a //= 2
        heappush(A, -a)
    print((-1) * sum(A))


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

Submission status: Accepted

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

for i in range(len(aa)):
    aa[i] = -aa[i]
heapq.heapify(aa)

for i in range(m):
    v = heapq.heappop(aa)
    heapq.heappush(aa,-(-v // 2))
cost = 0
for i in range(len(aa)):
    cost -=heapq.heappop(aa)
print(cost)

Submission status: Accepted

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

def solve(N: int, M: int, A: "List[int]"):
    A = [a*-1 for a in A]
    heapq.heapify(A)
    for m_ in range(M):
        a_ = heapq.heappop(A)
        heapq.heappush(A, int(a_/2))    
    print(sum(A)*-1)

    return



# Generated by 1.1.6 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:
n, m = map(int, input().split())
aa = list(map(int, input().split()))

from queue import PriorityQueue

q = PriorityQueue()
for a in aa:
    q.put(-a)
for i in range(m):
    g = q.get()
    q.put(-(-g // 2))
cost = 0
for a in aa:
    cost -=q.get()
print(cost)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()

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

for _ in range(M):
    val = heappop(A)
    if val == 0:
        break
    heappush(A, (val+1)//2)

print(-1 * sum(A))

Submission status: Accepted

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

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


if __name__ == '__main__':
    main()

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
n,m=map(int,input().split())
a=list(map(lambda x: int(x)*(-1),input().split()))
heapq.heapify(a)

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

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)

n, m = map(int, input().split())
li = [(-1)*int(x) for x in input().split()]
heapify(li)
for _ in range(m):
    temp = heappop(li)
    temp *= -1
    temp //= 2
    temp *= -1
    heappush(li, temp)

print((-1)*sum(li))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq as hp
N,M=map(int,input().split())
price_list=sorted([-1*int(item) for item in input().split()])
total_m=0
def discount(price_list,tickets_num):
    total_ticket =0
    hp.heapify(price_list)

    while total_ticket < tickets_num:
        temp = hp.heappop(price_list)
        hp.heappush(price_list,-1*(-1*temp//2))
        total_ticket+=1
    return price_list

res = discount(price_list,M)
print(-1*sum(res))

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

import heapq
n, m = lr()
a = list(map(lambda x: - int(x), input().split()))
heapq.heapify(a)
for i in range(m):
    b = heapq.heappop(a) * (-1)
    b //= 2
    heapq.heappush(a, -b)
print(-sum(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 i in range(m):
    b = heapq.heappop(a) * (-1)
    b //= 2
    heapq.heappush(a, -b)
print(-sum(a))

Submission status: Accepted

Solution code:
import heapq

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

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

ans=0
for i in range(N):
    item=heapq.heappop(pq)
    ans+=int(abs(item))

print(ans)

Submission status: Accepted

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

for i in range(m):
    largest = heapq.heappop(B)
    heapq.heappush(B, -(-largest//2))
    
ans = 0
for i in range(n):
    ans += -heapq.heappop(B)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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

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

heapq.heapify(a)

num = 0
hq = 1

while num < M and hq != 0:
    hq = -heapq.heappop(a)
    hq2 = hq // 2
    heapq.heappush(a, -hq2)
    num += 1

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq as hp
def solution():
    n, m = map(int, input().split())
    a = [int(aa) * -1 for aa in input().split()]
    hp.heapify(a)
    for i in range(m):
        hp.heappush(a, (hp.heappop(a)*-1 // 2) * -1)
    print(abs(sum(a)))

solution()

Submission status: Accepted

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

m_count = 0
while True:
    max_price = a_l[0]//2
    for j in range(n):
        if a_l[j] >= max_price:
            a_l[j] //= 2
            m_count += 1
            if m_count == m:
                break
        else:
            break
        if m_count == m:
            break
    a_l.sort(reverse=True)
    if m_count == m:
        break

ans = 0
for i in range(n):
    ans += a_l[i]
print(ans)

Submission status: Accepted

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

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

for i in range(n):
    t[i] = -t[i]

t.sort()

for i in range(m):
    x=heapq.heappop(t)
    x = -x
    x = int(x/2)
    heapq.heappush(t,-x)
    #print(t)
print(-sum(t))

Submission status: Accepted

Solution code:
import heapq
from math import ceil

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

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

for _ in range(m):
    temp = ceil(heapq.heappop(a_list) / 2)
    heapq.heappush(a_list, temp)
print(-sum(a_list))

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

Submission status: Accepted

Solution code:
# solution
import io
import math
import heapq
import bisect

n,m = (int(x) for x in input().split())

a = [int(i)*(-1) for i in input().split()]
heapq.heapify(a)
for _ in range(m):

    b  = -(heapq.heappop(a))//2
    heapq.heappush(a,-b)
print(-sum(a))

Submission status: Accepted

Solution code:
import heapq

N,M=map(int,input().split())
B=list(map(int,input().split()))
def hu(n):
    return n*(-1)
A=list(map(hu,B))
heapq.heapify(A)
for i in range(M):
    x=heapq.heappop(A)/2
    heapq.heappush(A,x)
A1=list(map(int,A))
print(-sum(A1))

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
class HeapQue(object):
    def __init__(self, iterable, max_heap=False):
        self.sign = -1 if max_heap else 1
        sequence = [number * self.sign for number in iterable]
        heapify(sequence)
        self.heapque = sequence

    def push(self, item):
        heappush(self.heapque, item * self.sign)

    def pop(self):
        return heappop(self.heapque) * self.sign

    def dump(self):
        return [heappop(self.heapque) * self.sign for _ in range(len(self.heapque))]

N, M = map(int, input().split())
heap = HeapQue(map(int, input().split()), max_heap=True)
for _ in range(M):
    heap.push(heap.pop() >> 1)
print(sum(heap.dump()))