Problem:


Score : 400 points

Problem Statement

Takahashi is going to buy N items one by one.

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

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

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

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

Constraints

All values in input are integers.

1 \leq N, M \leq 10^5

1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_N

Output

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

Sample Input 1

3 3
2 13 8

Sample Output 1

9

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

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

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

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

Sample Input 2

4 4
1 9 3 5

Sample Output 2

6

Sample Input 3

1 100000
1000000000

Sample Output 3

0

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

Sample Input 4

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

Sample Output 4

9500000000



Sample input:
3 3
2 13 8


Sample output:
9

Submission status: Accepted

Solution code:
import heapq
import sys

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

if N == 1:
    for i in range(M):
        A[0] = A[0] // 2
    print(sum(A))
    sys.exit()
h = []
for i in range(N):
    heapq.heappush(h, -A[i])

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


print(-sum(h))

Submission status: Accepted

Solution code:
import heapq

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

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

Submission status: Accepted

Solution code:
import sys
inputs = sys.stdin.readlines()

from heapq import heappush, heappop
N, M = map(int, inputs[0].split())
A = sorted(list(map(int, inputs[1].split())))

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

for _ in range(M):
    heappush(queue, -(-heappop(queue) // 2))
print(-sum(queue))

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

print(-(sum(a)))

Submission status: Accepted

Solution code:
import heapq

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

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

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

print(-sum(ans))

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(100000)

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

l = [int(c)*(-1) for c in input().split()]
# 優先度付きキューにする
heapq.heapify(l)

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

print(sum(l)*(-1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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

#print(A_tmp)
A = [-i for i in A_tmp]

heapq.heapify(A)
#print(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
#from heapq import heappush, heappop
import heapq

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

hq=[]
for a in alist:
  heapq.heappush(hq,-a)
  
while(M>0):
  target=-1*heapq.heappop(hq)
  target//=2
  heapq.heappush(hq,-target)
  M-=1

answer_list=[heapq.heappop(hq) for i in range(len(hq))]
#print(answer_list)
print(-sum(answer_list))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

hqueue = []
for a in a_list:
    heappush(hqueue, -a)

for i in range(m):
    max_item = -(-heappop(hqueue) // 2)
    heappush(hqueue, max_item)

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

print(cost)

Submission status: Accepted

Solution code:
# プライオリティキューの利用
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
# 最大の値段を取り出すために、全て(-1)を掛ける
a = list(map(lambda x: x * (-1), a))
heapq.heapify(a)
# 割引券を使い切るまで行う
while m != 0:
    # 最大の値段を取り出す
    price = heapq.heappop(a) * (-1)
    # 割引
    price //= 2
    m -= 1
    # プライオリティキューへ戻す
    heapq.heappush(a, (-1) * price)
# 最初に(-1)掛けているので、符号を戻す
print(sum(a) * (-1))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        return heapq.heappop(self.hq) * self.sign
 
    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)
 
    def top(self):
        return self.hq[0] * self.sign
N,M = map(int,input().split())
A_s = list(map(int,input().split()))
answer = sum(A_s)
A_s = Heapq(A_s,True)
for i in range(M):
    temp = A_s.pop()
    answer -= temp-temp//2
    temp //= 2
    A_s.push(temp)
print(answer)

Submission status: Accepted

Solution code:
# ABC141D - Powerful Discount Tickets
from heapq import heapify, heappop, heappush


def main():
    N, M, *A = map(int, open(0).read().split())
    B = [-i for i in A]
    heapify(B)
    for _ in range(M):
        x = -heappop(B) >> 1
        heappush(B, -x)
    ans = -sum(B)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
inputs = sys.stdin.readlines()

from heapq import heappush, heappop
N, M = map(int, inputs[0].split())
A = list(map(int, inputs[1].split()))

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

for _ in range(M):
    heappush(queue, -(-heappop(queue) // 2))
print(-sum(queue))

Submission status: Accepted

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

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

hq = []

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


while(M):
    k = heapq.heappop(hq) * -1
    k = k // 2
    heapq.heappush(hq, -k)
    M -= 1
ans = 0
for i in range(N):
    ans += heapq.heappop(hq)

print(-ans)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
lisA = [int(i) for i in input().split()]
#print(n, m)
#print(lisA)

lisA.sort(reverse=True)
half0 = lisA[0] // 2
count = 0
for i in range(m):
	if (count > n - 1):
		count = 0
	if (lisA[count] < half0):
		lisA.sort(reverse=True)
		half0 = lisA[0] // 2
		count = 0
	lisA[count] //= 2
	count += 1
print(sum(lisA))

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

Submission status: Accepted

Solution code:
import math
from heapq import heappush, heappop


def rint(s):
    return -int(s)


def sum(a):
    s = 0
    for v in a:
        s += math.floor(-v)
    return s


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

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

print(sum(a))

Submission status: Accepted

Solution code:
import heapq as h

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

h.heapify(la)

while m > 0:
    max = abs(la[0])
    h.heapreplace(la, (max // 2)*-1)
    m -= 1

print(abs(sum(la)))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
import math

N, M = map(int, input().split())
A = [ -int(a) for a in input().split() ]
heapq.heapify(A)
for m in range(M):
    heapq.heappush(A, math.ceil(heapq.heappop(A) / 2.0))

print(-sum(A))

Submission status: Accepted

Solution code:
# D 終了後再チャレンジ
# -*- coding: utf-8 -*-
import heapq

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

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

Submission status: Accepted

Solution code:
import heapq

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

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

q = []

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

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

print(-sum(q))

Submission status: Accepted

Solution code:
from math import ceil
import heapq

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

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

print(-sum(A))

Submission status: Accepted

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

Submission status: Accepted

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

print(sum([-1 * heapq.heappop(h) for i in range(len(h))]))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import heapq

N,M=map(int,input().split())
l=list(map(int,input().split()))
h=[]
for i in range(N):
    heapq.heappush(h,10**9-l[i])

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

print(10**9*len(h)-sum(h))

Submission status: Accepted

Solution code:
import heapq
import math
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,math.ceil(heapq.heappop(h) / 2))
print(sum(h)*(-1))

Submission status: Accepted

Solution code:
import copy
import heapq
import math
n,m=map(int,input().split())
a=[0]*n
atmp=list(map(int,input().split()))
for i in range(n):
  a[i]=-atmp[i]

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

total=0  
for i in range(n):
  total+=math.ceil(a[i])
print (-total)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi, log2
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

def main():
    N,M = map(int, input().split())
    A = []
    list(map(lambda x: heappush(A, -1*int(x)), input().split()))
    for _ in range(M):
        a = -1*heappop(A)
        heappush(A, a//2 * -1)
    ans = 0
    for _ in range(N):
        ans += -1 * heappop(A)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

while m > 0:
    bb = ((heapq.heappop(b) * (-1)) // 2) * (-1)
    heapq.heappush(b, bb)
    m -= 1

total = 0
for i in range(n):
    total += b[i] * -1

print(total)

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:
import heapq

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

heapq.heapify(AA)

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


print(sum(AA)* -1)

Submission status: Accepted

Solution code:
def calc(N, M, A):
    if (N == 1):
        return A[0] // (2 ** M)
    A.sort(key=lambda a: -a)
    B = [A]
    for _ in range(M):
        i = 0
        m = B[0][0] if B[0] else -1
        for j in range(1, len(B)):
            if (B[j] and B[j][0] > m):
                i = j
                m = B[j][0]
        p = B[i].pop(0) // 2
        if (len(B) == i + 1):
            B += [[]]
        B[i + 1] += [p]
        if (not (B[0])):
            B.pop(0)
    return sum([sum(b) for b in B])


(N, M) = tuple([int(s) for s in input().split(' ')])
A = [int(s) for s in input().split()]
print(calc(N, M, A))

Submission status: Accepted

Solution code:
import time
import sys
import heapq

input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
start = time.time()
ans = []
for a in A:
    heapq.heappush(ans, -a)

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

print(-sum(ans))

Submission status: Accepted

Solution code:
import heapq

def minus_int(s):
  return -1 * int(s)

N, M = map(int, input().split())
A = list(map(minus_int, input().split()))
heapq.heapify(A)
for _ in range(M):
  tmp = int(heapq.heappop(A) / 2)
  heapq.heappush(A, tmp)

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

Submission status: Accepted

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

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

if __name__ == '__main__':
    func()

Submission status: Accepted

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

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

# solve
ans = [-a for a in A]
heapq.heapify(ans)
for i in range(M):
    tmp = heapq.heappop(ans) * (-1) // 2
    heapq.heappush(ans, tmp * (-1))
ans = [-a for a in ans]

# output
print(sum(ans))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())  # 品物の数、割引券の枚数
A = list(map(int, input().split()))  # 品物の値段
A.sort(reverse=True)
i = 0
for _ in range(M):
    A[i] = A[i] // 2
    if i <= N - 2 and A[i] < A[i + 1] and A[0] < A[i+1]:
        i += 1
    else:
        A.sort(reverse=True)
        i = 0
print(str(sum(A)))

Submission status: Accepted

Solution code:
import math
import heapq

N, M = list(map(int, input().split()))
A = list(map(lambda a: -int(a), input().split()))
A.sort()
heapq.heapify(A)

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

amount = 0
for a in A:
  amount += math.floor(-a)
print(amount)

Submission status: Accepted

Solution code:
import math
import heapq

n, m = map(int, input().split())
prices = list(map(int, input().split()))
hq = []


def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


# 優先度付キューの作成
for price in prices:
    _heappush_max(hq, price)

# 割引適用
for _ in range(m):
    target = _heappop_max(hq)
    _heappush_max(hq, target/2)

total = 0
for price in hq:
    total += math.floor(price)

print(total)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
A = list(map(int,input().split()))
A = [x * -1 for x in A]
A.sort()
import heapq
import bisect
heapq.heapify(A)
for _ in range(m):
    min_ = heapq.heappop(A)
    tmp = min_ * -1 // 2 * -1
    index = bisect.bisect_left(A, tmp)
    heapq.heappush(A,tmp)
print(sum(A) * -1)

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)

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

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

ans = sum(A)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
it = 0
for i in range(M):
    A[it]=A[it]//2
    if it<N-1:
        if A[it]<A[it+1] and A[0]<A[it+1]:
            it+=1
        else:
            A.sort(reverse = True)
            it = 0
    if it == N-1:
        A.sort(reverse = True)
        it = 0
print(sum(A))

Submission status: Accepted

Solution code:
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)
import heapq


def main():
    N, M = map(int, input().split())
    A = [int(c) for c in input().split()]
    queue = []

    for i in range(N):
        heapq.heappush(queue, - A[i])
    for i in range(M):
        max_ = heapq.heappop(queue)
        heapq.heappush(queue, int(max_/2))
    
    print(- sum(queue))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

q = []
for a in Alist:
    heapq.heappush(q, -a)

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

print(-sum(q))

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

Submission status: Accepted

Solution code:
from heapq import heappop,heappush,heapify
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7) 
 
n,m = map(int,input().split())
a = [int(x) for x in input().split()]
 
a_minus = [-x for x in a]
heapify(a_minus)
 
pop = lambda: -heappop(a_minus)
push = lambda x: heappush(a_minus,-x)
 
for _ in range(m):
    x = pop()
    push(x//2)
 
print(-sum(a_minus))

Submission status: Accepted

Solution code:
from heapq import heapify,heappush,heappop
from math import ceil
n,m,*a=map(int,open(0).read().split())
a=[(-1)*x for x in a]
heapify(a)
for _ in range(m):
	x=heappop(a)
	heappush(a,ceil(x/2))
print(-sum(a))

Submission status: Accepted

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

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

print(-sum(item))

Submission status: Accepted

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

lst = list(map(lambda x: -int(x),input().split()))
heapq.heapify(lst)

for i in range(M):
    a = heapq.heappop(lst)
    a = a/2.0
    heapq.heappush(lst,a)
    #print(a)

ans=0
for i in lst:
    i *= (-1)
    #print(i)
    ans += i//1
print(int(ans))

Submission status: Accepted

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

print(-sum(item))

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
q=[]
a=[-int(i) for i in input().split()]
for i in a:
    heapq.heappush(q,i)
ans=chk=0
for i in range(m):
    x=heapq.heappop(q)
    heapq.heappush(q,-(-x//2))
print(-sum(q))
exit()

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,M = map(int,input().split())
A = list(map(int,input().split()))

l = []
for i in range(N):
    num = A[i]
    while num > 0:
        l.append(num)
        num = int(num / 2)

l.sort(reverse = True)

s = sum(A)
p = 0

if len(l) >= M:
    for i in range(M):
        p += l[i] - int(l[i] / 2)

    print(s - p)
    
else :
    print(0)

Submission status: Accepted

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

for i in range(m):
    v = - heapq.heappop(h)
    heapq.heappush(h, -int(v / 2))

print(-sum(h))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N,M=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort(reverse=True)
x=ls[0]
L=int(math.log2(x))
#2**L より大きいものをわける
def cut(lst,exp):
    for ii in range(len(lst)):
        if ii+1==len(lst):
            break
        if lst[ii+1]<exp:
           break
    return ii
m=M #残り回数
b=-1
ls3=[]
while True:
    if m==0:
        break
    a=b+1
    b=cut(ls,2**L)
    ls2=ls[a:b+1]
    ls3=ls3+ls2
    if ls2!=[]:
        ls3.sort(reverse=True)
    for j in range(len(ls3)):
        ls3[j]=ls3[j]//2
        m-=1
        if m==0:
            break
    L-=1
#    print(ls3,m,b)
#print(ls3,ls[b+1:])
s=sum(ls3)+sum(ls[b+1:])
print(s)

Submission status: Accepted

Solution code:
import sys

def main():
	input = sys.stdin.readline

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

	count = [0]*N
	ind = [0]
	for i in range(M):
		maximum = 0
		for j in ind:
			if A[j]>maximum:
				maxind = j
				maximum = A[j]

		if maximum==0: break

		# print(maxind)
		A[maxind] = A[maxind]/2
		count[maxind] += 1
		# print(count[maxind])
		if count[maxind]==len(ind):
			ind.append(0)
			# ind[-2] += 1
			ind[-2] = min(N-1,ind[-2]+1)
			# if ind[-1]!=N-1:
		else: 
			# ind[count[maxind]-1] += 1
			ind[count[maxind]-1] = min(N-1,ind[count[maxind]-1]+1)

		# print(ind)

	print(sum(map(int,A)))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

from heapq import heappush, heappop

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

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

Submission status: Accepted

Solution code:
import math
N,M=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort(reverse=True)
x=ls[0]
L=int(math.log2(x))
#2**L より大きいものをわける
def cut(lst,exp):
    for ii in range(len(lst)):
        if ii+1==len(lst):
            break
        if lst[ii+1]<exp:
           break
    return ii
m=M #残り回数
b=-1
ls3=[]
while True:
    if m==0:
        break
    a=b+1
    b=cut(ls,2**L)
    ls2=ls[a:b+1]
    ls3=ls3+ls2
    ls3.sort(reverse=True)
    for j in range(len(ls3)):
        ls3[j]=ls3[j]//2
        m-=1
        if m==0:
            break
    L-=1
#    print(ls3,m,b)
#print(ls3,ls[b+1:])
s=sum(ls3)+sum(ls[b+1:])
print(s)

Submission status: Accepted

Solution code:
import math
n, m = map(int, input().split())
an = list(map(int, input().split()))
maxi = max(an)
p = math.floor(math.log2(maxi))+1
ps = [0 for _ in range(p)]
for a in an:
  ps[math.floor(math.log2(a))] += 1

an.sort(reverse=True)

sum = 0
subtotal = 0
for p in ps[::-1]:
  if sum + subtotal + p > m:
    break
  subtotal += p
  an[:subtotal] = [a/2 for a in an[:subtotal]]
  sum += subtotal
# print(an)
an.sort(reverse=True)
p = m - sum
an[:p] = [a/2 for a in an[:p]]
# print(an)

sum = 0
for a in an:
  sum += math.floor(a)
print(sum)

Submission status: Accepted

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

Submission status: Accepted

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

a.sort(reverse=True)

for i in range(m):
    if i == 0:
        down = a[0]
        a.remove(down)
        b.append(down//2)
    else:
        if a != [] and a[0] >= b[0]:
            down = a[0]
            a.remove(down)
        else:
            down = b[0]
            b.remove(down)
        b.append(down//2)
    
print(sum(a)+sum(b))

Submission status: Accepted

Solution code:
import numpy as np

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

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

# As.sort(reverse=True)
As[::-1].sort()
max_A = As[0]

while M > 0:
    i=1
    for i in range(1, min(M, N)):
        if As[i] <= max_A//2:
            break
    # print(M)
    # print(As)
    # print(i)
    As[:min(M,i)] = As[:min(M,i)] // 2
    # print(As)
    M -= i
    As[::-1].sort()
    max_A = As[0]
    # print(As)

print(np.sum(As))

Submission status: Accepted

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

import heapq

heapq.heapify(A)

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

print(-1*sum(A))

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
L = list(map(int, input().split()))
q = []

for money in L:
    tmp = money*(-1)
    heapq.heappush(q, tmp)

for i in range(M):
    kakaku = heapq.heappop(q)*(-1)
    kakaku = int(kakaku/2)
    kakaku = kakaku*(-1)
    heapq.heappush(q, kakaku)

ans=0
while len(q)>0:
    ans += heapq.heappop(q)*(-1)

print(ans)

Submission status: Accepted

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

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

A = [int(i)*(-1) for i in input().split()]



# print(A)
# for i in range(M):
# 	max_index = A.index(max(A))
# 	A[max_index] = int(A[max_index]/2)

# print(sum(A))
heapq.heapify(A)

for i in range(M):
	

	min = heapq.heappop(A)
	# 最小値を削除と値を渡す
	# print(A)
	# print(min)

	heapq.heappush(A,int(min/2))
	# print(A)


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

Submission status: Accepted

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

b=[]

for i in range(n):
    for j in range(1+math.floor(math.log(a[i]+0.1)/math.log(2))):
        b.append(a[i]//(2**j)-a[i]//(2**(j+1)))
        
b.sort()
bb=b
b=[bb[len(b)-1-i] for i in range(len(bb))]


print(sum(a)-sum(b[0:m]))

Submission status: Accepted

Solution code:
import numpy as np
import heapq
N,M=map(int,input().split())
cost = list(map(int,input().split()))
ln=np.array(cost)
ln=ln*-1
cost=ln.tolist()
heapq.heapify(cost)
for i in range(M):
    v=heapq.heappop(cost)/2
    heapq.heappush(cost,v)
su=0
for i in range(len(cost)):
    x=-cost[i]
    su=su+int(x)
print(su)

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()

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

	A.sort()
	A = A[::-1]
	ans = 0
	A_new = []
	mimi = -1

	for i in range(1000000000000):
		for i,val in enumerate(A):
			if i == len(A)-1:
				A_new.append(val)
				break

			if mimi < val and M > 0:
				flg = False
				for j in range(1,M+1):
					if M - j != 0:
						tmp = val // (2**j)
						if tmp < A[i+1] or tmp < mimi:
							M -= j
							A_new.append(tmp)
							flg = True
							if mimi == -1:
								mimi = tmp
							break

				if flg == False:
					tmp = val // (2**M)
					M = 0
					A_new.append(tmp)

			else:
				A_new.append(val)

		#print(A_new)
		#A = copy.deepcopy(A_new)
		A = A_new
		A.sort()
		A = A[::-1]
		A_new = []
		mimi = -1

		if M == 0:
			break

	#print(A)

	ans = 0
	for i in A:
		ans += i

	print(ans)


if __name__ == "__main__":
	main()

Submission status: Accepted

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

def main():
    _,M=map(int,input().split())
    A = []
    for a in list(map(int, input().split())):
        heapq.heappush(A, -a)
    while M>0:
        a = -heapq.heappop(A)
        a //= 2
        M -= 1
        heapq.heappush(A, -a)
    print(-sum(A))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    input = lambda: stdin.readline()[:-1]
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    price = list(map(lambda x: x * -1, A))
    heapify(price)
    for _ in range(M):
        n = heappop(price)
        heappush(price, -(-n // 2))

    print(-sum(price))

main()