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:
'''
標準入力
4 4
1 9 3 5
'''

n,m=list(map(int, input().split()))
a=list(map(int, input().split()))
b=[-a[i] for i in range(n)]
#print(b) => [-1, -9, -3, -5]

import heapq
heapq.heapify(b)
#print(b) => [-9, -5, -3, -1]

for i in range(m):
	maximum=heapq.heappop(b)
#forなしでprint(maximum) => -9
	
	maximum=-(-maximum//2)
	heapq.heappush(b,maximum)
print((sum(b))*(-1))

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)

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

Submission status: Accepted

Solution code:
# https://juppy.hatenablog.com/entry/2018/11/08/%E8%9F%BB%E6%9C%AC_python_%E3%83%97%E3%83%A9%E3%82%A4%E3%82%AA%E3%83%AA%E3%83%86%E3%82%A3%E3%82%AD%E3%83%A5%E3%83%BC_heapq_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3
n, m = map(int, input().split())
a = list(map(int, input().split()))
A = [-int(x) for x in a]

import heapq
heapq.heapify(A)

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

Submission status: Accepted

Solution code:
#標準入力
N, M = map(int, input().split())
A = list(map(int, input().split()))
#heapqをimportして、Aの要素をすべてマイナスにしてheapify
import heapq
def minus(n):
    return -n
A = list(map(minus, A))
heapq.heapify(A)
#その最小値を出力して削除し、その半分を追加することをM回やる
for i in range(M):
    heapq.heappush(A, -(-heapq.heappop(A)//2))
#Aの要素を合計してminusして出力する
print(minus(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 _ in range(m) :
    max = heapq.heappop(a)
    heapq.heappush(a, -(-max // 2))

print(-sum(a))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# abc141/abc141_d
import sys
import heapq

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, M = i2nn()
    h = [-int(s) for s in sys.stdin.readline().rstrip().split()]
    heapq.heapify(h)
    for _ in range(M):
        heapq.heapreplace(h, -(-h[0] // 2))
    print(-sum(h))

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# abc141/abc141_d
import sys
import heapq

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, M = i2nn()
    h = [-int(s) for s in sys.stdin.readline().rstrip().split()]
    heapq.heapify(h)
    for _ in range(M):
        top_h = -(-h[0] // 2)
        heapq.heapreplace(h, top_h)
    print(-sum(h))

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)
    replace = lambda: heappush(H, -(-heappop(H) // 2))
    for _ in range(M):
        replace()
    ans = -sum(H)
    print(ans)


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)

tmp = 0
for i in range(M):
    # 商を求める際に一旦、正の数に変換
    tmp = (heapq.heappop(a)*(-1)) // 2
    # 負の数に変換して元に戻す
    heapq.heappush(a, -tmp)

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

Submission status: Accepted

Solution code:
import heapq
def f(str):
    return -int(str)

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

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

print(-sum(A))

Submission status: Accepted

Solution code:

N, M = map(int,input().split())
A = list(-int(i) for i in input().split())
import heapq

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

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, A))
heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
# D - Powerful Discount Ticket
from heapq import heappush, heappop
N, M = map(int, input().split())
A = list(map(int, input().split()))

queue = []
for a in A:
    heappush(queue, -a)
    
for _ in range(M):
    tmp = heappop(queue)
    heappush(queue, int(tmp / 2))
    
ans = 0
for _ in range(N):
    ans -= heappop(queue)
    
print(ans)

Submission status: Accepted

Solution code:
class heap():
    def __init__(self, maxcom=True):
        if maxcom:
            self.compare = lambda x, y: x > y
        else:
            self.compare = lambda x, y: x < y

    def heappush(self, x, heap):
        heap.append(x)
        length = len(heap)
        pointer = length
        while True:
            if pointer == 1:
                break
            if self.compare(heap[pointer - 1], heap[(pointer >> 1) - 1]):
                heap[pointer - 1], heap[(pointer >> 1) - 1] = heap[(pointer >> 1) - 1], heap[pointer - 1]
                pointer = pointer >> 1
            else:
                break

    def heapreplace(self, function, heap):
        heap[0] = function(heap[0])
        pointer = 1
        length = len(heap)
        while True:
            if (pointer << 1) > length:
                break
            elif (pointer << 1) + 1 > length :
                if self.compare(heap[(pointer << 1) - 1], heap[pointer - 1]):
                    heap[(pointer << 1) - 1], heap[pointer - 1] = heap[pointer - 1], heap[(pointer << 1) - 1]
                else:
                    break
            else:
                if self.compare(heap[(pointer << 1) - 1], heap[pointer << 1]):
                    next_pointer = pointer << 1
                else:
                    next_pointer = (pointer << 1) + 1
                if self.compare(heap[next_pointer - 1], heap[pointer - 1]):
                    heap[next_pointer - 1], heap[pointer - 1] = heap[pointer - 1], heap[next_pointer - 1]
                    pointer=next_pointer
                else:
                    break


n, m = map(int, input().split())
a = map(int, input().split())
heapq = []
heapc=heap(True)
for i in a:
    heapc.heappush(i,heapq)
for _ in range(m):
    heapc.heapreplace(lambda x:x>>1,heapq)
print(sum(heapq))

Submission status: Accepted

Solution code:
import heapq

N, M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
#print(N, M)
#print(A)

A = [-i for i in A]

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

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

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

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

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq


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

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

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

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

n, m = map(int,input().split())
q = Heapq(list(map(int,input().split())),True)
for i in range(m):
    q.push(q.pop()//2)
ans = 0
for i in range(n):
    ans += q.pop()
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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

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

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

Submission status: Accepted

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

q=[]
for x in a:
  heappush(q,-x)
  
for i in range(m):
  temp=-heappop(q)
  heappush(q,-(temp//2))
  
print(-sum(q))

Submission status: Accepted

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

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

# invert sign of p to get max value
prices = [ -p for p in map(int, input().split(' ')) ]
heapify(prices)

for _ in range(m):
    p = heappop(prices)
    heappush(prices, p / 2)

total = 0
while prices:
    total += math.floor(-heappop(prices))
print(total)

Submission status: Accepted

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

print(-sum(q))

Submission status: Accepted

Solution code:
import heapq

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

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

print(-1 * sum(A))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify

obj = input().strip().split(' ')
N, M = map(int, obj)

obj = input().strip().split(' ')
val_list = [-1 * item for item in list(map(int, obj))]

heapify(val_list)

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

print(-1 * sum(val_list))

Submission status: Accepted

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

print(-sum(q))

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*A[i]
heapq.heapify(A)
for i in range(M):
    q=heapq.heappop(A)
    q=q/2
    heapq.heappush(A,q)
for i in range(N):
    A[i]=-1*int(A[i])
print(sum(A))

Submission status: Accepted

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

#%%

# n, m, a = 3, 3, [1,2,3,4,7,9, 10,8,16,14]

#%%
max_heap = [a[0]]
#%%
def add_heap(array, number):
    array.append(number)

    def swap(array, number, idx):
        if idx == 1:
            return array[idx-1]

        ai = array[idx-1]
        target_idx = (idx//2)
        target = array[target_idx-1]
        
        if ai >= target:
            array[idx-1], array[target_idx-1] =  target, ai

            number = swap(array, number, target_idx)
        else:
            return array[idx-1]

    return swap(array, number, len(array))


#%%
for ai in a[1:]:
    add_heap(max_heap, ai)

#%%
for _ in range(m):
    
    #half
    max_heap[0] //= 2
    
    def sort_heap(array, number, idx):
        top = number
        left_idx = idx*2
        right_idx = idx*2 + 1
        
        if left_idx > len(array):
            left = -1
        else:
            left = array[left_idx - 1]

        if right_idx > len(array):
            right = -1
        else:        
            right = array[right_idx - 1]

        if top >= left and top >= right:
            return array
        elif left > right:
            array[idx-1], array[left_idx-1] = left, top
            sort_heap(array, top, left_idx)
        else:
            array[idx-1], array[right_idx-1] = right, top
            sort_heap(array, top, right_idx)

    sort_heap(max_heap, max_heap[0], 1)

#%%
print(sum(max_heap))

#%%

Submission status: Accepted

Solution code:
import math
import heapq

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

hq = []
for i in range(n):
  heapq.heappush(hq, a[i]*(-1))

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

ans = 0
for i in hq:
  ans += i *(-1)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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



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

print(-sum(L))

Submission status: Accepted

Solution code:
# D - Powerful Discount Tickets
import heapq

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

pq = []

for i in data:
    heapq.heappush(pq, -i)

for _ in range(m):
    # 先頭の "最小値"
    p = heapq.heappop(pq)
    heapq.heappush(pq, -(-p // 2))

print(-sum(pq))

Submission status: Accepted

Solution code:
#coding:utf-8
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
#heapqで最大値をとる際は一度マイナスにしてから
a = [-1 * i for i in a]

#その時買うものリストにある最高額に対して、割引券を1枚ずつ使う
#ただし愚直にやるとTLEのため、優先度付きキューを使う

#入力リストをheap化する
heapq.heapify(a)

#割引券の枚数分だけ、最高額を抽出し、割引券を使う
for i in range(0, m):
    #当時の最高額をheappopで取り出して割引後の価格を出す
    discount = (heapq.heappop(a) * (-1)) // 2
    #heappushで割引後の価格をリストに入れる
    heapq.heappush(a, discount * (-1))

print(-1 * sum(a))

Submission status: Accepted

Solution code:
import heapq	

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

if n==1:
  for i in range(m):
    hq[0]=(((-1)*hq[0])//2)*(-1)
else:
  for i in range(m):
    v=heapq.heappop(hq)
    heapq.heappush(hq,((v*-1)//2)*(-1))

ans=0
for i in range(len(hq)):
  ans=ans+(-1)*heapq.heappop(hq)

print(ans)

Submission status: Accepted

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

list1 = list(map(int,input().split()))
list1.sort()
list1.reverse()
i = 0
s = math.floor(list1[0]/2)
 
if n == 1:
    print(math.floor(list1[0]/(2**m)))
    exit()
 
while True:
    while True:
        if i+1 > n:
            break
        if list1[i] < s or m == 0:
            break
        list1[i] = math.floor(list1[i]/2)
        m -= 1
        i += 1
    if m == 0:
        break
    list1.sort()
    list1.reverse()
    s = math.floor(list1[0]/2)
    i = 0
print(sum(list1))

Submission status: Accepted

Solution code:
import sys
import heapq as hq
input = sys.stdin.readline
N, M = list(map(int,input().strip().split()))
A = list(map(int,input().strip().split()))
A = list(map(lambda x:-x, A))
hq.heapify(A)
for i in range(M):
	target = A[0]/2
	hq.heappushpop(A,target)
A = list(map(lambda x:-x, A))
print(sum(map(int,A)))

Submission status: Accepted

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

test = [0]*N

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

import heapq

heapq.heapify(A)

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

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

Submission status: Accepted

Solution code:
import heapq

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

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

Submission status: Accepted

Solution code:
from bisect import bisect_left
 
N,M = map(int, input().split())
A = sorted([int(x) for x in input().split()])
 
while M > 0:
    x = A.pop(-1)
    x //= 2
    ind = bisect_left(A, x)
    M -= 1
    if ind < N-1:
        temp = [x] + [A[-i-1]//2 for i in range(min(M, N-1 - ind))]
        A = sorted(A[:N-len(temp)] + temp)
    else:
        A.insert(bisect_left(A, x), x)
    M -= N-1 - ind
 
print(sum(A))

Submission status: Accepted

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

l = len(A)

if N>=2:
  while M>=1:
    A.sort(reverse=True)
    div = A[0]//2
    
    for i in range(l):
      if A[i]>=div:
        if M>=1:
          A[i] = A[i]//2
          M -= 1
        else:
          break
      else:
        break
 
  print(sum(A))
else:
    i=1
    while 2**(i+1)<=A[0]:
      i+=1
    if M>=i:
      print(0)
    else:
      print(A[0]//2**M)

Submission status: Accepted

Solution code:
import heapq

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

q = []
heapq.heapify(q)

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

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

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

ans = 0
for i in range(n):
    v = - heapq.heappop(q)
    ans += v
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# ABC141-D
import heapq
n, m = [int(x) for x in input().split()]
h = [-int(x) for x in input().split()]
heapq.heapify(h)
for i in range(m):
    x = heapq.heappop(h)
    heapq.heappush(h, -(-x//2))
z = 0
print(-sum(h))

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

Submission status: Accepted

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

heapq.heapify(A)

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

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

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

for i in range(M):
    n = -heappop(A_minus) // 2
    heappush(A_minus, -n)

print(-sum(A_minus))

Submission status: Accepted

Solution code:
import heapq as hq

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

arr = [-i for i in list(map(int,input().split()))]
hq.heapify(arr)

for i in range(m):
    hq.heappush(arr, -1*(-1*hq.heappop(arr)//2))

    
print(-1*sum(arr))

Submission status: Accepted

Solution code:
import heapq
 
N, M = list(map(int, input().split()))
A = input().split(" ")
neg_A = [-int(a) for a in A]
 
heapq.heapify(neg_A)
 
for t in range(M):
    heapq.heappush(neg_A, -(-heapq.heappop(neg_A)//2))
print(-sum(neg_A))

Submission status: Accepted

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

a.sort()
a = np.array(a)
a = -1 * a
a = list(a)
heapq.heapify(a)

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

print(-1 * sum(a))

Submission status: Accepted

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import nlargest
from heapq import nsmallest
#-------------------------------------------------------------------

N, M = map(int, input().split())		# 5 7 2
#A = list( map(int, input().split()) )
H = list( -int(i) for i in input().split() )

#p("A ",A)
p("H ",H)

heapify(H)

p("H ",H)

for _ in range(M):
	h = heappop(H)//(-2)
	heappush(H,-h)
	
	#p("h,H ",h,H)


print(-sum(H))

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
AT = [(-1)*a for a in A]
heapq.heapify(AT)
s = 0
while M > 0:
    m = heapq.heappop(AT)
    heapq.heappush(AT, -(-m//2))
    M -= 1
print(sum(AT)*(-1))

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

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

Submission status: Accepted

Solution code:
import math
from heapq import heappush, heappop

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

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

h = []

for i in a:
    heappush(h, -i)

for i in range(m):
    v = heappop(h)
    heappush(h, -(-v // 2))

print(-sum(h))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq as hq
def main():
    N,M = map(int,input().split())
    A=[-int(j) for j in input().split()]
    hq.heapify(A)
    for _ in range(M):
        tmp = hq.heappop(A)
        hq.heappush(A,(-((-tmp)//2)))
    print(-sum(A))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
N,M=input().split(" ")
N=int(N)
M=int(M)
Alist=input().split(" ")
# Alist = [-float(A) for A in Alist]
hAqueue=[]
for A in Alist:
    heappush(hAqueue,-float(A))

for m in range(M):
    tmp=heappop(hAqueue)
    heappush(hAqueue,tmp/2)
Alist = [-int(A) for A in hAqueue]
print(sum(Alist))

Submission status: Accepted

Solution code:
import heapq
 
L1 = input().split(" ")
L2 = input().split(" ")
tickets = int(L1[1])
L2int = [-int(s) for s in L2]
 
heapq.heapify(L2int)
 
for t in range(tickets):
    heapq.heappush(L2int,-(-heapq.heappop(L2int)//2))
print(-sum(L2int))

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)

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





print(sum(A)*-1)

Submission status: Accepted

Solution code:
import heapq


def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap) - 1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


itemCount, ticketCount = map(int, input().split(' '))
prices = map(int, input().split(' '))

h = []
for price in prices:
    _heappush_max(h, price)

for i in range(ticketCount):
    price = _heappop_max(h)
    _heappush_max(h, price // 2)
total = 0
for price in h:
    total += price

print(total)

Submission status: Accepted

Solution code:
import sys,heapq,math
sys.setrecursionlimit(100000)

def ins(): return input().split()
def ii(): return int(input())
def iil(): return list(map(int,ins()))
def lin(): return list(input())
def iin(): return map(int,ins())

n,m=iin()
a=list(map(lambda x:-int(x),ins()))
heapq.heapify(a)
tmp = heapq.heappop(a)
for i in range(m):
    tmp = heapq.heappushpop(a,math.ceil(tmp/2))
print(-(sum(a)+tmp))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
pque = [-int(x) for x in input().split()]
heapq.heapify(pque)

res = M
while res > 0:
    a = heapq.heappop(pque)
    a = -(abs(a) >> 1)
    heapq.heappush(pque, a)
    res -= 1
print(-sum(int(x) for x in pque))

Submission status: Accepted

Solution code:
from heapq import*;n,m,*a=map(lambda x:-int(x),open(0).read().split());heapify(a);exec("heappush(a,0-heappop(a)//-2);"*-m);print(-sum(a))

Submission status: Accepted

Solution code:
from heapq import*;n,m,*a=map(lambda x:-int(x),open(0).read().split());heapify(a)
for _ in[0]*-m:heappush(a,0-heappop(a)//-2)
print(-sum(a))

Submission status: Accepted

Solution code:
import heapq
import copy
def nint(x):
    return(int(x)*-1)
n, m = list(map(int, input().split()))
a = list(map(nint, input().split()))

b = copy.deepcopy(a)
heapq.heapify(b)

o = heapq.heappop(b)*-1
count = m
while o > 0 and count > 0:
    heapq.heappush(b, (o//2)*-1)
    count -= 1
    o = heapq.heappop(b)*-1

heapq.heappush(b, (o)*-1)

print(sum(b)*-1)

Submission status: Accepted

Solution code:
from sys import stdin
import heapq


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    As = []
    for i in [int(x) for x in stdin.readline().rstrip().split()]:
        heapq.heappush(As, -i)
    for _ in range(M):
        x = heapq.heappop(As)
        heapq.heappush(As, -(-x // 2))
    print(sum([-1 * x for x in As]))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

a = input()
list1 = list(map(int,a.split()))
list1.sort()
list1.reverse()
i = 0
s = math.floor(list1[0]/2)

if n == 1:
    print(math.floor(list1[0]/(2**m)))
    exit()

while True:
    while True:
        if i+1 > n:
            break
        if list1[i] < s or m == 0:
            break
        list1[i] = math.floor(list1[i]/2)
        m -= 1
        i += 1
    if m == 0:
        break
    list1.sort()
    list1.reverse()
    s = math.floor(list1[0]/2)
    i = 0
print(sum(list1))

Submission status: Accepted

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

Submission status: Accepted

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

heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
import sys
inputs = sys.stdin.readlines()

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

N, M = map(int, inputs[0].split())
A = list(map(int, inputs[1].split()))
_heapify_max(A)
for _ in range(M):
    _heappush_max(A, _heappop_max(A) // 2)
print(sum(A))

Submission status: Accepted

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

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

Submission status: Accepted

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

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

print(- sum(a))

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = [int(nm) for nm in input().split()]
A = [int(a) for a in input().split()]
A.sort(reverse = True)

while M >= 1:
  A[0] //= 2
  M -= 1
  
  i = 1
  while True:
    if N >= i*2 + 1:
      A1, A2, A3 = A[i-1], A[i*2 - 1], A[i*2]
    elif N == i*2:
      A1, A2, A3 = A[i-1], A[i*2 - 1], 0
    else:
      A1, A2, A3 = A[i-1], 0, 0

    if A1 < A2 or A1 < A3:
      if A2 >= A3:
        A[i-1], A[i*2 - 1] = A2, A1
        i = i*2
      else:
        A[i-1], A[i*2] = A3, A1
        i = i*2 + 1
    else:
      break

ans = sum(A)
print(ans)

Submission status: Accepted

Solution code:
import heapq
import math

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

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

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

b = []
for hqi in hq:
  b.append(hqi * -1)
  
print(sum(b))

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

Solution code:
import heapq, math

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

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

print(-sum(a))