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: Time Limit Exceeded

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

for i in range(m):
  l1 = sorted(l1)
  l1[-1] //= 2
print(sum(l1))

Submission status: Time Limit Exceeded

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

for i in range(m):
	a[n-1] = a[n-1] //2
	a.sort()
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
A = list(map(int,input().split()))
for i in range(M):
  max_item = A.index(max(A))
  A[max_item] //= 2
print(sum(A))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(m):
	L[0]=L[0]/2
	for j in range(n-1):
		if L[j]<L[j+1]:
			L[j], L[j+1]= L[j+1], L[j]
		else:
			break
#小数点を切り捨てる
for i in range(n):
	L[i]=int(L[i])
print(sum(L))

Submission status: Time Limit Exceeded

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

for _ in range(M):
    A[A.index(max(A))] = max(A)//2

print(sum(A))

Submission status: Time Limit Exceeded

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

for _ in range(M):
    A[0] = A[0]//2
    if len(A) > 1 and A[0] < A[1]:
        A.sort(reverse=True)

print(sum(A))

Submission status: Time Limit Exceeded

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

for _ in range(M):
  A.sort()
  A[-1] = A[-1]//2

print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
#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:
        #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.log(highest/next_highest)/math.log(2))
        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:
            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()
                
            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 list(discounted_deque)]
    print(sum(A_list)+sum(discounted_list))
else:
    A_list[-1] = A_list[-1]//(pow(2,M))
    print(A_list[-1])

Submission status: Time Limit Exceeded

Solution code:
#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:
        #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.log(highest/next_highest)/math.log(2))
        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:
            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()
                
            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])

Submission status: Time Limit Exceeded

Solution code:
#141D bisect
def main():
    import sys, bisect
    #from collections import deque
    
    N,M =map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    A.sort()
    #print(A)
    while M:
        tmp = A.pop()
        bisect.insort(A, tmp//2)
        M-=1
    print(sum(A))
   

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
t = 0
while t<M:
  A[N-1] = A[N-1]//2
  if A[N-1] < A[N-2]:
    A.sort()
  t += 1
s = 0
for i in range(N):
  s += A[i]
print(int(s))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
t = 0
while t<M:
  A[N-1] = A[N-1]//2
  A.sort()
  t += 1
s = 0
for i in range(N):
  s += A[i]
print(int(s))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
arr= list(map(int,input().split()))
 
while m > 0: 
    arr[arr.index(max(arr))] = max(arr)//2
    m -= 1
    
print(sum(arr))

Submission status: Time Limit Exceeded

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

"""
A.sort(reverse=True)

for m in range(M):
    A[m] //= 2
    A.sort()
    #print(A)

print(sum(A))
"""

for i in range(M):
    m = A.index(max(A))
    A[m] //= 2
    #print(A)

print(sum(A))

Submission status: Time Limit Exceeded

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

for m in range(M):
    A[-1] //= 2
    A.sort()
    #print(A)

print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
#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.log(highest/next_highest)/math.log(2))
        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])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M=(int(x) for x in input().split())
a=list(map(int,input().split()))
A=np.array(a)
for m in range(M):
    A[np.argmax(A)]=A[np.argmax(A)]/2
ans=0
for n in range(N):
    ans+=round(A[n])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = LIST()

while M:
	A.sort()
	A[-1] //= 2
	M -= 1

print(sum(A))

Submission status: Time Limit Exceeded

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

for i in range(M):
    ind = A.index(max(A))
    A[ind] = max(A)//2
print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
for i in range(M):
    A[-1] = A[-1]//2
    A.sort()
print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
for i in range(M):
    A=sorted(A,reverse=True)
    b=bin(A[0]>>1)
    A[0]=int(b,0)
print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import bisect

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

a.sort()
for i in range(m):
    value = a.pop()
    value //= 2
    insert_index = bisect.bisect_left(a, value)

    a.insert(insert_index, value)
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
from copy import copy

import numpy as np


def main():
    for _ in range(M):
        A2 = A.copy()
        A.sort()
        A[-1] = A[-1] // 2

    print(sum(A))


if __name__ == "__main__":
    N, M = map(int, input().split())
    A = np.array(list(map(int, input().split())))
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def main():
    for _ in range(M):
        A.sort()
        A[-1] = A[-1] // 2

    print(sum(A))


if __name__ == "__main__":
    N, M = map(int, input().split())
    A = np.array(list(map(int, input().split())))
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    for _ in range(M):
        A.sort()
        A[-1] = A[-1] // 2

    print(sum(A))


if __name__ == "__main__":
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    for _ in range(M):
        mx = max(A)
        A[A.index(mx)] = mx // 2

    print(sum(A))


if __name__ == "__main__":
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    main()

Submission status: Time Limit Exceeded

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

for _ in range(M):
    mx = max(A)
    A[A.index(mx)] = mx // 2

print(sum(A))

Submission status: Time Limit Exceeded

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

A.sort(reverse = True)

n = 0
if N > 1:
    while not M == 0:

        while A[0] >= A[1]:
            A[n] //= 2
            M -= 1
            if M == 0:
                break
        if M == 0:
            break

        a = A.pop(0)
        for i, num in enumerate(A):
            if num < a:
                A.insert(i, a)
                break
else:
    A[0] //= (2**M)


result = sum(A)
print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import insort_right
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for i in range(M):
  tmp = A[-1-i]
  insort_right(A,tmp//2)
print(sum(A[:-M]))

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import insort_right
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for i in range(M):
  tmp = A[-1]
  del A[-1]
  insort_right(A,tmp//2)
print(sum(A))

Submission status: Time Limit Exceeded

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

for i in range(M):
  A.sort()
  A[-1] //=2
print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
import bisect

[n, m] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
for i in range(m):
    tmp = a.pop(-1)
    bisect.insort(a, int(tmp / 2))
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
[n, m] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
for i in range(m):
    idx = a.index(max(a))
    a[idx] = int(a[idx] / 2)
print(sum(a))

Submission status: Time Limit Exceeded

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

while M > 0:
    maxv = max(A)
    max_index = A.index(maxv)
    A[max_index] = A[max_index] // 2
    M -= 1

print(sum(A))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
[n, m] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
for i in range(m):
    a[-1] = int(a[-1] / 2)
    a.sort()
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m=map(int,input().split())
a=sorted(deque(map(int,input().split())),reverse=True)
for i in range(m):
  a[0]=a[0]//2
  a.sort(reverse=True)
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
while m>0:
    a[a.index(max(a))] //=2
    m-=1
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
while a[0]>0 and m>0:
    a[0]=a[0]//2
    a.sort(reverse=True)
    m-=1
print(sum(a))

Submission status: Time Limit Exceeded

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

A.sort()

cnt = M
end_flag = True
while end_flag:
    max_num = A.pop(N-1)
    if len(A) > 0:
        while cnt > 0 and max_num >= A[N-2]:
                max_num = max_num // 2
                cnt -= 1
    else:
        while cnt > 0:
            max_num = max_num // 2
            cnt -= 1
    bisect.insort_left(A, max_num)
    if cnt == 0:
        end_flag = False
        
print(sum(A))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

print(sum(map(lambda x: int(-1 * x), hpq)))

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, M = [int(s) for s in input().split()]
A = [int(s) for s in input().split()]

hpq = list(map(lambda x: -1 * x, A))
for i in range(M):
    heapq.heapify(hpq)
    x = heapq.heappop(hpq)
    heapq.heappush(hpq, x / 2)

print(sum(map(lambda x: int(-1 * x), hpq)))

Submission status: Time Limit Exceeded

Solution code:
# D - Powerful Discount Tickets

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

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

print(sum(A))

Submission status: Time Limit Exceeded

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

while M > 0:
    A.sort()
    tmp = A.pop(-1)
    tmp = tmp//2
    M -= 1
    A.append(tmp)
    
print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
for i in range(M):
  B = A[-1]//2
  del A[-1]
  bisect.insort_left(A, B)
  #print(A)
print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
for i in range(M):
  B = A[-1]//2
  A=A[:N-1]
  bisect.insort_left(A, B)
  #print(A)
print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
nedan_list = []
append = nedan_list.append
for i in range(n):
  price = a[i]
  append((i, price))
  while price > 1:
    price = price >> 1
    append((i, price))

nedan_list.sort(key=lambda x:x[1], reverse=True)
count = 0
saisyo_list = [True]*n
for e in nedan_list[m:]:
  if saisyo_list[e[0]]:
    saisyo_list[e[0]] = False
    count += e[1]
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
nedan_list = []
for i in range(n):
  price = a[i]
  nedan_list.append((i, price))
  while price > 1:
    price //= 2
    nedan_list.append((i, price))

nedan_list.sort(key=lambda x:x[1], reverse=True)
count = 0
saisyo_list = [True]*n
for e in nedan_list[m:]:
  if saisyo_list[e[0]]:
    saisyo_list[e[0]] = False
    count += e[1]
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
nedan_list = []
for i in range(n):
  price = a[i]
  nedan_list.append((i, price))
  while price > 1:
    price //= 2
    nedan_list.append((i, price))

nedan_list = sorted(nedan_list, key=lambda x:x[1], reverse=True)
count = 0
saisyo_list = [True]*n
for e in nedan_list[m:]:
  if saisyo_list[e[0]]:
    saisyo_list[e[0]] = False
    count += e[1]
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
nedan_list = []
for i in range(n):
  price = a[i]
  nedan_list.append((i, price))
  while price > 0:
    price //= 2
    nedan_list.append((i, price))

nedan_list = sorted(nedan_list, key=lambda x:x[1], reverse=True)
count = 0
saisyo_list = [True]*n
for e in nedan_list[m:]:
  if saisyo_list[e[0]]:
    saisyo_list[e[0]] = False
    count += e[1]
print(count)

Submission status: Time Limit Exceeded

Solution code:
#標準入力からソートまで
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
#Aの中で一番でかいのをdiscountしてまた並び替え
import bisect
for i in range(M):
    tmp = A.pop(N-1) // 2
    bisect.insort_left(A, tmp)
print(sum(A))

Submission status: Time Limit Exceeded

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

for i in range(m):
  num = s[-1]
  s.pop(-1)
  s.append(num//2)
  s.sort()

print(sum(s))

Submission status: Time Limit Exceeded

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

for i in range(m):
  num = max(s)
  s.pop(-1)
  s.append(num//2)
  s.sort()
print(sum(s))

Submission status: Time Limit Exceeded

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

for i in range(m):
  num = max(s)
  s.remove(num)
  s.append(num//2)

print(sum(s))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,M = inputIL()
A = inputIL()

a = [[] for i in range(31)]

for x in A:
  n = math.floor(math.log(x)/math.log(2))
  a[n].append(x)

shorichu = []
for i in range(31)[::-1]:
  if M>=len(a[i]):
    if i>0:
      M -= len(a[i])
      disc = [x//2 for x in a[i]]
      a[i] = []
      a[i-1] += disc
      a[i-1].sort()
    else:
      print(0)
      exit()
  else:
    if i>0:
      for j in range(len(a[i])-M,len(a[i]))[::-1]:
        a[i-1].append(a[i][-1]//2)
        a[i] = a[i][:-1]
      break
    else:
      print(len(a[0])-M)
      exit()

print(sum(sum(item) for item in a))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,M = inputIL()
A = inputIL()

A.sort()

import bisect


while M:
  M -= 1
  x = A[-1]
  A = A[:-1]
  bisect.insort(A, x//2)
  
print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(i) for i in input().split(' ')]
A = [int(i) for i in input().split(' ')]
for i in range(M):
    max_value = max(A)
    A[A.index(max_value)] = max_value // 2
print(sum(A))

Submission status: Time Limit Exceeded

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

l=list(map(int,input().split()))

for i in range(m):
    j= l.index(max(l))
    l[j] = l[j]//2


print(sum(l))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=list(map(int,input().split()))
while m>0:
    max=0
    num=0
    for i in range(n):
        if A[i]>max:
            max=A[i]
            num=i
    A[num]=A[num]/2
   # print(num+1)
    m+=-1
sum=0
for a in A:
    #print(a)
    sum+=(a//1)
print(int(sum))

Submission status: Time Limit Exceeded

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

for _ in range(m):
    a.sort()
    a[-1] = int(a[-1] / 2)

print(sum(a))

Submission status: Time Limit Exceeded

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

import numpy as np

for _ in range(M):
  argmax = np.argmax(A)
  A[argmax] =  A[argmax]//2

print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from queue import Queue

#n = int(input())
n, m = [int(i) for i in input().split()]
#table = [[int(i) for i in input().split()] for j in range(n)]
#table = [list(input()) for n in range(h)]
s = [int(i) for i in input().split()]
#s = [int(i) for i in range(n)]
#s = [int(input()) for i in range(n)]
#s = input()
#list = list(s)
# dp = [[0 for _ in range(2)] for _ in range(13)]

#a = [[0 for _ in range(n+1)] for _ in range(n+1)]
#b = [[0 for _ in range(n+1)] for _ in range(n+1)]

for i in range(m) :
    s[s.index(max(s))] = math.floor(max(s)/2)

print(sum(s))

Submission status: Time Limit Exceeded

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

import numpy as np
a=np.array(a_ls)

for i in range(M):
	a_target=np.argmax(a)
	a[a_target]/=2

b=a.astype(int)
print(sum(b))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    sum_amount = 0
    dists = []
    dists_comb = {}

    for i in range(len(A)):
        k = 1
        if A[i] == 1:
            dists.append((i, k, k))
        else:
            while A[i] // 2**k > 0:
                dists.append((i, (A[i] // 2**(k - 1) - A[i] // 2**k), k))
                k += 1
    
    dists = sorted(dists, key=lambda x: x[1], reverse=True)
    
    for d in dists:
        if M == 0:
            break
        if dists_comb.get(d[0], 0) != 0:
            M -= (d[2] - dists_comb[d[0]])
            dists_comb[d[0]] = d[2]
        else:
            dists_comb[d[0]] = d[2]
            M -= d[2]
    
    if M > 0:
        print(0)
    else:
        for i in range(N):
            sum_amount += A[i] // (2 ** dists_comb.get(i, 0))
        print(sum_amount)
         

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    sum_amount = 0
    dists = []
    dists_comb = defaultdict(int)

    for i in range(len(A)):
        k = 1
        if A[i] == 1:
            dists.append((i, k, k))
        else:
            while A[i] // 2**k > 0:
                dists.append((i, (A[i] // 2**(k - 1) - A[i] // 2**k), k))
                k += 1
    
    dists = sorted(dists, key=lambda x: x[1], reverse=True)
    
    for d in dists:
        if M == 0:
            break
        if dists_comb[d[0]] != 0:
            M -= (d[2] - dists_comb[d[0]])
            dists_comb[d[0]] = d[2]
        else:
            dists_comb[d[0]] = d[2]
            M -= d[2]
    
    if M > 0:
        print(0)
    else:
        for i in range(N):
            sum_amount += A[i] // (2 ** dists_comb[i])
        print(sum_amount)
         

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = a
ans = 0
for i in range(m):
    max_idx = a.index(max(a))
    a[max_idx] /= 2
    b[max_idx] = int(a[max_idx])
print(sum(b))