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

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 collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


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 [Scanner.string() 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 [Scanner.int() 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):
        lower, upper = [], []
        i = 1
        while i * i <= n:
            if n % i == 0:
                lower.append(i)
                if i != n // i:
                    upper.append(n // i)
            i += 1
        return lower + upper[::-1]

    @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

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


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 solve():
    N, M = Scanner.map_int()
    A = Scanner.map_int()
    A = [-a for a in A]
    heapq.heapify(A)
    for _ in range(M):
        x = -heapq.heappop(A)
        x //= 2
        heapq.heappush(A, -x)
    print(-sum(A))


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

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

# N = 3
# M = 3
# A = [2, 13, 8]

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

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

Submission status: Accepted

Solution code:
from heapq import heappush as hpush
from heapq import heappop as hpop

class Descending_HeapQueue:
    def __init__(self, hq=[]):
        self.hq = []
        for i in hq:
            self.push(i)
    def push(self, n):
        hpush(self.hq, -n)
    def pop(self):
        return -hpop(self.hq)
    def sum(self):
        return -sum(self.hq)
    def __str__(self):
        return [-i for i in self.hq].__str__()

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    dhq = Descending_HeapQueue(A)
    for _ in range(M):
        dhq.push(dhq.pop() // 2)
    print(dhq.sum())
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):
    mx=heapq.heappop(a)
    heapq.heappush(a, (-1)*(-mx//2))

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
a = [-int(x) for x in input().split()]
heapq.heapify(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())
p = list(map(int,input().split()))
price = [x*(-1) for x in p]
heapq.heapify(price)
while m != 0:
    max_price = heapq.heappop(price)*(-1)
    heapq.heappush(price,(max_price//2)*(-1))
    m -= 1
print(sum(price)*(-1))

Submission status: Accepted

Solution code:
import heapq #今回は優先度キューを使う

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

A = list(map(lambda x:-int(x), input().split())) #優先度付きキューは最小値しか出せないので、×-1して最大値を最小値にしている
#A.sort() 今回は間に合わない
heapq.heapify(A) #優先度付きキューに変換
#print(A)

for _ in range(M):
    a = heapq.heappop(A) #最小値取得
    a = -a // 2 #負のまま計算すると切り捨てが違うところで起こる
    heapq.heappush(A,-a) #優先度付きキューに挿入

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

print(sum(a)*(-1))

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
A = [-int(x) for x in input().split()]
heapq.heapify(A)
for _ in range(M):
    pop = heapq.heappop(A)
    if pop % 2 == 0:
        num = pop//2
    else:
        num = (pop+1)//2
    heapq.heappush(A, num)

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq
import sys

def input():
    return sys.stdin.readline().strip()

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

    heapq.heapify(A)

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
# pythonのheapqは最小値しか取り出せないので−1をかける
a = list(map(lambda x: -1*int(x), input().split()))
# heapqへ
heapq.heapify(a)
for i in range(m):
    tmp = heapq.heappop(a)
    tmp *= -1
    x = tmp // 2 * -1
    heapq.heappush(a, x)

print(-sum(a))

Submission status: Accepted

Solution code:
# 優先度付きキューとか言うものが使えるかどうかが鍵になる
# pythonでは標準でheapqが使える．要するにヒープのこと．ただしヒープでは最小値しか取り出せないのでそこに注意する必要がある.
# 計算量はO(log(N))になる
N,M = map(int,input().split())
A = list(map(int,input().split()))
# 解法 bisectとsort(最初だけ)を使う
# dequeでbisectって使えんのかなぁ？
#A.sort()
#from collections import deque
#A = deque(A)
A = [-a for a in A]
import heapq
heapq.heapify(A)
import bisect
for i in range(M):
    a = heapq.heappop(A)
    new = a/2
    # listに挿入する．ただしpythonのlistは可変長配列なので，linked-listではない.それゆえ末尾や先頭以外への要素の挿入はO(N)かかる
    #bisect.insort_left(A,new)   # やってることはA.sort(bisect.bisect_left(A,new),new)．
    heapq.heappush(A,new)
import numpy as np
A = np.array(A,dtype=np.int64)
print(-A.sum())

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

N, M = map(int, input().split())
A = []
for i in input().split():
    A.append(-int(i))
heapify(A)
for _ in range(M):
    a = -heappop(A)
    heappush(A, (a // 2) * -1)
# print('A', A)
ans = -sum(A)
print(ans)

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

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


if __name__ == '__main__':
    resolve()

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

Submission status: Accepted

Solution code:
from heapq import heappop, heapify, heappush
def main():
    n, m = list(map(int, input().split()))
    A = list(map(lambda x: -int(x), input().split()))
    heapify(A)
    for _ in range(m):
        a = heappop(A)
        if a == 0:
            break
        a = -int(-a // 2)
        heappush(A, a)
    print(sum([-a for a in A]))

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()]
heapq.heapify(a)
for i in range(m):
 p=heapq.heappop(a)
 p*=-1
 p//=2
 heapq.heappush(a,-p)
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):
    # 一番高い商品に割引券を使って入れ直す
    a_max = -1 * heapq.heappop(a)
    a_max //= 2
    heapq.heappush(a, -a_max)

print(-sum(a))

Submission status: Accepted

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

heapq.heapify(a)

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

print(-sum(a))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def main():
    N, M = mi()
    A = list(map(lambda x: -int(x), input().split()))
    heapq.heapify(A)
    for i in range(M):
        t = heapq.heappop(A)
        heapq.heappush(A, -(-t//2))
    print(-sum(A))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b=mi()
l=list(mi())
l=list(map(lambda x: x*-1 , l))
heapq.heapify(l)
for i in range(b):
  s=heapq.heappop(l)
  s=(-1)*(((-1)*s)//2)
  heapq.heappush(l,s)
ans=0
for i in range(a):
  d=heapq.heappop(l)
  ans+=(-1)*d
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

for _ in range(m):
    x = heapq.heappop(a)
    heapq.heappush(a, (x+1)//2)

print(-sum(a))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

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

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()))
if N == 1:
    print(N >> M)
    exit()
heapify(A)
while M > 0:
    a = -heappop(A)
    while M > 0 and a >= -A[0]:
        a >>= 1
        M -= 1
    heappush(A, -a)
print(-sum(A))

Submission status: Accepted

Solution code:
from heapq import*

N, M = map(int, input().split())
a = list(map(lambda x: -int(x), input().split()))
heapify(a)
for _ in range(M):
    n = - heappop(a)
    n //= 2
    heappush(a, -n)
print(-sum(a))

Submission status: Accepted

Solution code:
#リストの挿入と最大値の取得を同時に行う
#そのようなものを高速でできるデータ構造としてheapq(優先度つきqがあげられる)
#最大値を取得する関数はheapqには入ってないためリストの要素を-1倍してから最小値を求めればいい
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
a=list(map(lambda x:x*(-1),a))

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

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):
    temp = -heapq.heappop(a)
    temp//=2
    heapq.heappush(a,-temp)
ans = 0
for _ in range(n):
    ans -= heapq.heappop(a)
print(ans)

Submission status: Accepted

Solution code:
def tickets(a, t):
  # a の最大値をt以下にするのに必要なチケットの枚数を答える
  ret = 0
  for x in a:
    while (x > t):
      x //= 2
      ret += 1
  return ret

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

  lb = -1
  ub = 1000000000
  while (ub - lb > 1):
    mid = lb + (ub - lb) // 2
    t = tickets(a, mid)
    if t < m:
      ub = mid
    else:
      lb = mid

  t = 0
  for i in range(n):
    while (a[i] > ub):
      a[i] //= 2
      t += 1

  a.sort(reverse=True)

  for i in range(min(n, m-t)):
    a[i] //= 2

  print(sum(a))

  return

if __name__ == "__main__":
  resolve()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
A = map(int, readline().split())

import heapq
q = []
for a in A:
    heapq.heappush(q, -a)

while M > 0:
    a = -heapq.heappop(q)
    a //= 2
    heapq.heappush(q, -a)
    M -= 1

ans = 0
while len(q) > 0:
    ans += abs(heapq.heappop(q))
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
M = max(a)
a = sorted(a,reverse=True)
t = 0
while M > 1:
    M = -(-M//2)
    t += 1
z = [[] for i in range(t+2)]
for i in range(n):
    s = 0
    b = a[i]
    while b > 1:
        b = -(-b//2)
        s += 1
    z[t-s].append(a[i])
count = 0
for i in range(t+1):
    z[i] = sorted(z[i])
    if count > m:
        break
    while z[i]:
        if count >= m:
            break
        c = z[i].pop()
        z[i+1].append(c//2)
        count += 1
ans = 0
for A in z:
    ans += sum(A)
print(ans)

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)
ans = 0
for i in range(M):
    most_expensive = -heapq.heappop(A)
    most_expensive //= 2
    heapq.heappush(A, -most_expensive)
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))  # 各要素を-1倍

heapq.heapify(a)

for i in range(m):
    minimum=heapq.heappop(a)
    mini=((minimum*(-1))//2)*(-1)
    heapq.heappush(a,mini)
    
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 i in range(m):
    hangaku = (heapq.heappop(a) * -1) // 2 * -1
    heapq.heappush(a, hangaku)    

print(-1*sum(a))

Submission status: Accepted

Solution code:
import heapq

n, m = map(int,input().split())
a = [-1 * int(i) for i in input().split()]

ans = 0

heapq.heapify(a)

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

print(-1*sum(a))

Submission status: Accepted

Solution code:
import heapq

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

for x in range(M):
    maxA = heapq.heappop(A)
    heapq.heappush(A, -1 * ((-1 * maxA) // 2))
A = list(map(lambda x: x * (-1), A))

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)

while m > 0:
    x = heapq.heappop(A)*(-1)
    x //= 2
    A.append(-x)
    m -= 1
print(abs(sum(list(A))))

Submission status: Accepted

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

def insertHeap(array, val):
    array.append(val)
    n = len(array)-1
    while n != 0:
        parent = int((n - 1) / 2)
        if array[n] > array[parent]:
            tmp = array[n]
            array[n] = array[parent]
            array[parent] = tmp
            n = parent
        else:
            break
    return array

def desertHeap(array):
    if array == []:
      return None
    array[0], array[-1] = array[-1], array[0]
    res = array.pop(-1)
    n = len(array)
    if n == 0 or n == 1:
      return res
    parent = 0
    while True:
        child = 2 * parent + 1
        if child >= n: break
        if (child + 1 < n) and array[child] < array[child + 1]:
            child += 1
        if array[parent] < array[child]:
            array[child], array[parent] = array[parent], array[child]
            parent = child;
        else:
            break
    return res
 

li = []
a.sort()
for aa in a:
  li = insertHeap(li, aa)

for i in range(m):
  val = desertHeap(li)
  li = insertHeap(li, val//2)

print(sum(li))

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))  # 各要素を-1倍することで，最小最大を逆転

heapq.heapify(a)#優先度付きキューに変換

for i in range(m):
  tmp = heapq.heappop(a)
  heapq.heappush(a,(-tmp//2)*(-1))#負の剰余では切り捨て方向が異なってしまうので，いったんプラスにする．
  
print(-sum(a))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# D

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop, heapify
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

q = []
for t in a:
    # heappush(q, (-t, 0))
    heappush(q, -t)
# print(q)

for m in range(M):
    val = heappop(q)
    val = (-val)//2
    heappush(q, -val)

print(-sum(q))

Submission status: Accepted

Solution code:
import heapq
N, M = map(int,input().split())
al = list(map(int,input().split()))
al = list(map(lambda x: x*(-1), al))
heapq.heapify(al)

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

Submission status: Accepted

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

heapq.heapify(malist)

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

print(-sum(malist))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

    for i in range(m):
        num, x, cnt = heappop(heap)
        heappush(heap, [num / 2, x, cnt + 1])

    ans = 0
    for i in range(n):
        num, x, cnt = heappop(heap)
        ans += int(num)
    print(-ans)


if __name__ == "__main__":
    resolve()

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

Submission status: Accepted

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
A_dic = {} #value: idx
for i in range(N):
    if A[i] not in A_dic:
        A_dic[A[i]] = []
    A_dic[A[i]].append(i)

# その時の最大のAに１つ使う　これを繰り返す
total = 0
rest = M
if N == 1:
    while rest > 0:
        rest -= 1
        A[0] //= 2
    total = A[0]
elif N == 2:
    while rest > 0:
        rest -= 1
        if A[0] >= A[1]:
            A[0] //= 2
        else:
            A[1] //= 2
    total = A[0] + A[1]
else:
    hq = [-A[i] for i in range(N)]
    heapq.heapify(hq)
    while rest > 0:
    #     temp_idx = A_items[0][1]
    #     while A_items[0][0] >= A_items[1][0]:
    #         rest -= 1
    #         A_items[0][0] //= 2
    #         A[temp_idx] //= 2
    #     idx = 2
    #     while A_items[0][0] < A_items[idx][0]:
    #         idx += 1
    #         if idx >= N-1:
    #             break
    #     u, v = A_items[0], A_items[idx-1]
    #     A_items[idx-1] = u
    #     A_items[0] = v
    # total = sum(A)
        
        max_v = heapq.heappop(hq) * (-1)
        max_idx = A_dic[max_v].pop()
        A[max_idx] //= 2
        if max_v//2 not in A_dic:
            A_dic[max_v//2] = []
        A_dic[max_v//2].append(max_idx)
        heapq.heappush(hq, (max_v//2) * (-1))
        rest -= 1
    total = sum(A)
    


print(total)

Submission status: Accepted

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

for i in range(M):
    expe = heapq.heappop(q)
    expe = -expe // 2
    heapq.heappush(q, -expe)
print(-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)

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

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq

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

an = [-1 * i for i in an]

heapq.heapify(an)

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

print(-1 * sum(an))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

def solve():
    N, M = map(int, input().split())
    A = list(map(lambda x: int(x) * -1, input().split()))
    
    heapq.heapify(A)
    
    for _ in range(M):
      t = heapq.heappop(A)
      heapq.heappush(A, -1*(-t//2))
    
    return -sum(A)

print(solve())

Submission status: Accepted

Solution code:
import heapq
def main():
    n, m = list(map(int, input().split()))
    t = list(map(int, input().split()))
    t = list(map(lambda x: x*(-1), t))
    heapq.heapify(t)
    while m > 0:
        v = heapq.heappop(t) * -1
        heapq.heappush(t, (v // 2)* -1)
        m -= 1

    print(sum(t)*-1)


if __name__ == '__main__':
    main()

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
import heapq

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, M = NMI()
    A = NLI()
    A = [-a for a in A]
    heapq.heapify(A)
    for i in range(M):
        a_max = -heapq.heappop(A)
        a_max = a_max // 2
        heapq.heappush(A, -a_max)
    print(-sum(A))



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(0,N):
    A[i]=-A[i]

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

ans=0
for i in range(0,N):
    ans-=A[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):
    x = heapq.heappop(a)
    heapq.heappush(a, -1 * ((-x) // 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):
    t = (heapq.heappop(a)*(-1)//2)*(-1)
    heapq.heappush(a,t)

print(sum(a)*(-1))

Submission status: Accepted

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

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

print(-sum(pq))

Submission status: Accepted

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

heapify(A)

for i in range(M):
    n = -1 * heappop(A)
    heappush(A, -1*(n//2))
    #print(n, A)
 
print(-1*sum(A))

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

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

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

print(-1*sum(A))

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

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

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

print(-1*sum(A))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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

al = [v*(-1) for v in al]
heapq.heapify(al)

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

print(sum(al)*(-1))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Jun  3 18:35:23 2020

@author: NEC-PCuser
"""
import heapq

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

heapq.heapify(A)

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

Submission status: Accepted

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

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

import heapq
heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

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

from heapq import heapify, heappop, heappush

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

heapify(a)

for i in range(m):
    min = heappop(a)
    heappush(a, (-1)*(-1*min//2)) # 要素の挿入

ans = -sum(a)

print(ans)

Submission status: Accepted

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

from heapq import heapify, heappop, heappush

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

for i in range(m):
    max = -1* heappop(a)
    heappush(a, int(-1*max/2))  # 要素の挿入

a = [-1*item for item in a]
ans = sum(list(a))

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
import heapq

input = lambda: sys.stdin.readline().rstrip()


def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    Am = [0] * N
    for i in range(N):
        Am[i] = -A[i]

    heapq.heapify(Am)

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

    print(-sum(Am))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(prod)

for _ in range(m):
    a = heapq.heappop(prod)*(-1)

    a = a//2

    heapq.heappush(prod,(-1)*a)


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

print(sum(ans))

Submission status: Accepted

Solution code:
import queue


def m():
    N, M = map(int, input().split())
    q = queue.PriorityQueue()
    A = list(map(int, input().split()))
    ans = []
    for a in A:
        q.put(-a)
    while M > 0:
        x = -q.get()
        x = -(x >> 1)
        M -= 1
        q.put(x)
    while not q.empty(): ans.append(q.get())
    return abs(sum(ans))


print(m())

Submission status: Accepted

Solution code:
from heapq import*
n, m, *a = eval(",-".join(open(0).read().split()))
a.sort()
for _ in [0]*-m:heappush(a, 0--heappop(a)//2)
print(-sum(a))