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 sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

import heapq

def solve():
    n, m = MI()
    A = LI()

    A = list(map(lambda x: -x, A))

    heapq.heapify(A)
    # print(A)

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

    A = list(map(lambda x: int(-x), A))
    print(sum(A))
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import heapq


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

A = [a * -1 for a in A]

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

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

#N,Mを取得
n,m = map(int,input().split())
#A_iを取得する…と見せかけて、A_iを-1倍したものをListで取得
a = list(map(lambda x:int(x)*(-1),input().split()))

#AをListから、priority queueと言うものに変換(コレはheap queueだけど、まあ同じ)
heapq.heapify(a)

for _ in range(m):  #割引券持ってるだけ使い続ける
    x = heapq.heappop(a) * -1       #priority queueの先頭の値(一番値が小さい)を取り出して、-1をかけて元の値に戻す。
    x //= 2     #割引する
    heapq.heappush(a,-1*x)      #   priority queueにお返しする(-1をかけなおして)。

#割引が終わったら、合計金額を取得する。
print(-sum(a))

Submission status: Accepted

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

for i in range(M):
    x, a, d = heappop(Q)
    if x == 0:
        break
    heappush(Q, [-(a//pow(2, d+1)), a, d+1])

print(sum([-q[0] for q in Q]))

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

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)
now = heapq.heappop(A)
for _ in range(M):
    now = heapq.heappushpop(A, (now+1) // 2)
heapq.heappush(A, now)
print(-sum(A))

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

Submission status: Accepted

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

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    q = []
    heapify(q)
    for a in A: heappush(q, -a)
    for m in range(M):
        a = -heappop(q)
        if a == 0: 
            heappush(q, -a)
            break
        else:
            a //= 2
            heappush(q, -a)
    ans = 0
    for _ in range(N):
        ans -= heappop(q)
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

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

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
a = list(map(lambda x: -1*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 heapq

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

hpq = list(map(lambda x: -1 * x, a_lst))
heapq.heapify(hpq)
for i in range(m):
    x = heapq.heappop(hpq)
    heapq.heappush(hpq, x / 2)
 
print(sum(map(lambda x: int(-1 * x), hpq)))

Submission status: Accepted

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

A = list(map(lambda x: x*(-1), A))
heapq.heapify(A)
ans = 0
while M > 0:
    max_price = heapq.heappop(A)

    max_price = math.ceil(max_price/2)
    M -= 1
    heapq.heappush(A, max_price)


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

for a in A:
    ans += 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*(-1),a))
heapq.heapify(a)
while m>0:
    ma = heapq.heappop(a)*(-1)
    ma //=2
    heapq.heappush(a,ma*(-1))
    m-=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)*(-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:
n, m = [int(i) for i in input().split()]
prices = sorted([int(i) for i in input().split()], reverse=True)
d = 1
while(True):
	d *= 2
	if d * 2 > 10 ** 9:
		break
while(d > 0):
	for i, price in enumerate(prices):
		if price >= d:
			prices[i] = prices[i] // 2
			m -= 1
			if m == 0:
				d = 0
				break
	prices = sorted(prices, reverse=True)
	d /= 2
print (sum(prices))

Submission status: Accepted

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

print(sum(map(lambda x: int(-1 * x), hpq)))

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
n, m = [int(it) for it in input().split(' ')]
items = [ - int(it) for it in input().split(' ')]
heapify(items)
for i in range(m):
    heappush(items, - (- heappop(items) // 2))

print(- sum(items))

Submission status: Accepted

Solution code:
import heapq
N, M = [int(s) for s in input().split(' ')]
A = [int(s) for s in input().split(' ')]
q = []
for a in A:
    heapq.heappush(q, (-a, a))
for y in range(M):
    _, a = heapq.heappop(q)
    a //= 2
    heapq.heappush(q, (-a, a))

print(sum([a for _, a in q]))

Submission status: Accepted

Solution code:
import math
import heapq
n, k = list(map(int, input().split(' ')))
aaa = list(map(int, input().split(' ')))
aaa = [-a for a in aaa]
heapq.heapify(aaa)
for i in range(k):  # TLE?
    t = heapq.heappop(aaa)
    t = math.ceil(t/2)
    heapq.heappush(aaa, t)
print(-sum(aaa))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 初期入力
N,M = (int(x) for x in input().split())
A = list(map(int, input().split()))
A =list(map(lambda x:x*(-1),A))     #最大値を取り出すため―１を掛ける
import heapq  # heapqライブラリのimport
heapq.heapify(A)  #         リストを優先度付きキューへ
m=0
for i in range(M):
    a=heapq.heappop(A)  #       最大値の取り出し
    a //=-2             # 負の値を2で割り切り捨てると、絶対値が大きくなる。
    heapq.heappush(A, -a) #正の値で2で割り、戻すとき負にする
    #print(A)

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

Submission status: Accepted

Solution code:
# D - Powerful Discount Tickets

import heapq

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

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

print(sum(A) * -1)

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

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
ai = 1
q1 = deque()
q1.append(a[0]//2)
for i in range(1,m):
    ql = q1.popleft()
    if ai < n and a[ai] > ql:
        q1.appendleft(ql)
        q1.append(a[ai]//2)
        ai += 1
    else:
        q1.append(ql//2)

ans = sum(q1)
for i in range(ai,n):
    ans += a[i]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

import heapq
for i in range(N):
    A[i] = -A[i]
    
heapq.heapify(A)

while M > 0:
    tmp = -heapq.heappop(A)
    tmp = tmp//2
    M -= 1
    heapq.heappush(A,-tmp)
    
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) #落としたりするのもO(N)かかってしまうのでHeapで実装
#A=[i for i in range(N)]
for i in range(M):
  B = heapq.heappop(A)
  heapq.heappush(A,-1*(-1*B//2))
  #print(A)
print(-sum(A))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

from collections import defaultdict, deque
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left

import sys
# sys.setrecursionlimit(1000000)
# list(map(int, input().split()))
mod = 10 ** 9 + 7
# https://atcoder.jp/contests/abc141/tasks/abc141_d

N,M = getNM()
# mapをlambdaで改造
A = list(map(lambda x:int(x) * (-1), input().split())) #-1倍してからリストに格納
heapq.heapify(A) #優先度付きキューに変換

for _ in range(M):
    max_value = heapq.heappop(A) * (-1) #最大値の取得
    heapq.heappush(A, (max_value // 2) * (-1)) #半額にして-1倍してからキューに戻す

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

c = 0
for i in range(len(a)):
  c -= heapq.heappop(a)
print(c)

Submission status: Accepted

Solution code:
#標準入力からソートまで
N, M = map(int, input().split())
A = list(map(lambda x : int(x) * (-1), input().split()))
#Aの中で一番でかいのをdiscountしてまた並び替え
#優先度付きqueuemを使う
import heapq
heapq.heapify(A)
for i in range(M):
    tmp = (-1) * heapq.heappop(A) // 2
    heapq.heappush(A, tmp * (-1))
print(-sum(A))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
import heapq
import collections
import itertools
import bisect
mod = 10 ** 9 + 7
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A = list(np.array(A)*-1)
heap_tree = heapq.heapify(A)
for i in range(M):
    max_value = heapq.heappop(A)*-1
    max_value = (max_value//2)*-1
    heapq.heappush(A, max_value)
ans = 0
for a in A:
    ans -= a
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heapify, heappop, heappush 
def main():
    N, M = map(int, readline().split())
    A = [-int(i) for i in readline().split()]
    heapify(A)
    for _ in range(M):
        v = -heappop(A)
        heappush(A, -(v//2))
    print(sum([-i for i in A]))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heapify, heappop, heappush 
def main():
    N, M = map(int, readline().split())
    A = [-int(i) for i in readline().split()]
    heapify(A)
    for _ in range(M):
        v = -heappop(A)
        heappush(A, -(v//2))
    print(-sum(A))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

import heapq
heapq.heapify(a)
for _ in range(m):
    now = -heapq.heappop(a)
    heapq.heappush(a,- (now//2) )
print(-sum(a))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
import heapq

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

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

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

print(ans)

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

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(s)

while m != 0:
  num = heapq.heappop(s)
  heapq.heappush(s, -1*num//2*-1)
  m -= 1

print(-1 * sum(s))

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 )

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

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

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

#############
# Main Code #
#############

N,M = inputIL()
A = inputIL()

a = [[] for i in range(31)]

for x in A:
  n = math.floor(math.log(x)/math.log(2))
  a[n].append(x)

for i in range(31)[::-1]:
  if M>=len(a[i]):
    if i>0:
      M -= len(a[i])
      disc = [x//2 for x in a[i]]
      a[i] = []
      a[i-1] += disc
      a[i-1].sort()
    else:
      print(0)
      exit()
  else:
    if i>0:
      disc = [x//2 for x in a[i][len(a[i])-M:len(a[i])]] 
      a[i-1] += disc
      a[i] = a[i][:len(a[i])-M]
      break
    else:
      print(len(a[0])-M)
      exit()

print(sum(sum(item) for item in 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)
#print(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq
from math import ceil


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

    # As heapq.heappop returns the mininum value of the sequence,
    # we need to multiply -1 in order to attain the maximum
    # value of the sequence.
    A = list(map(lambda x: (-1) * int(x), input().split()))
    heapq.heapify(A)
    for i in range(M):
        heapq.heappush(A, ceil(heapq.heappop(A) / 2))

    print(-sum(A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit
from queue import PriorityQueue

getarr = lambda _f: list(map(_f, input().split()))

n, m = getarr(int)
a = getarr(int)

q = PriorityQueue()
for ai in a:
    q.put(-ai)

for _ in range(m):
    ai = (-q.get()) / 2
    q.put(-ai)

ans = 0
while not q.empty():
    ans += int(-q.get())

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

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

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
def func(x):
    return -1*int(x)
A=list(map(func,input().split()))
#print(A)
heapq.heapify(A)
while m>0:
    x=heapq.heappop(A)
    x/=2
    heapq.heappush(A,x)
    m+=-1
sum=0
for a in A:
    #print((-1*a)//1)
    sum+=((-1*a)//1)
print(int(sum))

Submission status: Accepted

Solution code:
import heapq
n,m = [int(x) for x in input().split()]
a = [int(x)*(-1) for x in 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 math
import copy
from queue import Queue
import heapq

#n = int(input())
n, m = [int(i) for i in input().split()]
#table = [[int(i) for i in input().split()] for j in range(n)]
#table = [list(input()) for n in range(h)]
s = [int(i) for i in input().split()]
#s = [int(i) for i in range(n)]
#s = [int(input()) for i in range(n)]
#s = input()
#list = list(s)
# dp = [[0 for _ in range(2)] for _ in range(13)]

#a = [[0 for _ in range(n+1)] for _ in range(n+1)]
#b = [[0 for _ in range(n+1)] for _ in range(n+1)]

s = list(map(lambda x: x*(-1), s))
heapq.heapify(s)

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

print(sum(s)*(-1))

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
#from fractions import gcd
#from math import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n, m = Is()
A = LI()
A = list(map(lambda x: x*(-1), A))
heapify(A)

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

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

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

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)  # aを優先度付きキューに

for _ in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))  # 計算誤差の関係で-1を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)

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

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)

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

    M-=1
print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

def main():
    n, m = map(int, input().split())
    a = [int(i) for i in input().split()]
    ans = solve(n, m, a)
    print(ans)


def solve(n, m, a):
    a = list(map(lambda x: -x, a))
    heapq.heapify(a)
    #print(a)
    for i in range(m):
        x = heapq.heappop(a)
        heapq.heappush(a, -((-x) // 2))
        #print(a)
    a = list(map(lambda x: -x, a))
    #print(a)
    return sum(a)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

if n == 1:
    while m > 0:
        a[0] //= 2
        m -= 1
    print(a[0])
    exit()

while m > 0:
    a.sort(reverse = True)
    mid = a[0] // 2
    i = 0
    while a[i] >= mid:
        if m > 0:
            a[i] //= 2
            m -= 1
            i += 1
        else:
            break
        if i == len(a):
            break
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:
'''ika tako  コードはSatoooh
優先度付きキューを使うが、最大値を扱いたいのでマイナスを付ける。
popで取り出し。 pushで格納。
高い順に割引券を多く使いたい。1枚使ってもまだ他より高ければ
2枚、3枚、、、と使えばよいが、ある程度使って他の商品が高くなれば、
そちらに使った方がよい。なので、「今の最高額の商品を、
半額で置き換える」ことを  M  回繰り返す。heapqを使うと1回の操作に  
O(logN)  かかるので、全体で  O(MlogN)  となる。
pop()してpush()してもよいが、replace()を使えば2つの操作を1度に行え、
heap構造を保つための比較処理も1回で済むので定数倍高速。
heapreplace(aaa, aaa[0] // 2 + aaa[0] % 2)　ika tako
この+の後が、なぜ必要か、良く分からない。
'''
import heapq
N, M = map(int, input().split())
A = [-i for i in list(map(int, input().split()))]
#最大値を取り出したいので、マイナスを付ける
heapq.heapify(A)#リストをヒープ(二分木)へ変換
for m in range(M):
    A_max = -heapq.heappop(A)  # Aの最大値を削除して取り出す
    heapq.heappush(A, -(A_max // 2))#半分にして、ヒープに入れる
print(-sum(A))#マイナスを忘れないこと

Submission status: Accepted

Solution code:
'''ika tako
高い順に割引券を多く使いたい。1枚使ってもまだ他より高ければ
2枚、3枚、、、と使えばよいが、ある程度使って他の商品が高くなれば、
そちらに使った方がよい。なので、「今の最高額の商品を、
半額で置き換える」ことを  M  回繰り返す。heapqを使うと1回の操作に  
O(logN)  かかるので、全体で  O(MlogN)  となる。
pop()してpush()してもよいが、replace()を使えば2つの操作を1度に行え、
heap構造を保つための比較処理も1回で済むので定数倍高速。
'''
from heapq import heapify, heapreplace
 
n, m = list(map(int, input().split()))
aaa = [-a for a in map(int, input().split())]
#最大値を取り出したいので、-マイナスを付けている
heapify(aaa)#リストをヒープ(二分木)にする
 
for _ in range(m):
    heapreplace(aaa, aaa[0] // 2 + aaa[0] % 2)
    #heappopを行ってからheappushを行う
    
print(-sum(aaa))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
def LILI(n): return [LI() for _ in range(n)]
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main_1(): 
    text = (['Sunny', 'Cloudy'], ['Cloudy', 'Rainy'],['Rainy','Sunny'])
    s = SI()
    for i in text:
        if s == i[0]:
            print(i[1])

def main_2(): 
    s = SI()
    for num, i in enumerate(s):
        if num % 2 == 1: # even
            if not (i in 'LUD'):
                print('No')
                return
        else:
            if not (i in 'RUD'):
                print('No')
                return
    print('Yes')

def main_3():
    N, K, Q = LI()
    A = [0] * (N+1)
    for _ in range(Q):
        n = II()
        A[n] += 1

    for i in range(N):
        if K - Q + A[i+1] <= 0:
            print('No')
        else:
            print('Yes')


from heapq import heappop, heappush

def main():
    N, M = LI()
    A = LI()
    hq = []
    for a in A:
        heappush(hq, -a)  # heap からは最小値が出るのでマイナスを付けておくが、計算時は -1//2 = -1, 1//2 = 0 なので注意。
    for _ in range(M):
        a = -heappop(hq)
        heappush(hq, -(a//2))
    print(-sum(hq))


main()

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
As = list(map(int, input().split()))
As = list(map(lambda x: -x, As))
heapq.heapify(As)

count = 0
while count < M:
    tmp = heapq.heappop(As)
    tmp = int(tmp/2)
    heapq.heappush(As, tmp)
    count += 1

print(-sum(As))

Submission status: Accepted

Solution code:
import heapq
import math
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 = math.ceil(heapq.heappop(a)/2)
    heapq.heappush(a, tmp)
a = list(map(lambda x: x*(-1), a)) 
print(sum(a))

Submission status: Accepted

Solution code:
import heapq
import sys

readline = sys.stdin.readline

def main():
    N, M = map(int, readline().split())
    A = list(map(lambda x: -int(x), readline().split()))
    heapq.heapify(A)
    for m in range(M):
        maxA = heapq.heappop(A)
        heapq.heappush(A, -(-maxA//2))
    ans = -sum(A)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import heapq


def IN(): return sys.stdin.readline().split()


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

for _ in range(M):
    tmp = -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(lambda x:int(x)*(-1),input().split()))

heapq.heapify(a)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import os
import math
import bisect
import collections
import itertools
import heapq

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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

    N, M = il()
    A = il()
    A = list(map(lambda x:x*-1, A))
    heapq.heapify(A)

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


if __name__ == '__main__':
    main()