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 = list(map(lambda x: -int(x), input().split()))
heapq.heapify(A)
for m in range(M):
    a = -heapq.heappop(A)
    heapq.heappush(A, -(a//2))
print(-sum(A))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N, M = map(int, input().split())
a = [int(i) for i in input().split()]
ls = []
ans = [0]*N
for i in range(N):
  heappush(ls, (-a[i], i))
for i in range(M):
  x, j = heappop(ls)
  x = -1*x
  heappush(ls, (-x/2,j))
  ans[j] += 1

total = 0
for i in range(N):
  total += a[i]//(2**ans[i])
print(total)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappop, heappush, heapify
import sys
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N, M = inpl()
A = inpl()
Q = [[-A[i], A[i], 0] for i in range(N)]
F = 2
heapify(Q)

for _ in range(M):
    b, a, x = heappop(Q)
    if b:
        b = a//(2**(x+1))
    heappush(Q, [-b, a, x+1])

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

print(ans)

Submission status: Accepted

Solution code:
from heapq import *

N, M = map(int, input().split())
*A, = map(int, input().split())
minusA = [-a for a in A]
heapify(minusA)
while M:
    maxA = - heappop(minusA)
    heappush(minusA, - (maxA >> 1))
    M -= 1
print(sum(-a for a in minusA))

Submission status: Accepted

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

import heapq


def minimize_money(n, m, xs):
    pq = [-x for x in xs]
    heapq.heapify(pq)
    for _ in range(m):
        x = -heapq.heappop(pq)
        new_x = -(x // 2)
        heapq.heappush(pq, new_x)
    res = sum(-y for y in pq)
    return res


def main():
    n, m = (int(z) for z in input().split())
    xs = [int(z) for z in input().split()]
    res = minimize_money(n, m, xs)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for _ in range(M):
    v = heappop(A)
    v /= 2
    heappush(A, v)

print(sum([int(-a) for a in A]))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import math
N, M = map(int, input().split())
As = list(map(int, input().split()))
q = []
for a in As:
  heappush(q, -a)
for _ in range(M):
  a = heappop(q)
  heappush(q, math.ceil(a / 2))
print(-sum(q))

Submission status: Accepted

Solution code:
import heapq

def main():

    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    hq = []
    for a in A:
        heapq.heappush(hq, -a)
    for _ in range(M):
        a = heapq.heappop(hq)
        a = -a/2
        heapq.heappush(hq, -a)
    ans = 0
    for a in hq:
        ans += int(-a)
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

cnt = 0
while cnt < M:
    a = heappop(H)
    heappush(H, -((-a)//2))
    cnt += 1

print(-sum(H))

Submission status: Accepted

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


def solve(N: int, M: int, A: "List[int]"):
    a_heap = []

    for a in A:
        heapq.heappush(a_heap,(-a,a))

    for i in range(M):
        item = heapq.heappop(a_heap)
        new_p = item[1] // 2
        heapq.heappush(a_heap,(-new_p,new_p))

    print(sum(map(lambda x: x[1],a_heap)))

    return


# Generated by 1.1.4 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:
#!/usr/bin/env python3
import sys
import heapq
INF = float("inf")


def solve(N: int, M: int, A: "List[int]"):
    h = []
    tot = 0
    for a in A:
        heapq.heappush(h, (-a, 0))
        tot += a
    # print(tot)
    for i in range(M):
        p, kaisu = heapq.heappop(h)
        tot -= -p
        p = -p // 2
        tot += p
        heapq.heappush(h, (-p, kaisu+1))
        # print(tot)
    print(tot)
    return


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:
def slove():
    import sys
    import heapq
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    a = list(map(int, input().rstrip('\n').split()))
    for i in range(len(a)):
        a[i] = a[i] * - 1
    heapq.heapify(a)
    for i in range(m):
        p = heapq.heappop(a)
        p /= 2
        heapq.heappush(a, p)
    t = 0
    for i in range(len(a)):
        t += int(a[i])
    print(-t)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
from functools import reduce
sys.setrecursionlimit(200000)
# local only
# if not __debug__:
#     fin = open('in_1.txt', 'r')
#     sys.stdin = fin
# local only
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

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

def main():
    N, M = mi()
    A = lmi()
    q = Heapq(A, True)
    for i in range(M):
        x = q.pop()
        q.push(x // 2)
    print(-sum(q.hq))
    return


if __name__ == '__main__':
    if not __debug__:
        import doctest
        doctest.testmod()
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
import heapq

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [-1 * int(a) for a in input().split()]
    heapq.heapify(A)

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

    print(-1 * sum(A))


    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

heapq.heapify(a)

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
As = list(map(int, input().split()))
q = []
for A in As:
  heapq.heappush(q, -A)
for i in range(M):
  X = -heapq.heappop(q)
  X2 = X//2
  heapq.heappush(q, -X2)
r = -sum(q)
print(r)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

n, m = map(int, input().split())
a = map(int, input().split())
a = list(map(lambda x: -x, a))
heapify(a)
# print(a)

while m > 0:
    v = heappop(a)
    v *= -1
    v //= 2
    v *= -1
    heappush(a, v)
    m -= 1

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()]
heapq.heapify(a)
for _ in range(m):
    heapq.heappush(a, heapq.heappop(a) / 2)
print(-sum([int(heapq.heappop(a)) for _ in range(n)]))

Submission status: Accepted

Solution code:
import heapq


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

for i in range(m):
    v = heapq.heappop(costs)
    v = v / 2
    # print(v)
    heapq.heappush(costs, v)


print(sum(map(lambda c: int(-c), costs)))

Submission status: Accepted

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

from heapq import *

que = []
for a in a_list:
    que.append(-a)
heapify(que)

while M > 0:
    M -= 1
    q = heappop(que)
    q = abs(q) // 2
    heappush(que, -q)

print(abs(sum(que)))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappush, heappop

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

heap = []
for ai in a:
    heappush(heap, -ai)

for _ in range(m):
    cur = -heappop(heap)
    heappush(heap, -(cur // 2))

ans = 0
for hi in heap:
    ans += -hi
print(ans)

Submission status: Accepted

Solution code:
import heapq
import math

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

heap_lst = []
for i in lst:
    heap_lst.append((-i, i))

heapq.heapify(heap_lst)
for i in range(m):
    a, b = heapq.heappop(heap_lst)
    b = math.floor(b/2)
    heapq.heappush(heap_lst, (-b, b))

res = 0
for tpl in heap_lst:
    res += tpl[1]
print(res)

Submission status: Accepted

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

from heapq import heapify, heappush, heappop

heapify(A)

for _ in range(m):
    x = -heappop(A)
    x //= 2
    heappush(A, -x)

print(-sum(A))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

h = []

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

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

print(- sum(h))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
#n,k = [int(i) for i in readline().split()]

n,m = [int(i) for i in readline().split()]
a = [-int(i) for i in readline().split()]


from heapq import *


heapify(a)
for i in range(m):
    c = heappop(a)
    c = -((-c)//2)
    heappush(a,c)

print(-sum(a))

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs , heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
n,m = m()

a = l()

de = []
su=0
for i in range(n):
    hq.heappush(de,-a[i])

for i in range(m):
    kkk = hq.heappop(de)
    kkk = -(-kkk//2)
    hq.heappush(de,kkk)
print(-1*sum(de))

Submission status: Accepted

Solution code:
n,m=[int(j) for j in input().split()]
a=[-int(j) for j in input().split()]
import heapq
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:
#!/usr/bin/env python3
#ABC141 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.readline

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

    q = []
    for i in range(N):
        heapq.heappush(q, -a[i])
    
    for i in range(M):
        t = -heapq.heappop(q)
        t /= 2
        heapq.heappush(q, -t)
    
    ans = 0
    for i in range(N):
        ans += int(- q[i])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

B=[-a for a in A]
B.sort()

import heapq

heapq.heapify(B)

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

    #print(B)

print(-sum(B))

Submission status: Accepted

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

import heapq
i=0
heap=[]
res=[]
for t in a:
	heapq.heappush(heap,-t)
for _ in range(m):
	t=heapq.heappop(heap)
	heapq.heappush(heap,-(-t//2))
print(-sum(heap))

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
*A, = map(int,input().split())
import heapq
B = sorted(-a for a in A)
heapq.heapify(B)
for _ in [0]*M:
    b = -((-heapq.heappop(B))//2)
    heapq.heappush(B,b)
print(-sum(B))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
As = list(map(int, input().split()))
for i in range(len(As)):
    As[i] = -As[i]
import heapq

heapq.heapify(As)
for i in range(M):
    ma = heapq.heappop(As)
    heapq.heappush(As, -(-ma // 2))
s = sum(As)
print(-s)

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]
q = []
for i in range(n):
    heapq.heappush(q, a[i])

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

Submission status: Accepted

Solution code:
from heapq import heappop,heappush


N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
q = []
for i in range(N):
    heappush(q,-A[i])

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

ans = 0
for i in range(N):
    ans-=heappop(q)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, heapq
sys.setrecursionlimit(300000)


def solve(N: int, M: int, A: "List[int]"):
    h = []
    for i in range(N):
        heapq.heappush(h, -A[i])
    for i in range(M):
        tmp = -(heapq.heappop(h))
        tmp //= 2
        heapq.heappush(h, -tmp)
    ret = sum(h)
    ret = -ret
    print(ret)
    return


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 = list(map(int, input().split()))
A = list(map(int, input().split()))

import heapq
pop = heapq.heappop
push = heapq.heappush
q  = []

for i in A:
  push(q, -1 * i)

for i in range(M):
  t = pop(q)
  push(q, ((t * -1) // 2) * -1)

ans = 0
for i in range(N):
  ans += -1 * pop(q)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

"""
greedyに高い金額から割り引いていく
"""

from heapq import heappop,heappush,heapify

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

A_minus = [-x for x in A]
heapify(A_minus)

pop = lambda: -heappop(A_minus)
push = lambda x: heappush(A_minus,-x)

for _ in range(M):
    x = pop()
    push(x//2)

answer = -sum(A_minus)
print(answer)

Submission status: Accepted

Solution code:
import heapq

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

Q = []
for i in range(n):
    heapq.heappush(Q,-A[i])
for i in range(m):
    j = -heapq.heappop(Q)
    j //= 2
    heapq.heappush(Q,-j)

print(-sum(Q))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify
n,m = map(int, input().split())
a = list(map(int, input().split()))
b = [-i for i in a]
b.sort()

heapify(b)
for i in range(m):
    q = heappop(b)
    q /= 2
    heappush(b, q)

ans = sum(int(-i) for i in b)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque


def main():
    nun, waribiki_num = map(int, input().split())
    data = list(map(int, input().split()))

    aaa = []

    for i in range(nun):
        heapq.heappush(aaa, -data[i])

    for i in range(waribiki_num):
        b = heapq.heappop(aaa)
        c = (-1 * b) // 2
        # print(c)
        heapq.heappush(aaa, -c)
    # print(aaa)

    ans = -sum(aaa)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

import heapq

N,M = II()
A = III()

a = [(-x,x) for x in A]
heapq.heapify(a)

for _ in range(M):
    y = heapq.heappop(a)
    heapq.heappush(a,(y[0]/2, y[1]/2))

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

print(ans)

Submission status: Accepted

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

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

    def size(self):
        return len(self.hq)

q = Heapq(A, True)

for _ in range(M):
    a = q.pop()
    q.push(a//2)

print(-sum(q.hq))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    N,M = map(int,input().split())
    A = list(map(int,input().split()))
    
    import heapq
    P = []
    for i in A:
        heapq.heappush(P,-i)
    for i in range(M):
        X = heapq.heappop(P)
        #print(X)
        X = -(-X//2)
        heapq.heappush(P,X)
    ans = 0
    for i in range(N):
        X = heapq.heappop(P)
        ans -= X
    print(ans)
    
main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

c = []
for a in A :
    heappush(c, -a)
    
for _ in range(M) :
    b = heappop(c)
    heappush(c, (b + 1) // 2)
    
print(-sum(c))

Submission status: Accepted

Solution code:
from heapq import heapify, heapreplace

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

for _ in range(m):
    heapreplace(aaa, aaa[0] // 2 + aaa[0] % 2)

print(-sum(aaa))

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
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):heappush(h,-((-heappop(h))//2))
s=0
for i in range(n):s+=-heappop(h)
print(s)

Submission status: Accepted

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

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

print(-sum(A))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    h = []
    for a in A:
        heappush(h, -a)
    for _ in range(M):
        x = -heappop(h)
        heappush(h, -(x//2))
    ans = -sum(h)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
A = [-a for a in A]

heapq.heapify(A)

for _ in range(M):
    heapq.heapreplace(A, A[0] / 2)

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m = na()
a = na()
ans = sum(a)

import heapq
b = []

for i in a:
    heapq.heappush(b, -i)

for i in range(m):
    k = -(heapq.heappop(b))
    p = k//2
    ans -= (k-p)
    heapq.heappush(b, -p)

print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush, heapify
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

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

    que = [-a for a in A]

    heapify(que)

    for _ in range(M):
        maxA = -heappop(que)
        heappush(que, -(maxA // 2))

    ans = -sum(que)
    print(ans)

sol()

Submission status: Accepted

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

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 i in range(m):
  x = heapq.heappop(q)
  x /= 2
  heapq.heappush(q, x)
ans = 0
for x in q:
  ans += -x // 1
print(int(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = input()
    if s == "Sunny":
        print("Cloudy")
    elif s == "Cloudy":
        print("Rainy")
    else:
        print("Sunny")
    return

#B
def B():
    s = S()
    for i in range(len(s)):
        if i%2:
            if s[i] not in ["L","U","D"]:
                print("No")
                return
        else:
            if s[i] not in ["R","U","D"]:
                print("No")
                return
    print("Yes")
    return

#C
def C():
    n,k,q = LI()
    a = IR(q)
    f = [k-q]*(n)
    for i in range(q):
        ai = a[i]-1
        f[ai] += 1
    for i in f:
        if i <= 0:
            print("No")
        else:
            print("Yes")
    return

#D
def D():
    n,m = LI()
    a = LI()
    q = []
    for i in range(n):
        heappush(q,-a[i])
    for i in range(m):
        x = heappop(q)
        x *= -1
        x >>= 1
        heappush(q,-x)
    print(-sum(q))
    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
import heapq
N, M = [int(_) for _ in input().split()]
H = [-int(_) for _ in input().split()]
heapq.heapify(H)
ans = 0
for _ in range(M):
    a = heapq.heappop(H)
    heapq.heappush(H, a / 2)
print(-sum(int(a) for a in H))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

import heapq
n, m = getList()

nums = getList()

h = []
for num in nums:
    heapq.heappush(h, -num)

for i in range(m):
    cur = heapq.heappop(h)
    # print(cur, h)
    cur = cur / 2
    heapq.heappush(h, cur)
#
# print(h)
ans = 0

for num in h:
    ans += -num // 1
    # print(ans)

print(int(ans))

Submission status: Accepted

Solution code:
import heapq

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

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

print(-sum(pq))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = sorted(map(int,input().split()))

for i in range(m):
    a[-1] //= 2
    
    if a[-2] > a[-1]:
        a = sorted(a)
    
print(sum(a))

Submission status: Runtime Error

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

for m in range(M):
    A[0] = A[0]//2
    if A[0] > A[1]:
        continue
    else:
        A.sort(reverse=True)

print(sum(A))

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
from heapq import heapify,heappush,heappop

def main():
    N,M = map(int,input()split())
    A = [-x for x in map(int,input().split())]
    heapify(A)
    for i in range(M):
        tmp = heappop(A)
        tmp2 = tmp//2
        heappush(A,tmp2)
    ans = 0
    for i in range(N):
        ans += A[i]

    ans = abs(ans)
    return ans

print(main())

Submission status: Runtime Error

Solution code:
import sys
from math import log

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

a = sorted(a, reverse=True)
flag = True

if n == 1:
  ans = a[0] // (2**m)
  print(ans)
  sys.exit()

for i in range(n-1):
  if a[i] > a[i+1] * (10*3):
    s = int(log(a/b, 2))
    a[i] //= 2**(min(m, s))
    m = max(0, m-s)


while flag == True:
  index = 0
  if a[0]/2 < a[n-1]:
    index = n
  else:
    for i in range(1, n):
      if a[0]/2 > a[i]:
        index = i
        break
  if index < m:
    for i in range(index):
      a[i] //= 2
    a = sorted(a, reverse=True)
    m -= index
  else:
    for i in range(m):
      a[i] //= 2
    flag = False

print(sum(a))