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())
A = list(map(int,input().split()))
A.sort(reverse=True)

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
List = list(map(int,input().split()))
List.sort(reverse=True)
halves = [0]
max_halves = 0

for i in range(m):
  x = List.pop(0)
  if x >= max_halves:
    x = int(x/2)
    if len(List) == 0:
      List = [x]
    else:
      halves.append(x)
      if x >= max_halves:
        max_halves = x
  else:
    halves.remove(max_halves)
    halves.append(int(max_halves/2))
    max_halves = max(halves)
    List = [x]+ List
print(sum(List)+sum(halves))

Submission status: Time Limit Exceeded

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

for _ in range(M):
    A[0] = int(A[0]/2)
    A = sorted(A, reverse=True)

print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
pri =[0]*n

pri = list(map(int, input().split()))
    
for i in range(m):
	newp = 0
	p1=0
	for j in range(n):
		if pri[j] >newp:
			newp=pri[j]
			p1=j
	pri[p1] = pri[p1]//2	
#	print(p1,pri[p1])
total = 0
for i in range(n):
	total = total + pri[i]
print(total)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
pri =[0]*n
dc  =[0]*n

pri = list(map(int, input().split()))
    
for i in range(m):
	newp = 0
	p1=0
	for j in range(n):
		if pri[j]//(2**dc[j]) >newp:
			newp=pri[j]//(2**dc[j])
			p1=j
	dc[p1]=dc[p1]+1
#	print(p1,pri[p1]//(2**dc[p1]))
total = 0
for i in range(n):
	total = total + pri[i]//(2**dc[i])
print(total)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a = sorted([int(i) for i in input().split()])[::-1]
ans = 0

while m > 0:
    a[0] = a[0]//2
    m-=1
    for i in range(n-1):
        if a[i] < a[i+1]: a[i],a[i+1] = a[i+1],a[i]
        else: break
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
import bisect

n,m=map(int,input().split())
a = sorted([int(i) for i in input().split()])
ans = 0
while m > 0:
    temp = a[-1]//2
    a = a[:-1]
    index=bisect.bisect_left(a,temp)
    a.insert(index,temp)
    m-=1
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a = sorted([int(i) for i in input().split()])
ans = 0
while m > 0:
    a[-1] = a[-1]//2
    m-=1
    a.sort()
print(sum(a))

Submission status: Time Limit Exceeded

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

def main():
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())))

    for _ in range(M):
        ins = A.pop() // 2
        A.insert(bisect.bisect_left(A, ins), ins)

    print(sum(A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect


def main():
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())))

    for _ in range(M):
        ins = A.pop() // 2
        A.insert(bisect.bisect_left(A, ins), ins)

    print(sum(A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

A_pop = A.pop
A_insert = A.insert
for _ in range(M):
    ins = A_pop() // 2
    A_insert(bisect.bisect_left(A, ins), ins) 

print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

for _ in range(M):
    ins = A.pop() // 2
    A.insert(bisect.bisect_left(A, ins), ins) 

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)

for i in range(M):
    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()))

for i in range(M):
    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()))
A.sort(reverse = True)
ans = 0
for i in range(M):
  A[0] = A[0] // 2
  A.sort(reverse = True)
for i in range(N):
  ans += A[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import floor
from bisect import insort_left
n, m = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
for i in range(m):
  a = l.pop(-1)
  a /= 2
  insort_left(l, a)
ans = 0
for i in range(n):
  ans += floor(l[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import floor
from bisect import bisect_left
n, m = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
for i in range(m):
  a = l.pop(-1)
  a /= 2
  index = bisect_left(l, a)
  l.insert(index, a)
ans = 0
for i in range(n):
  ans += floor(l[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

for i in range(M):
    mx=max(A)
    A.remove(mx)
    A.append(mx/2)

A=list(map(math.floor, A))
print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
import heapq
import math
#これを加える！！！！
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

"""
a = [1,7,3,5,4]

#heapify
#配列a = [1,7,3,5,4]をheapにする
heapq._heapify_max(a)
print(a) #[7, 5, 3, 1, 4]

#heappop
#最大値の取り出し
print(_heappop_max(a)) #7
print(a) #[5, 4, 3, 1]

#heappush
#要素(2)の挿入
_heappush_max(a,2)
print(a) #[5, 4, 3, 1, 2]

#最大値の取り出し
print(_heappop_max(a)) #5
"""

N, M = map(int, input().split())
a = [int(i) for i in input().split()]
b = a[:N]
heapq._heapify_max(b)

okaiage = []
heapq._heapify_max(okaiage)
_heappush_max(okaiage, _heappop_max(b)/2)

m = M - 1
for j in range(N-1):
    temp_oka = _heappop_max(okaiage)
    temp_a = _heappop_max(b)
    if m > 0:
        if temp_a > temp_oka:
            _heappush_max(okaiage, temp_a/2)
            _heappush_max(okaiage, temp_oka)
        else:
            _heappush_max(okaiage, temp_a)
            _heappush_max(okaiage, temp_oka/2)
    else:
        _heappush_max(okaiage, temp_a)
        _heappush_max(okaiage, temp_oka)
    m -= 1
if m > 0:
    for i in range(m):
        temp_oka = _heappop_max(okaiage) / 2
        _heappush_max(okaiage, temp_oka)
okaiage_kiri = [int(math.floor(_heappop_max(okaiage))) for i in range(N)]
print(sum(okaiage_kiri))

Submission status: Time Limit Exceeded

Solution code:
import heapq
import math
#これを加える！！！！
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

"""
a = [1,7,3,5,4]

#heapify
#配列a = [1,7,3,5,4]をheapにする
heapq._heapify_max(a)
print(a) #[7, 5, 3, 1, 4]

#heappop
#最大値の取り出し
print(_heappop_max(a)) #7
print(a) #[5, 4, 3, 1]

#heappush
#要素(2)の挿入
_heappush_max(a,2)
print(a) #[5, 4, 3, 1, 2]

#最大値の取り出し
print(_heappop_max(a)) #5
"""

N, M = map(int, input().split())
a = [int(i) for i in input().split()]
b = [a[i] for i in range(N)]
heapq._heapify_max(b)

okaiage = []
heapq._heapify_max(okaiage)
_heappush_max(okaiage, _heappop_max(b)/2)

m = M - 1
for j in range(N-1):
    temp_oka = _heappop_max(okaiage)
    temp_a = _heappop_max(b)
    if m > 0:
        if temp_a > temp_oka:
            _heappush_max(okaiage, temp_a/2)
            _heappush_max(okaiage, temp_oka)
        else:
            _heappush_max(okaiage, temp_a)
            _heappush_max(okaiage, temp_oka/2)
    else:
        _heappush_max(okaiage, temp_a)
        _heappush_max(okaiage, temp_oka)
    m -= 1
if m > 0:
    for i in range(m):
        temp_oka = _heappop_max(okaiage) / 2
        _heappush_max(okaiage, temp_oka)
okaiage_kiri = [int(math.floor(_heappop_max(okaiage))) for i in range(N)]
print(sum(okaiage_kiri))

Submission status: Time Limit Exceeded

Solution code:
import heapq
import math
#これを加える！！！！
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

"""
a = [1,7,3,5,4]

#heapify
#配列a = [1,7,3,5,4]をheapにする
heapq._heapify_max(a)
print(a) #[7, 5, 3, 1, 4]

#heappop
#最大値の取り出し
print(_heappop_max(a)) #7
print(a) #[5, 4, 3, 1]

#heappush
#要素(2)の挿入
_heappush_max(a,2)
print(a) #[5, 4, 3, 1, 2]

#最大値の取り出し
print(_heappop_max(a)) #5
"""

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

okaiage = []
heapq._heapify_max(okaiage)
_heappush_max(okaiage, _heappop_max(a)/2)

m = M - 1
for j in range(N-1):
    temp_oka = _heappop_max(okaiage)
    temp_a = _heappop_max(a)
    #print(temp_oka, temp_a)
    if m > 0:
        if temp_a > temp_oka:
            _heappush_max(okaiage, temp_a/2)
            _heappush_max(okaiage, temp_oka)
        else:
            _heappush_max(okaiage, temp_a)
            _heappush_max(okaiage, temp_oka/2)
    else:
        _heappush_max(okaiage, temp_a)
        _heappush_max(okaiage, temp_oka)
    m -= 1
if m > 0:
    for i in range(m):
        temp_oka = _heappop_max(okaiage) / 2
        _heappush_max(okaiage, temp_oka)
#print(okaiage)
okaiage_kiri = [int(math.floor(_heappop_max(okaiage))) for i in range(N)]
#print(okaiage_kiri)
print(sum(okaiage_kiri))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
import numpy as np
N,M = (int(x) for x in input().split())
A = list(map(int, input().split()))
A.sort()
while M > 0:
    if A[N-1] >= A[N-2]:
        A[N-1] = A[N-1] / 2
        M -= 1
    else:
        temp = A[N-1]
        bisect.insort_left(A,temp)
        del A[-1]
B = np.floor(A)
print(int(np.sum(B)))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A,reverse = True)
dp = []
for _ in range(M):
  A[0] //= 2
  A = sorted(A,reverse = True)
print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
import bisect
 
N, M = map(int, input().split())
Ai = list(map(int, input().split()))
 
Ai.sort()
for _ in range(M):
    value = int(Ai.pop() / 2)
    bisect.insort(Ai, value)
 
print(sum(Ai))

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
for i in range(m):
  x=a.pop()//2
  bisect.insort_left(a, x, lo=0, hi=len(a))

print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
N, M=map(int, input().split())
A=list(map(int, input().split()))
def discount(lst):
    M=max(lst)
    A[A.index(M)]=M/2
    return lst
#print(A)
for i in range(M):

    A=discount(A)
    #print(A)
answer=list(map(int, A))
print(sum(answer))

Submission status: Time Limit Exceeded

Solution code:
import bisect

n, m = map(int, input().split())
a = map(int, input().split())
a = sorted(a)
for i in range(m):
  a[-1] = int(a[-1] / 2)
  tmp = a[:-1]
  p = bisect.bisect_left(tmp, a[-1])
  a = tmp[:p] + [a[-1]] + tmp[p:]
print(sum(a))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy

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

tmp_list = copy.copy(a_list)

ticket_list = np.zeros(n)

for i in range(m):
    max_value = max(tmp_list)
    max_index = tmp_list.index(max_value)
    ticket_list[max_index] += 1
    tmp_list[max_index] = a_list[max_index]//(2**(ticket_list[max_index]))

print(str(int(sum(tmp_list))))

#ans = 0
#for j in range(n):
#    ans += a_list[j] // (2**(ticket_list[j]))

#print(str(int(ans)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy

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

tmp_list = copy.copy(a_list)

ticket_list = np.zeros(n)

for i in range(m):
    max_value = max(tmp_list)
    max_index = tmp_list.index(max_value)
    ticket_list[max_index] += 1
    tmp_list[max_index] = a_list[max_index]//(2**(ticket_list[max_index]))

#print(ticket_list)

ans = 0
for j in range(n):
    ans += a_list[j] // (2**(ticket_list[j]))

print(str(int(ans)))

Submission status: Time Limit Exceeded

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

print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
def discount(base):
    return int(base/2)

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

for m in range(M):
    maxA = max(a_list)
    if(maxA == 0):
        break
    a_list[a_list.index(maxA)] = discount(maxA)
    
print(sum(a_list))

Submission status: Time Limit Exceeded

Solution code:
def discount(base):
    return int(base/2)

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

for m in range(M):
    a_list[a_list.index(max(a_list))] = discount(max(a_list))
print(sum(a_list))

Submission status: Time Limit Exceeded

Solution code:
def discount(base):
    return int(base/2)

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

for m in range(M):
    a_list[a_list.index(max(a_list))] = discount(max(a_list))
print(sum(a_list))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

sum=0

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

Submission status: Time Limit Exceeded

Solution code:
import bisect

n, m = map(int, input().split())
item = [int(a) for a in input().split()]
item.sort()
ans = 0

for _ in range(m):
    item_max = item.pop()
    bisect.insort_left(item, item_max / 2)

for i in item:
    ans += int(i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = (int(x) for x in input().split())
a = list(map(int,input().split()))

a.sort()

l = len(a) - 1
t = l
for i in range(M):
  t = l
  a[l] = a[l] // 2
  while a[t-1] > a[t]:
    tmp = a[t]
    a[t] = a[t-1]
    a[t-1] = tmp
    t -= 1
    if t==0:
      break;
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
x,y=list(map(int, input().split()))
z=list(map(int, input().split()))
t=0
for i in range(y):
	t=z.index(max(z))
	z[t]=z[t]//2
print(sum(z))

Submission status: Time Limit Exceeded

Solution code:
import math

[n,m] = [int(x) for x in input().split(" ")]
an = [int(x) for x in input().split(" ")]
an.sort(reverse=True)

for i in range(m):
    max_value = an[0]
    an[0] = max_value / 2
    an.sort(reverse=True)

discounted_an = [math.floor(x) for x in an]
print(sum(discounted_an))

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

for i in range(m) :
  heapq.heapify(a)
  at = -1*(-1*heapq.heappop(a)//2)
  heapq.heappush(a, at)

print(sum(a)*-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

for i in range(m) :
  heapq.heapify(a)
  at = -1*(-1*heapq.heappop(a)//2)
  heapq.heappush(a, at)

print(sum(a)*-1)

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) :
  a[n-1] = a[n-1]//2
  b = a[0:n-1]
  index = bisect.bisect_right(b,a[n-1])
  a.insert(index,a[n-1])
  del a[-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()

for i in range(m) :
  a[n-1] = a[n-1]//2
  b = a[0:n-1]
  index = bisect.bisect_right(b,a[n-1])
  if index == n-1 :
    continue
  at = a[index]
  a[index] = a[n-1]
  a[index+2:n] = a[index+1:n-1]
  a[index+1] = at

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) :
  index = a.index(max(a))
  a[index] = a[index]//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_max = max(a)
    a_max_i = a.index(a_max)
    new = int(a_max / 2) if not a_max == 0 else 0
    a[a_max_i] = new

print(int(sum(a)))

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] = int(a[n-1]//2)
  a.sort()

res = 0
for i in a:
  res += i
  
print(res)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from collections import deque
    n, m = map(int, input().split())
    a = deque(map(int, input().split()))
 
    for i in range(m):
        a = deque(sorted(a))
        maxa = a.pop()
        maxa //= 2
        a.appendleft(maxa)
    print(sum(a))
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from collections import deque
    n, m = map(int, input().split())
    a = deque(map(int, input().split()))

    for i in range(m):
        a = deque(sorted(a))
        maxa = a.pop()
        maxa //= 2
        a.appendleft(maxa)
    print(sum(a))
resolve()

Submission status: Time Limit Exceeded

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

    for i in range(m):
        a = sorted(a, reverse = True)
        a[0] = a[0]//2
    print(sum(a))
resolve()

Submission status: Time Limit Exceeded

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

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    used = 0
    while used < M:
        ma = max(A)
        idx = A.index(ma)
        A[idx] = A[idx] // 2
        used += 1
    print(sum(A))


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    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))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
import numpy as np
N, M = map(int,input().split())
A = list(map(int,input().split()))
A = np.array(A)
A = -A
A = list(A)
for _ in range(M):
    heapify(A)
    s = heappop(A)
    heappush(A, -(-s // 2))
A = np.array(A)
print(-int(np.sum(A)))

Submission status: Time Limit Exceeded

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

for i in range(d):
    t = a.index(max(a))
    a[t] //= 2
    if max(a) == 0:
        break
print(sum(a))

Submission status: Time Limit Exceeded

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


while M>0:
    mylist.sort(reverse=True)
    mylist[0]/=2
    M-=1
    
mylist=[math.floor(i) for i in mylist]
#print(mylist)
print(sum(mylist))

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
a = LIST()
for i in range(m):
    aa = max(a)
    idx = a.index(aa)
    a[idx] //= 2
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
a = LIST()
for i in range(m):
    a.sort(reverse=True)
    a[0] //= 2
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

import bisect

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

for _ in range(M):
    a = A.pop()
    a = a / 2
    bisect.insort_right(A, a)
    
print(sum([int(x) for x in A]))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

import bisect
import copy

N, M = map(int, input().rstrip().split())
A = list(map(int, input().rstrip().split()))
A = sorted(A)
ori_A = copy.copy(A)
maisu = [0] * N

for i in range(M):
    _, b, c = A.pop(), ori_A.pop(), maisu.pop()
    a = b // 2 ** (c + 1)
    idx = bisect.bisect_right(A, a)
    A.insert(idx, a)
    ori_A.insert(idx, b)
    maisu.insert(idx, c + 1)
    
print(sum(A))

Submission status: Time Limit Exceeded

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

for _ in range(0, M, 1):
	A[0] >>= 1
	for i in range(1, len(A), 1):
		if A[i - 1] < A[i]:
			A[i], A[i - 1] = A[i - 1], A[i]
		else:
			break

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(0, M, 1):
	A.sort(reverse = True)
	A[0] >>= 1

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(0, M, 1):
	A[A.index(max(A))] >>= 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)
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()))

import bisect

for i in range(M):
  M = max(A)
  A.remove(M)
  x = M//2
  A.append(x)
print(sum(A))

Submission status: Time Limit Exceeded

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

import bisect

for i in range(M):
  x = A[-1]//2
  insert_index = bisect.bisect_left(A[:-1],x)
  A = A[:-1] 
  A.insert(insert_index,x)
print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = [int(c) for c 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:
import bisect
import sys
input = sys.stdin.readline

def main():

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

    while M > 0:
        tmp = A.pop()
        tmp = tmp // 2
        bisect.insort_right(A, tmp)
        M -= 1
    print(sum(A))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math
import bisect

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

while M > 0:
    tmp = A.pop()
    tmp = tmp // 2
    index = bisect.bisect_right(A, tmp)
    A.insert(index, tmp)
    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(key = lambda x: -x)

if n == 1:
    print(a[0]//2**m)
    exit()

# idx = 0
while m > 0:
    a[0] //= 2
    idx = 0
    m -= 1
    if m <= 0: break
    while idx < n-1 and a[idx] < a[idx+1]:
        a[idx], a[idx+1] = a[idx+1],a[idx]
        idx += 1
    # idx = 0

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:
  u=max(a)
  a[a.index(u)]=u//2
  m=m-1
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))]=max(a)//2
  m=m-1
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [-i for i in a]
heapq.heapify(a)
for i in range(m):
    c = heapq.heappop(a)
    c = -c // 2
    heapq.heappush(a, -c)
    if sum(a) == 0:
        break
print(-sum(a))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for k in range(N):
    A[k]=-A[k]

for i in range(M):
    heapq.heapify(A)
    A[0] = -(-A[0] // 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] = 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()))

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

print(sum(A))

Submission status: Time Limit Exceeded

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

a = sorted(list(map(int,input().split())),reverse=True)
for i in range(m):
    a[0] = a[0]/2
    a = sorted(a,reverse=True)
print(sum(list(map(int,a))))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
A = [int(i) for i in input().split()]
 
A.sort(reverse=True)
 
def bisect(A,x):
  lo = -1
  hi = len(A)
  while lo+1 < hi:
    idx = (lo+hi)//2
    if A[idx] > x:
      lo = idx
    else:
      hi = idx
  return lo
 
for i in range(m):
  v = A.pop(0)//2
  idx = bisect(A,v)+1
  A = A[:idx] + [v] + A[idx:]

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(reverse=True)

def bisect(A,x):
  lo = -1
  hi = len(A)
  while lo+1 < hi:
    idx = (lo+hi)//2
    if A[idx] > x:
      lo = idx
    else:
      hi = idx
  return lo

for i in range(m):
  v = A.pop(0)//2
  idx = bisect(A,v)+1
  A = A[:idx] + [v] + A[idx:]

print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
f = lambda:map(int,input().split())
n,m = f()
l = sorted(f())
for _ in range(m):
  l.append(l.pop()//2)
  l.sort()
print(sum(l))

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))]//=2
print(sum(A))

Submission status: Time Limit Exceeded

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

A = sorted(A)
for i in range(m):
    a = A[-1]//2
    A = A[:-1]
    A.append(a)
    A = sorted(A)
print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
pq = []
for i in range(n):
    pq.append((-a[i], -a[i], 0))
heapq.heapify(pq)
for i in range(m):
    mx = heapq.heappop(pq)
    if -mx[1] < (2 ** (mx[2] + 1)): heapq.heappush(pq, (0, mx[1], mx[2] + 1))
    else: heapq.heappush(pq, (-(-mx[1] // (2 ** (mx[2] + 1))), mx[1], mx[2] + 1))
ans = 0
while len(pq) != 0:
    ans -= heapq.heappop(pq)[0]
print(ans)
"""
import heapq
a = [(3, 0), (1, 0), (2, 2), (6, 4)]
#listのheap化
#heapはsortではないので順番は割とあべこべになる。最小値は先頭
heapq.heapify(a)
print(a)

#挿入
heapq.heappush(a, (3, 3))
print(a)

#最小値を削除&出力
print(heapq.heappop(a))
print(a)
"""