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
import math
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
logof2=[0]*N
mi=0
buf=0
#print(A)
for i in range(N):
    A[i]=-A[i]  #heapqは実装上最初値しか取り出さないので、数列を-1倍し、最小値が最大に当たるようにする
heapq.heapify(A)#priority_que化
for i in range(M):
    buf=heapq.heappop(A)    #最大値を取り出すことに相当
    buf=(-buf)/2           #切り捨て(floor)の挙動は負数の時おかしくなるので一旦正値に変換して計算し
    buf=-buf                #負数に戻す
    heapq.heappush(A,buf)   #
    #print(A)
for i in range(N):
    mi=mi+math.floor(-1*A[i])  #残った要素ごとの足し算に相当する

print(mi)

Submission status: Accepted

Solution code:
import heapq
import math
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
logof2=[0]*N
mi=0
buf=0
#print(A)
for i in range(N):
    A[i]=-A[i]
heapq.heapify(A)
for i in range(M):
    buf=heapq.heappop(A)
    buf=(-buf)//2
    buf=-buf
    heapq.heappush(A,buf)
    #print(A)
for i in range(N):
    mi=mi-math.floor(A[i])

print(mi)

Submission status: Accepted

Solution code:
import heapq

n,m=map(int,input().split())
a = sorted([int(i) for i in input().split()])
a = list(map(lambda x: x*(-1), a))
heapq.heapify(a)

while m > 0:
    t = heapq.heappop(a)*(-1)//2
    heapq.heappush(a,-t)
    m-=1
print(-sum(a))

Submission status: Accepted

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

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, a))
heapq.heapify(a)

#print(a)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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

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

print(-sum(A))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(n):
        a[i] = -a[i]
    heapify(a)
    for _ in range(m):
        b = heappop(a)
        b = -(-b // 2)
        heappush(a, b)
    print(-sum(a))




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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
import math
#これを加える！！！！
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

"""
a = [1,7,3,5,4]

#heapify
#配列a = [1,7,3,5,4]をheapにする
heapq._heapify_max(a)
print(a) #[7, 5, 3, 1, 4]

#heappop
#最大値の取り出し
print(_heappop_max(a)) #7
print(a) #[5, 4, 3, 1]

#heappush
#要素(2)の挿入
_heappush_max(a,2)
print(a) #[5, 4, 3, 1, 2]

#最大値の取り出し
print(_heappop_max(a)) #5
"""

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

for j in range(M):
    _heappush_max(a, _heappop_max(a)//2)
print(sum(a))

Submission status: Accepted

Solution code:
import heapq
from numpy import ceil,sum
N,M = (int(x) for x in input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(A)
for i in range(M):
    t1 = heapq.heappop(A)
    t2 = t1 / 2
    heapq.heappush(A, t2)
B = ceil(A)
print(int(sum(B)*(-1)))

Submission status: Accepted

Solution code:
import heapq
from math import ceil

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

if len(A) == 1:
    for i in range(M):
        A[0] = ceil(A[0]/2)
    A[0] = -A[0]
    print(A[0])
else:
    count = 0
    heapq.heapify(A)
    a = heapq.heappop(A)
    b = heapq.heappop(A)
    while count < M:
        while a <= b:
            a = ceil(a/2)
            count += 1
            if count == M:
                break
        if count == M:
            break
        heapq.heappush(A,a)
        a = b
        b = heapq.heappop(A)
    heapq.heappush(A,a)
    heapq.heappush(A,b)
    ans = (-1)*sum(A)
    print(ans)

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

ans = 0
for i in range(N):
    ans += heapq.heappop(A)

print(-ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    N, M = Scanner.map_int()
    A = [-a for a in Scanner.map_int()]
    heapq.heapify(A)
    for _ in range(M):
        a = heapq.heappop(A)
        a = -(-a // 2)
        heapq.heappush(A, a)
    print(-sum(A))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import ceil
from heapq import heappop,heappush
from collections import deque
N,M = map(int,input().split())
a = list(map(int,input().split()))
a = list(map(lambda x:x*(-1), a))
A = []

for a_ in a:
    heappush(A,a_) 

for _ in range(M):
  maxA = ceil(heappop(A)/2)
  A.append(maxA)
  
ans = sum(A)*-1
print(ans)

Submission status: Accepted

Solution code:
#python3
from heapq import heappop
from heapq import heappush
from heapq import heapify
def main():
    n, m = map(int, input().split())
    a = [-int(i) for i in input().split()]
    heapify(a)
    for i in range(m):
        v = -heappop(a)//2
        heappush(a, -v)
    ans = sum([-i for i in a])
    print(ans)
main()

Submission status: Accepted

Solution code:
from collections import deque

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

Ai.sort(reverse=True)
Ai_deque = deque(Ai)
kari = deque()
for _ in range(M):
    try:
        if Ai_deque[0] > kari[0]:
            value = Ai_deque.popleft() // 2
        else:
            value = kari.popleft() // 2
    
    except:
        if not kari:
            value = Ai_deque.popleft() // 2
        else:
            value = kari.popleft() // 2
    
    kari.append(value)
    
print(sum(Ai_deque) + sum(kari))

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
A = [int(x) * -1 for x in input().split()]
heapq.heapify(A)

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

ans = sum([int(x * -1) for x in A])
print(ans)

Submission status: Accepted

Solution code:
import queue

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

q = queue.PriorityQueue()

for i in range(n):
    q.put(-a[i])

for i in range(m):
    x = q.get()
    x = -((-x) // 2)
    q.put(x)

ans = 0

for i in range(n):
    x = q.get()
    ans -= x

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import collections
from collections import deque
import heapq
#n = int(input())
n, m = map(int, sys.stdin.readline().split())
#s = input()
a = list(map(int, sys.stdin.readline().split()))
a = list(map(lambda x: -x, a))
heapq.heapify(a)
for i in range(m):
    x = heapq.heappop(a) * (-1)
    x = math.floor(x/2)
    heapq.heappush(a, -x)

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

Submission status: Accepted

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

import heapq

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a = [-x for x in a]  # Negate to use min-heap as max-heap
    heapq.heapify(a)
    for i in range(m):
        x = heapq.heappop(a) * (-1)
        x //= 2
        heapq.heappush(a, -x)
    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 i in range(m):
  tmp = int(heapq.heappop(a) / 2)
  heapq.heappush(a, tmp)
print(-1 * sum(a))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush, heapify

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = lr()
A = [-x for x in A]
heapify(A)

def discount(A):
    a = heappop(A)
    heappush(A, a/2)
    return A

for _ in range(M):
    A = discount(A)

total = sum(int(-x) for x in A)
print(total)

Submission status: Accepted

Solution code:


import heapq


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

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

    print(-sum(q))        


if __name__ == "__main__":
    submit()

Submission status: Accepted

Solution code:
import copy
import heapq

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

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

heapq.heapify(tmp_list)
#print(tmp_list)

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

print(str(int(-sum(tmp_list))))

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

Submission status: Accepted

Solution code:
#import numpy as np
import copy
import heapq

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

tmp_list = list(map(lambda x: x*(-1), a_list))
#print(tmp_list)
heapq.heapify(tmp_list)

#ticket_list = np.zeros(n)

for i in range(m):
    max_value = heapq.heappop(tmp_list)*(-1)
    heapq.heappush(tmp_list, (-1)*(max_value//2))

print(-sum(tmp_list))

#ans = 0
#for j in range(n):
#    ans += a_list[j] // (2**(ticket_list[j]))

#print(str(int(ans)))

Submission status: Accepted

Solution code:
import heapq as hq

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

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

ans=0
for i in range(n):
    ans+=int(-hq.heappop(A))
print(ans)

Submission status: Accepted

Solution code:
import math

n,m=map(int,input().split())
A=list(reversed(sorted(map(int,input().split()))))
L=[math.log(a,2) for a in A]
L.append(-1)

now=int(L[0]) #log2のどこまで使うか
for i in range(n):
    cnt=m//(i+1)
    d=now-int(L[i+1])
    if cnt<d:
        now-=cnt
        m=m%(i+1)
        break
    else:
        m-=d*(i+1)
        now=int(L[i+1])

for k in range(i+1):
    A[k]/=2**(int(L[k])-now)

A=list(reversed(sorted(A)))
for i in range(min(n,m)):
    A[i]/=2
for i in range(n):
    A[i]=int(A[i])
print(sum(A))

Submission status: Accepted

Solution code:
import math

n,m=map(int,input().split())
A=list(reversed(sorted(map(int,input().split()))))
L=[math.log2(a) for a in A]
L.append(-1)

now=int(L[0]) #log2のどこまで使うか
for i in range(n):
    cnt=m//(i+1)
    d=now-int(L[i+1])
    if cnt<d:
        now-=cnt
        m=m%(i+1)
        break
    else:
        m-=d*(i+1)
        now=int(L[i+1])

for k in range(i+1):
    A[k]/=2**(int(L[k])-now)

A=list(reversed(sorted(A)))
for i in range(min(n,m)):
    A[i]/=2
for i in range(n):
    A[i]=int(A[i])
print(sum(A))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

Solution code:
import heapq

n,m = map(int,input().split())
li = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(li)
for _ in range(m):
    tmp_min = heapq.heappop(li)
    heapq.heappush(li, (-1)*(-tmp_min//2))  # 計算誤差の関係で-1を2回かけてます
print(-sum(li))

Submission status: Accepted

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

sum=0
A=[-1 * i for i in A]
heapq.heapify(A)

for m in range(M):
    rep=-(-heapq.heappop(A)//2)
    heapq.heappush(A,rep)
for a in A:
    sum-=a

print(sum)

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
item = [-1 * int(a) for a in input().split()]
heapq.heapify(item)
ans = 0

for _ in range(m):
    item_max = heapq.heappop(item)
    item_max = item_max / 2
    heapq.heappush(item, item_max)

for i in item:
    ans += int(i)

print(- ans)

Submission status: Accepted

Solution code:
import copy
import math
import string
import heapq
import bisect
import sys
sys.setrecursionlimit(10**7)

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

while M > 0:
    M -= 1
    a = heapq.heappop(A)
    heapq.heappush(A,math.ceil(a/2))
ans = 0
for i in range(N):
    ans += abs(heapq.heappop(A))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    lastelt = heap.pop()
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

n,m,*a = map(int, open(0).read().split())

heapq._heapify_max(a)
s = sum(a)
d = 0
for i in range(m):
  t = _heappop_max(a)
  d += t-t//2
  _heappush_max(a, t//2)

print(s-d)

Submission status: Accepted

Solution code:
# https://juppy.hatenablog.com/entry/2019/04/05/%E8%9F%BB%E6%9C%AC_Python_%E3%83%97%E3%83%A9%E3%82%A4%E3%82%AA%E3%83%AA%E3%83%86%E3%82%A3%E3%82%AD%E3%83%A5%E3%83%BC_2_heapq_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3
import heapq
#これを加える！！！！
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

n,m,*a = map(int, open(0).read().split())


# a = [1,7,3,5,4]

# #heapify
# #配列a = [1,7,3,5,4]をheapにする
heapq._heapify_max(a)
# print(a) #[7, 5, 3, 1, 4]

# #heappop
# #最大値の取り出し
# print(_heappop_max(a)) #7
# print(a) #[5, 4, 3, 1]

# #heappush
# #要素(2)の挿入
# _heappush_max(a,2)
# print(a) #[5, 4, 3, 1, 2]

# #最大値の取り出し
# print(_heappop_max(a)) #5
s = sum(a)
d = 0
for i in range(m):
  t = _heappop_max(a)
  d += t-t//2
  _heappush_max(a, t//2)
  # print(a)

print(s-d)

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

Submission status: Accepted

Solution code:
import heapq
a,b = map(int,input().split())
L = list(map(int,input().split()))
L = [-x for x in L]

heapq.heapify(L)
for i in range(b):
    a =heapq.heappop(L)
    a= -(-a//2)
    heapq.heappush(L,a)

L = [-x for x in L]
print(sum(L))

Submission status: Accepted

Solution code:
import math

[n,m] = [int(x) for x in input().split(" ")]
an = [int(x) for x in input().split(" ")]
an.sort(reverse=True)

log2_an = [math.ceil(math.log2(x) + 1) for x in an]
max_log2 = log2_an[0]
rest_ticket = m

for i in range(max_log2):
    cnt = log2_an.count(log2_an[0])
    if(cnt <= rest_ticket):
        for j in range(cnt):
            an[j] = an[j] / 2
            log2_an[j] -= 1
    else:
        for j in range(rest_ticket):
            an[j] = an[j] / 2
        break
    rest_ticket -= cnt
    an.sort(reverse=True)

discounted_an = [math.floor(x) for x in an]
print(sum(discounted_an))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq

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

# ヒープキューでpopしたときに最大値を取得できるよう、全要素に-1を掛ける
minus_A = [i * -1 for i in A]

# Aをヒープキューリストに変換
heapq.heapify(minus_A)

# 最大価格の商品をM回割引していく
for i in range(M):
    val = heapq.heappop(minus_A)
    val /= 2
    val = int(val)
    heapq.heappush(minus_A, val)

# 割引券適用後の価格をまとめる
total = sum(minus_A)
print(total * -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):
    a_min = heapq.heappop(a)
    heapq.heappush(a, int(a_min / 2))

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

print(sum(a)*-1)

Submission status: Accepted

Solution code:
import math
import time
from collections import deque
from collections import defaultdict
from copy import deepcopy
import heapq

mod = 10 ** 9 + 7
t = time.time()



def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret


def main():
    N, M = iip()
    values = iip()
    if type(values) == int:
        values = [values]
    values = [-i for i in values]
    heapq.heapify(values)

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

    ans = 0
    #print(values)
    for value in values:
        ans += value
    ans = ans * -1
    print(ans)



main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
import heapq

def main():
    N, M = input_nums()
    A = input_nums()
    A = list(map(lambda x: -x, A))
    heapq.heapify(A)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
D - Powerful Discount Tickets
https://atcoder.jp/contests/abc141/tasks/abc141_d

"""
import sys


from heapq import heappop, heappush


def solve(N, M):
    hq = []
    for a in input().split():
        heappush(hq, int(a) * -1)
    for _ in range(M):
        x = heappop(hq)
        x *= -1
        x //= 2
        heappush(hq, -x)
    return sum(hq) * -1


def main(args):
    N, M = map(int, input().split())
    ans = solve(N, M)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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

from heapq import heappush, heappop

class MaxHeap:
  def __init__(self, li):
    self.hp = []
    for e in li:
      heappush(self.hp, -e)

  def push(self, x):
    heappush(self.hp, -x)

  def pop(self):
    ret = heappop(self.hp)
    ret *= -1
    return ret

  def seak(self):
    return -self.hp[0]

  def sum(self):
    return -sum(self.hp)

AMH=MaxHeap(A)
for i in range(M):
  a=AMH.pop()
  a=a//2
  AMH.push(a)
  
print(AMH.sum())

Submission status: Accepted

Solution code:
import heapq 
h = []

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

start = heapq.heappop(h)
for i in range(M):
  start = heapq.heappushpop(h, -((-start)//2))

print(-(sum(h)+start))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heapify,heappop,heappush
N,M=map(int,input().split())
A=list(map(int,input().split()))
A=list(map(lambda x:x*(-1),A))
heapify(A)
while(M>0):
    temp=heappop(A)*-1
    
    heappush(A,temp//2*-1)
    M-=1
print(sum(A)*-1)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import math
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
A =list(map(int, input().split()))
Hq = []
for a in A:
  heappush(Hq, -a)
 
for _ in range(m):
  max = -heappop(Hq)
  heappush(Hq, -math.floor(max/2))
print(-sum(Hq))

Submission status: Accepted

Solution code:
def main():
    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):
        x=heapq.heappop(a)
        heapq.heappush(a,(x+1)//2)
    
    print(sum(a)*-1)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

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

a = list(map(int,input().split()))
b = list(map(lambda x:-x,a))

heapq.heapify(b)

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

res = 0

for i in range(n):
  
  res += heapq.heappop(b)
  
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 _ in range(m):
    num = heapq.heappop(a)
    heapq.heappush(a, -(-num//2))

print(-sum(a))

Submission status: Accepted

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

Submission status: Accepted

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

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

heapq.heapify(ais)

for i in range(m):
    j = heapq.heappop(ais)
    heapq.heappush(ais, -(-j//2))
    #print(ais)

print(-sum(ais))

Submission status: Accepted

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

Submission status: Accepted

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

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

    for _ in range(M):
        a = heapq.heappop(A) * -1
        a = a // 2
        heapq.heappush(A, a * -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(int,input().split()))
for i in range(n):
    a[i] = -a[i]
heapq.heapify(a)
ans = 0
for i in range(m):
    temp = (heapq.heappop(a)+1)//2
    heapq.heappush(a,temp)
print(-sum(a))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
import numpy as np
N, M = map(int,input().split())
A = list(map(int,input().split()))
A = np.array(A)
A = -A
A = list(A)
heapify(A)
for _ in range(M):    
    s = heappop(A)
    heappush(A, -(-s // 2))
A = np.array(A)
print(-int(np.sum(A)))

Submission status: Accepted

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

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

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)


def d(x):
    return -((-x)//2)


for _ in range(m):
    b = heapq.heappop(a)
    heapq.heappush(a, d(b))

print(-sum(a))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
def int_(num_str):
    return int(num_str) * -1

Alist = list(map(int_, input().split()))
from heapq import heapify, heappop, heappush
heapify(Alist)
for i in range(M):
    heappush(Alist, heappop(Alist)/2)
ans = map(int_, Alist)
print(sum(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 _ in range(M):
    heapq.heappush(A, (heapq.heappop(A) + 1) // 2)

ans = sum(A) * -1

print(ans)

Submission status: Accepted

Solution code:
import heapq

cnt, ticket = map(int, input().split())
lst = list(map(lambda i:int(i) * (-1) , input().split()))
heapq.heapify(lst)

for _ in range(ticket):
  tmp_min = heapq.heappop(lst)
  heapq.heappush(lst, (-1) * (-tmp_min//2))
  
print(-sum(lst))

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 sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from heapq import heapify, heappop, heappush
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
a = [-i for i in LIST()]
heapify(a)
for i in range(m):
    b = heappop(a)
    b = - (- b // 2)
    heappush(a, b)
print(-sum(a))