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

Solution (Python):

import math

def main():
    N, M = map(int,input().split())
    A = list(map(int,input().split()))
    B = [[] for _ in range(40)]

    Bmax = 1
    for Ai in A:
        Bi = int(math.log2(Ai)) + 1
        B[Bi].append(Ai)
        Bmax = max(Bmax, Bi)

    while M >= 0 and Bmax > 0:
        B[Bmax].sort(key=lambda x:-x)
        count = len(B[Bmax])
        Bcur = min(M, count)
        for i in range(Bcur):
            B[Bmax][i] = B[Bmax][i] // 2 
            
        Bmax -= 1
        B[Bmax].extend(B[Bmax+1])
        B[Bmax+1] = []
        M -= count

    Total = 0
    for Bi in B:
        for Ai in Bi:
            Total += Ai

    print(Total)




if __name__ == "__main__":
    main()

Solution (Python):
import math
import numpy as np




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

a_list = np.sort(a_list)

a_logs = np.log2(a_list).astype('int64')

max_num = max(a_logs)
num = max_num*1

count_num = 0
flag = True
while(flag):
    count_num_temp = sum(a_logs>=num) + count_num
    if(count_num_temp > m):
        flag = False
        remain = m - count_num
    else:
        count_num = count_num_temp
        num -= 1
        if(num == -1):
            print('0')
            exit()

a_list = a_list // 2**((a_logs > num) * (a_logs - num))

if(remain > 0):
    a_list = np.sort(a_list)
    a_list[(n-remain):] = a_list[(n-remain):] //2

ans = sum(a_list)
print(ans)

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

As = input().split()
A = [0]*N

for n in range(N): 
  A[n] = float(int(As[n]))+0.1
A.sort()

tid = [0]*M
ct = -1
cid = -1
ms = 0

for m in range(M):
  if ct==-1:
    A[N-1] = A[N-1]/2.0
    tid[0] = N-1
    ct = 1
    cid = 0
  else:
    if N-1-m+ms<0 or A[tid[cid]]>A[N-1-m+ms]:
      A[tid[cid]] = A[tid[cid]]/2.0
      tid[ct] = tid[cid]
      ct += 1
      cid += 1
      ms+=1
    else:
      A[N-1-m+ms] = A[N-1-m+ms]/2.0
      tid[ct] = N-1-m+ms
      ct += 1

Asum = 0
for n in range(N):
  Asum += int(A[n])
print(Asum)

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

Solution (Python):
n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort(reverse=True)

while 1:
    a.sort(reverse=True)
    if m > 0:
        a[0] //= 2
        tmp_max = a[0] 
        m -=1
    if m == 0:
        break
    for i in range(1,n):
        if tmp_max <= a[i]:
            a[i] //= 2
            m -= 1
        if m == 0:
            break
print(sum(a))

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

from math import floor
import heapq

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

h = []
for ele in a:
	heapq.heappush(h, ele)

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

ans = 0
for ele in h:
	ans += floor(-ele)

print(ans)

Solution (Python):
from heapq import heappush, heappop, heapify

n, m = [int(v) for v in input().split()]
values = [-int(v) for v in input().split()]
heapify(values)

for _ in range(m):
    v = -((-heappop(values)) >> 1)
    heappush(values, v)

print(-sum(values))

Solution (Python):
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))
    exit()

a.sort()
i = 0
while i < m:
    a[n-1] = a[n-1] // 2
    i+=1
    num = len([1 for x in a[:n-1] if x > a[n-1]])
    hoge = min(m-i, num)
    for j in range(hoge):
        a[n-2-j] = a[n-2-j] // 2
    i += hoge
    a.sort()

print(sum(a))

Solution (Python):
import heapq


def main():
    N, M = map(int, input().split())
    A_i = list(map(lambda x: -int(x), input().split()))
    heapq.heapify(A_i)
    for i in range(M):
        m = -heapq.heappop(A_i)
        m = m//2
        heapq.heappush(A_i, -m)
    print(-sum(A_i))


main()

Solution (Python):



def idx(n):
    i = 0
    while True:
        if 2**i > n:
            return i - 1
        i += 1


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

    a_max = max(A)
    K = idx(a_max) + 1

    pow_list = [[] for _ in range(K)]
    for a in A:
        pow_list[idx(a)].append(a)

    

    no_k0 = False
    for k in range(K-1, 0, -1):  
        
        
        
        
        if len(pow_list[k]) <= M:
            tmp = [p // 2 for p in pow_list[k]]
            pow_list[k-1].extend(tmp)
            M -= len(pow_list[k])

            if M == 0:
                limit = k
                no_k0 = True
                break
        else:  
            pow_list[k] = sorted(pow_list[k], reverse=True)
            pow_list[k-1].extend([p // 2 for p in pow_list[k][0:M]])
            for i in range(M):
                pow_list[k][i] = 0
            limit = k + 1
            no_k0 = True
            break

    if not no_k0:
        if len(pow_list[0]) <= M:
            return 0
        else:
            pow_list[0] = sorted(pow_list[0], reverse=True)
            for m in M:
                pow_list[0][m] = 0
            return sum(pow_list[0])

    ans = 0
    for i in range(limit):
        ans += sum(pow_list[i])

    return ans


if __name__ == "__main__":
    print(main())

Solution (Python):
import heapq
N, M = map(int, input().split())
A = map(int, input().split())
AA = [-1 * x for x in A]

heapq.heapify(AA)

for i in range(M):
  a = heapq.heappop(AA)
  
  heapq.heappush(AA, -(-a >> 1))

print(-sum(AA))

Solution (Python):
import sys, math
sys.setrecursionlimit(5 * 10**5)
input=sys.stdin.readline

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

groups = [list() for _ in range(31)]

for a in A:
    for i in range(31):
        if a < 2**i:
            groups[i].append(a)
            break

for i in range(30, 0, -1):
    if len(groups[i]) > 0:
        if len(groups[i]) <= M:
            M -= len(groups[i])
            for e in groups[i]:
                groups[i-1].append(e / 2)
            groups[i].clear()
        else:
            groups[i].sort()
            for j in range(len(groups[i])-1, len(groups[i])-1-M, -1):
                groups[i-1].append(groups[i].pop(j) / 2)
            break

ans = 0

for group in groups:
    for e in group:
        ans += math.floor(e)

print(ans)

Solution (Python):
import numpy as np

N, M=map(int, input().split())
A=np.sort(np.array(list(map(int, input().split()))))
P=np.array([int(np.log2(A[i])) for i in range(N)])

maxp=P[-1]
while M>0:
  temp=np.sum(P==maxp)
  if temp<=M:
    P[-temp:]=P[-temp:]-1
    A[-temp:]=A[-temp:]//2
    M-=temp
  else:
    A=np.sort(A)
    A[-M:]=A[-M:]//2
    M=0
    
  if np.sum(A)==0:
    break
  maxp-=1
    
print(np.sum(A))

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

A = sorted(A,reverse=True)

X = M
for i in range(M):
    A[0] //= 2
    X -= 1
    count = 0
    for j in range(min(N-1,M)):
        if A[j] < A[j+1]:
            x = A[j]
            A[j] = A[j+1]
            A[j+1] = x
            count += 1
        else:
            break
            
    if count >= X:
        for j in range(X):
            A[j] //= 2
        break
    else:
        for j in range(count):
            A[j] //= 2
        X -= count
        A = sorted(A,reverse=True)
        
        
ans = 0
for i in A:
    ans += i

print(ans)

Solution (Python):
N, M = map(int, input().split())
nums = list(map(int, input().split()))
tik = 0
while tik < M:
    nums.sort(reverse=True)
    nums[0] = nums[0] // 2 
    tik += 1
    if tik == M:
        break
    for i in range(1,N):
        if tik == M:
            break
        if nums[i] > nums[0]:
            nums[i] = nums[i] // 2
            tik += 1
        else:
            break
print(sum(nums))

Solution (Python):




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


a.sort()
a.reverse()

divlist = list()
divlist.append(int(a[0] / 2)) 
idx = 1
zflg = False

for i in range(1, m):
    if idx < n:
        if divlist[0] < a[idx]:
            
            divlist.append(int(a[idx] / 2))
            idx = idx + 1
    
        else:
            
            popval = divlist.pop(0)
            divlist.append(int(popval / 2))
    else:
        
        if divlist[0] <= 0:
            zflg = True
            break
        else:
            
            popval = divlist.pop(0)
            divlist.append(int(popval / 2))

ans = 0
if zflg == False:
    
    for i in range(len(divlist)):
        ans = ans + divlist[i]
    
    
    for i in range(idx, n):
        ans = ans + a[i]


print(ans)

Solution (Python):
import heapq

def solve(N, M, A):
    q = []
    for a in A:
        heapq.heappush(q, -a)
    for i in range(M):
        a = heapq.heappop(q)
        heapq.heappush(q, a / 2)
    return -sum([int(v) for v in q])

def main():
    N, M = map(int, input().strip().split())
    A = map(int, input().strip().split())
    print(solve(N, M, A))

if __name__ == "__main__":
    main()

Solution (Python):
import heapq

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

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

Solution (Python):
from heapq import heappush, heappop

N, M = map(int, input().split())
A = list(map(int, input().split()))
hp = []
for i in range(N):
    heappush(hp, A[i] * -1)
for i in range(M):
    tmp = heappop(hp)
    heappush(hp, -(-tmp // 2))
print(sum(hp) * -1)

Solution (Python):
import math
import heapq
from heapq import heapify

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

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    lastelt = heap.pop() 
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

for _ in range(M):
  x = math.floor(_heappop_max(A)/2)
  _heappush_max(A,x)
print(sum(A))