ABC141D priority heap

priority heapを使うと、最大値の取得がlogNで可能に。
ランダムな値の挿入もlogNで可能。

import sys
import heapq
stdin = sys.stdin

n,m = map(int, stdin.readline().split())

# heap は通常、最小値がrootのヒープを作成する。最大値を取得するために、マイナス各値にマイナスをかける。
an = [i*(-1) for i in map(int, stdin.readline().split())]
#print(an)

# リストのheap化
heapq.heapify(an)

# heapから最大値を取り出して、半分にしてヒープに戻すことをｍ回。
for _ in range(m):
    b = heapq.heappop(an)
    heapq.heappush(an, (-1)*((-1)*b//2))

ans = (-1)*sum(an)
print(ans)