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

heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
h = []
for i in A:
    heapq.heappush(h, -i)

if len(A) == 1:
    print(A[0] // 2 ** M)
    exit()

used_discount_num = 0
for i in range(M):
    ma = -heapq.heappop(h)
    next_ma = -heapq.heappop(h)
    for j in range(used_discount_num, M):
        ma //= 2
        used_discount_num += 1
        if next_ma > ma:
            heapq.heappush(h, -ma)
            heapq.heappush(h, -next_ma)
            break
    if next_ma <= ma:
        heapq.heappush(h, -ma)
        heapq.heappush(h, -next_ma)
        break

print(-sum(h))

Submission status: Accepted

Solution code:
import heapq

if __name__ == "__main__":
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A = [(-x, x) for x in A]
    heapq.heapify(A)

    for i in range(M):
        tmp = heapq.heappop(A)
        v = tmp[1] // 2
        heapq.heappush(A, (-v, v))
    
    res = 0
    for i in range(len(A)):
        res += A[i][1]
    
    print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import *

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

# print(A)
A = [-a for a in A]
heapify(A)
# print(A)
for _ in range(M):
    x = -heappop(A)
    heappush(A, -(x/2))

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

Submission status: Accepted

Solution code:
# A, B = [int(i) for i in input().split(" ")]
# A = int(input())
# As = [int(i) for i in input().split(" ")]
# Ss = ["".join(sorted(input())) for _ in range(N)]

from heapq import heappush, heappop
N, M = [int(i) for i in input().split(" ")]
As = [int(i) for i in input().split(" ")]
pq = []
for a in As:
  heappush(pq, -a)

for _ in range(M):
  i = heappop(pq)
  heappush(pq, -(-i // 2))
ans = sum(-i for i in pq)
print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
a=list(map(int,input().split()))
q=[]
for i in range(n):
  q.append((-1)*a[i])
heapq.heapify(q)
for k in range(m):
  ma=heapq.heappop(q)
  if ma%2==0:
    heapq.heappush(q,ma//2)
  else:
    heapq.heappush(q,ma//2+1)
print(sum(q)*(-1))

Submission status: Accepted

Solution code:
import sys
from heapq import *
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n,m=map(int, input().split())
    aa=list(map(int, input().split()))
    hp=[]
    for a in aa:
        heappush(hp,-a)
    for _ in range(m):
        a=heappop(hp)
        a/=2
        heappush(hp,a)
    print(sum(int(-a) for a in hp))

main()

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
Alist = map(int,input().split())
heapAlist = []

for A in Alist:
    heapq.heappush(heapAlist,-1*A)

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

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]*(-1)
heapq.heapify(a)
for i in range(m):
  b=int(heapq.heappop(a)*(-1))
  b=(b//2)*(-1)
  heapq.heappush(a,b)
for i in range(n):
  ans+=a[i]
print(ans*(-1))

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
h = a[0: n]
heapq.heapify(h)
for i in range(m):
    L=heapq.heappop(h)
    heapq.heappush(h,(L+1)//2)
print(sum(h)*(-1))

Submission status: Accepted

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    N,M = LMIIS()
    import heapq
    A = list(map(lambda x:-x,map(int,input().split())))
    heapq.heapify(A)
    for _ in range(M):
        a = -heapq.heappop(A) //2

        heapq.heappush(A,-a)

    print(-sum(A))
if __name__ == '__main__':
    main()

Submission status: Accepted

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


class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign


def solve():
    N, M = list(map(int, sys.stdin.readline().split()))
    As = list(map(int, sys.stdin.readline().split()))
    h = Heapq([], True)
    for i, a in enumerate(As):
        h.push(a)

    for i in range(M):
        a = h.pop()//2
        h.push(a)

    ans = 0
    for i in range(N):
        ans += h.pop()

    print(ans)



if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import heapq
A =[]
n,m= map(int,input().split())
a = list(map(int,input().split( )))
for i in range(n):
    a [i]*= -1
    heapq.heappush(A,a[i])
#print(*A)
cnt = 0
while cnt < m:
    i = heapq.heappop(A)
    i *= -1
    i //=2
    i *=-1
    heapq.heappush(A,i)
    cnt+=1
sm = 0
for i in A:
    sm += i
sm *=-1
#print(*A)
print(sm)

Submission status: Accepted

Solution code:
import heapq

n,m=map(int,input().split())
ls=list(map(lambda x:-int(x),input().split()))
heapq.heapify(ls)
for i in range(m):
    a=heapq.heappop(ls)
    a=-((-a)//2)
    heapq.heappush(ls,a)

print(-sum(ls))

Submission status: Accepted

Solution code:
import numpy as np
import heapq
n, m = map(int, input().split())
a = np.array(list(map(int, input().split())))
q = list(-a)
heapq.heapify(q)
#print(q)
for _ in range(m):
    temp = heapq.heappop(q)
    temp = -temp
    temp //= 2
    heapq.heappush(q, -temp)
print(-sum(q))

Submission status: Accepted

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

item.sort(reverse=True)
s = 0

while s == 0:
    for i in range(n):
        if i == 0:
            item[i] = int(item[i]/2)
            m -= 1
            temp = item[i]
            if m == 0:
                s = 1
                break
            continue
        if item[i] > temp:
            item[i] = int(item[i]/2)
            m -= 1
            if m == 0:
                s = 1
                break
            continue
        item.sort(reverse=True)
        break
        

print(sum(item))

Submission status: Accepted

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

from heapq import heappush, heappop

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

for i in range(m):
    d = -heappop(queue)
    dd = d // 2
    heappush(queue, -dd)

print(int(-sum(queue)))

Submission status: Accepted

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

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

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


print(sum(A)*-1)

Submission status: Accepted

Solution code:
from math import ceil
import heapq

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

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

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq
def double(x):
    return int(x) * -1
n, m = map(int, input().split())
A = list(map(double, input().split()))

heapq.heapify(A)

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

Submission status: Accepted

Solution code:
import heapq
import math

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

b = []
for ai in a:
    heapq.heappush(b, ai* -1)
# print(b)

for i in range(m):
    tmp = math.ceil(heapq.heappop(b)/2)
    heapq.heappush(b, tmp)
    # print(b)

print(sum(b) * -1)

Submission status: Accepted

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

A.sort()
A.reverse()
#print(A)
if n==1:
    ans=A[0]//(2**m)
    print(ans)
else:
    A.append(0)
    big=A[0]
    stc=0
    now=0
    while m>0:
        A[now]=A[now]//2
        m-=1
        big=A[0]
        for i in range(n-1):
            if A[i+1]>=big and m>0:
                A[i+1]=A[i+1]//2
                m-=1
            else:
                A.sort()
                A.reverse()
                break
        #print(A)
    else:
        print(sum(A))

Submission status: Accepted

Solution code:
import numpy as np
import heapq
n, maisuu = map(int, input().split())
a_map = map(int, input().split())
a_list = []
for a in a_map:
    heapq.heappush(a_list, -a)

for _ in range(maisuu):
    value = heapq.heappop(a_list)
    waribiki_value = int(value * 0.5)
    heapq.heappush(a_list, waribiki_value)
minus_sum = 0
for a in a_list:
    minus_sum += a
print(-minus_sum)

Submission status: Accepted

Solution code:
from heapq import  heapify,heappop,heappush

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

heapify(A)
for i in range(m):
    a = heappop(A)
    if a % 2 == 0:
        a //= 2
    else:
        a = a // 2 +1
    heappush(A,a)

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)
#print(A)

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

ans = - sum(A)
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]
B = heapq.heapify(A)
i = 0
while i < m:
  h = heapq.heappop(A) 
  heapq.heappush(A, -(-h//2))
  i += 1
print(-sum(a for a in list(A)))

Submission status: Accepted

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

for i in range(M):
    z = heapq.heappop(h) / 2
    heapq.heappush(h, z)
c=0
for i in h:
    c += int(i)
print(-c)

Submission status: Accepted

Solution code:
import heapq

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

for _ in range(M):
    a = heapq.heappop(A)
    a = a // 2 if a % 2 == 0 else a // 2 + 1
    heapq.heappush(A, a)

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

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

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

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

    print(-sum(H))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
#import itertools
import math
import numpy as np
#import sys

#N = int(input())
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A = list(np.array(A) * -1)

heapq.heapify(A)
#print(HA)
for i in range(M) :
    v = heapq.heappop(A)
    v = math.floor(-1 * v / 2) * -1
    heapq.heappush(A, v)

print(sum(A) * -1)

Submission status: Accepted

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq


class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign


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

    q = Heapq(an, True)

    for _ in range(M):
        value = q.pop() / 2.0
        q.push(value)

    res = sum(list(map(lambda x: int(x * -1), q.hq)))

    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq as hq

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

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

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq
import math

def minus_float(s):
    return float(s)*-1

def main():
    N,M=map(int, input().split())
    A=list(map(minus_float, input().split()))
    heapq.heapify(A)

    for i in range(M):
        t = heapq.heappop(A)
        heapq.heappush(A, t/2)
    
    ans = 0
    for a in A:
        ans += math.floor(a * -1)
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq


n, m = list(map(int,input().split()))
a_arr = list(map(int,input().split()))
a_arr = [ i * -1.0 for i in a_arr]
heapq.heapify(a_arr)
for i in range(m):
    n = heapq.heappop(a_arr)
    n = -n
    n = n / 2.0
    heapq.heappush(a_arr, -n)
s = 0
for a in a_arr:
    a = -a
    a = int(a)
    s += a

print(s)

Submission status: Accepted

Solution code:
import heapq
import math

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

heapq.heapify(A)

for _ in range(M):
  el = heapq.heappop(A)
  heapq.heappush(A, math.ceil(el/2))

print(sum(A) * -1)

Submission status: Accepted

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

import heapq


class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign

hq = Heapq(A,desc=True)
for _ in range(M):
    highest = hq.pop()
    hq.push(int(highest/2))
ans = 0
for _ in range(N):
    ans += hq.pop()
print(ans)

Submission status: Accepted

Solution code:
import heapq

class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        return heapq.heappop(self.hq) * self.sign
 
    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)
 
    def top(self):
        return self.hq[0] * self.sign

n,m = map(int, input().split())
a = list(map(int, input().split()))
b = Heapq(a, True)
ans = sum(a)
while m > 0:
  i = b.pop()
  t = i // 2
  ans -= i - t
  b.push(t)
  m -= 1
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify

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

    heap = []

    for i in a:
        heappush(heap, -i)

    for i in range(m):
        max_price = heappop(heap) * -1
        discount_price = max_price // 2
        heappush(heap, -discount_price)

    print(sum(heap) * -1)





resolve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
while M > 0:
	A = sorted(A, reverse=True)
	M -= 1
	A[0] = mx = A[0]//2
	for i in range(1, N):
		if M > 0:
			if A[i] > mx:
				A[i] = A[i]//2
				M -= 1
			else: break
		else: break
		
print(sum(A))

Submission status: Accepted

Solution code:
import heapq
n,m = map(int,input().split())
an = [-int(i) for i in input().split()]
heapq.heapify(an)
hpop = heapq.heappop
hpush = heapq.heappush

for i in range(m):
  v = hpop(an) 
  hpush(an,-(-v//2))
print(-sum(an))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import queue

#+++++
		
def main():
	n,m = map(int, input().split())
	al=list(map(int, input().split()))
	ppq=queue.PriorityQueue()
	for a in al:
		ppq.put(-a)
	
	for _ in range(m):
		t = ppq.get()
		ppq.put(t/2)
		
		
	rr=0
	while not ppq.empty():
		rr += int(ppq.get())
	print(-rr)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import heapq
import math
n, m = [int(v) for v in input().split()]
a_s = [-int(v) for v in input().split()]
#print(a_s)
heapq.heapify(a_s)
#print(a_s)
for i in range(m):
  max_a = heapq.heappop(a_s)
  heapq.heappush(a_s, max_a/2)

ans = 0
for a in a_s:
  ans += math.floor(-a)
print(ans)

Submission status: Accepted

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

def solve(N: int, M: int, A: "List[int]"):
    q.heapify(A)
    for _ in range(M):
        Max = q.heappop(A)
        q.heappush(A, math.ceil(Max/2))
    print(-sum(A))


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [-int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

print(-sum(h))

Submission status: Accepted

Solution code:
import heapq
import math

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

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

heapq.heapify(a)

for i in range(m):
	maximum = heapq.heappop(a)
	add = math.trunc(maximum/2)
	heapq.heappush(a,add)

print(-1 * sum(a))

Submission status: Accepted

Solution code:
import heapq

NM = input().split(' ')
N = int(NM[0])
M = int(NM[1])
AN = input().split(' ')
An = [ int(i)*(-1) for i in AN ] 
heapq.heapify(An)

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

Submission status: Accepted

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

N,M=map(int, raw_input().split())
A=map(int, sys.stdin.readline().split())
A=map(lambda a: a*-1, A)
heapify(A)

for _ in range(M):
	a=heappop(A)
	a=math.ceil(float(a)/2)
	heappush(A,a)

print int(sum(A)*-1)

Submission status: Accepted

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

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

heapify(a)

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

ans = 0
for _ in range(n):
    p = heappop(a)
    ans += -p

print(ans)

Submission status: Accepted

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

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

count = 0
for i in a:
    count += i
print(count)

Submission status: Accepted

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

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

for i in range(m):
    v = heapq.heappop(a) / 2
    heapq.heappush(a, v)
    
for i in range(n):
    a[i] = int(a[i])
print(-(sum(a)))

Submission status: Accepted

Solution code:
import sys
from pprint import pprint

import heapq

n, m = map(int, sys.stdin.readline().strip().split(" "))
a = list(map(int, sys.stdin.readline().strip().split(" ")))

q = []
for a_i in a:
    heapq.heappush(q, -1 * a_i)

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

# pprint(q)
print(-1 * sum(q))

Submission status: Accepted

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

from heapq import heapify, heappop, heappush
heapify(A)

for i in range(M):
    cur_max = heappop(A)
    new = -((-cur_max) // 2)

    heappush(A, new)


print(-sum(A))

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop


def main():
    n, m = [int(x) for x in input().split()]
    a = [(-int(x), int(x)) for x in input().split()]

    heapify(a)
    # print(a)

    for _ in range(m):
        x = (heappop(a))[1] // 2
        heappush(a, (-x, x))
        # print(a)

    print(sum([y for x, y in a]))


main()

Submission status: Accepted

Solution code:
import heapq
import math

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

# heap
heapq.heapify(a)


for i in range(m):
    j = heapq.heappop(a)
    k = math.floor(j[1]/2)
    heapq.heappush(a, (-k, k))


sum_v = 0
for i in a:
    sum_v += i[1]
print(sum_v)

Submission status: Accepted

Solution code:
#import pysnooper
#import os,re,sys,operator,math,heapq,string
#from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from copy import deepcopy
import heapq
setrecursionlimit(10**6)
input=stdin.readline

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

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

print(-sum(a))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
import heapq

def main():
    n, m = list(map(int, input().strip().split()))
    v = list(map(lambda x: -x, map(int, input().strip().split())))
    q = []
    for item in v:
        heapq.heappush(q, item)
    for _ in range(m):
        p = heapq.heappop(q)
        # print(p)
        heapq.heappush(q, (p+1) // 2)
    print(-sum(q))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

from heapq import heappush, heappop, heapify

B = []
for i in range(N):
    B.append(-A[i])
    
heapify(B)

cnt=0
while cnt<M:
    tmp = heappop(B)
    heappush(B, -(-tmp//2))
    cnt+=1
    
print(sum(B)*(-1))

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

Submission status: Accepted

Solution code:
import heapq

N,M = (int(i) for i in input().split())
A = map(int,input().split())
A = list(map(lambda x: -1*x,A))
A.sort()
for i in range(M):
    item = heapq.heappop(A)
    if item % 2== 0:
        heapq.heappush(A,item//2)
    else:
        heapq.heappush(A,item//2+1)


print(-1*sum(A))

Submission status: Accepted

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

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

p = 0
q = -1
list.sort(a,reverse= True)


for i in range(m):
  x = int(a[p]/2)
  a[p] = x
  if(q == -1):
    q = x

  if(p == n -1):
    q = -1
    p = 0
    list.sort(a,reverse=True)
  elif(a[p+1] < q):
    q = -1
    p = 0
    list.sort(a,reverse=True)
  else:
    p += 1


print(sum(a))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
a = inpl()
hq = []
heapq.heapify(hq)
ans = 0
for i in range(n):
    tt = a[i]
    heapq.heappush(hq,-tt)
for i in range(m):
    tmp = heapq.heappop(hq)
    tmp /= 2
    heapq.heappush(hq,tmp)
    # print(hq)
for i in range(n):
    tttt = heapq.heappop(hq)
    ans -= math.ceil(tttt)
print(ans)

Submission status: Accepted

Solution code:
import heapq

from collections import deque

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


heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

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

for i in range(M):
    #A = sorted(A, reverse=True)
    a = int(heapq.heappop(h)[1]/2)
    heapq.heappush(h, (-a,a))

#print h
print sum([x[1] for x in h])

Submission status: Accepted

Solution code:

import heapq
import numpy as np

def acinput():
    return list(map(int,input().split(" ")))



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

A=sorted(A,reverse=False)
#print(A)
for i in range(M):
    a=heapq.heappop(A)
    heapq.heappush(A,np.ceil(a/2))

res=0
for sa in A:
    res+=sa

print(int(-res))

Submission status: Accepted

Solution code:
import heapq

n,m = map(int,raw_input().split())
a = map(int,raw_input().split())
h = []
for x in a:
	heapq.heappush(h, -1*x)
for i in xrange(m):
	x = heapq.heappop(h)
	new = (-1*x) >> 1
	heapq.heappush(h, -1*new)
res = 0
for i in xrange(n):
	res += heapq.heappop(h)
print -1*res

Submission status: Accepted

Solution code:
"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

import heapq

N, M = map(int,input().split())
A = list(map(int,input().split())) ## 横一列

heap = []
for i in range(N):
  heapq.heappush(heap, -A[i])
  
for i in range(M):
  max_price = heapq.heappop(heap)
  heapq.heappush(heap, max_price / 2.0)

ans = 0
for i in range(N):
  ans += -int(heap[i])

print(ans)

Submission status: Accepted

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

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

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

for i in range(M):
    #print(q)
    b = hp.heappop(q)

    c = b//2
    if b % 2 != 0:
        c += 1
    hp.heappush(q, c)

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

Submission status: Accepted

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

Submission status: Accepted

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

a = [-i for i in list(map(int, input().split()))]

heapq.heapify(a)

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

print(abs(sum(a)))

Submission status: Accepted

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n, m = readmi()
t = readt()
h = []
for i in t:
    a = i * (-1)
    heapq.heappush(h, a)
for i in range(m):
    t = heapq.heappop(h)
    t *= -1
    t //= 2
    t *= -1
    heapq.heappush(h, t)
s = 0
for i in h:
    s += i * (-1)
print(s)

Submission status: Accepted

Solution code:
# ABC141d
import sys
import heapq
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

ha = []

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


# print(ha)

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

# print(ha)
print(-sum(ha))