Problem:


Score : 400 points

Problem Statement

Takahashi is going to buy N items one by one.

The price of the i-th item he buys is A_i yen (the currency of Japan).

He has M discount tickets, and he can use any number of them when buying an item.

If Y tickets are used when buying an item priced X yen, he can get the item for \frac{X}{2^Y} (rounded down to the nearest integer) yen.

What is the minimum amount of money required to buy all the items?

Constraints

All values in input are integers.

1 \leq N, M \leq 10^5

1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_N

Output

Print the minimum amount of money required to buy all the items.

Sample Input 1

3 3
2 13 8

Sample Output 1

9

We can buy all the items for 9 yen, as follows:

Buy the 1-st item for 2 yen without tickets.

Buy the 2-nd item for 3 yen with 2 tickets.

Buy the 3-rd item for 4 yen with 1 ticket.

Sample Input 2

4 4
1 9 3 5

Sample Output 2

6

Sample Input 3

1 100000
1000000000

Sample Output 3

0

We can buy the item priced 1000000000 yen for 0 yen with 100000 tickets.

Sample Input 4

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 4

9500000000



Sample input:
3 3
2 13 8


Sample output:
9

Submission status: Accepted

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

h = []
for a in A_array:
    heapq.heappush(h, -a)

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

ans = 0
for i in range(N):
    p = heapq.heappop(h)
    ans += int(-p)

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from heapq import *
N, M = map(int, input().split())
A = [-int(x) for x in input().split()]
heapify(A)
for x in range(M):
    tmp = int(heappop(A)/2)
    heappush(A,tmp)
res = 0
for x in A:
    res -= x
print(res)

Submission status: Accepted

Solution code:
def main():
    import sys,heapq,math
    input = sys.stdin.readline

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

    tank = []
    for e in a:
        heapq.heappush(tank,-e)
    
    for i in range(m):
        heapq.heappush(tank,heapq.heappop(tank)/2.0)

    res = 0
    for e in tank:
        res += math.floor(-e)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.buffer.readline
class SkewHeap:
  def __init__(self, init_val = None):
    self.val = init_val
    self.left = None
    self.right = None
    self.root = None
  def heapmeld(self, h1, h2):
    if h1 == None: return h2
    if h2 == None: return h1
    if h1.val > h2.val:
      h1.val, h1.left, h1.right, h2.val, h2.left, h2.right = h2.val, h2.left, h2.right, h1.val, h1.left, h1.right
    h1.right = self.heapmeld(h2, h1.right)
    h1.left, h1.right = h1.right, h1.left
    return h1
  def heappop(self):
    res = self.root.val
    self.root = self.heapmeld(self.root.left, self.root.right)
    return res
  def heappush(self, x):
    h = SkewHeap(x)
    self.root = self.heapmeld(self.root, h)
  def heaptop(self):
    return self.root.val
N, M = map(int, input().split())
a = list(map(int, input().split()))
h = SkewHeap()
res = 0
for e in a:
  h.heappush(-e)
for _ in range(M):
  h.heappush(-(-h.heappop() // 2))
for _ in range(N):
  res -= h.heappop()
print(res)

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)

#for i in range(n):
#    a.append(int(input())*(-1))

heapq.heapify(a)

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

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

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
n,m=map(int,input().split())
aa=list(map(int,input().split()))
a=[]
for i in range(n):
	heappush(a,-aa[i])
for _ in range(m):
	heappush(a,(heappop(a)+1)//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 (0,len(A)):
    A[i]*=(-1)

heapq.heapify(A)

def chaep(n):
    n=int(n/2)
    return  n
i=0
while(i<M):
    tmp=heapq.heappop(A)
    tmp=chaep(tmp)
    heapq.heappush(A,tmp)
    i+=1

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 (0,len(A)):
    A[i]*=(-1)

heapq.heapify(A)

def chaep(n):
    n=int(n/2)
    return  n
i=0
while(i<M):
    tmp=heapq.heappop(A)
    tmp=chaep(tmp)
    heapq.heappush(A,tmp)
    i+=1

ans=0
for i in range (0,N):
    ans+=A[i]

print(ans*(-1))

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)

ans=0
def cheap(x,y):
    x=int(x/(2**y))
    return x

i=0
while(i<M):
    tmp=heapq.heappop(A)
    tmp=cheap(tmp,1)
    heapq.heappush(A,tmp)
    i+=1

for i in range(0,N):
    ans+=A[i]

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Oct  3 07:43:37 2019

@author: avina
"""

import heapq

class Maxheap():
    
    def __init__(self, x):
        self.heap = [-e for e in x]
        heapq.heapify(self.heap)
    
    def push(self, value):
        heapq.heappush(self.heap, -value)
    
    def pop(self):
        return -heapq.heappop(self.heap)

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

l = list(map(int, input().split()))
a = Maxheap(l)
for i in range(t):
    b = a.pop()//2
    a.push(b)
    
sums = 0
for i in range(n):
    sums += a.pop()
print(sums)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Oct  2 07:56:16 2019

@author: avina
"""
from queue import PriorityQueue as Q
n,t = map(int,input().split())

q = Q()
for i in input().split():
    a = -1*int(i)
    q.put(a)

while t >0:
    a = -1*(q.get())
    a = -1*(a//2)
    q.put(a)
    t-=1

ans = 0
while q.qsize()>0:
    ans += q.get()
print(-1*ans)

Submission status: Accepted

Solution code:

import heapq


class MaxHeap(object):
    def __init__(self, x):
        self.heap = [-e for e in x]
        heapq.heapify(self.heap)

    def push(self, value):
        heapq.heappush(self.heap, -value)

    def pop(self):
        return -heapq.heappop(self.heap)

N, M = list(map(lambda x:int(x), input().split(' ')))
l = list(map(lambda x:int(x), input().split(' ')))

maxheap = MaxHeap(l)

WARI = 0.5
for _ in range(0, M):
    v = int(maxheap.pop() * WARI)
    maxheap.push(v)

SUM = 0
for _ in range(0, N):
    SUM += maxheap.pop()

print(SUM)

Submission status: Accepted

Solution code:

#優先度付きキュー
#値の追加 O(log|Q|)
#値の削除 O(log|Q|)
#最大値の取得 O(1)
#pythonでは 最小値のみしか取得できないため事前に全要素に-1をかけておき最後のまた-1かける

import math
import heapq

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

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

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

print(-1 * sum(A))

Submission status: Accepted

Solution code:
#atcorder beginner contest 141
#D powerful discount tickets
import math
import heapq

goods, tickets = map(int, input().split())

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


for i in range(tickets):
    max = heapq.heappop(price) * (-1)
    heapq.heappush(price, math.ceil(-max/2))
   

total = 0
for i in range(goods):
    total += price[i]

print(total * (-1))

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
values = list(map(int, input().split()))
sortedValues = []

for v in values:
    heapq.heappush(sortedValues, (-1)*v)

for i in range(M):
    heapq.heappush(sortedValues, int((heapq.heappop(sortedValues) * 1/2)))

print((-1) * sum([heapq.heappop(sortedValues) for i in range(len(sortedValues))]))

Submission status: Accepted

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

print(-sum(a))

Submission status: Accepted

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

pque = []

for i in A:
    heapq.heappush(pque, -i)

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

print (-sum(pque))

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
a=list(map(int,input().split()))
a=[-i for i in a]
heapq.heapify(a)
for _ in range(m):
    mm=heapq.heappop(a) #最小値(元のaの最大値)を取り出す
    heapq.heappush(a,(-1)*(-mm//2)) #Pythonでは -11//2=6になってしまう
print(-sum(a))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import heapq
class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 3
2 13 8"""
        output = """9"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """4 4
1 9 3 5"""
        output = """6"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """1 100000
1000000000"""
        output = """0"""
        self.assertIO(input, output)
    def test_入力例_4(self):
        input = """10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000"""
        output = """9500000000"""
        self.assertIO(input, output)
def resolve():
    (n,m)=(int(i) for i in input().split())
    A=[int(i) for i in input().split()]
    q=[]
    for i in A:
        heapq.heappush(q,-i)
    for i in range(m):
        x=q[0]
        heapq.heappushpop(q,int(x/2))
    print(-sum(q))
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

Solution code:
# coding: utf-8
from heapq import heapify, heappop, heappush
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
item_list = [int(x) * (-1) for x in input().split()]

heapify(item_list)

for i in range(M):
    price = heappop(item_list)
    price = int(price / 2)
    heappush(item_list, price)

total = -sum(item_list)
print(total)

Submission status: Accepted

Solution code:
import heapq


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

# use priority queue
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 sys
import heapq

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

if len(A) == 1:
    A[0] //= (2 ** M)
    print(sum(A))
    sys.exit()

h = [(1/a, a) for a in A]
heapq.heapify(h)

for m in range(M):
    x = heapq.heappop(h)
    _, a = x

    a //= 2

    heapq.heappush(h, (1/a if a > 0 else float('inf'), a))

print(sum([a for _, a in h]))

Submission status: Accepted

Solution code:
import heapq
import math

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

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(h)

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

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

Submission status: Accepted

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

import heapq
class MaxHeap(object):
    def __init__(self, x):
        self.heap = [-e for e in x]
        heapq.heapify(self.heap)
    def push(self, value):
        heapq.heappush(self.heap, -value)
    def pop(self):
        return -heapq.heappop(self.heap)
    def sum(self):
        return -sum(self.heap)

a = MaxHeap(a)

for i in range(m):
    largest = a.pop()
    a.push(largest//2)
print(a.sum())

Submission status: Accepted

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

args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False

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

# sys.stdin = open('/dev/tty')

heapq.heapify(A)

#### functions
def discount(num_coupon):
  max = -heapq.heappop(A) / 2
  heapq.heappush(A, -max)

#### execution
# if em: embed()
for i in range(0, M):
  max = math.floor(-heapq.heappop(A) / 2)
  heapq.heappush(A, -max)

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

Submission status: Accepted

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

Submission status: Accepted

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

#品物を高い順に並び替える
item.sort(reverse=True)

#割引券がなくなるまで操作を繰り返す
while m != 0:
    
    #品物の高いものから順に割引券を使用していく
    for i in range(n):
        
        #一番高い品物の割引券を使用した後の値段はtempとして保持しておく
        if i == 0:
            item[i] = int(item[i]/2)
            m -= 1
            temp = item[i]
            if m == 0:
                break
            continue
        
        #tempよりも品物の値段が高い間は割引券を使用しながらfor文を回し続ける
        if item[i] > temp:
            item[i] = int(item[i]/2)
            m -= 1
            if m == 0:
                break
            continue
        
        #tempよりも品物の値段が安くなったら、もう一度値段の高い順にソートし直して操作を繰り返す
        item.sort(reverse=True)
        break

#品物の値段を合計して出力        
print(sum(item))

Submission status: Accepted

Solution code:
import heapq

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

for _ in range(m):
  v = heapq.heappop(a)
  o = v % 2
  v /= 2
  heapq.heappush(a, v + o)

print(-1*sum(a))

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
A=tuple(map(int,input().split()))
l=[(-i,i) for i in A]
heapq.heapify(l)
for _ in range(M):
    m=heapq.heappop(l)
    heapq.heappush(l,(-(m[1]//2),m[1]//2))
a=0
for i in l:
    a+=i[1]
print(a)

Submission status: Accepted

Solution code:
import heapq

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

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

print(sum([int(-x // 1) for x in a_list]))

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):
    mx = heapq.heappop(a)
    heapq.heappush(a, -(-mx // 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 i in range(m):
    k=heapq.heappop(a)
    heapq.heappush(a,-(abs(k)//2))
print(-sum(a))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

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

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)
import math
for i in range(M):
  maxi=heapq.heappop(A)
  maxi=math.ceil(maxi/2)
  heapq.heappush(A,maxi)
  
ans=sum(A)*(-1)
print(ans)

Submission status: Accepted

Solution code:
import heapq


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

for i in range(m):
    minus_max = alist[0]
    heapq.heapreplace(alist, ((-1)*minus_max >> 1)*(-1))

print(-1*sum(alist))

Submission status: Accepted

Solution code:
import heapq

######## クラス ############
class MaxHeap:
    def __init__(self, H=[]):
        self.heapify(H)

    def heapify(self, H):
        self._neg_heap = [ -a for a in H ] # マイナスをかける
        heapq.heapify( self._neg_heap )

    def push(self, value):
        heapq.heappush(self._neg_heap, -value)

    def pop(self):
        return (-1) * heapq.heappop(self._neg_heap)

    def get_heap(self):
        return [ -a for a in self._neg_heap ]



##### プログラム ###############

# 入力を受け取る
N, M = input().strip().split()
N, M = [int(N), int(M)]
A = input().strip().split()
A = [int(a) for a in A] # 整数に変換

price_heap = MaxHeap(A)

i = 0
for i in range(M):# 各割引券1枚ずつ、一番高い品物に使っていく
    price = price_heap.pop() # 一番高い品物
    price //= 2  # 一番高い商品に割引券を使って半額にする
    price_heap.push(price) # 半額になった商品をheapに戻す
    i += 1

total_price = 0
new_prices = price_heap.get_heap()

for i in range(N):
    total_price += new_prices[i]

print(total_price)

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
def main():
    n, m = map(int, input().split())
    a = [-int(i) for i in input().split()]
    heapify(a)
    for _ in range(m):
        heappush(a, -(-heappop(a) // 2))
    print(-sum(a))
    
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import queue
MAXIMUM = 10 ** 10
q = queue.PriorityQueue()
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
for a in A:
  q.put((-a, a))

while M > 0:
  item = q.get()
  if item[1] == 0:
    break
  q.put((-int(item[1]/2), int(item[1]/2)))
  M -= 1

result = 0
while not q.empty():
  result += q.get()[1]
print(result)

Submission status: Accepted

Solution code:
import heapq

def receive_shopping_plan():
    num_commodity, num_coupon = input().split(' ')
    num_commodity, num_coupon = int(num_commodity), int(num_coupon)
    return num_commodity, num_coupon

def calc_minimized_sum(num_commodity, num_coupon):
    prices = list(map(lambda x: int(x) * -1 , input().split(' ')))
    heapq.heapify(prices)
    for _ in range(num_coupon):
        max_price = heapq.heappop(prices) // (2*-1)
        heapq.heappush(prices, max_price*-1)

    print(sum(prices)*-1)

if __name__ == '__main__':
    num_commodity, num_coupon = receive_shopping_plan()
    calc_minimized_sum(num_commodity, num_coupon)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


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

    pqueue = []
    for A in lst_A:
        heappush(pqueue, -A)

    for m in range(M):
        a = heappop(pqueue)
        a *= -1
        a //= 2
        a *= -1
        heappush(pqueue, a)
    ans = -sum(pqueue)
    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()))

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

for _ in range(m):
    heapq.heappush(hq,-(-heapq.heappop(hq)//2))

print(-sum(hq))

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
lst=list(map(int,input().split()))
A=[]
for i in range(N):
  heapq.heappush(A,-1*lst[i])
while M!=0:
  val=heapq.heappop(A)
  M-=1
  new_val=val/2
  heapq.heappush(A,new_val)

ans=0
for i in range(N):
  ans+=-1*int(A[i])
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import numpy as np

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

price = [int(x) for x in input().split()] 
hq_price = []
for p in price:
  heappush(hq_price, -p)

for m in range(M):
  max_tmp = heappop(hq_price)
  heappush(hq_price, max_tmp/2.)

price = [int(-x) for x in hq_price]
print(sum(price))

Submission status: Accepted

Solution code:
import heapq

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

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

heapq.heapify(nums)

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

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

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()))
a = list(map(lambda x: x*(-1), a))


heapq.heapify(a)

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

ans = 0
for num in a:
    ans += int(-num)

print(ans)

Submission status: Accepted

Solution code:
import heapq

n,m = map(int,input().split())
a = list(map(int,input().split()))
a = [-x for x in a]
heapq.heapify(a) 
ans =0
for i in range(m):
  b = a[0]
  c = (-1)*b //2
  heapq.heappop(a) 
  heapq.heappush(a, c*(-1)) 
print(sum(a)*(-1))

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(a)

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

print(-sum(a))

"""
for i in range(m):
    a.sort()
    a.reverse()
    m -= 1
    a[0] = a[0] // 2

print(sum(a))
"""
"""
def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]
"""

Submission status: Accepted

Solution code:
import heapq

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

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

Submission status: Accepted

Solution code:
import heapq

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

H = []
for a in map(int, input().split()):
    heapq.heappush(H, -a)

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

print(-1 * sum(H))

Submission status: Accepted

Solution code:
# coding: utf-8
import heapq

n, m = map(int, input().split())
l = [ -1 * int(n) for n in input().split()]

heapq.heapify(l)

for i in range(m):
    a = heapq.heappop(l) * (-1)
    a = int(a/2)
    if a != 0:
        heapq.heappush(l, a * (-1))
    if len(l) == 0:
        break
    
    
print(sum(l) * (-1))

Submission status: Accepted

Solution code:
import math
import heapq

# 入力の取得(1行目。数値)
i = list(map(int, input().split()))

# 変数セット
# 1.購入する品物の数
itemCount = i[0]
# 2.割引券の数
discountTicketsCount = i[1]

# 入力の取得(2行目。数値)
priceList = list(map(int, input().split()))

# 「符号反転した」リストを優先度付きキューに変換
# ★ポイント★
# heapqは最小値しか取り出せないため、
# 符号反転してからキューに変換=>最小値を取る、という手法を行う。
priceList = [ n * -1 for n in priceList]
heapq.heapify(priceList)

# 割引件数分ループ
for i in  range(discountTicketsCount):

    # キューから最小値の取り出し(ここで符号反転も行っておく)
    target = abs(heapq.heappop(priceList))

    # 2で割る。(小数点切り下げ)
    target = math.floor(target / 2)

    # 割引券利用後の金額をキューに格納(ここで符号反転する)
    heapq.heappush(priceList, target * -1)

# 合計金額を出力
print(abs(sum(priceList)))

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

Submission status: Accepted

Solution code:
import heapq

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

h = []
for ai in a:
    heapq.heappush(h, -ai)

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

print(-sum(h))

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


print(-sum(A))

Submission status: Accepted

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

npA = []
for x in a:
    heapq.heappush(npA, -x)

# for x in range(N):
#     print(a[x])
npA.sort()


for x in range(M):
    # temp=heapq.heappop(npA)
    # print("{}//2={}".format(temp,math.ceil(temp/2)))
    heapq.heappush(npA, math.ceil(heapq.heappop(npA)/2))#get the max value!!
    

total = 0
for x in range(N):
    # temp = heapq.heappop(npA)
    # print(temp)
    total+=heapq.heappop(npA)

print(-total)

Submission status: Accepted

Solution code:
import heapq

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

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

Submission status: Accepted

Solution code:
# ABC141 D -Powerful Discount Tickets

import heapq
import math

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

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

heapq.heapify(A)


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

print(-sum(A))

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

decimal.getcontext().prec = 20
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    n, m = f.read_int_list()
    a = f.read_int_list()

    h = []
    for ai in a:
        heapq.heappush(h, -decimal.Decimal(ai))

    two = decimal.Decimal(-2)
    for i in xrange(m):
        item = -heapq.heappop(h)
        heapq.heappush(h, item/two)

    ans = 0
    for hi in h:
        ans += int(-hi)

    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Accepted

Solution code:
import heapq

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

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

Submission status: Accepted

Solution code:
import heapq

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

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

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

Submission status: Accepted

Solution code:
from bisect import bisect_right
import heapq
n,m=map(int,input().split())
lists=list(map(int,input().split()))
uselists=[]
for _ in lists:
    uselists.append(-_)

heapq.heapify(uselists)

cnt=0
while cnt<m:
    y=heapq.heappop(uselists)

    z=(-y)//2
    heapq.heappush(uselists,-z)
    

    cnt+=1
anslist=[]
for j in uselists:
    anslist.append(-j)
print(sum(anslist))

Submission status: Accepted

Solution code:
import heapq
X = list(map(int, input().split()))
# A = list(map(int, input().split()))
A = list(map(lambda x: int(x)*(-1), input().split())) # 最大値を取るために各要素を-1倍
heapq.heapify(A)

for i in range(X[1]):
  x = heapq.heappop(A) * (-1) # 最大値の取り出し
  heapq.heappush(A, int(x/2) * (-1))

ans = 0
for i in range(X[0]):
  ans -= A[i]

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

ans = 0

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

for i in range(N):
    ans -= A_heap[i]

print(ans)