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):
class Heap:

    
    def __init__(self):
        self.array = []

    def num(self):
        return len(self.array)
        
    
    def put(self, val):
        pos = len(self.array)
        
        self.array.append(val)
        
        self.pop_up(pos)
        
    
    def get(self):
        assert len(self.array) > 0

        val = self.array[0]
        
        
        t_val = self.array[-1]
        self.array[0] = t_val
        del self.array[-1]
        self.push_down(0)
        return val

    
    def pop_up(self, pos):
        while pos > 0:
            p_pos = (pos - 1) // 2
            val = self.array[pos]
            p_val = self.array[p_pos]
        
            if val > p_val:
                self.array[pos] = p_val
                self.array[p_pos] = val
                pos = p_pos
            else:
                break
            
    def push_down(self, pos):
        while True:
            l_pos = 2 * pos + 1
            r_pos = 2 * pos + 2
            n = len(self.array)
            
            if n <= l_pos:
                
                break
            
            elif n == r_pos:
                
                val = self.array[pos]
                l_val = self.array[l_pos]
                
                if val < l_val:
                    self.array[pos] = l_val
                    self.array[l_pos] = val
                    
                break #
            
            else:
                
                val = self.array[pos]
                l_val = self.array[l_pos]
                r_val = self.array[r_pos]
                
                if l_val > r_val:
                    if val < l_val:
                        self.array[pos] = l_val
                        self.array[l_pos] = val
                        pos = l_pos
                    else:
                        break
                else:
                    if val < r_val:
                        self.array[pos] = r_val
                        self.array[r_pos] = val
                        pos = r_pos
                    else:
                        break

                        
h = Heap()
sn,sm = input().split(" ")
n = int(sn)
m = int(sm)
sa_list = input().split(" ")
l = len(sa)

for sa in sa_list:
  a = int(sa)  
  h.put(a)
 
for i in range(m):  
    max_a = h.get()
    h.put(max_a // 2)

    

print(sum(h.array))


class Heap:

    
    def __init__(self):
        self.array = []

    def num(self):
        return len(self.array)
        
    
    def put(self, val):
        pos = len(self.array)
        
        self.array.append(val)
        
        self.pop_up(pos)
        
    
    def get(self):
        assert len(self.array) > 0

        val = self.array[0]
        
        
        t_val = self.array[-1]
        self.array[0] = t_val
        del self.array[-1]
        self.push_down(0)
        return val

    
    def pop_up(self, pos):
        while pos > 0:
            p_pos = (pos - 1) // 2
            val = self.array[pos]
            p_val = self.array[p_pos]
        
            if val > p_val:
                self.array[pos] = p_val
                self.array[p_pos] = val
                pos = p_pos
            else:
                break
            
    def push_down(self, pos):
        while True:
            l_pos = 2 * pos + 1
            r_pos = 2 * pos + 2
            n = len(self.array)
            
            if n <= l_pos:
                
                break
            
            elif n == r_pos:
                
                val = self.array[pos]
                l_val = self.array[l_pos]
                
                if val < l_val:
                    self.array[pos] = l_val
                    self.array[l_pos] = val
                    
                break #
            
            else:
                
                val = self.array[pos]
                l_val = self.array[l_pos]
                r_val = self.array[r_pos]
                
                if l_val > r_val:
                    if val < l_val:
                        self.array[pos] = l_val
                        self.array[l_pos] = val
                        pos = l_pos
                    else:
                        break
                else:
                    if val < r_val:
                        self.array[pos] = r_val
                        self.array[r_pos] = val
                        pos = r_pos
                    else:
                        break

                        
h = heap()
sn,sm = input().split(" ")
n = int(sn)
m = int(sm)
sa_list = input().split(" ")
l = len(sa)

for sa in sa_list:
  a = int(sa)  
  h.put(a)
 
for i in range(m):  
    max_a = h.get()
    h.put(max_a // 2)

    

print(sum(h.array))


sn,sm = input().split(" ")
n = int(sn)
m = int(sm)
a = input().split(" ")
l = len(sa)

 
for i in range(l):
  a[i] = int a[i]
  
for i in range(m):  
  ind = a.index(max(a))
  a[ind] = a[ind] //2
  
print(sum(a))

class Heap:

    
    def __init__(self):
        self.array = []

    def num(self):
        return len(self.array)
        
    
    def put(self, val):
        pos = len(self.array)
        
        self.array.append(val)
        
        self.pop_up(pos)
        
    
    def get(self):
        assert len(self.array) > 0

        val = self.array[0]
        
        
        t_val = self.array[-1]
        self.array[0] = t_val
        del self.array[-1]
        self.push_down(0)
        return val

    
    def pop_up(self, pos):
        while pos > 0:
            p_pos = (pos - 1) // 2
            val = self.array[pos]
            p_val = self.array[p_pos]
        
            if val > p_val:
                self.array[pos] = p_val
                self.array[p_pos] = val
                pos = p_pos
            else:
                break
            
    def push_down(self, pos):
        while True:
            l_pos = 2 * pos + 1
            r_pos = 2 * pos + 2
            n = len(self.array)
            
            if n <= l_pos:
                
                break
            
            elif n == r_pos:
                
                val = self.array[pos]
                l_val = self.array[l_pos]
                
                if val < l_val:
                    self.array[pos] = l_val
                    self.array[l_pos] = val
                    
                break #
            
            else:
                
                val = self.array[pos]
                l_val = self.array[l_pos]
                r_val = self.array[r_pos]
                
                if l_val > r_val:
                    if val < l_val:
                        self.array[pos] = l_val
                        self.array[l_pos] = val
                        pos = l_pos
                    else:
                        break
                else:
                    if val < r_val:
                        self.array[pos] = r_val
                        self.array[r_pos] = val
                        pos = r_pos
                    else:
                        break

                        
h = Heap()
sn,sm = input().split(" ")
n = int(sn)
m = int(sm)
sa_list = input().split(" ")


for sa in sa_list:
  a = int(sa)  
  h.put(a)
 
for i in range(m):  
    max_a = h.get()
    h.put(max_a // 2)

    

print(sum(h.array))


Verdicts: Runtime Error

Runtime Error

Runtime Error

Accepted