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:
import math
N, M = map(int,input().split())

A = [int(x) for x in input().split()]
A.sort(reverse=True)

# first coupon
max = 0
newval = A[max] >> 1
A[max] = newval
# second coupon

if(M==1):
    print(sum(A))
else:
    # rest of coupons
    for i in range(1, M):
        if(A[max] >= A[i]):
            A[max] = A[max] >> 1
            if(A[max] < A[i]):
                max = i
        else:
            A[i] = A[i] >> 1
            if(A[i] > A[max]):
                max = i

    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)
count = m
while count > math.floor(m/2) or a[0] > a[1]:
    a[0] = a[0]/2
    count = count - 1
a[1] = a[1]/2
count = count - 1
print(round(sum(a)))

Submission status: Runtime Error

Solution code:
import numpy as np 

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
top, bottom = 0, M-1

if len(A) == 1:
    for _ in range(M):
        A[0] //= 2
else:
    for _ in range(M):
        A[top] //= 2
        print(top, bottom)
        if A[top] >= A[bottom]:
            bottom -= 1
            continue
        else:
            top += 1
print(sum(A))

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
it = 0
for i in range(M):
    A[it]=A[it]//2
    if it<N-1:
        if A[0]<=A[it+1] and A[it]<=A[it+1]:
            it+=1
        else: it = 0
    if it == N-1:
        it = 0
    print(A)
print(sum(A))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A=[int(n) for n in input().split()]
A.sort()
        
for _ in range(M):
    a = A[-1]//2
    del A[-1]
    for i in range(N):
        if A[i] >a:
            A.insert(i, a)
            break
print(sum(A))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a)
mx=a[-1]
mn=a[-2]
while m>0 :
  
  if mx>mn :
    mx=mx//2
    m-=1;
  else:
    a.pop(-1)
    a.append(mx)
    mn=mx
    a=sorted(a)
    mx=a[-1]
  print(a)
a.pop(-1)
a.append(mx)
print(sum(a))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True)
t = [a.pop(0)//2]

for i in range(0,m - 1):
  l = t.index(max(t))
  if a[0] > t[l]:
    t.append(a.pop(0)//2)
  else:
    t[l] = t[l]//2
print(sum(t) + sum(a))

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)

for cnt in range(m):
    if a[0] == 0:
        break
    a[0] = a[0] // 2
    if a[0] < a[1]:
         a.sort(reverse = True)

print(sum(a))

Submission status: Runtime Error

Solution code:
import bisect


n,m = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a)
k = 0
for _ in range(m):
    k -= 1
    if(k > 0):continue
    a_tmp = a.pop()
    if(len(a)==0):a.append(a_tmp//2)
    else:
        a2 = a[-1]
        k = a_tmp // a2
        a_tmp //= 2 ** k
        if(a_tmp >= a[-1]):a.append(a_tmp)
        elif(a_tmp <= a[0]):a.insert(0,a_tmp)
        else:
            index = bisect.bisect_left(a,a_tmp)
            a.insert(index,a_tmp)


print(sum(a))

Submission status: Runtime Error

Solution code:
import bisect
import copy

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
A2 = copy.deepcopy(A[N-M:])

for _ in range(M):
  tmp_a = int(A2[-1]/2)
  del A2[-1]
  if A2 <= tmp_a: A2.append(tmp_a)
  else: A2.insert(bisect.bisect_left(A2,tmp_a),tmp_a)
print(sum(A[:N-M])+sum(A2))

Submission status: Runtime Error

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

a.sort(reverse = True)

while i < m:
    tmp = a[0] // a[1]
    if tmp > m - i:
        a[0] = a[0] // 2 ** (m - i)
        break

    else:
        a[0] = a[0] // 2 ** tmp
        i += tmp
        a.sort(reverse = True)

print(sum(a))

Submission status: Runtime Error

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

if n == 1:
    print(a[0]//(2**m))
else:
    for i in range(m):
        if m < 1:
            a[0] = a[0]//(2**y)
            break
        else:
            a[a.index(max(a))] = a[a.index(max(a))]//(2**y)
            m -= 1
    
    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] + 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**i for i in t-b]
    print(int(np.sum(np.array(a, astype="object")/tm//1)))

Submission status: Runtime Error

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


def discount(x, y):
    return int(x / (2 ** y))

A.sort()

for i in range(M):
    if i == 0:
        res = sum(A) - A[N-1] + discount(A[N-1], M)
    else:
        _res = sum(A)
        for j in range(i+1):
            _res -= A[N-1-j]
            _res += discount(A[N-1-j], M-1-j)
        res = min(res, _res)

print(res)

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()] /= 2
b = np.array([abc // 1 for abc in a])
print(b.sum(b))

Submission status: Runtime Error

Solution code:
import sortedcontainers as sc

N,M = map(int,input().split())
As = []
l =  sc.SortedListWithKey(key=lambda x:-x)
As = list(map(int,input().split()))
for a in As:
	l.add(a)
	#print(list(l))
	
for _ in range(M):
	f = l.pop(0)
	l.add(int(f/2))

#print(list(l))
print(sum(list(l)))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
data=input().rstrip().split(" ")
data[0]=int(data[0])
data[1]=int(data[1])
yen=input().rstrip().split(" ")
for i in range(data[0]):
    yen[i]=int(yen[i])
    
yen=sorted(yen,reverse=True)
for i in range(data[1]):
    if data[0] >2:
       if(yen[0] <yen[1]):
            bef=yen[0]
            j=1
            while(bef < yen[j]):
                yen[j-1]=yen[j]
                j=j+1
            
            yen[j-1]=bef
        
    yen[0]=int(yen[0]/2)

ans=0
for i in range(data[0]):
    ans= ans + yen[i]
print(ans)

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)
    for j in range(len(ans)):
        if ans[j] <= -a[now]:
            tmp = math.ceil(ans[j] / 2)
            idx = bisect.bisect_right(ans,tmp)
            #print(ans,idx,tmp)
            ans.insert(idx,tmp)
            del ans[j]
            break
        if j == len(ans)-1:
            ans.append(math.ceil(-a[now]/2))
            now += 1
#print(ans,ans,ans,ans)
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:
import math
N,M = map(int,input().split())
A = list(map(int,input().split()))
total = 0
    max(A) //= 2
    M -= 1
    if M <= 0:
        break
for i in range(N):
    total += A[i]
print(total)

Submission status: Runtime Error

Solution code:
import numpy as np
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
for i in range(M):
  A[-1] = A[-1]/2
  if len(A) == 1:
    continue
  elif A[-1] < A[-2]:
    At=A[-1]
    for i in range(len(A)-1):
      x = i+2
      if A[-x] < At:
        np.insert(A,-x,At)
        np.delete(A,-1)
     
A = np.array(A)
A = np.floor(A)
print(int(np.sum(A)))

Submission status: Runtime Error

Solution code:

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

i = 0
j = 0

for m in range(M):
    
    A[j] //= 2
    
    if j == N-1:
        j = 0
    elif A[j] < A[i + 1]:
        j = i + 1
        i +=1
    else:
        j = 0
        
    
        
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)
while m>0:
  a[0]/=2
  m-=1
  if a[0]<a[1]:
    a.sort(reverse=True)
for i in range(n):
  a[i]=math.floor(a[i])
print(sum(a))

Submission status: Runtime Error

Solution code:
import math

class Solution(object):
    def __init__(self):
        pass
        
    def Sol(self, n, m, a):
        a.sort()  
        return self.Best(n, m, a, {}) 

    def Best(self, idx, m, a, tb):
        if idx == 0:
            return 0

        if (idx, m) in tb:
            return tb[(idx, m)]

        sl = 2 ** 60 
        for i in range(0, m + 1):
            sl = min(sl, int(math.floor(a[idx - 1] / 2 ** i)) + self.Best(idx - 1, m - i, a, tb))
            if a[idx - 1] < 2 ** i:
                break
        tb[(idx, m)] = sl
        return sl


def main():
    info = [int(e) for e in input().split()]
    a = [int(e) for e in input().split()]
    print(Solution().Sol(info[0], info[1], a)) 
    return 0

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math

n,m = map(int,input().split())
a = list(map(int,input().split()))
b = [math.log2(i) for i in a]
list.sort(a,reverse=True)
list.sort(b,reverse=True)
i = 1
while m > 0:
    if m >= i:
        m -= i
        for j in range(i):
            b[j] -= 1
            a[j] = a[j] // 2
        if b[i-1] - b[i] < 1:
            i += 1
        
        
    else:
        list.sort(a,reverse=True)
        list.sort(b,reverse=True)
        for k in range(m):
            b[k]-=1
            a[k] = a[k] // 2
        m = 0
ans = sum(a)
print(ans)

Submission status: Runtime Error

Solution code:
import math
N,M=(int(x) for x in input().split())
A=[int(input()) for i in range(N)]

for k in range(M):
    A[A.index(max(A))]=max(A)/2
for l in range(N):
    A[l]=math.floor(A[l])
print(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 _ in range(M):
    tmp = A.argmax()
    A[tmp] = A[tmp] // 2
print(str(sum(A)))

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

s = input().split()
N = int(s[0])
M = int(s[1])
# A = np.array(list(map(int, input().split())))
A = [int(input()) for _ in range(N)]
for i in range(M):
    A[A.argmax()] //= 2
print(np.sum(A))

Submission status: Runtime Error

Solution code:
A = list(map(int, input().split()))
for i in range(NM[1]):
    maxIndex = A.index(max(A))
    A[maxIndex] = int(max(A)/2)
minMoney = 0
for j in range(NM[0]):
    minMoney = minMoney + A[j]
print(minMoney)

Submission status: Runtime Error

Solution code:
import numpy as np
import math
N,M = [int(x) for x in input().split(" ")]
a = np.array([int(x) for x in input().split(" ")])
alog = np.log2(a)
sorted_args = np.argsort(alog)
sorted_args = N-sorted_args - 1
sorted_alog = np.sort(alog)[::-1]
sorted_Ms = [0 for _ in range(N)]
next_start_idx = 0
for m_idx in range(M):
    for idx in range(next_start_idx,len(sorted_alog) - 1):
        if sorted_alog[idx + 1] <= sorted_alog[idx]:
            next_start_idx = idx
            break
        idx += 1
    sorted_alog[idx] -= 1
    sorted_Ms[idx] += 1
    next_start_idx = 0
Ms = [0 for _ in range(N)]
for order, m_count in enumerate(sorted_Ms):
    for idx, this_order in enumerate(sorted_args):
        if order == this_order:
            Ms[idx] = m_count
res = 0
for i, price in enumerate(a):
    res += math.floor(price / (2 ** Ms[i]))
print(res)

Submission status: Runtime Error

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

for i in range(N):
	A[N] // 2
	A.sort()

B = sum(A)

print(B)

Submission status: Runtime Error

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

while m>0:
  A.sort(reverse=True)
  A[0]=A[0]//2
  m-=1
  print(A,m)
print(sum(A))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = map(int, input().split())
a = sorted(a)
a.reverse()
min_sum = 0
ti = 0
if m % 2 == 1:
  ti = m // 2 + 1
else:
  ti = m // 2

for _a in a:
  if m > 0:
    min_sum += _a // (2 ** ti)
    ti -= 1
  else:
    min_sum += _a

print(min_sum)

Submission status: Runtime Error

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

    a = sorted(a)

    ans = 0

    for i in range(m):
        a[n-1] = a[n-1]//2
        func(n-1, a)

    ans = sum(a)
    print(ans)

def func(i:int, ls:list):
    if i == 0:
        return
    else:
        if ls[i] < ls[i-1]:
            ls[i], ls[i-1] = ls[i-1], ls[i]
            i -= 1
            func(i, ls)
        return

if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
x = map(int,raw_input().split())
n=x[0]
m=x[1]
a = map(int,raw_input().split())
a.sort(reverse=True)

for i in range(m):
    if a[0]<a[1]:
        a.sort(reverse=True)
    a[0]=float(a[0])/2

a=list(map(int, a))

print(sum(a))

Submission status: Runtime Error

Solution code:
import math
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)

c = 0
for i in range(M):
  if c < M:
    x = max(math.log(A[0]/A[1] ,2)//1, 1)
    y = min(x, M - c)
    A[0] = A[0] //(2 ** y)
  A = sorted(A, reverse = True)
  
print(sum(A))

Submission status: Runtime Error

Solution code:
import numpy as np

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

sorted_an = sorted(an)
sorted_an.reverse()

discounts = []
for a in sorted_an:
    row = [] # 差が入る
    prev_discounted_price = a
    for i in range(1, m + 1):
        discounted_price = a // (2 ** i)
        if discounted_price == 0:
            row.append(discounted_price - prev_discounted_price)
            break
        row.append(discounted_price - prev_discounted_price)
        prev_discounted_price = discounted_price
    discounts.append(row)

flatten = np.array(discounts).flatten()
reversed_discounts = np.sort(flatten)
total_discounts = reversed_discounts[:m]
print(sum(an) + np.sum(total_discounts))

Submission status: Runtime Error

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

if n == 1:
    for _ in range(m):
        a[0] //=2
    print(a[0])
    exit()

temp = []
temp.append(a.pop())

while m > 0:
    if temp[-1] < a[-1]:
        temp.append(a.pop())
    else:
        temp = sorted(temp)
        temp[-1] //= 2
        m -= 1

print(sum(temp)+sum(a))

Submission status: Runtime Error

Solution code:
from bisect import insort
N,M = map(int,input().split())
A = (list(map(int,input().split())))
A.sort()
for i in range(M):
  mx = A.pop()
  insert_index = bisect.bisect_left(A,mx//2)
  A.insert(insert_index,mx//2)
print(sum(A))

Submission status: Runtime Error

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

A = sorted(A)[::-1]

waribiki = 0
index = 0

if len(A)==1:
    print(A[0]//pow(2,M))
    exit()

while waribiki < M:
    if index==0 and A[index] < 3: break
    if A[index]>2 and A[index+1]>2:
        x = A[index] // A[index+1]
        if x+waribiki>M: x = M-waribiki

    if A[index] > 2:
        A[index] = A[index]//pow(2, x)
        waribiki+=x

    index += 1
    if index==N:
        index=0



if waribiki < M:
    index = 0
    while waribiki < M:
        A[index] = A[index] // 2
        waribiki += 1

        index += 1
        if index==N: index=0

        if sum(A)==0:break


print(sum(A))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=sorted(map(int,input().split()),reverse=True)
i=0
for _ in range(m):
    a[i]//=2
    i=a.index(max(a))
    print(a)
print(sum(a))

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline


def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a=sorted(a,reverse=True)
    for i in range(m):
        if a[1]!=0:
            x=a[0]//a[1]
            if x<=m:
                a[0]//=2**x
                m-=x
            elif x>m and m>0:
                a[0]//=2**m
                m=0
        if m==0:
            break
        a = sorted(a, reverse=True)

    print(sum(a))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math

def main():
  n, m = [int(x) for x in raw_input().split()]
  prices = [int(x) for x in raw_input().split()]
  memo = {}
  
  def solve(i, k):
    if (i, k) in memo:
        return memo[(i, k)]

    if i >= n:
      return 0
    if k == 0:
      memo[(i, k)] = prices[i] + solve(i+1, 0)
      return memo[(i, k)]
    
    results = [prices[i]+solve(i+1, k)]

    for x in xrange(k):
      price = int(math.floor(prices[i] / 2**(k-x))) + solve(i+1, x)
      results.append(price)

    memo[(i, k)] = min(results)
    return memo[(i, k)]
      
  print(solve(0, m))
  

main()

Submission status: Runtime Error

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

count = 0

if n == 1:
    for i in range(m):
        a_list[0] = a_list[0] // 2
else:
    while m>count:
        else:
            a_list.sort(reverse=True)
            a_list[0] = a_list[0] // 2
            count += 1
            if a_list[0] >= a_list[1]:
                a_list[0] = a_list[0] // 2
                count += 1
print(sum(a_list))

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = 3, 3
items = np.array((2, 13, 8))
for i in range(M):
    items[items.argmax()]/=2
    if np.max(items)<0.5:
        break
print(round(np.sum(items)))

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 _ in range(M):
    A[A.argmax()] = np.max(A) // 2
print(str(sum(A)))

Submission status: Runtime Error

Solution code:
def nibutan(a,b,l,x):#一つ後ろ
    while a+1!=b:
        mid=int((a+b)/2)
        if x<l[mid]:
            b=mid
        elif x>l[mid]:
            a=mid
        else:
            return mid
    if x<=l[a]:
        return a
    elif x<=l[b]:
        return b
    else:
        return b+1


N,M=map(int,input().split())
la=list(map(int,input().split()))
la.sort()
for i in range(M):
    #la.sort()
    la[N-1]/=2
    ll=la[N-1]
    la.pop()
    la.insert(nibutan(0,N-2,la,ll),ll)

ans=0
for i in range(N):
    ans+=int(la[i])
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

A = deque(A)
A = sorted(A)

for i in range(M):
    temp = A.pop() // 2

    for j in range(N)[::-1]:
        if j>0:
            if A[j-1] <= temp:
                A.insert(j,temp)
                print(A)
                break
        else:
            A.insert(0,temp)

print(sum(A))

Submission status: Runtime Error

Solution code:



def main():


    N, M = map(int,input().split())
    priceList = list(map(int,input().split()))
    priceList.sort(reverse=True)

    if N <= 3:
        for _ in range(M):
            priceList[0] //= 2
            priceList.sort(reverse=True)
        print(sum(priceList))
        exit()

    atMax = 1
    
    for _ in range(M):
        if atMax-1 < 0: atMax = 1
        
        if priceList[atMax-1] > priceList[atMax+1]:
            if priceList[atMax-1] >priceList[atMax]:
                priceList[atMax-1] //= 2
                if priceList[atMax+1] > priceList[atMax-1]:
                    atMax = atMax+1
                else:
                    atMax = atMax-1
            else:
                priceList[atMax] //= 2
        else: 
            if priceList[atMax+1] > priceList[atMax]:
                priceList[atMax+1] //=2
                if priceList[atMax+1] > priceList[atMax-1]:
                    atMax = atMax+1
                else:
                    atMax = atMax-1
            else:
                priceList[atMax] //= 2
    print(sum(priceList))











if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
import numpy as np
dp = np.zeros((N+1, M+1))
#dp = [[0 for _ in range(M+1)] for j in range(N+1)]
B = [[A[i]//2**k for k in range(M+1)] for i in range(N)]
B = np.array(B)
for i in range(0, N):
  for j in range(0, M+1):
    dp[i+1][j] = min([dp[i][j-k] + B[i][k] for k in range(0, M+1) if j-k>=0])
print(int(dp[N][M]))

Submission status: Runtime Error

Solution code:
import bisect 
n,m = map(int,input().split())
a = sorted(list(map(int,input().split())))
b = a[-1]

for i in range(m):
  if int(b/2) >= a[-2]:
    b = int(b/2)
  else:
    bisect.insort(a,b)
    b = a[-1]
    b = int(b/2)

a.append(b)
print(sum(a))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.append(0)
a.sort(reverse=True)
b = [a[0], a[1]]


def hikaku(i, tempb):
    b[i - 1] = b[i]
    b[i] = tempb
    if len(b) == i + 1:
        b.append(a[i + 1])
    if b[i] < b[i + 1]:
        hikaku(i + 1, tempb)


while m > 0:
    b[0] = b[0] // 2
    if b[0] < b[1]:
        hikaku(1, b[0])
    if b[0] < 1:
        break
    m -= 1


if b[0] < 1:
    print(0)
else:
    for i in range(len(b), len(a)):
        b.append(a[i])
    print(sum(b))

Submission status: Runtime Error

Solution code:
import math
import numpy as np

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


for i in range(m):
    tem = ar.argmax()
    ar[tem] = math.floor(ar[tem]/2)

print(sum(ar))

Submission status: Runtime Error

Solution code:
def A():
    w = ['Sunny', 'Cloudy', 'Rainy']
    today = input()
    index = w.index(today)
    if index == 2:
        index = -1
    print(w[index+1])

def B():
    odd = 'RUD'
    even = 'LUD'

    s = input()
    for i in range(len(s)):
        if (i+1)%2 == 0:
            if s[i] not in even:
                print('No')
                return
        else:
            if s[i] not in odd:
                print('No')
                return
        
    print('Yes')

def C():
    temp = [int(i) for i in input().split()]
    N = temp[0]
    K = temp[1]
    Q = temp[2]
    points = {}

    for i in range(N):
        points[i] = 0

    for i in range(Q):
        num = int(input())
        points[num-1] += 1

    for i in points.keys():
        if K - (Q - points[i]) > 0:
            print('Yes')
        else:
            print('No')

def D():
    temp = [int(i) for i in input().split()]
    N = temp[0]
    M = temp[1]
    A = sorted([int(i) for i in input().split()])
    memo = {}

    #recursive solution
    def getMin(items, num_of_tickets):
        if len(items) == 0:
            return 0

        if (items[0], num_of_tickets) in memo:
            #print('working')
            return memo[(items[0], num_of_tickets)]

        minimum = items[0] + getMin(items[1:], num_of_tickets)
        for i in range(1, num_of_tickets+1):
            temp = items[0]//(2**i) + getMin(items[1:], num_of_tickets-i)
            memo[(items[0], num_of_tickets)] = temp
            minimum = min(minimum, temp)

        return minimum

    print(getMin(A, M))
        
D()

Submission status: Runtime Error

Solution code:
import math
n, m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]

max_value = max(a)
l = math.ceil(math.log2(max_value))

b = [[] for i in range (l)]

for i in a:
    index = math.floor(math.log2(i))
    b[index].append(i)

ticket = m
p = l-1
while ticket > 0 and p >= 0:
    max_value = max(b[p])
    b[p].remove(max_value)
    if p > 0:
        b[p-1].append(max_value // 2)
    ticket = ticket - 1
    while len(b[p]) == 0 and p >= 0:
        p = p-1


sum_value = 0
for i in range(l):
    sum_value += sum(b[i])

print(sum_value)

Submission status: Runtime Error

Solution code:
# coding: utf-8
N, M = [int(x) for x in input().split(" ")]
prices = [int(x) for x in input().split(" ")]
prices.sort()
for i in range(M):
    prices[-1] //= 2
    if prices[-1] < prices[-2]:
        prices.sort()
sum = 0
for num in prices:
    sum += num
print(sum)

Submission status: Runtime Error

Solution code:
import bisect
from collections import deque

n,m = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a)
a = deque(a)
for _ in range(m):
    a_tmp = a.pop()
    a_tmp //= 2
    if(len(a)==0):a.append(a_tmp)
    else:
        if(a_tmp >= a[-1]):a.append(a_tmp)
        elif(a_tmp <= a[0]):a.appendleft(a_tmp)
        else:
            index = bisect.bisect_left(a,a_tmp)
            a.insert(index,a_tmp)


print(sum(a))

Submission status: Runtime Error

Solution code:
import math
n, m = map(int, input().split())
a = sorted(map(int, input().split()), reverse=True)
i = 1
while m > 0:
	if m>=i:
		m -= i
		a[0:i] = [num//2 for num in a[0:i]]
		j = 0
		while a[0]<a[i+j] and i+j < n-1:
			j += 1
		temp = a[i:i+j]
		a[j:i+j] = a[0:i]
		a[0:j] = temp
		i += 1
	else:
		a[0:m] = [num//2 for num in a[0:m]]
		m=0
print(sum(a))

Submission status: Runtime Error

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


B = [[] for _ in range(100)]
max_id = 0
for a in A:
    i = len(bin(a)) - 2
    B[i].append(a)
    max_id = max(max_id, i)

B = B[:max_id+1]

j = -1
while True:
    if M == 0:
        break
    if len(B) == 1:
        break

    if len(B[j]) < M:
        M -= len(B[j])
        B[j-1].extend(list(map(lambda x: x//2, B.pop(j))))
    else:
        b = B.pop(j)
        b.sort(key=lambda x: -x)
        for k in range(M):
            B[j].append(b.pop(k)//2)
        B.append(b)
        M = 0

ans = 0
for b in B:
    ans += sum(b)
print(ans)

Submission status: Runtime Error

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

while(M>0):
  alist[0]//=2
  if alist[0]<alist[1]:
    alist.sort(reverse=True)
  M-=1

print(sum(alist))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A=[int(n) for n in input().split()]
A.sort()
        
for _ in range(M):
    a = A[-1]//2
    del A[-1]
    for i in range(N):
        if A[i] >a:
            A.insert(i, a)
            break
    print(A)
print(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())))

if N == 1:
    for i in range(M):
        a //= 2
    print(a[0])
    exit()

a.sort()
cur = M - 1
for i in range(M):
    if i == 0:
        a[-1] //= 2
    else:
        if (a[cur-1] > a[cur]):
            cur -= 1
            a[a[cur:].argmax()+cur] //= 2
        else:
            a[-1] //= 2
print(sum(a))

Submission status: Runtime Error

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

C=[]
C.append(A.pop(-1)/2)
for i in range(M-1):
    max_idx = C.index(max(C))
    if C[max_idx] < A[-1]:
        C.append(A.pop(-1)/2)
    else:
        C[max_idx] = C[max_idx]/2
        
ans = 0
for i in (A+C):
    ans+=int(i)
print(ans)

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)

for cnt in range(m):
    a[0] = a[0] // 2
    if a[0] < a[1]:
         a.sort(reverse = True)

print(sum(a))

Submission status: Runtime Error

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

a.sort(reverse = True)
i = 0

while i < m:
    tmp = a[0] // a[1]
    if tmp > m - i:
        a[0] = a[0] // 2 ** (m - i)
        break

    else:
        a[0] = a[0] // 2 ** tmp
        i += tmp
        a.sort(reverse = True)


print(sum(a))

Submission status: Runtime Error

Solution code:
import heapq
n,m=map(int,input().split())
q=[]
a=[-int(i) for i in input().split()]
for i in a:
    heapq.heappush(q,(i,i,0))
ans=chk=0
while 1:
    f=1
    for i in range(m):
        x=heapq.heappop(q)
        j=-x[1]
        k=-q[0][1]
        if (i==m-1) or (j//(2**(i+1+x[2]))<k):
            f=0
            heapq.heappush(q,(-(j//(2**(i+1+x[2]))),x[1],x[2]+i+1))
            m-=(i+1)
            break
    if f:
        break
for i in q:
    ans+=-i[0]
print(ans)

Submission status: Runtime Error

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

A = sorted(A)[::-1]

waribiki = 0
index = 0

if len(A)==1:
    print(A[0]//pow(2,M))
    exit()

while waribiki < M:
    if index==0 and A[index] < 3: break
    if A[index]>2 and A[index+1]>2:
        x = A[index] // A[index+1]
        if x+waribiki>M: x = M-waribiki

    if A[index] > 2:
        A[index] = A[index]//pow(2, x)
        waribiki+=x

    index += 1
    if index==N:
        index=0



if waribiki < M:
    index = 0
    while waribiki < M:
        A[index] = A[index] // 2

        index += 1
        if index==N: index=0

        if sum(A)==0:break


print(sum(A))