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: Runtime Error

Solution code:
N, M = map(int,input().split())
A = list(map(int,input().split()))
if N == 1:
    while A[0] > 0:
        A[0] = A[0]//2
    print(0)
    sys.exit()

list.sort(A,reverse = True)
for i in range(M):
    while A[0] >= A[1]:
        A[0] = A[0]//2
    for i in range(0,M-1):
        if A[i] < A[i+1]:
            A[i] , A[i+1] = A[i+1] , A[i]

print(sum(A))

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = map(int, input().split())
a = [int(i) for i in input().split(" ")]
a = np.sort(a)
b = np.log2(a)
if np.sum(b//1)+n < m:
    print(0)
else:
    t = b.copy()
    c = m
    ind = n-1
    while c>0:
        if b[ind] == b[ind-1]:
            ind -= 1
            if ind == 1:
                for i in range(int(c)):
                    b[b.argmax()] -= 1
                c = 0
            continue
                
        if (b[ind] - b[ind-1] + 1)//1*(n-ind) <= c:
            c -= (b[ind] - b[ind-1] + 1)//1*(n-ind)
            b[ind:] -= (b[ind] - b[ind-1] + 1)//1
            ind -= 1
        else:
            for i in range(int(c)):
                b[b.argmax()] -= 1
            c = 0
    tm = [2**int(i) for i in t-b]
    print(int(np.sum(np.array(a, dtype="object")/tm//1)))

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = map(int, input().split())
a = [int(i) for i in input().split(" ")]
a = np.sort(a)
b = np.log2(a)
if np.sum(b//1)+n < m:
    print(0)
else:
    t = b.copy()
    c = m
    ind = n-1
    while c>0:
        if b[ind] == b[ind-1]:
            ind -= 1
            if ind == 1:
                for i in range(int(c)):
                    b[b.argmax()] -= 1
                c = 0
                
        if (b[ind] - b[ind-1] + 1)//1*(n-ind) <= c:
            c -= (b[ind] - b[ind-1] + 1)//1*(n-ind)
            b[ind:] -= (b[ind] - b[ind-1] + 1)//1
            ind -= 1
        else:
            for i in range(int(c)):
                b[b.argmax()] -= 1
            c = 0
    tm = [2**int(i) for i in t-b]
    print(int(np.sum(np.array(a, dtype="object")/tm//1)))

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;
 
int main() {
    int n, m;
    cin >> n >> m;
 
    int s = 0;
    priority_queue <int> pq;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
 
        s += a;
        pq.push(a);
    }

    // 引換券の数だけ繰り返す
    for (int i = 0; i < m; i++) {
        int a = pq.top(); pq.pop();
        pq.push(a / 2);
        s += a / 2 - a;
    }
 
    cout << s << endl;
 
    return 0;
}

Submission status: Runtime Error

Solution code:
import heapq
I = list(map(int,input().split()))
N = I[0]
M = I[1]
A = list(map(lambda x:-x,map(int,input().split())))
heapq.heapify(A)
for i in range(M):
    num = heapq.heappop(A)
    num = math.ceil(num / 2)
    heapq.heappush(A,num)

print(-sum(A))

Submission status: Runtime Error

Solution code:
I = list(map(int,input().split()))
N = I[0]
M = I[1]
A = list(map(int,input().split()))

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

B = map(int,A)
ans = sum(B)
print(ans)

Submission status: Runtime Error

Solution code:
I = list(map(int,input().split()))
N = I[0]
M = I[1]
A = list(map(int,input().split()))

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

A = map(int,A)
ans = sum(A)
print(ans)

Submission status: Runtime Error

Solution code:
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
A = inpl()
A.sort(reverse=True)
L = list(map(lambda a: len(bin(a)-2),A))
L.append(0)
l = L[0]
P = []
D = []
for i in range(1,N):
    if L[i] == l:
        continue
    elif i > M:
        break
    else:
        d = L[i] - l
        r = M // i
        if d < r:
            P.append(i)
            D.append(d)
            M -= d*i
        else:
            P.append(i)
            D.append(r)
            M -= r*i
            break
c = 0
E = [0]
for dd in D:
    E.append(E[-1]+dd)
i = 0
for n in range(len(P)):
    while i < P[n]:
        A[i] <<= E[-i-1]
        i += 1
A.sort(reverse=True)
for m in range(M):
    A[m] <<= 1

print(sum(A))

Submission status: Runtime Error

Solution code:
n,m = [int(s) for s in input().split()]
price = [int(s) for s in input().split()]
price.sort()
for i in range(m):
  price[0] /= 2
  price.sort()

answer = 0
for i in range(price):
  answer += int(price)
print(answer)

Submission status: Runtime Error

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

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

for cnt in range(m):
    temp = heapq.heappop(a)*(-1)
    if temp == 0:
        break
    heapq.heappush(a, (temp//2)*(-1))

print(sum(a)*(-1))

Submission status: Runtime Error

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

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

for cnt in range(m):
    temp = heapq.heappop(a)*(-1)
    if temp == 0:
        break
    heapq.heappush(a, (temp//2)*(-1))

print(sum(a))

Submission status: Runtime Error

Solution code:
import heapq

mnum, gnum = map(int, input().split())
array = list(map(lambda a: -int(a), input().split()))

array.sort()
heapq.heapify(array)

for i in range(gnum):
	temp = heapq.heappop(array)
	temp /= 2.0
	heapq.heappush(array, temp)
    
amount = 0
for a in array:
  amount += math.floor(-a)
print(amount)

Submission status: Runtime Error

Solution code:
import heapq

mnum, gnum = map(int, input().split())
array = list(map(lambda a: -int(a), input().split()))

array.sort()
heapq.heapify(array)

for i in range(gnum):
	temp = heapq.heappop(array)
	temp = temp/2
	heapq.heappush(array, temp)
    
amount = 0
for a in array:
  amount += math.floor(-a)
print(amount)

Submission status: Runtime Error

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

from heapq import heappush, heappop
hq=[]

for a_val in a:
    # heappopで最も小さい値が取り出されるため、(-1)をかけて入れる
    heappush(hq, -a)
for _ in range(m):
    heappush(hq, -(heappop(hq)*(-1))//(-2))
print(-sum(hq))

Submission status: Runtime Error

Solution code:
import heapq
n, m = map(int, input().split())
a = list(map(lambda x: int(x) * (-1), a))
heapq.heapify(a)
for _ in range(m):
    min = ((heapq.heappop(a) * (-1)) // 2) * (-1)
    heapq.heappush(a, min)
print(sum(a)*(-1))

Submission status: Runtime Error

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

# import heapq
# print(A)
heapq.heapify(A)
# print(A)
for _ in range(M):
    a = heapq.heappop(A)
#     print( "aaa",a)
    heapq.heappush(A,-1*((-1*a)//2))
#     print("AAA",A)
    
# print("list",A)

print(-1*sum(A))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

a = list(map(int, input().split()))
a.sort(reverse=True)

print(a)
i = 0
while i < m:
    a[0] = a[0] // 2
    j = 0
    while i + j + 1 < m and j < n:
        if a[j+1] < a[0]:
            break
        j = j + 1
        a[j] = a[j] // 2
    a.sort(reverse=True)
    i = i + j + 1

print(sum(a))

Submission status: Runtime Error

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

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

for _ in range(m):
	heapq._heapify_max(li) 
	x = heapq._heappop_max(li)
	heapq.heappush(li, x // 2)
print(sum(list(li)))

Submission status: Runtime Error

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)
  if l == 1:
    continue
  ain = a[1:min(l,m-i-1)]
  lin = len(ain)
  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:]

Submission status: Runtime Error

Solution code:
import bisect
import array

n, m = map(int, input().split())
a = map(int, input().split())
a = array.array("L", sorted(list(a)))
for _ in range(m):  # O(m*n)
    max_num = a.pop()  # O(1)
    index = bisect.insert(a, max_num // 2)  # O(log n)
print(sum(a))

Submission status: Runtime Error

Solution code:
import bisect
import array
 
n, m = map(int, input().split())
a = map(int, input().split())
a = array.array("L", sorted(list(a)))
for _ in range(m):  # O(m*n)
    max_num = a.pop()  # O(1)
    index = bisect.insert(a, max_num // 2)  # O(log n)
print(sum(a))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = map(int, input().split())
a = array.array("L", sorted(list(a)))
for _ in range(m):  # O(m*n)
  max_num = a.pop()  # O(1)
  index = bisect.bisect(a, max_num // 2)  # O(log n)
  a.insert(index, max_num // 2)  # O(n)
 print(sum(a))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = map(int, input().split())
a = array.array("L", sorted(list(a)))
for _ in range(m):  # O(m*n)
  max_num = a.pop()  # O(1)
  index = bisect.bisect(a, max_num // 2)  # O(log n)
  a.insert(index, max_num // 2)  # O(n)
  print(sum(a))

Submission status: Runtime Error

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()
a2 = As[-2]
N1 = int(N/10)
for _ in range(M):
    As[-1] /= 2.0
    if As[-1] < a2:
        As[-N1:].sort()

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

Submission status: Runtime Error

Solution code:
import heapq
N, M = map(int, input())
A = list(map(lambda x: int(-x), input().split()))
heapq.heapify(A)
for i in range(M):
    tmp = heapq.heappop(A[0])
    heapq.heappush(tmp // 2)
print(str(sum(A)))

Submission status: Runtime Error

Solution code:
#n:shinamono no kazu
#m:waribiki maisuu
import heapq

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

a=heaqp.heapify(list(map(lambda x : int(x)*(-1),input().split())))

for _ in range(m):
  minA=heapq.heappop(a)
  heapq.heappush(a,minA/2.0)
#print(a)
result=0
for item in a:
  result+=item*(-1)//1
  
print(int(result))

Submission status: Runtime Error

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

if N == 1:
  print (int(A[0] // 2 ** M))
  sys.exit()
while M:
  A[-1] //= 2
  if A[-1] < A[-2]:
    d = A[-1]
    b = bisect.bisect(A,d) 
    A[b+1:] = A[b:-1]
    A[b] = d
  M -= 1
print (sum(A))

Submission status: Runtime Error

Solution code:
import heapq
import sys
input = sys.stdin.readine
n, m = map(int, input().split(" "))
liste = list(map(int, input().split(" ")))
liste = [(-1 * i) for i in liste]
heapq.heapify(liste)
for i in range(m):
    maxi = heapq.heappop(liste)
    maxi /= 2
    heapq.heappush(liste, int(maxi))
liste = [(-1 * i) for i in liste]
print(sum(liste))

Submission status: Runtime Error

Solution code:
# ABC141D - Powerful Discount Tickets
from heapq import heapify, heappop, heappush


def main():
    N, M, *A = map(int, open(0).read().split())
    H = [-i for i in A]
    heapify(H)
    pop_max, push_max = lambda: -heappop(H), lambda x: heappush(-x)
    for _ in range(M):
        x = pop_max()
        push_max(x // 2)
    ans = -sum(H)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import heapq

N, M = map(int, input().split(" "))
A = [-int(_) for _ in input().split(" ")]

for i in range(M):
    print(A)
    heapq.heapify(A)
    heapq.heappush(A, -(-heapq.heappop(A)// 2))

print(-sum(A))

Submission status: Runtime Error

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]
                    pointer=next_pointer
                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)
    print(heapq)
for _ in range(m):
    heapc.heapreplace(lambda x:x>>1,heapq)
print(sum(heapq))

Submission status: Runtime Error

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

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: Runtime Error

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(hp, a[i]*(-1))

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

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

Submission status: Runtime Error

Solution code:
import math
n, m = map(int, input().split())

list1 = list(map(int,input().split()))
list1.sort()
list1.reverse()

i=0
s = math.floor(list1[0]/2)

if n==1:
    print(math.floor(list[1]/(2**m)))
    # 処理終了
    exit() 

while True:
    while True:
        if i+1 > n:
            break
        if list1[i] < s or m == 0:
            break
        list1[i] = math.floor(list1[i]/2)
        m -= 1
        i += 1
    if m==0:
        break
    list1.sort()
    list1.reverse()
    s = math.floor(list1[0]/2)
    i = 0
print(sum(list1))

Submission status: Runtime Error

Solution code:
import heapq
n,m = map(int,input().split())
a=  list(map(int,input().split()))
h = list(map(lambda x:-1*x,a))
heapq.heapify(h)
for i in range(m):
    heapq.heapreplace(h,-(-h[0]//2))
    print(h)

Submission status: Runtime Error

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

A = A.sort(reverse=True)
l = len(A)

if N>=2:
  while M>=1:
    div = A[0]//2
    
    for i in range(l):
      if A[i]>=div:
        if M>=1:
          A[i] = A[i]//2
        else:
          break
      else:
        break
 
  print(sum(A))
else:
    i=1
    while 2**(i+1)<=A[0]:
      i+=1
    if M>=i:
      print(0)
    else:
      print(A[0]//2**M)

Submission status: Runtime Error

Solution code:
import math
from heapq import heappush, heappop

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

a = list(map(int, input().split(' ')))

h = []

for i in a:
    heappush(h, -i)

for i in range(m):
    v = heappop(h)
    heappush(h, -(-v // 2))
    print(h)

print(-sum(h))

Submission status: Runtime Error

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





print(sum(A)*-1)

Submission status: Runtime Error

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):
    
    print( B)
    
    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: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[int(i) for i in input().split()]
b=sorted(a)
c=len(b)



for i in range(0,m):
    b[-1] = b[-1] // 2
    if c != 1:
        if b[-1] < b[-2]:
            b[-1],b[-2] = b[-2],[-1]
            if c!= 2:
                if b[-1] < b[-3]:
                    b.sort()

print(sum(b))

Submission status: Runtime Error

Solution code:
import sys
input= sys.stdin.readline
N, M = map(int,input().split())
 
A= list(map(int,input().split()))
 
A.sort(reverse=True)
cnt = 1
A[0]=A[0]//2
 
if N==1:
    while A[0]>0 and cnt<M:
        cnt+=1
        A[0]=A[0]//2
else:
    while cnt<M:
        c=min(M-cnt,int(math.log2(A[0]/A[1])+1))
        cnt+=c
        A[0]=A[0]//(2**c)
          
        b=A[0]
        A.sort(reverse=True)
    
print(sum(A))

Submission status: Runtime Error

Solution code:
import heapq

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

Submission status: Runtime Error

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

# %%
A = list(map(lambda x: int(x), input().split(' ')))
A.sort()
A = A[::-1]

for _ in range(M):
    A[0] = A[0] // 2
    for i in range(N):
        if A[i+1] > A[i]:
            A[i+1], A[i] = A[i:i+2]
        else:
            break
    
print('{}'.format(sum(A)))

Submission status: Runtime Error

Solution code:
import numpy as np


n,m = map(int,input().split())
a = np.array(list(map(int,input().split())))
for i in range(m):
    a[a.argmax()] = a[a.argmax()]//2 
print(np.sum(a))

Submission status: Runtime Error

Solution code:
import bisect

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

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

Submission status: Runtime Error

Solution code:
import bisect
import array

n, m = map(int, input().split())
a = map(int, input().split())
a = array.array("Q", sorted(list(a)))
for _ in range(m):
    max_num = a.pop()
    i = bisect.bisect_left(a, max_num // 2)
    if i != n - 1:
        a[i + 1:] = a[i:]
    a[i] = max_num // 2
print(sum(a))

Submission status: Runtime Error

Solution code:
import heapq
N, M = [int(_) for _ in input().split()]
A = [-int(_) for _ in input().split()]

heapq.heapify(A)

for _ in range(M):
    a = heapq.heappop(A)
    heapq.heappush(A, -(-a//2))
    print(A)
    if sum(A) == 0:
        break
    
print(-sum(A))

Submission status: Runtime Error

Solution code:
import heapq

n, m = map(int, input().split())
prices = [int(p) for p in input().split()]
heapq._heapify_max(prices)
for _ in range(m):
    p = heapq._heappop_max(prices) // 2
    prices.append(p)
    heapq._siftdown_max(prices, 0, n - 1)
print(sum(prices))

Submission status: Runtime Error

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: Runtime Error

Solution code:
import bisect
import array

n, m = map(int, input().split())
a = map(int, input().split())
a = array.array("L", sorted(list(a)))
for _ in range(m):
    max_num = a.pop()
    i = bisect.bisect_left(a, max_num // 2)
    if i != n - 1:
        a[i + 1:] = a[i:]
    a[i] = max_num // 2
print(sum(a))

Submission status: Runtime Error

Solution code:
import bisect

N, M = map(int, input().split(" "))
As = 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)

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
import bisect

N, M = map(int, input().split(" "))
As = 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)

if j > As[-1-cnt-1]:
  bisect.insort_left(As,j)

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

Submission status: Runtime Error

Solution code:
import bisect
import array

n, m = map(int, input().split())
a = map(int, input().split())
a = array.array("L", sorted(list(a)))
for _ in range(m):
    max_num = a.pop()
    i = bisect.bisect(a, max_num // 2)
    a[i + 1:] = a[i:]
    a[i] = max_num // 2
print(sum(a))

Submission status: Runtime Error

Solution code:
import heapq

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

Submission status: Runtime Error

Solution code:
#include<vector>
#include<iostream>
#include<queue>

using ll = long long;
using namespace std;

int N, M;

int main(void) {

    cin >> N >> M;
    priority_queue<int, vector<int>> q;

    int tmp;
    for (int i = 0; i < N; ++i) {
        cin >> tmp;
        q.push(tmp);
    }

    while(M--){
        int t = q.top();
        q.pop();
        q.push(t/2);
    }

    ll ans = 0;
    while(!q.empty()) {
        ans += q.top();
        q.pop();
    }

    cout << ans << endl;

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort(reverse=True)

if n > 1:
    a.append(0)
    biggest = a[0]
    now = 0
    while m > 0:
        a[now] = a[now]//2
        m -= 1
        biggest = a[0]
        for i in range(n-1):
            if a[i+1] >= biggest and m > 0:
                a[i+1] = a[i+1]//2
                m -= 1
            else:
                a.sort(reverse=True)
                break
    else:
        break

else:
  for j in range(m):
    a[0] //= 2

print(sum(a))

Submission status: Runtime Error

Solution code:
import bisect
import math

n,m = map(int,input().split())
a = [int(i) for i in input().split()]

a.sort(reverse=True)

ans=[math.ceil(-a[0]/2)]
num = 0
now = 1

if n == 1:
    print(a[0] // 2**m)
    exit()
    
for i in range(m-1):
    #print(ans[0],a[now],now,ans)
    if now >= n:
        tmp = math.ceil(ans[0] / 2)
        idx = bisect.bisect_right(ans,tmp)
        #print(ans,idx,tmp)
        ans.insert(idx,tmp)
        del ans[0]
    if ans[0] <= -a[now]:
        tmp = math.ceil(ans[0] / 2)
        idx = bisect.bisect_right(ans,tmp)
        #print(ans,idx,tmp)
        ans.insert(idx,tmp)
        del ans[0]
    else:
        ans.append(math.ceil(-a[now]/2))
        now += 1
#print(ans,ans,ans,ans)
        
if len(ans) == len(a):
    print(-sum(ans))
    exit()
        
print(-sum(ans)+sum(a[len(ans):]))
exit()
for i in range(1,n):
 if num >= m:
   break
 if -a[i]>=ans[-1]: #i番目の要素がansの最小値以下であればansに付け加える
   ans.append(-a[i]//2)
   num+=1
 else:
   pos=bisect.bisect_right(ans,-a[i]) #i番目の要素以下の値で、最も大きい値の位置を求める
   ans[pos]=-a[i] #その位置の値をi番目の要素と置き換える

print(ans)
print(-sum(ans))
exit()

a = [-a]
print(a)
exit()

tmp = a[0] // 2

del a[0]

idx = bisect.bisect_right(a,tmp)
a.insert(idx,tmp)
print(a,idx)
exit()

if a[0] >= a[1]:
    a[0] = a[0] // 2
else:
    a[1] = a[1] // 2
    
print(a)

Submission status: Runtime Error

Solution code:
obj = input().strip().split(' ')
N, M = map(int, obj)

obj = input().strip().split(' ')
val_list = [-1 * item for item in list(map(int, obj))]

heapify(val_list)

for _ in range(M):
    val = (-1) * ((heappop(val_list) * (-1)) // 2)
    heappush(val_list, val)

print(-1 * sum(val_list))

Submission status: Runtime Error

Solution code:
import heapq

L1 = input().split(" ")
L2 = input().split(" ")
tickets = int(L1[1])
L2int = [-int(s) for s in L2]

heapq.heapify(L2int)

for t in range(tickets):
    heapq.heappush(L2int,heapq.heappop//2)
print(-sum(L2int))

Submission status: Runtime Error

Solution code:
import math
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True)
#print(a)
if n == 1:
    for _ in range(m):
        a[0] //= 2
else:
    for _ in range(m):
        a[0]//=2
        if a[0] < a[1]:
            b = a[0]
            a[0] = a[1]
            a[1] = b
            for i in range(1, m-1):
                if a[i] < a[i + 1]:
                    b = a[i]
                    a[i] = a[i+1]
                    a[i+1] = b
                else:
                    break

sum = 0
for i in range(n):
     sum += a[i]
print(sum)

Submission status: Runtime Error

Solution code:
import heapq

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

a = list(map(int, input().split(" ")))
heapq._heapify_max(a)

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

print(sum(a))

Submission status: Runtime Error

Solution code:
import sys
import heapq


def input():
    return sys.stdin.readline().rstrip()


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

    for i in range(M):
        maxaa = -1 * heapq.heappop(A)
        if max(A) == 0:
            print("0")
            exit()
        heapq.heappush(A,  maxaa // 2 * (-1))
    print(sum(A) * (-1))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
n = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort(reverse=True)
M=n[1]
def kyoukai(lis,m):
    s=0
    for i in range(n[0]):
        s+=math.log2(lis[i])
        if s>=m*2:
            boundary=i+1
            break
    return boundary
d=kyoukai(a,M)
k=0
while k!=1:
    for i in range(d):
        a[i]=int(a[i]/2)
    if M-d>0:
        M-=d
        d=kyoukai(a,M)
    else:
        break
print(sum(a))

Submission status: Runtime Error

Solution code:
import math
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True)
#print(a)
if n == 1:
    for _ in range(m):
        a[0] //= 2
else:
    for _ in range(m):
        a[0]//=2
        b = a[0]
        a.pop(0)
        i = 0
        for _ in range(m-1):
            if a[i] < b:
                a.insert(i, b)
                break
            i+=1
        if i == m-1:
            a.insert(i, b)
        #print(a)

sum = 0
for i in range(n):
     sum += a[i]
print(sum)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import heapq
readints = lambda: map(int, raw_input().split())

def solve(N, M, A):
    pq = [-x for x in A]
    heapq.heapify(pq)
 
    for _ in xrange(M):
        x = -heapq.heappop(pq)
        x /= 2
        heapq.heappush(pq, -x)
    return -sum(pq)

N, M = readints()
print solve(N, M, rrm())

Submission status: Runtime Error

Solution code:
import sys
import heapq


def input():
    return sys.stdin.readline().rstrip()


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

    for i in range(M):
        maxaa=-1 * heapq.heappop(AA)
        if max(A) == 0:
            print("0")
            exit()
        heapq.heappush(AA,  maxaa // 2 * (-1))
    print(sum(AA) * (-1))


if __name__ == '__main__':
    main()