Problem:


Score : 400 points

Problem Statement

Takahashi is going to buy N items one by one.

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

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

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

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

Constraints

All values in input are integers.

1 \leq N, M \leq 10^5

1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_N

Output

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

Sample Input 1

3 3
2 13 8

Sample Output 1

9

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

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

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

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

Sample Input 2

4 4
1 9 3 5

Sample Output 2

6

Sample Input 3

1 100000
1000000000

Sample Output 3

0

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

Sample Input 4

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

Sample Output 4

9500000000



Sample input:
3 3
2 13 8


Sample output:
9

Submission status: Accepted

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

Submission status: Accepted

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

rl = sys.stdin.readline

n, m = map(int, rl().split())
h = list(map(lambda x: -1*int(x), rl().split()))
heapq.heapify(h)
for _ in range(m):
    heapq.heappushpop(h, math.ceil(h[0]/2))
print(-sum(h))

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

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

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

Submission status: Accepted

Solution code:
import heapq  # heapqライブラリのimport
N,M=map(int,input().split())
A = list(map(int,input().split()))
for j in range(N):
 A[j]*=-1
heapq.heapify(A)  # リストを優先度付きキューへ
for i in range(M):
 c=heapq.heappop(A)
 c=((-c)//2)
 heapq.heappush(A, -c)
print(-sum(A))

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import math
import heapq
n, m = map(int, input().split())
a = [int(i) * (-1) for i in input().split()]
heapq.heapify(a)
i = 0
while i < m:
    max_a = - heapq.heappop(a)
    max_a /= 2
    heapq.heappush(a, -max_a)
    i += 1
total = 0
for k in a:
    total += math.floor(-k)
print(total)

Submission status: Accepted

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


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a = [-ai for ai in a]
    heapify(a)

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

    print(-sum(a))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
import math
import heapq
n,m = map(int, raw_input().split(' '))

heap = [-e for  e in map(int, raw_input().split(' '))]
heapq.heapify(heap)
while(m and heap):
	u = heapq.heappop(heap)
	u *= -1
	u /=2
	if u:
		heapq.heappush(heap, -u)
	m-=1
	"""

	q = int(math.ceil(math.log(u,2)))
	if 2 ** q <= u: q +=1
	if q <= m:
		m-= q
	else:
		u /= 2
		m -=1
		if u:
			heapq.heappush(heap, -u)

	"""
print -sum(heap or [0])

Submission status: Accepted

Solution code:
# 「毎回最大のやつ取れない限り無理じゃね...?」 <- それできます。優先度付きキューならね
import heapq
from functools import reduce
n, m = map(int, input().split())
arr = list(map(lambda x: int(x) * -1, input().split()))
heapq.heapify(arr)
for i in range(m):
    t = -1 * heapq.heappop(arr)
    heapq.heappush(arr, -1 * (t // 2))
print(-1 * reduce(lambda a, b: a + b, arr))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
A = list(map(int, input().split()))

import heapq

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

for _ in range(m):
    tmp = heapq.heappop(A)/2
    heapq.heappush(A, tmp)
    
ans = 0
for a in A:
    ans += -int(a)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

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

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

print(-sum(arr))

Submission status: Accepted

Solution code:
from heapq import heapify, heapreplace

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

for _ in range(m):
    heapreplace(arr, int(arr[0] / 2))

print(-sum(arr))

Submission status: Accepted

Solution code:
import heapq as hp
n,m=[int(x) for x in input().rstrip().split()]
a=[-int(x) for x in input().rstrip().split()]

hp.heapify(a)
a.sort()

while(m):
  
  m-=1
  now=hp.heappop(a)
  now=-((-now)//2)
  hp.heappush(a,now)
  
print(-sum(a))

Submission status: Accepted

Solution code:
import heapq
n,m = map(int,input().split())
A = [-n for n in map(int,input().split())]
heapq.heapify(A)
while m >= 1:
    k = (-heapq.heappop(A))//2
    heapq.heappush(A, -k)
    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)*(-1),input().split()))
heapq.heapify(a)  #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())
A = [int(x) for x in input().split()]
A.sort(reverse=True)
A = list(map(lambda x: x*-1,A))
heapq.heapify(A)
while(m>0):
    m-=1
    num = heapq.heappop(A)
    if(num == 0):
        break
    num //= (-2)
    heapq.heappush(A,num*-1)

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

Submission status: Accepted

Solution code:
n, m  = map(int, input().split())
import numpy as np
import heapq
import math
a = [-1*int(i) for i in input().split()]
heapq.heapify(a)

if n > 1:
  for i in range(m):
    x = heapq.heappop(a)
    heapq.heappush(a,math.ceil(x/2))
  a = np.array(a)
  print(-1*a.sum())
else:
  print(-1*a[0]//(2**m))

Submission status: Accepted

Solution code:
#優先度付きキュー
import heapq
n,m=map(int,input().split())
#入力時に全ての数に-1をかける
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))
print(-sum(a))

Submission status: Accepted

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
from heapq import heapify,heappush,heappop
n,m=n1()
A=n1()
h=[-i for i in A]
heapify(h)

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

B=[int(-i) for i in h]
print(sum(B))

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N, M = rl()
A = rl()

import heapq

heap = []
for i, a in enumerate(A):
	heapq.heappush(heap, (-a, i))
nums = [0] * N
for i in range(M):
	a, i = heapq.heappop(heap)
	if abs(a) < 1:
		break
	a = a / 2
	nums[i] += 1
	heapq.heappush(heap, (a, i))
ans = 0
for i in range(N):
	ans += A[i] // pow(2, nums[i])
print(ans)

Submission status: Accepted

Solution code:
#優先度付きキュー
import heapq

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

#heapqは最小値しか取り出せないので全ての要素に-1をかける
A = list(map(lambda x: int(x)*(-1), input().split()))
# print(A)

#リストを優先度付きキューに入れる
heapq.heapify(A)

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

Submission status: Accepted

Solution code:
import heapq
import math

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

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    AA = list(map(calc, A)) 
    heapq.heapify(AA) 
    
    for i in range(M):
        tmp = heapq.heappop(AA)
        tmp = math.floor(-tmp / 2)*(-1)
        heapq.heappush(AA, tmp)
    
    print(sum(AA)*(-1))

main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import heapq

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

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

Submission status: Accepted

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

    ans = -sum(map(lambda x: int(x), a))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import heapq
    n, m, *a = map(lambda x: -int(x), open(0).read().split())
    heapq.heapify(a)
    while m:
        x = heapq.heappop(a)
        heapq.heappush(a, x / 2)
        m += 1
    ans = -sum(map(lambda x: int(x), a))
    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()))

#全要素に-1かける
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:
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

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

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

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

Submission status: Accepted

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

import heapq
heapq.heapify(A)

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

print(-sum(A))

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

Submission status: Accepted

Solution code:
import heapq

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

for a in A:
    heapq.heappush(pA, -a)

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

print(-sum(pA))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
q = []
for i in a:
    q.append(-i)

import heapq
heapq.heapify(q)

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

print(-sum(q))

Submission status: Accepted

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

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

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

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

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

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

Submission status: Accepted

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


print(-1 * sum(a_list))

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)

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

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

Submission status: Accepted

Solution code:
import heapq

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

while M > 0:
    M -= 1
    now = heapq.heappop(B)
    now = (now+1) // 2
    heapq.heappush(B, now)
print(-sum(B))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

H = []

for i in A:
  heappush(H, i)

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

print((-1)*sum(H))

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

Submission status: Accepted

Solution code:
#ABC141D
def main():
    import sys
    import heapq as hp
    N, M = map(int, sys.stdin.readline().split())
    A = list(map(lambda x:-int(x), sys.stdin.readline().split()))
    A.sort()
    hp.heapify(A)
    #print(A)
    while M>0:
        tmp = hp.heappop(A) #左から取り出す
        tmp = -((-tmp)//2)
        hp.heappush(A, tmp)
        M-=1
    print(-sum(A))
   
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
#141d
from collections import deque
import bisect
import math

N,M = map(int, input().split()) #1≤N,M≤10^5
A_list = list(map(int, input().split()))

#→高額なものに割引券を使った方が良い
if len(A_list) > 1:
    A_list.sort(reverse=False)
    highest = A_list.pop()
    next_highest = A_list[-1]

    discounted_deque = deque()

    while 1:
        use_tickets = math.ceil(math.log(highest/next_highest)/math.log(2))
        if use_tickets == 0:
            use_tickets = 1
        elif use_tickets > M:
            use_tickets = M
            
        highest /= pow(2,use_tickets)
        M -= use_tickets
        
        if M!= 0:
            discounted_deque.appendleft(highest)
            
            if len(A_list) > 0:
                if A_list[-1] > discounted_deque[-1]:
                    highest = A_list.pop()
                else:
                    highest = discounted_deque.pop()
            else:
                highest = discounted_deque.pop()
                
            if len(A_list) > 0 and len(discounted_deque) > 0:
                if A_list[-1] > discounted_deque[-1]:
                    next_highest = A_list[-1]
                else:
                    next_highest = discounted_deque[-1]
            elif len(A_list) == 0 and len(discounted_deque) > 0:
                next_highest = discounted_deque[-1]
            elif len(A_list) > 0 and len(discounted_deque) == 0:
                next_highest = A_list[-1]
            
        else:
            A_list.append(highest)
            break

    A_list = [int(A) for A in A_list]
    discounted_list = [int(B) for B in discounted_deque]
    
    print(sum(A_list)+sum(discounted_list))
else:
    A_list[-1] = A_list[-1]//(pow(2,M))
    print(A_list[-1])

Submission status: Accepted

Solution code:
from math import ceil
from heapq import heappush, heappop, heapify
N, M = map(int, input().split())
A_i = list(map(lambda x: -int(x), input().split()))
heapify(A_i)

for _ in range(M):
    heappush(A_i, ceil(heappop(A_i) / 2))

print(-sum(A_i))

Submission status: Accepted

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

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]

import heapq
heapq.heapify(a)
for i in range(m):
    mx = heapq.heappop(a)
    tmp = (-mx)//2
    heapq.heappush(a,-tmp)

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
    judge=A[0]//2
    for i in range(len(A)):
        if A[i]>judge and M>0:
            A[i]=A[i]//2
            M-=1
        else:
            break
print(sum(A))

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = LIST()

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

for _ in range(M):
	heappush(A, -(-heappop(A)//2))

print(-sum(A))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = LIST()

A = [-x for x in A]
A.sort()

for _ in range(M):
	heappush(A, -(-heappop(A)//2))
	

print(-sum(A))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = LIST()

A = [-x for x in A]
A.sort()

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

print(-sum(A))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import queue

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

q = queue.PriorityQueue()
for a in A:
    q.put((-a,a))

for _ in range(M):
    v = q.get()[1] // 2
    q.put((-v, v))

ans = 0
while not q.empty():
    ans += q.get()[1]
print(ans)

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
# import bisect
# import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    a = [-int(i) for i in input().split()]
    heapq.heapify(a)

    cnt = 0
    while cnt < m:
        cnt += 1

        item = heapq.heappop(a)
        item = (item + 1) // 2
        heapq.heappush(a, item)

    ans = 0
    while len(a) > 0:
        ans += - heapq.heappop(a)

    print(ans)


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)

#print(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
class PriorityQueue():
    def __init__(self, queue=[]):
        self.queue = queue
        heapify(queue)
    def push(self, item):
        heappush(self.queue, item)
    def pop(self):
        return heappop(self.queue)
    def __str__(self):
        return self.queue
    def __len__(self):
        return len(self.queue)
    def __iter__(self):
        return iter(self.queue)
N, M = map(int, input().split())
def int_(num_str):
    return -int(num_str)


Alist = list(map(int_, input().split()))
pq = PriorityQueue(Alist)
for _ in range(M):
    max_val = pq.pop()
    pq.push(-1 * (-1*(max_val))/2)
ans = sum([int(-1 * item) for item in pq])
print(ans)

Submission status: Accepted

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

n, m = map(int, input().split())
#a = list(map(int, input().split()))
a = list(map(lambda x: int(x) * (-1), input().split()))
heapq.heapify(a)  # aを優先度付きキューに

for _ in range(m):
    MAX = heapq.heappop(a)  # −１かけたリストのMin　＞Max
    heapq.heappush(a, (-1) * (-MAX // 2))

ans = (sum(a)) * (-1)  # そのままリストでOK
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    n,m=map(int, readline().rstrip().split())
    arr=list(map(int, readline().rstrip().split()))
    for i in range(n):
        arr[i]*=-1
    heapq.heapify(arr)
    for _ in range(m):
        x=(heapq.heappop(arr)*-1)//2
        heapq.heappush(arr, -x)
    ans=0
    for i in range(n):
        ans+=(arr[i]*-1)
    print(ans)
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

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

PQ = [-A for A in As]
heapify(PQ)

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

#print('PQ:', PQ)

print(-sum(PQ))

Submission status: Accepted

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

from heapq import heappop,heappush,heapify

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

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

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
dat = list(map(lambda x: -int(x), input().split()))
heapq.heapify(dat)
#print(dat)
for i in range(m):
    #print(dat)
    c = heapq.heappop(dat)
    c = -(-c//2)
    heapq.heappush(dat, c)
#print(dat)
print(-sum(dat))

Submission status: Accepted

Solution code:
import heapq

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

for i in range(m):
  maxa = heapq.heappop(a)
  heapq.heappush(a, maxa/2)
  
ans = 0
for i in range(n):
  ans += int(heapq.heappop(a))
  
print(-ans)

Submission status: Accepted

Solution code:
import numpy as np
import heapq as hq
import math

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

for i in range(m):
    tmp = hq.heappop(a)
    hq.heappush(a, math.ceil(tmp/2))
ans = - sum(a)
print(ans)

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    A = [int(i) for i in input().split()]
    a = []
    for i in A:
        heapq.heappush(a, -i)

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

    sum = 0
    for i in a:
        sum += i
    print(-sum)
    return 

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def solve(N: int, M: int, A: "List[int]"):
    a = []
    for i in A:
        heapq.heappush(a, -i)

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

    sum = 0
    for i in a:
        sum += i
    print(-sum)
    return


# Generated by 1.1.7.1 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(lambda x: - int(x), input().split()))
heapq.heapify(a)
ans = 0


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

print(-sum(a))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import heapq
# import bisect

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

# print(a)
print(-sum(a))

Submission status: Accepted

Solution code:
import heapq
import math

n, m = map(int, input().split())
a = []
for i in input().split():
    a.append(-1 * int(i))
heapq.heapify(a)
for _ in range(m):
    b = heapq.heappop(a)
    heapq.heappush(a, math.ceil(b / 2))
print(-1 * sum(a))

Submission status: Accepted

Solution code:
import heapq
import math

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

heapq = []
for i in range(n):
    heappush(heapq, -a[i])
    
for i in range(m):
    saidai = heappop(heapq)
    heappush(heapq, -(-saidai//2))

cost = 0
for i in range(n):
    cost += -heappop(heapq)

print(cost)

Submission status: Accepted

Solution code:
import heapq


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

    print(sum(A) * -1)


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

Submission status: Accepted

Solution code:
import numpy as np
import heapq as hq

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

for i in range(m):
    max = hq.heappop(a)
    hq.heappush(a, int(max/2))

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

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


result = -sum(A)
print(result)

Submission status: Accepted

Solution code:
import sys
import heapq
from bisect import insort_right
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [-a for a in A]
heapq.heapify(A)
  
for i in range(M):
  tmp = heapq.heappop(A)
  heapq.heappush(A,int(tmp/2))
print(sum([-a for a in A]))

Submission status: Accepted

Solution code:
import heapq

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