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 as hp

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

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

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

print(-sum(a))

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

def resolve():
  N, M = map(int, input().split(" "))
  A = [(-1)*int(x) for x in input().split(" ")]
  heapify(A)

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

if __name__ == "__main__":
  resolve()

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,m=mp()
a=lmp()
l=[]
heapq.heapify(l)
for i in a:
    heapq.heappush(l,(-1)*i)
for i in range(m):
    j=heapq.heappop(l)
    heapq.heappush(l,-(-j//2))
print(-sum(l))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heappop,heappush

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

h=[]
for l in a:
    heappush(h,-l) 
    
for i in range(m):
    amax=heappop(h)
    l=(-amax)//2
    heappush(h,-l)
    
print(-sum(h))

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(aL)

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

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

Submission status: Accepted

Solution code:

import heapq

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


#print(A)
heapq.heapify(A)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

I = input().split()
N = int(I[0])
M = int(I[1])
# N: 品物の数
# M: 割引券の数
# A: 品物の値段行列
A = list(map(int , input().split()))

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

heapq.heapify(A)
for i in range(M):
    M -= 1
    pri = heapq.heappop(A)

    pri *= -1
    pri //= 2
    pri *= -1

    heapq.heappush( A , pri )

Fi_pri = 0
for i in range(N):
    Fi_pri += A[i]

print( -1 * Fi_pri )

Submission status: Accepted

Solution code:
def bin_tree( pri , li_pri , len_li ):
    #pri: どこに入れていいかわからない値段
    #li_pri: 値段のリスト(昇順)
    #len_li: リストの長さ
    lo = 0
    hi = len_li - 1
    while hi - lo > 1:
        mid = lo + (hi - lo) // 2
        guess = li_pri[mid]
        if guess >= pri:
            hi = mid
        else:
            lo = mid
    return lo

I = input().split()
N = int(I[0])
M = int(I[1])
# N: 品物の数
# M: 割引券の数
# A: 品物の値段行列
A = list(map(int , input().split()))
A.sort()

while M > 0:
    M -= 1
    pri = A.pop( N - 1 )
    pri = pri // 2
    if len(A) == 0:
        ans = 0
    elif (pri < A[0] ):
        ans = 0
    else:
        ans = bin_tree( pri , A , N - 1 ) + 1
    # ans: pri以上となる値段のうち最小のインデックス
    A[ans:ans] = [pri]    

F_pri = 0
for i in range(N):
    F_pri += A[i]
print(F_pri)

Submission status: Accepted

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


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


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    n, m = MI()
    a = LI()
    heap = []
    for i in range(n):
        heapq.heappush(heap, a[i] * -1)

    while m > 0:
        min_ = heapq.heappop(heap) * -1
        min_ = (min_ // 2) * -1
        heapq.heappush(heap, min_)
        m -= 1
    print(sum(heap) * -1)


main()

Submission status: Accepted

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

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

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heapify,heappush,heappop

def main():
    N,M = map(int,input().split())
    A = [ -x for x in map(int,input().split()) ]
    heapify(A)

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


    ans = 0
    for i in range(N):
        ans += A[i]

    ans = abs(ans)
    return ans

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import heapq

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

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

Submission status: Accepted

Solution code:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
INT_MIN=-10**13
import bisect as B
###############################################################################\
n,m=INPUT()
A=INPUT()
A.sort()
for _ in range(m):
    B.insort(A,A.pop()//2)
print(sum(A))

Submission status: Accepted

Solution code:
import heapq
from fractions import Fraction

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

a = list(map(lambda x: Fraction(1, int(x)), input().split()))

heapq.heapify(a)

for i in range(m):
    x = heapq.heappop(a)
    y = Fraction(x.numerator * 2, x.denominator)
    if y.numerator < y.denominator:
        heapq.heappush(a, y)
    elif len(a) == 0:
        break

s = 0


for j in range(len(a)):
    s += int(Fraction(a[j].denominator, a[j].numerator))

print(s)

Submission status: Accepted

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

discount_list = []
for a in A:
    while a > 0:
        discount = a//2
        discount_list.append(a-discount)
        a = discount
        
discount_list.sort(reverse=True)
# print(discount_list)

print(sum(A)-sum(discount_list[:M]))

Submission status: Accepted

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

while M > 0:
    x = heapq.heappop(heap)
    heapq.heappush(heap, int(x/2))
    M -= 1
print(sum(heap)*(-1))

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
n, m = map(int, input().split())
a = list(map(lambda x:-int(x), input().split()))
heapify(a)
for _ in range(m):
    x = heappop(a)
    x /= 2
    heappush(a, x)
print(-sum(map(lambda x : int(x), 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//=2
    heapq.heappush(A,-a)

print(-sum(A))

Submission status: Accepted

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


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

coupon = M
while coupon:
    try:
        if B:
            if A[-1] >= B[-1]:
                B.appendleft(A.pop() // 2)
            else:
                B.appendleft(B.pop() // 2)
        else:
            B.append(A.pop() // 2)
        coupon -= 1
    except IndexError:
        A, B = B, A


ans = sum(int(i) for i in A) + sum(int(i) for i in B)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
su = sum(A)
l = []

for i in range(N):
    for j in range(30):
        l += -(-A[i]//2),
        A[i] //= 2

l.sort(reverse=True)

print(su - sum(l[:M]))

Submission status: Accepted

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

while M:
    A[-1]//=2
    M-=1
    i=-2
    while M and (-N<=i and A[i]>=A[-1]):
        A[i]//=2
        M-=1
        i-=1
    A.sort()

print(sum(A))

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

print(-sum(a))

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

Submission status: Accepted

Solution code:
inp=list(map(int,input().split()))
m=inp[1]
inp=list(map(int,input().split()))
ans=0
inp=[-1*item for item in inp]
import heapq
heapq.heapify(inp)
while m>0:
    a=heapq.heappop(inp)
    a*=-1
    x=a//2
    heapq.heappush(inp,-1*x)
    m-=1
print (-1*sum(inp))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import heapq

n, m, *a = map(int, open(0).read().split())

a = [*map(lambda x: -x, a)]
heapq.heapify(a)
for _ in range(m):
    heapq.heappush(a, -(-heapq.heappop(a) >> 1))
print(-sum(a))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from bisect import insort_right

n, m, *a = map(int, open(0).read().split())
a.sort()
for _ in range(m):
    insort_right(a, a.pop() >> 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 i in range(m):
    tmp_min=heapq.heappop(a)
    if tmp_min%2==0:
        push=tmp_min/2
    else:
        push=tmp_min//2+1
    heapq.heappush(a,push)
print(int(-sum(a)))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
from collections import defaultdict as D
from functools import reduce
from heapq import heappop,heappush,heapify
import numpy as np
import sys
import os
sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353    

N, M = LI()
A = LI()

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):
    # 高速に値を取り出す。O(logN)
    x = pop()
    push(x//2)
 
answer = -sum(A_minus)
print(answer)

Submission status: Accepted

Solution code:
from collections import deque

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

A = deque(sorted(A,reverse=True))
B = deque([])
n = 0
for m in range(M):
    if A:
        if B:
            if (A[0] > B[0]):
                B.append(A.popleft()//2)
                continue
        else:
            B.append(A.popleft()//2)
            continue
    # print(m,n)
    n += 1
    b = B.popleft()
    B.append(b//2)

print(sum(A)+sum(B))

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

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
As = list(mapint())
Q = []
from heapq import heappop, heappush
for a in As:
    heappush(Q, -a)
for i in range(M):
    v = heappop(Q)
    heappush(Q, v/2)
lis = [-int(x) for x in Q]
print(sum(lis))

Submission status: Accepted

Solution code:
import heapq

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

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

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

heapq.heapify(a)

count = 0

while count < m:
    item = heapq.heappop(a)
    item= abs(item)
    discount_item = item//2
    heapq.heappush(a,-1*discount_item)
    count += 1

print(abs(sum(a)))

Submission status: Accepted

Solution code:
import heapq

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

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

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

heapq.heapify(a)

count = 0

while count < m:
    item = heapq.heappop(a)
    item= abs(item)
    discount_item = item//2
    heapq.heappush(a,-1*discount_item)
    count += 1

result_prime = [-1*i for i in a]

print(sum(result_prime))

Submission status: Accepted

Solution code:
N, M = list(map(int,input().split()))
A = sorted(list(map(int,input().split())), reverse=True)
b = []

b.append(A.pop(0)//2)
for i in range(1,M):
    if A == []:
        b.append(b.pop(0)//2)
    else:
        if A[0] > b[0]:
            b.append(A.pop(0)//2)
        else:
            b.append(b.pop(0)//2)

print(sum(A)+sum(b))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

Solution code:

from heapq import heappop, heappush

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

pq = []
for v in X:
    heappush(pq, -v)

for _ in range(M):
    u = heappop(pq)
    heappush(pq, -(-u // 2))

print(-sum(pq))

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))
ticket_num = m
heapq.heapify(a)

if n > 1:
    for i in range(m):
        MAX = heapq.heappop(a)
        MAX = math.ceil(MAX / 2)
        heapq.heappush(a,MAX)
        
else:
    MAX = heapq.heappop(a)
    MAX = math.ceil(MAX / (2**m))
    heapq.heappush(a,MAX)

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

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
N, M = map(int, input().split())
*A, = map(lambda x: -int(x), input().split())
heapify(A)
for _ in range(M):
    x = heappop(A)
    x = -(-x//2)
    heappush(A, x)
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 i in range(m):
    a = heapq.heappop(A)
    heapq.heappush(A, a/2)
print(sum([-int(a) for a in A]))

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from sys import stdin

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

lb = -1
ub = 1e+09 + 3
total_money = sum(a)

while ub - lb > 1:
    mid = (lb + ub) // 2
    count = 0
    ac = a[:]
    for i in range(len(ac)):
        while ac[i] > mid:
            if ac[i] == 0:
                break
            ac[i] //= 2
            count += 1
        if count > m:
            break
    if count > m:
        lb = mid
    else:
        ub = mid
        ac.sort(reverse=True)
        if count < m:
            for i in range(m-count):
                if i >= n:
                    break
                ac[i] //= 2
        total_money = sum(ac)


print(total_money)

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

print(-sum(A))

Submission status: Accepted

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

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

print(sum(int(-x) for x in a))

Submission status: Accepted

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

#print(list_A)

#heapifyが動作が重い。for文の中に入れるとTLE。
heapq.heapify(list_A) #list_Aを優先度付きキューに
for i in range(M):
  
  target = heapq.heappop(list_A)
  #print("after heappop",list_A)
  
  '''負の要素の切り捨て除算は切り捨てがマイナスの方に
  行くため少しだけややこしい。'''
  target = (-1)*((-target) // 2)
  heapq.heappush(list_A, target)  # 要素の挿入
  #print("No.",i,"change finished",list_A)

print((-1)*sum(list_A))

Submission status: Accepted

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

#print(list_A)
heapq.heapify(list_A)
for i in range(M):
  
  target = heapq.heappop(list_A)
  #print("after heappop",list_A)
  
  '''負の要素の切り捨て除算は切り捨てがマイナスの方に
  行くため少しだけややこしい。'''
  heapq.heappush(list_A, (-1)*((-target) // 2))  # 要素の挿入
  #print("No.",i,"change finished",list_A)

print(-sum(list_A))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

print(-sum(a))

Submission status: Accepted

Solution code:
# 解説を読んだ。優先度付きキューね，はい。
import heapq


def main():
    item_no, discount_no = [int(x) for x in input().split()]
    prices = [int(x) * -1 for x in input().split()]
    heapq.heapify(prices)

    for _ in range(discount_no):
        current_max = heapq.heappop(prices)
        current_max = current_max * -1 // 2 * -1
        heapq.heappush(prices, current_max)

    print(- sum(prices))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect

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

Ali.sort()
for i in range(M):
  a = Ali.pop(-1)
  a //= 2
  Ali.insert(bisect(Ali,a), a)

print(sum(Ali))

Submission status: Accepted

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

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

import heapq

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

heapq.heapify(A)

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

print(sum(list(map(lambda x: x*(-1), 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)
num = 0
while num < m:
    maximum = -1 * heapq.heappop(a)
    maximum //= 2
    heapq.heappush(a, -maximum)
    num += 1
print(-sum(a))

Submission status: Accepted

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

Submission status: Accepted

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

tmp_list = []

for i in range(n):
    tmp = A[i]
    now = tmp
    while True:
        if tmp != 0:
            tmp = tmp // (2)
            tmp_list.append(now - tmp)
            now = tmp
        else:
            break

tmp_list.sort(reverse=True)
print(sum(A) - sum(tmp_list[:m]))

Submission status: Accepted

Solution code:
import heapq
t = 1
# t = input()
# t = int(t)
def max(a,b):
	if a > b:
		return a
	return b
while t > 0:
	t -= 1
	# s = input()
	# ans = ""
	# if s == "Sunny":
	# 	ans = "Cloudy"
	# elif s == "Cloudy":
	# 	ans = "Rainy"
	# else:
	# 	ans = "Sunny"
	# print(ans)
	n,m = map(int,input().split())	
	v = list(map(int,input().strip().split()))[0:n]
	for i in range(n):
		v[i] = -v[i]
	heapq.heapify(v)
	for i in range(m):
		x = heapq.heappop(v)
		x = -x
		x = x//2
		heapq.heappush(v,-x)
	ans = 0
	for i in range(n):
		ans += (-heapq.heappop(v))
	print(ans)
	# # m = {}
	# l = []
	# for i in range(n):
	# 	l.append(0)
	# # ans = 0
	# j = 1
	# for i in v:
	# 	l[i-1] = j
	# 	j += 1
	# # print(ans)
	# for i in l:
	# 	print(i,end=" ")

Submission status: Accepted

Solution code:
import heapq
NM,a=open(0).read().rstrip().split('\n')
N,M=map(int,NM.split())
A=list(map(int,a.split()))
A=[-1*i for i in A]
heapq.heapify(A)
for i in range(M):
    sample=heapq.heappop(A)
    sample=-1*sample//2
    heapq.heappush(A,-1*sample)
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 x in range(M):
  t=(-1)*heapq.heappop(A)
  heapq.heappush(A,(-1)*(t//2))
print(-1*sum(A))

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for y in a:
  b.append(y*(-1))

heapq.heapify(b)
for x in range(m):
  c=heapq.heappop(b)*(-1)
  d=(c//2)*(-1)
  heapq.heappush(b,d)
  
sum1=sum(b)*(-1)
print(sum1)

Submission status: Accepted

Solution code:
import heapq

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

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

print(sum(A) * -1)

Submission status: Accepted

Solution code:
import heapq
N,M = map(int, input().split())
A = list(map(lambda x:-int(x), input().split()))
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(lambda x: int(x)*-1,input().split()))
heapq.heapify(A)
while M:
    tmp=heapq.heappop(A)*-1
    heapq.heappush(A,tmp//2*-1)
    M -=1
print(sum(A)*-1)

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

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

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

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

print(sum([int(-B[i]) for i in range(N)]))

Submission status: Accepted

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

    heapq.heapify(a)
    cnt = 0
    while cnt < m:
        x = heapq.heappop(a)
        heapq.heappush(a, -(-x//2))
        cnt += 1
        if x == 0: break

    return sum(a)*(-1)

print(solve())

Submission status: Accepted

Solution code:
from heapq import heappushpop, heapify

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

heap = [-a for a in A]
heapify(heap)

for _ in range(M):
    heappushpop(heap, (-1 * heap[0] // 2) * -1)

print(-1 * sum(heap))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def resolve():
    import heapq
    import sys
    input = sys.stdin.readline
    _, M = [int(i) for i in input().split()]
    A = [-int(i) for i in input().split()]
    heapq.heapify(A)
    for _ in range(M):
        heapq.heappush(A, -(-heapq.heappop(A) // 2))
    print(-sum(A))

resolve()

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    n, m = i_map()
    num_list = i_list()

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

    heapify(num_list)

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

    print(sum(num_list)*-1)

if __name__ == '__main__':
    main()