Problem p02912 (python)

Fixed submission:
#141d
from collections import deque
import bisect
import math

N,M = map(int, input().split()) #1≤N,M≤10^5
A_list = list(map(int, input().split()))

#→高額なものに割引券を使った方が良い
if len(A_list) > 1:
    A_list.sort(reverse=False)
    highest = A_list.pop()
    next_highest = A_list[-1]

    discounted_deque = deque()

    while 1:
        use_tickets = math.ceil(math.log(highest/next_highest)/math.log(2))
        if use_tickets == 0:
            use_tickets = 1
        elif use_tickets > M:
            use_tickets = M
            
        highest /= pow(2,use_tickets)
        M -= use_tickets
        
        if M!= 0:
            discounted_deque.appendleft(highest)
            
            if len(A_list) > 0:
                if A_list[-1] > discounted_deque[-1]:
                    highest = A_list.pop()
                else:
                    highest = discounted_deque.pop()
            else:
                highest = discounted_deque.pop()
                
            if len(A_list) > 0 and len(discounted_deque) > 0:
                if A_list[-1] > discounted_deque[-1]:
                    next_highest = A_list[-1]
                else:
                    next_highest = discounted_deque[-1]
            elif len(A_list) == 0 and len(discounted_deque) > 0:
                next_highest = discounted_deque[-1]
            elif len(A_list) > 0 and len(discounted_deque) == 0:
                next_highest = A_list[-1]
            
        else:
            A_list.append(highest)
            break

    A_list = [int(A) for A in A_list]
    discounted_list = [int(B) for B in discounted_deque]
    
    print(sum(A_list)+sum(discounted_list))
else:
    A_list[-1] = A_list[-1]//(pow(2,M))
    print(A_list[-1])

Buggy submission (verdict: Runtime Error):
#141d
from collections import deque
import bisect
import math

N,M = map(int, input().split()) #1≤N,M≤10^5
A_list = list(map(int, input().split()))

#→高額なものに割引券を使った方が良い
if len(A_list)>1:
    A_list.sort(reverse=False)
    highest = A_list.pop()
    next_highest = A_list[-1]

    while 1:
        #print(A_list,highest)
        
        #highest/(pow(2,X)) <= next_highest に持っていきたい
        #highest <= next_highest * pow(2,X)
        #highest/next_highest <= 2**X
        #log2(highest/next_highest) <= X
        use_tickets = math.ceil(math.log2(highest/next_highest))
        if use_tickets == 0:
            use_tickets = 1
        if use_tickets > M:
            use_tickets = M
        highest /= pow(2,use_tickets)
        M -= use_tickets
        
        #print(A_list,highest)
        
        if M!= 0:
            bisect.insort(A_list,highest)
            highest = A_list.pop()
            next_highest = A_list[-1]
        else:
            A_list.append(highest)
            break

    A_list = [int(A) for A in A_list]
    print(sum(A_list))
else:
    A_list[-1] = A_list[-1]//(pow(2,M))
    print(A_list[-1])

Buggy submission (verdict: Runtime Error):
#141d
from collections import deque

N,M = map(int, input().split()) #1≤N,M≤10^5
A = list(map(int, input().split()))
A.sort()
discounted = deque()
#高橋くんは N 個の品物を 1個ずつ順番に買う予定です。
#i番目に買う品物の値段は Ai円です。
#高橋くんは M枚の割引券を持っています。品物を買う際に割引券を好きな枚数使うことができます。
#X円の品物を買う際に Y 枚の割引券を使った場合、その品物を X/(2^Y)円(小数点以下切り捨て)で買うことができます。
#最小で何円あれば全ての品物を買うことができるでしょうか。

#→高額なものに割引券を使った方が良い

highest = A.pop(-1)
discounted.append(highest/2)

for i in range(M-1):
    if len(A)>0:
        if discounted[0] > A[-1]:
            discounted.append((discounted.popleft())/2)
        else:
            discounted.append((A.pop(-1))/2)
    else:
        discounted.append((discounted.popleft())/2)

discounted = [math.floor(discounted_price) for discounted_price in list(discounted)]

print(sum(A)+sum(discounted))