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:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
 
##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力
 
# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと
 
##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順
 
# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順
 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M = inputMap()
    A = inputList()
    
    AA = []
    heapq.heapify(AA)
    for val in A:
        heapq.heappush(AA, val * (-1))
    
    for i in range(M):
        tmp = heapq.heappop(AA) * (-1)
        tmp = tmp // 2
        heapq.heappush(AA, tmp * (-1))
        
    ans = 0
    for i in range(N):
        tmp = heapq.heappop(AA) * (-1)
        ans += tmp
        
    print(ans)
    
    
if __name__ == "__main__":
	main()

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):
  heapq.heappush(A, (heapq.heappop(A)+1)//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()))
q = []
heapq.heapify(q)

for i in range(n):
    heapq.heappush(q, -a[i])

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

print(sum(q) * -1)

Submission status: Accepted

Solution code:
import heapq

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

A = [(-1)*x for x in A]
heapq.heapify(A)

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

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

Submission status: Accepted

Solution code:
import heapq

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

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

Submission status: Accepted

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



A=list(map(int,A))
print(-sum(A))

Submission status: Accepted

Solution code:
# 2019-11-18 17:34:23(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


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

    heapq.heapify(a)
    for _ in range(m):
        highest = - heapq.heappop(a)
        heapq.heappush(a, -(highest // 2))
    
    print(-sum(a))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
import math
n,m=map(int,input().split())
a=list(map(lambda x:int(x)*(-1),input().split()))
heapq.heapify(a)
for i in range(m):
    heapq.heappush(a,math.ceil(heapq.heappop(a)/2))
   
    
    
print(-1*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:
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
for i in range(M):
    x = heapq.heappop(A)*(-1)
    heapq.heappush(A, math.floor(x/2)*(-1))

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

print(sum(A))

Submission status: Accepted

Solution code:
import heapq

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

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

Submission status: Accepted

Solution code:
import heapq


def int_and_reverse(num):
    return int(num) * -1


N, M = map(int, input().split())
Alist = list(map(int_and_reverse, input().split()))
heapq.heapify(Alist)
for _ in range(M):
    x = (heapq.heappop(Alist) * -1) // 2
    heapq.heappush(Alist, -x)
print(-sum(Alist))

Submission status: Accepted

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

Submission status: Accepted

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

print(-(sum(a)))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A =list(map(int,input().split()))
A.sort(reverse=True)
A_len =len(A)
count =0
if A_len ==1:
    for l in range(0,M):
        A[0]=A[0]/2
else:
    for l in range(0,M):
        comp = A[0]/2
        for i in range(0,A_len-1,1):
            if count >= M:
                break
            if A[i+1]<comp:
                break
            while True:
                count +=1
                if A[i]/2 > A[i+1]:
                    A[i] = A[i]/2
                else:
                    A[i] = A[i]/2
                    break
        A.sort(reverse=True)
        if count>=M:
            break
A = [int(i) for i in A]
sumN =sum(A)
print(sumN)

Submission status: Accepted

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

print(-sum(a))

Submission status: Accepted

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

while M != 0:
  max_ = -heapq.heappop(A) // 2
  heapq.heappush(A, -max_)
  M -= 1
  
print(-sum(A))

Submission status: Accepted

Solution code:
# coding: utf-8
import heapq

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

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

print(-sum(s))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#D
import heapq

n,m = map(int,input().split())
L = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(L) #リストをキューに
for _ in range(m):
    a = heapq.heappop(L)
    heapq.heappush(L, (-1)*(-a//2))

print(-sum(L))

Submission status: Accepted

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

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

ans = 0
for i in ar:
    ans += math.floor(-i)

print(ans)

Submission status: Accepted

Solution code:
#powerful discount tickets
n,m=map(int,input().split())
lists=list(map(int,input().split()))
uselist=[0 for i in range(n)]
for j in range(n):
    uselist[j]=lists[j]*(-1)
import heapq
heapq.heapify(uselist)
for _ in range(m):
    #m回この作業を繰り返す
    mini=heapq.heappop(uselist)
    heapq.heappush(uselist,mini/2) 
#バイナリツリーと同じ方法で保管していると考えられる
ans=0
import math
for some in uselist:
    ans+=math.floor(-some)
print(ans)

Submission status: Accepted

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

import math

buckets = [[] for i in range(31)]
count = [0 for i in range(31)]
for num in AS:
    buckets[math.floor(math.log(num)/math.log(2))].append(num)
    
for lst in buckets: lst.sort(reverse=True)

hi = 30
while buckets[hi-1] == []: hi -= 1
found = 0
while True:
    try:
        if M > found:
            for i in range(hi, 31):
                count[i] += 1
            hi -= 1
            M -= found
            found += len(buckets[hi])
        else:
            total = 0
            for i in range(hi):
                total += sum(buckets[i])
                
            lst = []
            for i in range(hi, 30):
                for item in buckets[i]:
                    lst.append(item // pow(2, count[i]))
             
            lst.sort(reverse=True)
            
            for i in range(M):
                lst[i] //= 2

            total += sum(lst)

            print(total)
            break
    except:
        print(0)
        break

Submission status: Accepted

Solution code:
import math
import bisect

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

def XX(A, M):
  if M <= 0 or A[0]<1:
    return
  A[0] = A[0]/2
  M -= 1
  for i in range(1, len(A)):
    if A[i] > A[0] and M > 0:
      A[i] = A[i]/2
      M -= 1
    else:
      break
  A.sort(reverse = True)
  XX(A, M)
  
XX(A, M)
A = list(map(math.floor, A))
print(sum(A))

Submission status: Accepted

Solution code:
def main():
    import heapq
    import sys

    input = sys.stdin.readline

    n,m = map(int,input().split())
    def int2(x):
        a = -int(x)
        return a
    s = list(map(int2,input().split()))
    heapq.heapify(s)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

print(sum(A)*-1)

Submission status: Accepted

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

N, M = map(int, input().strip().split())
A = list(map(int, input().strip().split()))
A = [-x for x in A]
A.sort()
for i in range(M):
  heappush(A, math.ceil(heappop(A)/2))

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(len(a)):
  a[i]*=(-1)

import heapq
heapq.heapify(a)

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import heapq as hq
def print_ans(N, M, input_line):
    """Test Case
    >>> print_ans(3, 3, "2 13 8")
    9
    >>> print_ans(4, 4, "1 9 3 5")
    6
    >>> print_ans(1, 100000, "1000000000")
    0
    >>> print_ans(10 ,1, "1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000")
    9500000000
    """
    ar = [-int(i) for i in input_line.split()]
    hq.heapify(ar)
    for _ in range(M):
        hq.heappush(ar, -(-hq.heappop(ar) // 2))
    
    print(-sum(ar))

if __name__ == '__main__':
    N, M = map(int, input().rstrip().split())
    input_line = input().rstrip()
    print_ans(N, M, input_line)

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

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

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

Submission status: Accepted

Solution code:
import heapq
import math

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


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

print(sum(li_a) * -1)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import heapq
n,m = list(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)
    heapq.heappush(a, -((-tmp) // 2))
print(-sum(a))

Submission status: Accepted

Solution code:
import sys
import heapq


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    a = [-v for v in list(map(int, input().rstrip('\n').split()))]
    heapq.heapify(a)
    for i in range(m):
        t = -heapq.heappop(a)
        heapq.heappush(a, -(t // 2))
    print(-sum(a))


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from heapq import heapify,heappop,heappush
    n,m=map(int,input().split())
    A=[-a for a in map(int,input().split())]
    heapify(A)
    for _ in range(m):
        x=-heappop(A)
        heappush(A,-(x//2))
    print(-sum(A))
resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import ceil
from heapq import *

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

for _ in range(m):
	amax = -heappop(a_s)
	heappush(a_s, -(amax // 2))

res = -sum(a_s)
print(res)

Submission status: Accepted

Solution code:
from math import ceil
from heapq import *

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

for _ in range(m):
	amax = heappop(a_s)
	heappush(a_s, ceil(amax / 2))

res = sum([-heappop(a_s) for _ in range(n)])
print(res)

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(li)

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

print(-sum(li))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque
from heapq import heappush, heappop


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


# A
def A():
    s = input()
    if s == "Sunny":
        print("Cloudy")
    elif s == "Cloudy":
        print("Rainy")
    else:
        print("Sunny")
    return


# B
def B():
    s = S()
    for i in range(len(s)):
        if i % 2:
            if s[i] not in ["L", "U", "D"]:
                print("No")
                return
        else:
            if s[i] not in ["R", "U", "D"]:
                print("No")
                return
    print("Yes")
    return


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


# D
def D():
    n, m = LI()
    a = LI()
    q = []
    for i in range(n):
        heappush(q, -a[i])
    for i in range(m):
        x = heappop(q)
        x *= -1
        x >>= 1
        heappush(q, -x)
    print(-sum(q))
    return


# E
def E():
    return


# F
def F():
    return


# Unittest
def resolve():
    D()
    return


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

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)
    if tmp % 2 == 0:
        tmp //= 2
    else:
        tmp //= 2
        tmp += 1
    heapq.heappush(a,tmp)
print(sum(a)*(-1))

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(a)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
def main():
    N, M = map(int, input().split())
    A = list(int(x)*-1 for x in input().split())
    heapq.heapify(A)

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

    print(sum(A)*-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
mlmis = lambda: [-int(x) for x in input().split()]
INF = float('inf')
#

def main():
    N,M = mis()
    A = mlmis()
    import heapq
    heapq.heapify(A)
    for _ in range(M):
        a = heapq.heappop(A)
        heapq.heappush(A, a/2)
    print(sum(-int(a) for a in A))



main()

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(l)

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

    else:
        heapq.heappush(l,a//2+1)
    m=m-1

print(-sum(l))

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
l=list(map(int,input().split()))
l=[-n for n in l]
heapq.heapify(l)
while M>0:
  a=-heapq.heappop(l)
  a=a//2
  heapq.heappush(l,-a)
  M-=1
print(-sum(l))

Submission status: Accepted

Solution code:
import heapq

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

    heapq.heapify(a)

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

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

Submission status: Accepted

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

import heapq
a = [-i for i in a]

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify

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

  if N == 1: A[0] = A[0] // 2 ** M
  else:
    for i in range(N): A[i] *= -1

    heapify(A)

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

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

Submission status: Accepted

Solution code:
import heapq as hq

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

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

Submission status: Accepted

Solution code:
#ソートしてでかいやつから割引券使っていって、次に値段が高いやつよりも値段が低くなれば次にいく。
#これを繰り返せばいい。
#一周してもまだ割引券が余っていればもう一度ソートして同じことをする。
#途中で割引券がなくなれば終了して、合計を計算する。
#実際に買い物をする順番は気にしなくていい。どこで何枚使うのが最適かが分かればいい
#ということは割引券を使うたび毎回ソートする？
#毎回ソートしてるとやっぱりTLEになる。次に値段が高いやつよりも値段が低くなれば次にいく。でいい

#n,m = map(int,input().split())
#A = list(map(int,input().split()))
#print(A)
#A.sort(reverse=True)
#while m!=0:
#  while A[0] > A[1]:
 #   M_A = max(A)
  #  A[0] = M_A //2
   # m -= 1
  #A.sort(reverse=True)
#print(sum(A))

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]=a[i]*(-1)
  
import heapq
#小さい順に並べる
heapq.heapify(a)
for j in range(m):
  # 最小値を取り出して-1をかけ,bとする。
  b=heapq.heappop(a)*(-1)
  # b//2に-1をかけて,aに入れる。
  heapq.heappush(a,(b//2)*(-1))
  #print(a)
c=sum(a)
print(c*(-1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
import heapq
n, m = [int(x) for x in stdin.readline().rstrip().split()]
a = [int(x) for x in stdin.readline().rstrip().split()]
a = [-1 * x for x in a]
heapq.heapify(a)
for i in range(m):
    harf = heapq.heappop(a)
    harf = ((harf*(-1))//2)*(-1)
    heapq.heappush(a,harf)
print(sum(a)*(-1))

Submission status: Accepted

Solution code:
import heapq
import math

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

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

print(-sum(a))

Submission status: Accepted

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

heapq.heapify(a)


for i in range(M):
  tmp_min = heapq.heappop(a)
  heapq.heappush(a,math.ceil(tmp_min/2))
  
  
print(-sum(a))

Submission status: Accepted

Solution code:
from sys import stdin
import heapq

n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = list(map(int,stdin.readline().rstrip().split()))

for i in range(n):
    li[i] = li[i]*(-1)

heapq.heapify(li)

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

li.sort()
print(sum(li)*(-1))

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 i in range(M):

    num = heapq.heappop(A)
    num *= -1
    num //= 2
    num *= -1
    heapq.heappush(A, num)


print(-1 * sum(A))

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]=-a[i]
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 = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)

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

Submission status: Accepted

Solution code:
import heapq
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N, M = LI()
A = LI()
ans = int(0)

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

for _ in range(M):
    cur = heapq.heappop(A)
#    print(cur)
    heapq.heappush(A, ((cur+1)//2))

#print(A)
print(-sum(A))

Submission status: Accepted

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

while M > 0:
    A.sort(reverse=True)
    if A[0] == 0:
        break
    ham = A[0] // 2
    for i, a in enumerate(A):
        if ham < a and M > 0:
            A[i] = A[i] // 2
            M -= 1
        else:
            break
print(sum(A))

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import heapq


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

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


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3
2 13 8"""
        output = """9"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4 4
1 9 3 5"""
        output = """6"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """1 100000
1000000000"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000"""
        output = """9500000000"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from enum import Enum
from queue import Queue

import numpy as np

import collections
import bisect
import sys
import math
import heapq

from scipy.sparse.csgraph import floyd_warshall

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
n,m=map(int,input().split())
x=list(map(int,input().split()))
for k in range(n):
    x[k]-=2*x[k]
heapq.heapify(x)
ans=0
for i in range(m):
    maxvalue=heapq.heappop(x)*(-1)
    heapq.heappush(x,(maxvalue//2)*(-1))
ans=-1*sum(x)
print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
prices = list(map(int,input().split()))
for i in range(len(prices)):
  prices[i] *= -1

heapq.heapify(prices)
for i in range(M):
  temp = heapq.heappop(prices)
  temp *= -1
  temp //= 2
  temp *= -1
  heapq.heappush(prices,temp)

print(sum(prices)*-1)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
a = [-int(i) for i in input().split()]
heapq.heapify(a)
for _ in range(m):
    mx = -heapq.heappop(a)
    heapq.heappush(a, -(mx // 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()))

now=[]

for i in range(N):   #O(NlogN)
    heapq.heappush(now,-A[i])

for j in range(M):  #O(MlogN)
    MIN=heapq.heappop(now)
    MIN/=2
    heapq.heappush(now,MIN)

for k in range(N):  #O(N)
    now[k]=math.floor(-now[k])

print(sum(now))

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M,=input().split()  #複数数値入力　「A B」みたいなスペース空いた入力のとき

N=int(N)
M=int(M)

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

a=[]
for n in range(N):
    a.append(int(A[n]) * (-1))

import heapq
import math

heapq.heapify(a)
for m in range(M):
    heapq.heappush(a,math.ceil(heapq.heappop(a)/2))   
    
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*(-1), a)) 

heapq.heapify(a)

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

a = list(map(lambda x: x*(-1), a)) 
print(sum(a))

Submission status: Accepted

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

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

for i in range(M):

    max = heapq.heappop(A_q) * (-1) // 2
    heapq.heappush(A_q, -max)



result = 0
A_q = list(map(lambda x:x*(-1),A_q))

for i in range(N):
    result += A_q[i]

print(result)