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: Wrong Answer

Solution code:
while True:
	try:
		N, M = map(int, input().split())
		A = list(map(int, input().split()))
		if (N==1):
			for i in range(M):
				A[0] //= 2
			print(A[0])
			continue
		A.sort()
		stack = []
		while (M > 0):
			while (stack):
				if (stack[-1] >= A[-1]):
					A.append(stack.pop())
				else:
					break
			if (stack):
				while (M > 0 and A[-1] >= A[-2] and A[-1] >= stack[-1] and A[-1] > 0):
					A[-1] //= 2
					M -= 1
			else:
				while (M > 0 and A[-1] >= A[-2] and A[-1] > 0):
					A[-1] //= 2
					M -= 1
			stack.append(A.pop())
			#print(f"M = {M}, A = {A}")
			#print(f"stack = {stack}")
		print(sum(A) + sum(stack))
	except:
		break

Submission status: Wrong Answer

Solution code:
import heapq

n, m = map(int, input().split())
a = []
#a = list(map(int, input().split()))
#a = list(reversed(sorted(a)))
#heapq.heapify(a)
for i in input().split():
    heapq.heappush(a, -int(i))

ans = 0

for i in range(len(a)):
    while True:
        if m <= 0:
            break

        maxV = heapq.heappop(a)
#        print('maxV: ' + str(maxV))
        heapq.heappush(a, maxV // 2)
        m -= 1
        # print('m: ' + str(m))
        # print('a: ' + str(a))
ans = -sum(a)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
sm = sum(a)
a.sort(reverse=True)
a = a[0:min(n,m)]
discount = 0
for i in range(m):
  newa = a[0]//2
  discount += a[0] - newa
  l = len(a)
  ain = a[1:min(l,m-i-1)]
  lin = len(ain)
  if lin == 0:
    a = [newa]
    continue
  if newa > ain[0]:
    a = [newa] + ain
    continue
  j = 0
  k = lin-1
  while j < k:
    mid = (j+k)//2
    if newa <= ain[mid]:
      k = mid
    else:
      j = mid
  a = ain[0:j+1] + [newa] + ain[j+1:]
print(sm - discount)

Submission status: Wrong Answer

Solution code:
import heapq
N,M = map(int,input().split())
A = [(-1)*int(i) for i in input().split()]
heapq.heapify(A)
flag = True
while flag:
    tmp = heapq.heappop(A)
    tmp = (-1)*((-1*tmp)//2)
    heapq.heappush(A,tmp)
    M-=1
    if M<=0 or tmp==0:
        flag = False

print(-sum(A))

Submission status: Wrong Answer

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

print(-sum(A))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
priceList = [int(i) for i in input().split()]

priceList.sort(reverse=True)
if N == 1:
    while M > 0:
        priceList[0] = priceList[0] // 2
        M -= 1
else:
    while M > 0:
        while priceList[0] >= priceList[1] and M > 0:
            priceList[0] = priceList[0] // 2
            M -= 1

        rangeStart = 1
        rangeEnd = N-1
        nowIndex = (rangeStart+rangeEnd) // 2
        isComp = False
        while not isComp:
            if priceList[nowIndex] >= priceList[0]:
                rangeStart = nowIndex
            else:
                rangeEnd = nowIndex
            nowIndex = (rangeStart+rangeEnd) // 2
            if rangeStart == rangeEnd - 1:
                isComp = True
        priceList.insert(rangeEnd, priceList[0])
        priceList.pop(0)

sum = 0
for i in range(N):
    sum += priceList[i]

print(sum)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
As = np.array( list( map(float, input().split()) ) )
As /= 2.0
As.sort()
N1 = int(N/2)
for _ in range(M):
    As[-1] /= 2.0
    if As.size == 1:
      continue
    elif (As[-1] < As[-2]):
        As[-N1:].sort()

ans = np.sum(np.floor(As*2.0))
print(int(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
As = np.array( list( map(float, input().split()) ) )
As /= 2.0
As.sort()
N1 = int(N/10)
for _ in range(M):
    As[-1] /= 2.0
    if As.size == 1:
      continue
    elif (As[-1] < As[-2]):
        As[-N1:].sort()

ans = np.sum(np.floor(As*2.0))
print(int(ans))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# coding: UTF-8


#import scipy.optimize
from math import ceil,floor
from heapq import heappush, heappop, heapify
    
##################################################################

if __name__ == "__main__":

    Input = [input() for i in range(2)]
    N,M = list(map(int,Input[0].split()))
    A = list(map(int,Input[1].split()))
    A = [-a for a in A]
    heapify(A)
    if N==1:
        Money = floor(A[0]/(2**M))
        print(Money)
    else:
        Use = 0
        while Use < M:
            temp = -1*heappop(A)
            temp = floor(temp/2)
            heappush(A, -temp)
            Use += 1
##                if A[0] == A[1]:
##                    Usenow = 1
##                    Use += Usenow
##                else:
##                    Usenow = math.ceil(math.log2(A[0])-math.log2(A[1]))
##                    Use += Usenow
##                    if Use > M:
##                        Usenow -= Use - M
##                        Use = M
##                temp = math.floor(A[0]/(2**Usenow))
##                if temp >= A[1]:
##                    A[0] = temp
##                else:
##                    for i in range(2,N):
##                        if temp >= A[i]:
##                            A[0:i-1] = A[1:i]
##                            A[i-1] = temp
##                            break
##                        elif i == N-1:
##                            A[0:N-1] = A[1:N]
##                            A[N-1] = temp                        
##                        else:
##                            continue
        print(sum([-1*heappop(A) for i in range(N)]))

Submission status: Wrong Answer

Solution code:
import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from heapq import heappush, heappop
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


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

    if N == 1:
        print(math.floor(stuff[0] / (2**M)))
        sys.exit()

    for i in range(M):
        m = -heappop(stuff)
        m = math.floor(m / 2)
        heappush(stuff, -m)
        # stuff[stuff.index(max(stuff))] = math.floor(stuff[stuff.index(max(stuff))] / 2)

    print(-sum(stuff))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

import heapq
heapq.heapify(b)

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

Submission status: Wrong Answer

Solution code:
a = []
a = input().split()
N = int(a[0])
M = int(a[1])

A = input().split()
A = [int(n) for n in A]
B = [[] for i in range(M+1)]
#B = [[]]

#B[0] = A
for i in range(M+1) :
#  B.append(A)
#  B[i+1].append(A)
  B[i] = A



count_j = [int(0) for i in range(N)]

for i in range(M) :
  for j in range(N) :
    if B[i][j] == max(B[i]) :
      print('B[i][j]', B[i][j])
      count_j[j] = count_j[j] + 1
      B[i+1][j] = B[i+1][j] // (2**(count_j[j]))     
#      B[i+1][j] = B[0][j] // (2**(count_j[j]))
      print('count_j', count_j)
      print('A', A)
      print('B', B)
      break

print('N', N)
print('M', M)
print('A', A)
print('B', B)
print('count_j', count_j)

Submission status: Wrong Answer

Solution code:
class heap():
    def __init__(self, maxcom=True):
        if maxcom:
            self.compare = lambda x, y: x > y
        else:
            self.compare = lambda x, y: x < y

    def heappush(self, x, heap):
        heap.append(x)
        length = len(heap)
        pointer = length
        while True:
            if pointer == 1:
                break
            if self.compare(heap[pointer - 1], heap[(pointer >> 1) - 1]):
                heap[pointer - 1], heap[(pointer >> 1) - 1] = heap[(pointer >> 1) - 1], heap[pointer - 1]
                pointer = pointer >> 1
            else:
                break

    def heapreplace(self, function, heap):
        heap[0] = function(heap[0])
        pointer = 1
        length = len(heap)
        while True:
            if (pointer << 1) > length:
                break
            elif (pointer << 1) + 1 > length :
                if self.compare(heap[(pointer << 1) - 1], heap[pointer - 1]):
                    heap[(pointer << 1) - 1], heap[pointer - 1] = heap[pointer - 1], heap[(pointer << 1) - 1]
                else:
                    break
            else:
                if self.compare(heap[(pointer << 1) - 1], heap[pointer << 1]):
                    next_pointer = pointer << 1
                else:
                    next_pointer = (pointer << 1) + 1
                if self.compare(heap[next_pointer - 1], heap[pointer - 1]):
                    heap[next_pointer - 1], heap[pointer - 1] = heap[pointer - 1], heap[next_pointer - 1]
                else:
                    break


n, m = map(int, input().split())
a = map(int, input().split())
heapq = []
heapc=heap(True)
for i in a:
    heapc.heappush(i,heapq)
for _ in range(m):
    heapc.heapreplace(lambda x:x>>1,heapq)
print(sum(heapq))

Submission status: Wrong Answer

Solution code:
def division(a):
  ans = int(a / 2)
  return ans

def list_div(a):
  half_a = []
  for i in range(len(a)):
    half_a.append(division(a[i]))
  num = half_a.index(max(half_a))
  a.pop(num)
  a.insert(num,max(half_a))
  return a

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

half_a = []
ans = 0

for i in range(m):
  list_div(a)

ans = sum(a)

print(ans)

Submission status: Wrong Answer

Solution code:
import math
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]*(-1))

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

ans = 0
for i in hq:
  ans += i *(-1)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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


print(L)


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

print(-sum(L))

Submission status: Wrong Answer

Solution code:
import heapq

n,m=map(int,input().split())
a=list(map(int,input().split()))
hq=[]
for i in range(len(a)):
  heapq.heappush(hq,-a[i])

if n==1:
  for i in range(m):
    hq[0]=hq[0]//2
else:
  for i in range(m):
    v=heapq.heappop(hq)
    heapq.heappush(hq,((v*-1)//2)*(-1))

ans=0
for i in range(len(hq)):
  ans=ans+(-1)*heapq.heappop(hq)

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
 
N,M = map(int, input().split())
A = sorted([int(x) for x in input().split()])
 
while M > 0:
    x = A.pop(-1)
    x //= 2
    ind = bisect_left(A, x)
    M -= N - ind
    if ind < N-1:
        temp = [x] + [A[-i-1]//2 for i in range(min(M, N-1 - ind))]
        A = sorted(A[:N-len(temp)] + temp)
    else:
        A.insert(bisect_left(A, x), x)
 
print(sum(A))

Submission status: Wrong Answer

Solution code:
# ABC141-D
import heapq
n, m = [int(x) for x in input().split()]
h = [-int(x) for x in input().split()]
heapq.heapify(h)
for i in range(m):
    x = heapq.heappop(h)
    heapq.heappush(h, x//2)
z = 0
for i in h:
    z -= i
print(z)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
for i in range(m):
    a[0] /= 2
    if n > 2 and a[0] < a[2]:
        a[0], a[1], a[2] = a[1], a[2], a[0]
    elif n > 1 and a[0] < a[1]:
        a[0], a[1] = a[1], a[0]
ans = [i//1 for i in a]
print(int(sum(ans)))

Submission status: Wrong Answer

Solution code:
import math

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

L = sorted(L,reverse=True)


while M > 0:
	L[0] = int(math.floor(L[0] / 2))
	L = sorted(L,reverse=True)
	for i in range(1,N):
		if L[i] < L[0]:
			p = L[0]
			L[0] = L[i-1]
			L[i-1] = p
	M -= 1
	
print(sum(L))

Submission status: Wrong Answer

Solution code:
import math

N, M = list(map(int, input().split()))
A = sorted(list(map(lambda x: int(x), input().split(' '))), reverse=True)


while True:
    if len(A) > 1:
        A_set = sorted(list(set(A)), reverse=True)
        if len(A_set) > 1:
            curr_max = math.ceil((A_set[0] / A_set[1])/2)
        else:
            curr_max = A_set[0]
        can_use = min([curr_max, M])
    else:
        can_use = M
    A[0] = A[0] // (2 ** can_use)
    M -= can_use
    if M == 0:
        break
    
    for i in range(N-1):
        if A[i] < A[i+1]:
            A[i+1], A[i] = A[i:i+2]
        else:
            break

print('{}'.format(sum(A)))

Submission status: Wrong Answer

Solution code:
import bisect
 
N, M = map(int, input().split(" "))
As = [0]+list(map(int, input().split(" ")))
As.sort()
cnt = 0
cnt2 = 1
for _ in range(M):
  i = As[-1+cnt]  
  i = i>>cnt2
  if i < As[-1+cnt-1]:
    cnt -= 1
    cnt2 = 1
    bisect.insort_left(As,i)
  else:
    cnt2 += 1

if i >= As[-1+cnt-1]:
  cnt -= 1
  bisect.insort_left(As,i)
  
print(sum(As[:cnt]))

Submission status: Wrong Answer

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

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

print(sum(A))

Submission status: Wrong Answer

Solution code:

from decimal import *

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

B = [A.pop()]
j = 0
b = 1

for m in range(M):
    
    if A == []:
        B[j] /= 2
        j = (j+1)%b
    elif B[j] > A[-1]:
        B[j] /= 2
        j = (j+1)%b
    else:
        B.append(A.pop()/2)
        b += 1
        

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

Submission status: Wrong Answer

Solution code:

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

B = [A.pop()]
j = 0
b = 1

for m in range(M):
    
    if A == []:
        B[j] /= 2
        j = (j+1)%b
    elif B[j] > A[-1]:
        B[j] /= 2
        j = (j+1)%b
    else:
        B.append(A.pop()/2)
        b += 1
        

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

Submission status: Wrong Answer

Solution code:

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

B = [A.pop()]
j = 0
b = 1

for m in range(M):
    
    if A == []:
        B[j] /= 2
        j = (j+1)%b
    elif B[j] > A[-1]:
        B[j] /= 2
        j = (j+1)%b
    else:
        B.append(A.pop()/2)
        b += 1
        

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

Submission status: Wrong Answer

Solution code:
import sys
from bisect import insort_left
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    a = [int(i) for i in input().split()]
    for _ in range(m):
        b = a.pop()//2
        insort_left(a, b)
    print(sum(a))


main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import insort_left
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    a = [int(i) for i in input().split()]
    for i in range(m):
        b = a.pop()//2
        insort_left(a, b)
    print(sum(a))


main()

Submission status: Wrong Answer

Solution code:
# Y 割引券の枚数
# 割引 = x / 2 ** Y
import math

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


for i in range(M):
    prices[prices.index(max(prices))] = prices[prices.index(max(prices))] / 2
    # print(prices[i])
    # prices[i] / 2 ** Y

print(math.floor(sum(prices)))

Submission status: Wrong Answer

Solution code:
import heapq as hq

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

arr = [-i for i in list(map(int,input().split()))]
hq.heapify(arr)

for i in range(m):
    arr[0] = -1*(-1*arr[0]//2)
    hq.heapify(arr)

    
print(sum(arr))

Submission status: Wrong Answer

Solution code:
import heapq

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

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

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





print(sum(A)*-1)

Submission status: Wrong Answer

Solution code:

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

B = [A.pop()]
j = 0
b = 1

for m in range(M):
    
    if A == []:
        B[j] //= 2
        j = (j+1)%b
    elif B[j] > A[-1]:
        B[j] //= 2
        j = (j+1)%b
    else:
        B.append(A.pop()//2)
        b += 1
            
print(sum(A + B))

Submission status: Wrong Answer

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 _ in range(m):
  p=-heapq.heappop(q)//2
  print(p)
  heapq.heappush(q,-p)
print(-sum(q))

Submission status: Wrong Answer

Solution code:
N, M, *A, = map(int, open(0).read().split())
A.sort(reverse=True)
Amae = A[:M]
Aushiro = A[M:]
print(Amae)
print(Aushiro)
for _ in range(M):
    Amae[0] = Amae[0] // 2
    Amae.sort(reverse=True)
print(sum(Amae) + sum(Aushiro))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
cnt = 0
if n == 1:
    a[0] //= 2**m
elif n == 2:
    while m > 0:
        a[0] //= 2
        m-= 1
        if a[0] < a[1]:
            a[0],a[1] = a[1],a[0]
else:
    while m > 0:
        a[0] //= 2
        m -= 1
        for i in range(n-1):
            if a[0] < a[i]:
                a.insert(0,a.pop(i))
                cnt = i
                break
            elif a[cnt+1] < a[0]:
                break
print(sum(a))

Submission status: Wrong Answer

Solution code:

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

B = [A.pop()]
j = 0
b = 1

for m in range(M):
    
    if A == []:
        B[j] //= 2
        j = (j+1)%b
    elif B[j] > A[-1]:
        B[j] //= 2
        j = (j+1)%b
    else:
        B.append(A.pop()//2)
        b += 1
        j=0
            
print(sum(A + B))

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
        self.same = 1

class BST:
    def __init__(self):
        self.root = None
    
    def insert(self,data):
        n = self.root
        if n == None:
            self.root = Node(data)
            return
        else:
            while True:
                if n.data > data:
                    if n.left is None:
                        n.left = Node(data)
                        return
                    n = n.left
                elif n.data < data:
                    if n.right is None:
                        n.right = Node(data)
                        return
                    n = n.right
                elif n.data == data:
                    n.same += 1
                    return
    
    def delete_max(self):
        n = self.root
        while True:
            if n.right == None:
                break
            else:
                n = n.right
        tmp = n.data//2
        if n.same > 1:
            n.same -= 1
        else:
            if n.left == None:
                n = None
            else:
                n.data = n.left.data
                n.left = None

        self.insert(tmp)
    
    def sum_bst(self,node):
        if node.left == None and node.right == None:
            return node.data*node.same
        else:
            s = node.data*node.same
            if node.left != None:
                s += self.sum_bst(node.left)
            if node.right != None:
                s += self.sum_bst(node.right)
            return s

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

bst = BST()
for a in list(map(int,input().split())):
    bst.insert(a)
for i in range(M):
    bst.delete_max()
print(bst.sum_bst(bst.root))

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
        self.same = 1

class BST:
    def __init__(self):
        self.root = None
    
    def insert(self,data):
        n = self.root
        if n == None:
            self.root = Node(data)
            return
        else:
            while True:
                if n.data > data:
                    if n.left is None:
                        n.left = Node(data)
                        return
                    n = n.left
                elif n.data < data:
                    if n.right is None:
                        n.right = Node(data)
                        return
                    n = n.right
                elif n.data == data:
                    n.same += 1
                    return
    
    def delete_max(self):
        n = self.root
        while True:
            if n.right == None:
                break
            else:
                n = n.right
        tmp = n.data//2
        if n.same > 1:
            n.same -= 1
        else:
            if n.left == None:
                n = None
            else:
                n.data = n.left.data
                n.left = None

        self.insert(tmp)
    
    def sum_bst(self,node):
        if node.left == None and node.right == None:
            return node.data*node.same
        else:
            s = node.data*node.same
            if node.left != None:
                s += self.sum_bst(node.left)
            if node.right != None:
                s += self.sum_bst(node.right)
            return s

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

bst = BST()
for a in list(map(int,input().split())):
    bst.insert(a)
print(bst.sum_bst(bst.root))
for i in range(M):
    bst.delete_max()
print(bst.sum_bst(bst.root))

Submission status: Wrong Answer

Solution code:
import heapq

n, m = map(int, input().split())
prices = [-int(p) for p in input().split()]
heapq.heapify(prices)
for _ in range(m):
    p = heapq.heappop(prices) // 2
    heapq.heappush(prices, p)
print(-sum(prices))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

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

for _ in range(m):
    max_i = prices.argmax()
    prices[max_i] = prices[max_i] / 2

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

Submission status: Wrong Answer

Solution code:
N, M, *A, = map(int, open(0).read().split())
A.sort(reverse=True)
Amae = A[:100000]
Aushiro = A[100000:]
for _ in range(M):
    a = A.index(max(A))
    A[a] = A[a] // 2
print(sum(Amae) + sum(Aushiro))

Submission status: Wrong Answer

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


for _ in range(M):
  if len(A)>1:
  	if A[0] < A[1]:
  	  A = sorted(A,reverse=True)
  A[0] = A[0] // 2
print(sum(A))

Submission status: Wrong Answer

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):
    x = heapq.heappop(A)
    if x == 0:
        break
    x = x // 2
    heapq.heappush(A, x)  # pop minimum
print(-sum(A))

Submission status: Wrong Answer

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

B = [A.pop()]
j = 1
b = 1

for m in range(M):
    
    if A == []:
        B[j-1] //= 2
        j = (j+1)%b
    elif B[j-1] > A[-1]:
        B[j-1] //= 2
        j = (j+1)%b
    else:
        B.append(A.pop()//2)
        b += 1
        j=1
            
print(sum(A + B))

Submission status: Wrong Answer

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


def main():
    n, m = map(int, input().split())

    if n == 1:
        a = int(input())
        for i in range(m):
            a //= 2
        print(a)
        exit()

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

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

    a = [-1 * i for i in a]
    print(sum(a))

Submission status: Wrong Answer

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

A.sort()
A.reverse()
if N == 1:
    total_price += A[N-1]//(2**M)
else:    
    for i in range(N-1):
        if 0 < M:
            y = 0
            tmp = A[i]
            while True:
                if M == 0:
                    break
                elif M == 1 and A[i] < A[i+1]:
                    break
                elif 1 < M and  A[i+1]/2+A[i+1]/4 > A[i]/2+A[i+1]/2:
                    break
                A[i] = A[i]/2
                y += 1
                M -= 1
            total_price += tmp//(2**y)
        else:
            total_price += A[i]
    total_price += A[N-1]//(2**M)

print(total_price)

Submission status: Wrong Answer

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


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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq

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

a = [- int(i) for i in input().split(" ")]
heapq.heapify(a)

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

print(- sum(a))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

import numpy as np

def main():
    n, m = map(int, input().split())
    a = np.array([int(i) for i in input().split()])
    a.sort()

    while True:
        temp = a[-1]//2
        a[-1] = temp
        a.sort()
        ind = np.where(a==temp)[0][0]
        m -= 1
        if m == 0:
            print(np.sum(a))
            break
        elif n - ind < m:
            a[ind:] = a[ind:]//2
            a.sort()
            m = m - (n-ind)
            if m>0:
                pass
            else:
                print(np.sum(a))
                break
        else:
            a[min(-m,-n):] = a[min(-m,-n):]//2
            print(np.sum(a))
            break

main()

Submission status: Wrong Answer

Solution code:
import numpy as np
n = list(map(int,input().split()))
a = np.array(list(map(int,input().split())))
print(a)
for i in range(n[1]):
    a[a.argmax()] = a[a.argmax()]//2 
print(np.sum(a))

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
N,M=map(int,input().split())
A=np.array(list(map(int,input().split())))
print(A)
while M>0:
    M-=1
    A[A.argmax()]/=2
ans=0
for a in A:
    ans+=math.floor(a)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import heapq

N, M = map(int, input().split())
A = list(map(lambda x:[-int(x),int(x)], input().split()))
heapq.heapify(A)

for m in range(M):
  x = heapq.heappop(A)
  x[1] //= 2
  x[0] = -x[1]
  heapq.heappush(A, x)
  if x[1] < 1:
    break
ans = 0
for a in A:
  ans += a[1]
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

N, M = map(int, input().split(" "))
As = [0]+list(map(int, input().split(" ")))
As = sorted(As)
cnt = 0
j = 0
for _ in range(M):
  if j >= As[-1-cnt]:
    i = j>>1
  else:
    i = As[-1-cnt]>>1
    
  j = i
  
  if i < As[-1-cnt-1]:
    cnt += 1
    bisect.insort_left(As,i)

print(sum(As[:-cnt]))

Submission status: Wrong Answer

Solution code:
from sys import stdin
import heapq


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    As = []
    for i in [int(x) for x in stdin.readline().rstrip().split()]:
        heapq.heappush(As, i)
    for _ in range(M):
        x = heapq.heappop(As)
        heapq.heappush(As, x // 2)
    print(sum([int(x) for x in As]))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
prices = list(map(int,input().split()))
prices.sort(reverse=True)
for _ in range(M):
    price = prices.pop(0) // 2
    if len(prices) == 0:
        prices.append(price)
    elif prices[-1] > price:
        prices.append(price)
    else:
        for i in range(len(prices)):
            if prices[i] < price:
                prices.insert(i,price)
                break
print(sum(prices))

Submission status: Wrong Answer

Solution code:
# 他参加者の回答を参考にした．現在のAtcoderでのpythonのバージョンではdequeにinsertできないので（全ての値に-1をかけて）heapqがよさそう？
import bisect
N, M = map(int, input().split())
B = [int(x) for x in input().split()]
A = sorted(B, reverse=True)
ite = 0
for i in range(M):
    A[ite] //= 2
    if ite < N - 1:
        if A[ite] < A[ite + 1] and A[0] < A[ite+1]:
            ite += 1
        else:
            A = sorted(A, reverse=True)
            ite = 0

ans = sum(A)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import heapq


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    As = []
    for i in [int(x) for x in stdin.readline().rstrip().split()]:
        heapq.heappush(As, i)
    for _ in range(M):
        x = heapq.heappop(As)
        heapq.heappush(As, x / 2)
    print(sum([int(x) for x in As]))


if __name__ == "__main__":
    main()