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:
## 2020/01/19 Not yet
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))


"""
### abswer example
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))

# 要は、M 階動的に最大値を半分にしていけばよい
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [i*-1 for i in a]
heapq.heapify(a)
 
for _ in range(m):
    pop = heapq.heappop(a)
    p = -(pop*-1//2)
    # 負数の切り捨て（割り切れないとき）は絶対値が1上がるので注意
    heapq.heappush( a, p)
print(sum(list(a))*-1)
"""

Submission status: Accepted

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

items = list(map(lambda x:int(x)*(-1), input().split()))
heapq.heapify(items)
             
for i in range(m):
    pop = heapq.heappop(items)*(-1)//2
    heapq.heappush(items, pop*(-1))

print(-1*sum(items))

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().strip().split())
heap = list(map(lambda a: -int(a), input().strip().split()))

heapq.heapify(heap)

for i in range(m):
    highest = heap[0]
    heapq.heapreplace(heap, highest / 2.0)

ans = -sum(map(int, heap))
print(ans)

Submission status: Accepted

Solution code:
import heapq


def main():
    n, m = map(int, input().split())
    alist = map(int, input().split())
    heap = []
    for a in alist:
        heapq.heappush(heap, a * -1)
    for _ in range(m):
        v = heapq.heappop(heap)
        heapq.heappush(heap, int(v / 2))
    print(int(-1 * sum(heap)))


main()

Submission status: Accepted

Solution code:
import heapq
import math
 
def LI():
  return [int(s) for s in input().split()]
 
N,M = LI()
a = LI()
a = list(map(lambda x: x*(-1), a))  # 各要素を-1倍
 
heapq.heapify(a)
 
for i in range(M):
    x = (-1)*(abs(heapq.heappop(a))//2)
    heapq.heappush(a,x)

cost = 0
for i in range(N):
  x = heapq.heappop(a)
  cost+=abs(x)
  
print(cost)

Submission status: Accepted

Solution code:
import heapq

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

A = list((-1)*(int(x)) for x in input().split())
heapq.heapify(A)

sum = 0

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

for i in range(len(A)):
    sum += -A[i]

print(sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

from heapq import heappush, heappop

queue = []
for a in A:
  heappush(queue, -a)

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

print(-sum(queue))

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 _ 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())
Alist = list(map(int,input().split()))
newA = list(map(lambda x: x*(-1),Alist))
heapq.heapify(newA)
for i in range(M):
    current = -heapq.heappop(newA)
    heapq.heappush(newA,-(current//2))
cost = 0
print(-sum(newA))

Submission status: Accepted

Solution code:
import heapq as hp
n, m = (int(x) for x in input().split())
a = [int(x)*(-1) for x in input().split()]
hp.heapify(a)
for _ in range(m):
    min = hp.heappop(a)
    hp.heappush(a, (-1)*(-min//2))
print(-sum(a))

Submission status: Accepted

Solution code:
import heapq
import math

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

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

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

print(-sum(A))

Submission status: Accepted

Solution code:
def minus(a:str):
    return int(a)*-1

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

import heapq as hq

def main():
    hq.heapify(A)
    for _ in range(M):
        target = hq.heappop(A)
        target = -1*((-1*target) // 2)
        hq.heappush(A,target)
    print(sum(A)*-1)
    return 

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
import heapq
import numpy as np
N, M = map(int,input().split())
a = list(map(int,input().split()))
a = list((np.array(a))*(-1))
heapq.heapify(a)
for m in range(M):
    tgt = -heapq.heappop(a)
    heapq.heappush(a,-(tgt//2))
res = 0
for n in range(N):
    res += int(heapq.heappop(a))
print(-res)

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

Submission status: Accepted

Solution code:
import heapq


nm = list(map(int, input().split()))
n, m = nm[0], nm[1]

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

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

heapq.heapify(prices)

while m > 0:
    top = heapq.heappop(prices)
    discounted = ((top * -1) // 2) * -1
    heapq.heappush(prices, discounted)
    m -= 1


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

Submission status: Accepted

Solution code:
import heapq

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

input_list = [-x for x in input_list]

heapq.heapify(input_list)
discount_element = heapq.heappop(input_list)


i = 0
while i < m:
    discount_element = -(-(discount_element) // 2)
    heapq.heappush(input_list, discount_element)
    discount_element = heapq.heappop(input_list)
    i += 1

heapq.heappush(input_list, discount_element)

print(-(sum(input_list)))

Submission status: Accepted

Solution code:
# 要は、M 階動的に最大値を半分にしていけばよい
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [i*-1 for i in a]
heapq.heapify(a)

for _ in range(m):
    pop = heapq.heappop(a)
    p = -(pop*-1//2)
    # 負数の切り捨て（割り切れないとき）は絶対値が1上がるので注意
    heapq.heappush( a, p)
print(sum(list(a))*-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):
    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_max = heapq.heappop(a)
    heapq.heappush(a,tmp_max - tmp_max//2) #プッシュ
print(-sum(a))

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
A = [-i for i in map(int,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:
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse = True)
while M > 0:
    A[0] //= 2
    for i in range(1,M):
        if i < N and A[i] >= A[0]:
            A[i] //= 2
        else:
            M -= i
            A.sort(reverse = True)
            break
    else:
        break
print(sum(A))

Submission status: Accepted

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

import numpy as np
l = list(map(int, input().split()))
l = list(map(lambda x: -1 * x, l))

import heapq

heapq.heapify(l)

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

print(-1 * sum(l))

Submission status: Accepted

Solution code:
import heapq as hq

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

print(-sum(b))

Submission status: Accepted

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

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

print(sum(a)*-1)

Submission status: Accepted

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

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

print(-sum(a))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort(reverse=True)
while m>0:
  a[0]//=2
  for i in range(1, m):
    if i<n and a[i] >= a[0]:
      a[i]//=2
    else:
      a.sort(reverse=True)
      m-=i
      break
  else:
    break
print(sum(a))

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush


def negative(str):
    return -1 * int(str)


def main():
    N, M = map(int, input().split(" "))
    A = list(map(negative, input().split(" ")))
    heapify(A)
    while M > 0:
        x = heappop(A)
        heappush(A, -1 * (-1 * x // 2))
        M -= 1
    print(sum(A) * -1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    a = LI()
    q = []
    for c in a:
        heapq.heappush(q,-c)
    for i in range(m):
        t = -heapq.heappop(q)
        heapq.heappush(q,-(t//2))

    return -sum(q)


print(main())

Submission status: Accepted

Solution code:
# ABC141D - Powerful Discount Tickets
from heapq import heapify, heappop, heappush

pop_max, push_max = lambda heap: -heappop(heap), lambda heap, x: heappush(heap, -x)


def main():
    N, M = map(int, input().split())
    A = [-i for i in map(int, input().split())]
    heapify(A)
    for _ in range(M):
        x = pop_max(A)
        push_max(A, x // 2)
    ans = -sum(A)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

N, M = tuple(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) * (-1) // 2
    heapq.heappush(A, tmp * (-1))
print(sum(A) * (-1))

Submission status: Accepted

Solution code:
import heapq

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

    heapq.heapify(A)

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


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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

print(sum(a) * -1)

Submission status: Accepted

Solution code:
from _collections import deque


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)


def good(ub):
    cnt = 0
    for a in A:
        base = 1
        while (a // base) > ub:
            base *= 2
            cnt += 1
            if cnt > M:
                return False
    return True


import numpy
import scipy
from collections import deque
#https://atcoder.jp/contests/abc141/tasks/abc141_d
#D - Powerful Discount Tickets
"""
need to consider the case that ticket is not enough to lower everything
"""
N = gi()
M = gi()
A = [0] * N

for i in range(N):
    A[i] = gi()

A.sort()
low = 0
high = A[N - 1]

while low < high:
    mid = (low + high) // 2
    if (good(mid)):
        high = mid
    else:
        low = mid + 1

after = []
remains = M
for a in A:
    base = 1
    while a // base > low:
        base *= 2
        remains -= 1

    after.append(a // base)

after.sort()

ans = 0
for i in range(N - 1, -1, -1):
    if remains:
        remains -= 1
        ans += after[i] // 2
    else:
        ans += after[i]

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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):
    a=heapq.heappop(A)
    heapq.heappush(A,-(-a//2))
print(-sum(A))

Submission status: Accepted

Solution code:
# coding: utf-8
import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: -1 * x, A))
# A.sort(reverse=True)
heapq.heapify(A)
for i in range(M):
    tmp = heapq.heappop(A)
    heapq.heappush(A, -1 * (-tmp // 2))
print(-sum(A))

Submission status: Accepted

Solution code:
# ABC-141-D
# https://qiita.com/ellio08/items/fe52a9eb9499b7060ed6
import heapq

N, M = map(int, input().split())
A = [i * (-1) for i in list(map(int, input().split()))]
heapq.heapify(A)

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

# これだとTLEになる。
# for _ in range(M):
#     A[A.index(max(A))] //= 2

print(sum(A)*-1)

Submission status: Accepted

Solution code:
import heapq
def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    for i,aa in enumerate(a):
        a[i] = -1 * aa
    heapq.heapify(a)
    for i in range(m):
        tmp = heapq.heappop(a) * (-1) // 2
        heapq.heappush(a,tmp * (-1))
    print(sum(a) * (-1))
if __name__=='__main__':
    main()

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()))
for i in range(N):
    A[i]*=-1

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

print(sum(A)*-1)

Submission status: Accepted

Solution code:
#Priority Queueを使った解法
import heapq

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

heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
#二分探索を使った解法
import bisect
N,M = map(int,input().split())
A = list(map(int,input().split()))

A.sort()
while M != 0:
    x = bisect.bisect_left(A,A[-1]//2)
    if N-x <= M:
        M -= N-x
        for i in range(x,N):
            A[i] = A[i]//2
        A.sort()
    else:
        for i in range(N-M,N):
            A[i] = A[i]//2
        M = 0
        A.sort()

print(sum(A))

Submission status: Accepted

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

A.sort()
while M != 0:
    x = bisect.bisect_left(A,A[-1]/2)
    if N-x <= M:
        M -= N-x
        for i in range(x,N):
            A[i] = A[i]/2
        A.sort()
    else:
        for i in range(N-M,N):
            A[i] = A[i]/2
        M = 0
        A.sort()

print(sum(map(int,A)))

Submission status: Accepted

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

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 i in range(M):
    b = heapq.heappop(A) * (-1)
    heapq.heappush(A, (b // 2) * (-1))
    

print(sum(A) * -1)

Submission status: Accepted

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

A.sort()
l = -1
r = A[-1] + 1


while r - l > 1:
    m = (r + l) // 2
    mc = 0
    a = 0
    for i in range(N):
        s = A[i]
        while m < s:
            s //= 2
            mc += 1
        a += s
    if mc <= M:
        r = m
        ans = a - (M - mc) * ((m // 2) + m % 2)
    else:
        l = m 
            
print(ans)

Submission status: Accepted

Solution code:
#n = int(input())
#L = list(map(int, input().split()))
import math
import sys
import heapq
import fractions
L = list(map(int, input().split()))
A = list(map(int, input().split()))
A = [n*(-1) for n in A]
heapq.heapify(A)
for _ in range(L[1]):
    mx = heapq.heappop(A)*(-1)
    heapq.heappush(A, (mx//2)*(-1))

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

Submission status: Accepted

Solution code:
import heapq


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

# print(a_l)

ans = 0
heapq.heapify(a_l)
for i in range(m):
    tmp = (-1) * heapq.heappop(a_l)
    heapq.heappush(a_l, (-1) * (tmp // 2))
    # print(a_l)
for i in range(len(a_l)):
    ans -= a_l[i]
print(ans)

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

print(sum(A) * -1)

Submission status: Accepted

Solution code:
import heapq

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

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

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

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 _ in range(M):
    heapq.heapreplace(A, int(A[0]/2))
print(-sum(A))

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):
#Hは全部マイナスをつけたからaは最大値的なのはいる
    a = heapq.heappop(A)
    heapq.heappush(A, int(a/2))
print(-sum(A))

Submission status: Accepted

Solution code:
import math
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):
    a_max = heapq.heappop(a)
    heapq.heappush(a,-(-a_max//2))
print(-sum(a))

Submission status: Accepted

Solution code:
import heapq

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

B = []

for i in A:
    B.append(-i)

heapq.heapify(B)

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

print(-sum(B))

Submission status: Accepted

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

a=[-1*i for i in a]#最大値をとるため＊－１
heapq.heapify(a)#二分木の形にする
for i in range(m):#ｍ回
    ma=heapq.heappop(a)#listから最小（最大）を取り出しその値を記憶するためのma
    ma*=-1#-のままだと-3//2=2になってしまうので計算が合わない
    heapq.heappush(a,-1*(ma//2))#2で割った値に－１を懸けて戻す
print(sum(a)*-1)#https://qiita.com/T_Wakasugi/items/dac6eb77a3cace54f95e

Submission status: Accepted

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

a=[-1*i for i in a]
heapq.heapify(a)
for i in range(m):
    ma=heapq.heappop(a)
    ma*=-1
    heapq.heappush(a,-1*(ma//2))
print(sum(a)*-1)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y
def primes(n):
    P = [2]
    for L in range(3, n):
        isP = True
        for L2 in P:
            isP = isP and L%L2
            if not isP: break
        if isP: P.append(L)
    return P


N,M=LI()
As = LI()
Bs = list(map(lambda x: -x, As))
heapq.heapify(Bs)

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

print(-sum(Bs))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
As = list(map(int, input().split()))
ks = []
for a in As:
    ks.append(len(bin(a))-2)
K=100
d = [0]*K
for k in ks:
    d[k] += 1
s = 0
ss = 0
ri = 0
for i in range(K):
    i = K-i-1
    s += d[i]
    ss += s
    if ss >= M:
        ri = i
        break
Bs = []
qs = 0
for a in As[::-1]:
    q=max(0, len(bin(a))-2-ri)
    qs += q
    Bs.append(a//(2**q))
Bs.sort()
r = 0
c = 0
for b in Bs[::-1]:
    if c < M-qs:
        b = b//2
    c += 1
    r += b
print(r)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

q = []
N, M = map(int, input().split())
A = map(int, input().split())

for a in A:
    heappush(q, -a)

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

print(-1 * sum(q))

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

Submission status: Accepted

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

A = [a * (-1) for a in A]
import heapq
heapq.heapify(A)

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

print(abs(sum(A)))

Submission status: Accepted

Solution code:
import heapq

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

cnt = 0
while cnt < M:
  a = heapq.heappop(A)
  heapq.heappush(A,-((-a)//2))
  cnt += 1
print(-sum(A))

Submission status: Accepted

Solution code:
import heapq
from sys import stdin
n,m = map(int,stdin.readline().split())
*l, = map(lambda x:-int(x),stdin.readline().split())
heapq.heapify(l)
for i in [0]*m:
  a=heapq.heappop(l)
  heapq.heappush(l, -(-a//2))
print(-(sum(l)))

Submission status: Accepted

Solution code:
import collections
import math
import operator as op
from functools import reduce
import numpy as np
import math
import bisect
import heapq


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


def get_inputs(cast_func=int):
    return list(map(cast_func, input().split()))


def get_input(cast_func=int):
    return cast_func(input())


def main():
    N, M = get_inputs()
    A = get_inputs()

    max_heap = [-a for a in A]
    heapq.heapify(max_heap)
    while M > 0:
        a_max = -heapq.heappop(max_heap)
        a_max //= 2
        heapq.heappush(max_heap, -a_max)
        M -= 1

    ans = -sum(max_heap)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq

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

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

print(-sum(a))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
L=list(map(int,input().split()))
Lh=list(map(lambda x: x*(-1), L))
import heapq
#heapqは置き直さなくてOK
heapq.heapify(Lh)
for _ in range(m):
    x=heapq.heappop(Lh)
    heapq.heappush(Lh,(x+1)//2)#負の数の割り算のため+1
print(sum(Lh)*(-1))

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().strip().split())
A = list(map(lambda x: int(x)*(-1), input().strip().split())) # -1 for heap

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

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

Submission status: Accepted

Solution code:
import math
import heapq

N,M = map(int,input().split())
A = [0]*N
A = list(map(lambda x: int(x)*(-1),input().split()))
if (N == 1):
    print((-1 * A[0])//(2**M))
else:
    """
    while (M != 0):
        A.sort(reverse=True)
        y = min(math.floor(log2(A[0]/A[1])+1),M)
        A[0] //= 2**y
        M -= y
    """
    """
    A.sort(reverse=True)
    for i in range(N):
        y = min(A[i] // 2,M)
        A[i] //= 2**y
        M -= y
        if (M <= 0):
            break
    """
    heapq.heapify(A)

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

Submission status: Accepted

Solution code:
import heapq

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

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

heapq.heapify(A)

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

Submission status: Accepted

Solution code:
# ----- 優先度付きキュークラス ----- #
import heapq

class PriorytyQueue(object):

    def __init__(self, arr, target='min'):
        self.arr = arr
        self.target = target
        self._heapify()
    
    def _heapify(self):
        if self.target == 'max':
            self.arr = list(map(lambda x:x*(-1), self.arr))
        heapq.heapify(self.arr)
    
    def push(self, x):
        if self.target == 'max':
            x *= -1
        heapq.heappush(self.arr, x)

    def pop(self):
        res = heapq.heappop(self.arr)
        if self.target == 'max':
            return res*(-1)
        else:
            return res
    
    def get_arr(self):
        if self.target == 'max':
            return list(map(lambda x:x*(-1), self.arr))
        else:
            return self.arr
    
    def is_empty(self):
        return len(self.arr) == 0

N, M = map(int, input().split())
A = list(map(int, input().split()))
pq = PriorytyQueue(A, target='max')

for i in range(M):
    max_value = pq.pop()
    pq.push(max_value//2)

print(sum(pq.get_arr()))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
import numpy as np
A = list(map(int,input().split()))
A.sort(reverse = True)
B = list(map(int,np.floor(np.log2(np.array(A)))))
BB = B
C = [0]*len(A)
MM = M
for i in range(max(B),-1,-1):
  k = BB.count(i)
  if MM < k:
    break
  else:
    MM -= k
    for j in range(k):
      C[j]+=1
      BB[j]-=1

for i in range(N):
  if C[i]==0:
    break
  else:
    A[i] = A[i]//2**C[i]

A.sort(reverse = True)
for i in range(min(MM,len(A))):
  A[i] = A[i]//2

print(sum(A))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from heapq import heappush,heappop,heapify
def resolve():
    n,m=map(int,input().split())
    A=list(map(lambda x:-int(x),input().split()))
    heapify(A)
    for _ in range(m):
        x=-heappop(A)
        x//=2
        heappush(A,-x)

    print(-sum(A))
resolve()