Buggy python submission (verdict: Time Limit Exceeded):
######## 関数 ############

def find_max(A):
    max = A[0]
    max_index = 0
    for i in range(len(A)):
        if A[i] > max:
            max_index = i
            max = A[i]
    return max_index

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

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

for i in range(M): # 各割引券1枚ずつ、一番高い品物に使っていく
    max_i = find_max(A)  # O(N)
    A[max_i] //= 2  # 割引券1枚で50% OFF

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

print(total_price)

Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
######## 関数 ############

# insertion sort : 小さいものから順に並べる
# リストの途中までソートされている場合に時間を短縮
# A[0], ..., A[m-1]までソート済み、A[m],...,A[n]はソートされていない場合
# insertion_sort( A[m:n+1], A[0:m]) とすることで、時間短縮
def insertion_sort(unsorted, sorted = []):
    A = sorted + unsorted # リストを連結
    for i in range(len(sorted), len(A)): # i = len(sorted), len(sorted)+1, ..., len(A)-1
        for j in range(i, 0, -1): # j = i, i-1, ..., 1
            if A[j] < A[j-1]:
                temp = A[j]
                A[j] = A[j-1]
                A[j-1] = temp
    return A

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

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

# Aを安い順にソートする
A = insertion_sort(A)

for i in range(M): # 各割引券1枚ずつ、一番高い品物に使っていく
    A[N-1] //= 2   # 右端が一番高い。1枚使うと半額
    A = insertion_sort(A[N-1:N], A[0:N-1]) # 安い順に並び替え

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

print(total_price)

Fixed submission:
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)