Problem:


Score : 400 points

Problem Statement

Takahashi is going to buy N items one by one.

The price of the i-th item he buys is A_i yen (the currency of Japan).

He has M discount tickets, and he can use any number of them when buying an item.

If Y tickets are used when buying an item priced X yen, he can get the item for \frac{X}{2^Y} (rounded down to the nearest integer) yen.

What is the minimum amount of money required to buy all the items?

Constraints

All values in input are integers.

1 \leq N, M \leq 10^5

1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_N

Output

Print the minimum amount of money required to buy all the items.

Sample Input 1

3 3
2 13 8

Sample Output 1

9

We can buy all the items for 9 yen, as follows:

Buy the 1-st item for 2 yen without tickets.

Buy the 2-nd item for 3 yen with 2 tickets.

Buy the 3-rd item for 4 yen with 1 ticket.

Sample Input 2

4 4
1 9 3 5

Sample Output 2

6

Sample Input 3

1 100000
1000000000

Sample Output 3

0

We can buy the item priced 1000000000 yen for 0 yen with 100000 tickets.

Sample Input 4

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 4

9500000000



Sample input:
3 3
2 13 8


Sample output:
9

Submission status: Accepted

Solution code:
import heapq
import math
h = []
N,M = map(int,input().split())
pr = list(map(int,input().split()))
for i in pr:
    heapq.heappush(h, -i)
for i in range(M):
    point = -heapq.heappop(h)
    heapq.heappush(h, -(point // 2))
print(-sum(h))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    d = {"Sunny":1 , "Cloudy":2, "Rainy":0}
    a = ["Sunny", "Cloudy", "Rainy"]
    print(a[d[input().rstrip()]])
    return

#B
def B():
    s = S()
    for i, si in enumerate(s):
        if i % 2:
            if si == "R":
                print("No")
                return
        else:
            if si == "L":
                print("No")
                return
    print("Yes")
    return

#C
def C():
    n, k, q = LI()
    d = [0] * n
    for _ in range(q):
        a = II() - 1
        d[a] += 1
    for a in d:
        if k - (q - a) > 0:
            print("Yes")
        else:
            print("No")
    return

#D
def D():
    n,m = LI()
    a = LI()
    q = []
    for ai in a:
        heappush(q, -ai)
    for _ in range(m):
        heappush(q, heappop(q) / 2)
    ans = 0
    while q:
        ans += int(-heappop(q))
    print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
import heapq

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

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

sum = 0
for _ in range(N): 
	sum -= heapq.heappop(h)
print(sum)

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

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):
    A[i] *= -1

for i in range(N):
    heapq.heappush(h, A[i])

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

print(-sum(h))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#coding:utf-8
 
import heapq
 
N, M = map(int, input().split())
invA = []
for a in map(int, input().split()):
    heapq.heappush(invA, -1*a)
for m in range(M):
    heapq.heappush(invA, heapq.heappop(invA)/2)
total = -1*sum(map(int, invA))
 
print(total)

Submission status: Accepted

Solution code:
#coding:utf-8

import heapq

N, M = map(int, input().split())
invA = []
for a in map(int, input().split()):
    heapq.heappush(invA, -1*a)
for m in range(M):
    heapq.heappush(invA, heapq.heappop(invA)/2)
total = -1*sum(map(int, invA))

print(total)

Submission status: Accepted

Solution code:
#import pysnooper
#import numpy
#import os,re,sys,operator
#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
#import math
#import string

setrecursionlimit(10**6)
input=stdin.readline

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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_min = heapq.heappop(A)
    heapq.heappush(A,int(tmp_min / 2))
    
print(-sum(A))

Submission status: Accepted

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

MOD = 10 ** 9 + 7

N, M = map(int, input().split())
AN = map(int, input().split())
hq = []
for an in AN:
    heapq.heappush(hq, -an)

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

ans = - sum(hq)

print(ans)

Submission status: Accepted

Solution code:
import heapq

N, M =map(int, input().split())
A = list(map(int, input().split()))
A.sort()
reversed_A = [n * (-1) for n in A]
heapq.heapify(reversed_A)
for i in range(M):
    max_value = heapq.heappop(reversed_A) * (-1)
    half_value = max_value // 2
    heapq.heappush(reversed_A, (-1)*half_value)

discount_prices = [n * (-1) for n in reversed_A]
ans = sum(discount_prices)
print(ans)

Submission status: Accepted

Solution code:
#problem-D needs priority queue
import heapq
n,m = map(int, input().split())
price = list(map(int, input().split()))
for i in range(n):
    price[i] = -price[i]
heapq.heapify(price)

for i in range(m):
    x = heapq.heappop(price)
    if x%2 == 0:
        heapq.heappush(price,x//2)
    else:
        heapq.heappush(price,x//2+1)
print(-sum(price))

Submission status: Accepted

Solution code:
import heapq as hq


def solve():
    N, M = map(int, input().split())
    pl = list(map(lambda x: int(x)*(-1), input().split()))
    hq.heapify(pl)
    
    for _ in range(M):
        tmp = hq.heappop(pl)
        hq.heappush(pl, (-1)*(-tmp // 2))
    
    print(-sum(pl))
    


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# https://atcoder.jp/contests/abc141/tasks/abc141_d
import heapq

# 整数の入力
N, M = map(int, input().split())
A = list(map(int, input().split()))

for i in range(N):
    A[i] *= -1

heapq.heapify(A)

for _ in range(M):
    heapq.heappush(A, ((heapq.heappop(A) * -1) >> 1) * -1)

print(sum(A) * -1)

Submission status: Accepted

Solution code:
# heapq が最小ヒープなので、Aの数値は負にする
from heapq import heappop, heappush

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

heap = []
for i in input().split():
    heappush(heap, -int(i))

for i in range(M):
    a = -heappop(heap)
    half = a // 2
    heappush(heap, -half)
    
ans = -sum(heap)
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A_list)

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

print(sum(A_list) * -1)

Submission status: Accepted

Solution code:
import heapq

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

for i in range(len(A)):
    A[i] *= -1

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

print(-sum(A))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
import math
def main():
  a,b=map(int,input().split())
  c=list(map(int,input().split()))
  c=[-i for i in c]
  heapq.heapify(c)
    
  for j in range(b):
    x=heapq.heappop(c)
    heapq.heappush(c,math.ceil(x/2))
    
  print(-sum(c))
  
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
import math
n,m = map(int,input().split())
lst = [int(x) * (-1) for x in input().split()]
heapq.heapify(lst)
for use_cnt in range(m):
    num = heapq.heappop(lst) * -1
    nxt_num = math.floor(num / 2)
    heapq.heappush(lst,nxt_num * -1)
print(sum(lst) * (-1))

Submission status: Accepted

Solution code:
import heapq

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

cost=[]
heapq.heapify(cost)

for i in range(N):
    heapq.heappush(cost,-A[i])

min_cost=sum(A)

while M>0:
    max_cost=(-1)*heapq.heappop(cost)
    cut_cost=max_cost-max_cost//2
    min_cost-=cut_cost
    max_cost-=cut_cost
    heapq.heappush(cost,(-1)*max_cost)
    M-=1

print(min_cost)

Submission status: Accepted

Solution code:
# -*-coding: utf-8 -*-
import heapq
def main():
    N, M = map(int, input().split())
    A = list(map(lambda x: int(x)*(-1), input().split()))
    heapq.heapify(A)

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

goods = list(map(int, input().split()))
goods_heap = []

for i in range(N):
    heappush(goods_heap, -goods[i])

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

print(sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

n,m=map(int,input().split())
arr=list(map(int,input().split()))
q=[]
for i in range(n):
  heapq.heappush(q,-arr[i])
for _ in range(m):
  tmp=-heapq.heappop(q)
  heapq.heappush(q,-(tmp//2))
ans=0
for _ in range(n):
  ans+=-heapq.heappop(q)
print(ans)

Submission status: Accepted

Solution code:
import heapq
import math

# get input parameter
n, m = map(int, input().split())

# get price list (convert max heap)
price_list = [ int(x) * -1 for x in input().split() ]
heapq.heapify(price_list)

# use ticket
for use_count in range(m):
    # get most expensive price
    max_price = heapq.heappop(price_list) * -1
    
    # use ticket
    new_price = math.floor(max_price / 2)
    
    # add heap que
    heapq.heappush(price_list, new_price * -1)

# print price sum
print(sum(price_list) * -1)

Submission status: Accepted

Solution code:
import math
import heapq

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

#map()とlambdaをあわせて使うことで、リストの要素をすべて-1倍した。


heapq.heapify(a) # リストのheap化(プライオリティキューにしてる)

#heapはsortではないので、割と順番はあべこべ。ただ最小値が先頭に来る。

for i in range(m):
    x=heapq.heappop(a) # heap化されたリストaから最小値を削除&その最小値を出力
    heapq.heappush(a, math.ceil(x/2)) # heap化されたリストaに要素を加える。正の数なら切り捨てはmath.floorやけど、負の数なのでmath.ceilを用いる。

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = [-a for a in A]
heapq.heapify(B)
for _ in range(M):
    v = heapq.heappop(B)
    v = -(abs(v)//2)
    heapq.heappush(B, v)
print(-sum(B))

Submission status: Accepted

Solution code:
import heapq

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

d = list(map(lambda x: -x, data))
heapq.heapify(d)

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

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

print( sum(d) )

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, value, N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            self.node[i] = left_i if self.comp(left_v, right_v) else right_i

    def update(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            new_i = left_i if self.comp(left_v, right_v) else right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def at(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def query(self, l=0, r=-1):
        return self.at(self.query_index(l,r))

    def query_index(self, l=0, r=-1):
        if r < 0: r = self.N
        L = l + self.N; R = r + self.N
        s = None
        while L < R:
            if R & 1:
                R -= 1
                if self.comp(self.at(self.node[R-1]), self.at(s)):
                    s = self.node[R-1]
            if L & 1:
                if self.comp(self.at(self.node[L-1]), self.at(s)):
                    s = self.node[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

inpl = lambda: list(map(int,input().split()))

if __name__ == '__main__':
    N, M = inpl()
    A = inpl()
    segt = SegmentTree(A, reverse=True)
    for _ in range(M):
        i = segt.query_index()
        v = segt.at(i)
        segt.update(i, v//2)
    print(sum(segt.at(i) for i in range(N)))

Submission status: Accepted

Solution code:
import heapq

def calc_minus(n):
    return n * (-1)

N, M = map(int, input().split())
values = list(map(int, input().split()))
tmp = 0

values_minus = []
for val1 in values:
    values_minus.append(calc_minus(val1))

heapq.heapify(values_minus)

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

values_plus = []
for val2 in values_minus:
    values_plus.append(calc_minus(val2))

result = 0
for val3 in values_plus:
    result += val3

print(result)

Submission status: Accepted

Solution code:
import heapq

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

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 a in A:
    heapq.heappush(h, -a)

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

print(-sum([heapq.heappop(h) for x in range(len(h))]))

Submission status: Accepted

Solution code:
import heapq
import math

n, m = map(int, input().split())
goods = list(map(lambda x: int(x) * -1, input().split()))
heapq.heapify(goods)
for i in range(m):
    the_most_expensive = heapq.heappop(goods)
    heapq.heappush(goods, math.ceil(the_most_expensive / 2))

print(sum(goods) * -1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

Solution code:
import sys
n,m = map(int,input().split())
lst_a = list(map(int,input().split()))
temp = 0
cnt = 0
loop = 0
debug = 0
if n == 1:
    for i in range(m):
        lst_a[0] //= 2
    print(lst_a[0])
    sys.exit()
while debug < 10:
    loop = 0
    temp = 0
    lst_a.sort(reverse=True)
    while loop < n-1:
        lst_a[loop] //= 2
        cnt += 1
        temp = max(temp,lst_a[loop])
        if cnt == m:
            print(sum(lst_a))
            sys.exit()
        if temp > max(lst_a[loop],lst_a[loop + 1]):
            break
        if lst_a[loop + 1] > lst_a[loop]:
            loop += 1

Submission status: Accepted

Solution code:
import sys
n,m = map(int,input().split())
lst_a = list(map(int,input().split()))
temp = 0
cnt = 0
fin = 0
loop = 0
debug = 0
temp2 = 0
if n == 1:
    for i in range(m):
        lst_a[0] //= 2
    print(lst_a[0])
    sys.exit()
while debug < 10:
    loop = 0
    #temp2 = temp
    temp = 0
    lst_a.sort(reverse=True)
    while loop < n-1:
        lst_a[loop] //= 2
        cnt += 1
        temp = max(temp,lst_a[loop])
        if cnt == m:
            #print(lst_a)
            print(sum(lst_a))
            sys.exit()
        if temp > max(lst_a[loop],lst_a[loop + 1]):
            break
        if lst_a[loop + 1] > lst_a[loop]:
            loop += 1
        
        
        
"""        if lst_a[loop] >= max(lst_a[loop + 1],temp):
            lst_a[loop] //= 2
            temp = max(lst_a[loop],lst_a[loop+1])
            cnt += 1
            if cnt == m:
                print(sum(lst_a))
                sys.exit()
            if temp > lst_a[loop + 1]:
                break
            
            
        loop += 1
    
    #debug += 1
print(lst_a[99999])
# print(temp)
# print(cnt)
# print(lst_a)
# print(sum(lst_a))
"""

Submission status: Accepted

Solution code:
def slove():
    import sys
    import heapq
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    a = [- i for i in list(map(int, input().rstrip('\n').split()))]
    heapq.heapify(a)
    for i in range(m):
        heapq.heappush(a, -(-heapq.heappop(a) // 2))
    print(-sum(a))


if __name__ == '__main__':
    slove()

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    from heapq import heapify, heappush, heappop
    from math import floor
    n, m = list(map(int, input().split(' ')))
    a = list(map(int, input().split(' ')))
    a = [x*(-1) for x in a]
    heapify(a)
    for _ in range(m):
        x = floor(-heappop(a)/2)*(-1)
        heappush(a, x)
     
    print(-sum(a))
main()

Submission status: Accepted

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

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

import heapq

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

print(-sum(A))

Submission status: Accepted

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

heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline-------------------------------------------
    N,M =map(int,input().split())
    A = list(map(int,input().split()))
    heap = []
    for i in range(N):
        heappush(heap,-A[i])
    for i in range(M):
        p = -heappop(heap)//2
        heappush(heap,-p)
    print(-sum(heap))
    
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
import heapq as h

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

Submission status: Accepted

Solution code:
import heapq

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

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

print(-sum(a))

Submission status: Accepted

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

heapq.heapify(b)
for i in range(m):
    h = heapq.heappop(b)
    heapq.heappush(b, math.ceil(h / 2))

print(sum(b)*(-1))

Submission status: Accepted

Solution code:
import heapq
import math

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

heapq.heapify(b)
for i in range(m):
    h = heapq.heappop(b)
    heapq.heappush(b, math.ceil(h / 2))

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

print(sum(c))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math
import queue
import bisect
import heapq

mod = 1e9+7

def swap(a,b):
    return (b,a)

def gcd(a,b):
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def divisors(a):
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def main():
    n,m = map(int,input().split())
    a = [-x for x in map(int,input().split())]
    heapq.heapify(a)
    for i in range(m):
        x = heapq.heappop(a)
        if x%2==0:
            heapq.heappush(a,x//2)
        else:
            heapq.heappush(a,x//2+1)
    ans = 0
    for i in range(n):
        ans += heapq.heappop(a)*(-1)
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
A = [int(_) for _ in input().split()]
A.sort(reverse=True)
ans = 0

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

queue = Heapq([], True)
for value in A:
    queue.push(value)

for i in range(M):
    work = queue.pop()
    queue.push(work // 2)

print(sum(queue.hq) * -1)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import heapq

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()
A = LI()

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

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

print(-sum(pq))

Submission status: Accepted

Solution code:
# D - Powerful Discount Tickets
import heapq
n,m= map(int, input().split())

a = [int(s) for s in input().split()]
a = list(map(lambda x: x*(-1), a))  # 各要素を-1倍

heapq.heapify(a)

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

print(-sum(a))

Submission status: Accepted

Solution code:
from heapq import *

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

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

print(abs(sum(h)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from heapq import heappop,heappush,heapify

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

A_minus = [-x for x in A]
heapify(A_minus)

pop = lambda: -heappop(A_minus)
push = lambda x: heappush(A_minus, -x)

for _ in range(M):
  x = pop()
  push(x//2)
  
ans = -sum(A_minus)
print(ans)

Submission status: Accepted

Solution code:
import heapq
def calc_Inversion(num):
    return num * -1

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

heapq.heapify(a)

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

print(sum(a) * -1)

Submission status: Accepted

Solution code:
import heapq
n, m = (int(i) for i in input().split())
a = [int(i) * (-1) for i in input().split()]
heapq.heapify(a)
for i in range(m):
    tmp_min = ((a[0] * (-1)) //2) * (-1)
    heapq.heappushpop(a,tmp_min)
print(abs(sum(a)))

Submission status: Accepted

Solution code:
import heapq

a = []
a = input().split()
N = int(a[0])
M = int(a[1])
A = input().split()
A = [int(n) for n in A]

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

heapq.heapify(A)

for i in range(M) :
  c = heapq.heappop(A)
  heapq.heappush(A, (c+1) // 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 _ in range(m):
    t = -(-a[0] // 2)
    heapq.heapreplace(a, t)

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq

n,m = (int(x) for x in input().split())

a = [int(i)*(-1) for i in input().split()]
heapq.heapify(a)
for _ in range(m):

    b  = -(heapq.heappop(a))//2
    heapq.heappush(a,-b)


print(-sum(a))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import sys
import heapq
# input = sys.stdin.readline
sys.setrecursionlimit(100000)
MOD = 10 ** 9 + 7

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

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

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



print(-sum(Q))

Submission status: Accepted

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

import heapq, math
A_list = [-x for x in A_list]
heapq.heapify(A_list)

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

print(-sum(A_list))

Submission status: Accepted

Solution code:
import heapq

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

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

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

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