Problem: 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?

Submission attempts (in order):
def bin_tree( 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])



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

print(A)

while M > 0:
    M -= 1
    pri = A.pop( N - 1 )
    pri = pri // 2

    ans = bin_tree( pri , A , N - 1 ) + 1
    
    A[ans:ans] = [pri]

    print(A)
    

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

def bin_tree( pri , li_pri , len_li ):
    
    
    
    lo = 0
    hi = len_li - 1
    while hi - lo > 1:
        mid = (lo + hi) // 2
        guess = li_pri[mid]
        if guess == pri:
            hi = mid
        if guess > pri:
            hi = mid
        else:
            lo = mid
    return lo

I = input().split()
N = int(I[0])
M = int(I[1])



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

print(A)

while M > 0:
    M -= 1
    pri = A.pop( N - 1 )
    pri = pri // 2
    if ( pri < A[0] ):
        ans = 0
    else :
        ans = bin_tree( pri , A , N - 1 ) + 1
    A[ans:ans] = [pri]

    print(A)
    

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

def bin_tree( 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])



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

print(A)

while M > 0:
    M -= 1
    pri = A.pop( N - 1 )
    pri = pri // 2

    ans = bin_tree( pri , A , N - 1 ) + 1
    
    A[ans:ans] = [pri]

    print(A)
    

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

def bin_tree( 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])



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

print(A)

while M > 0:
    M -= 1
    pri = A.pop( N - 1 )
    pri = pri // 2
    if ( pri < A[0] ):
        ans = 0
    else:
        ans = bin_tree( pri , A , N - 1 )
    A[ans:ans] = [pri]

    print(A)
    

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

def bin_tree( 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])



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

print(A)

while M > 0:
    M -= 1
    pri = A.pop( N - 1 )
    pri = pri // 2

    ans = bin_tree( pri , A , N - 1 )
    A[ans:ans] = [pri]

    print(A)
    

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

import heapq

I = input().split()
N = int(I[0])
M = int(I[1])



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 )

Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted