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()))
for i in range(m):
  a[a.index(max(a))]//=2
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 i in range(m):
  t=a[-1]
  t//=2
  a.pop()
  bisect.insort_left(a,t)
  #print(i,a)
print(sum(a))

Submission status: Time Limit Exceeded

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

while m>0:
    max_value = max(a)
    max_index = a.index(max_value)
    a[max_index]=max_value/2
    m-=1
a=[int(x) for x in a]
print(sum(a))

Submission status: Time Limit Exceeded

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

i=0
while m>0:
    a.sort(reverse=True)
    a[0]=a[0]/2
    m-=1
a=[int(x) for x in a]
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

As.sort()

#print(As)

for _ in range(M):
    discount = As.pop(-1)

    if(discount == 0):
        break

    discount //= 2

    i = bisect.bisect_left(As, discount)
    As.insert(i, discount)
#    print(As)

print(sum(As))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

As.sort()

#print(As)

for _ in range(M):
    discount = As.pop(-1) // 2

    i = bisect.bisect_left(As, discount)
    As.insert(i, discount)
#    print(As)

print(sum(As))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

As.sort()

#print(As)

for _ in range(M):
    discount = As.pop(-1) // 2

    bisect.insort_left(As, discount)
#    print(As)

print(sum(As))

Submission status: Time Limit Exceeded

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

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

print(sum(prices))

Submission status: Time Limit Exceeded

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 i in range(M):
    a = A.index(max(A))
    A[a] = int(A[a]/2)

print(sum(A))

Submission status: Time Limit Exceeded

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

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

for i in range(M):
    a = A.index(max(A))
    A[a] = int(A[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()

for i in range(m):
    a.append(a[-1]/2)
    del a[-2]
    a.sort()

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

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.append(a[0]/2)
    del a[0]
    a.sort(reverse = True)
    
ans = 0
for i in range(n):
    ans += int(a[i])
print(ans)

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.sort(reverse = True)
        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 _ in range(M):
    max_i = A.index(max(A))
    A[max_i] >>= 1

print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
import math

n, m = map(int, input().split())
A = list(map(int, input().split()))
a = sorted(A, reverse = True)
cnt = 0
ans = 0
while cnt < m:
    max_a = max(a)
    for i in range(n):
        if cnt == m:
            break
        if a[i] == max_a:
            cnt += 1
            a[i] = a[i]/2
for j in a:
    ans += math.floor(j)

print(ans)

Submission status: Time Limit Exceeded

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

out=sum(A)
for i in range(M):
    saidai = max(A)
    out-=saidai
    out+=saidai//2
    A[A.index(saidai)] = saidai//2
    # print('dam,out:',saidai,out)

print(out)

Submission status: Time Limit Exceeded

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

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

print(sum(price))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

items_number, tickets_number = map(int, input().split())
item_prices = list(map(int, input().split()))

for i in range(tickets_number):
  max_item_price_index = item_prices.index(max(item_prices))
  discounted_price = item_prices[max_item_price_index] // 2
  item_prices[max_item_price_index] = discounted_price

 

print(sum(item_prices))

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M=map(int,input().split())
a=list(map(int,input().split()))
heapq.heapify(a)
for _ in range(M):
    a = list(map(lambda x: x * (-1), a))  # 各要素を-1倍
    heapq.heapify(a)  # リストを優先度付きキューへ
    number=heapq.heappop(a) * (-1) # 最大値の取り出し
    a = list(map(lambda x: x * (-1), a))  # 各要素を-1倍
    heapq.heappush(a, number//2)  # 要素の挿入
print(sum(a))

Submission status: Time Limit Exceeded

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

if n == 1:
  print((a[0]//(2**m)))
else:
  while m > 0:
    a.sort()
    if a[n-1] == 0:
      break
    if a[n-2] != 0:
      b = a[n-1] // a[n-2]
      a[n-1] = a[n-1] // (2**b) 
      m -= b
  print(sum(a))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

while m > 0 :
  ans1 = a.sort()
  a[n-1] = a[n-1] // 2 
  m -= 1

for i in range(n):
  ans += a[i]

print(ans)

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]//=2
    A.sort(reverse=True)
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 = A.pop(0) // 2
  f = 0
  for j in range(N-2):
    if A[j] >= a >= A[j+1]:
      A.insert(j+1, a)
      f = 1
      break
  if f == 0:
    A.append(a)
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))] = max(a)//2
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
def discount(money):
    return money//2

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

dic = {}
for i in range(n):
    dic.setdefault(a[i],0)
    dic[a[i]] += 1
#print(dic)

while m>0:
    tmp = max(dic.keys())
    while m>0 and dic[tmp]>0:
        money = discount(tmp)
        dic[tmp] -= 1
        dic.setdefault(money,0)
        dic[money] += 1
        m -= 1
    if dic[tmp]==0:
        del dic[tmp]
ans = 0
for item in dic.items():
    ans += item[0] * item[1]
#print(dic)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import log

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

a = sorted(a, reverse=True)
flag = True

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


while flag == True:
  index = 0
  if a[0]/2 < a[n-1]:
    index = n
  else:
    for i in range(1, n):
      if a[0]/2 > a[i]:
        index = i
        break
  if index < m:
    for i in range(index):
      a[i] //= 2
    a = sorted(a, reverse=True)
    m -= index
  else:
    for i in range(m):
      a[i] //= 2
    flag = False

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

while flag == True:
  index = 0
  if a[0]/2 < a[n-1]:
    index = n
  else:
    for i in range(1, n):
      if a[0]/2 > a[i]:
        index = i
        break
  if index < m:
    for i in range(index):
      a[i] //= 2
    a = sorted(a, reverse=True)
    m -= index
  else:
    for i in range(m):
      a[i] //= 2
    flag = False

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

while flag == True:
  index = 0
  if a[0]/2 < a[n-1]:
    index = n
  else:
    for i in range(1, n):
      if a[0]/2 > a[i]:
        index = i
        break
  if index < m:
    b = [a[i]//2 for i in range(index)]
    b.extend(a[index:])
    a = b
    a = sorted(a, reverse=True)
    m -= index
  else:
    b = [a[i]//2 for i in range(m)]
    b.extend(a[m:])
    a = b
    flag = False

print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import deque
n,m=map(int,input().split())
A=list(map(int,input().split()))
#print(A)
for i in range(n):
    A[i]*=-1
#print(A)

for i in range(m):
    heapq.heapify(A)
    x=heapq.heappop(A)
    #print(x,A)
    if x%2==0:
        x//=2
    else:
        x=x//2 +1
    heapq.heappush(A,x)
    #print(A)
ans=-1*sum(A)
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(m):
    bisect.insort(a, a.pop()//2)

print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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


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

print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
import sys

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))
  sys.exit()


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

print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
import sys

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))
  sys.exit()


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

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):
  b = max(a)
  a.remove(max(a))
  a.append(b//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 = sorted(a)[::-1]
    a[0] //= 2

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 i in range(m):
    x = a.pop() // 2
    bisect.insort_right(a, 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(reverse=True)
for i in range(0,M):
    A[0]=int(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()))
A.sort()
for i in range(0,M):
    A[N-1]=int(A[N-1]/2)
    A.sort()
count=0

print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
import math

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

d = {}
for i, a in enumerate(aL):
    if a in d:
        d[a].append(i)
    else:
        d[a] = [i]

cnt = 0
while True:
    if len(d) == 0:
        break
    dMax = max(d)
    while True:
        if cnt == m:
            ans = 0
            for k, v in d.items():
                ans += k * len(v)
            print(ans)
            exit()
        nxt = d[dMax].pop(0)

        if (dMax // 2) in d:
            d[dMax // 2].append(nxt)
        else:
            d[dMax // 2] = [nxt]

        cnt += 1

        if len(d[dMax]) == 0:
            del d[dMax]
            break

ans = 0
for k, v in d.items():
    ans += k * len(v)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
g = list(map(int, input().split()))
d = 0
for i in range(k):
    d = max(g)
    idx = g.index(d)
    d //= 2
    g[idx] = d
print(sum(g))

Submission status: Time Limit Exceeded

Solution code:
import math

n, m = map(int, input().split(" "))
aL = sorted(list(map(int, input().split(" "))), reverse=True)

for i in range(m):
    aL[0] //= 2
    for i in range(1, n):
        if aL[0] > aL[i]:
            aL = aL[1:i] + [aL[0]] + aL[i:]
            break

print(sum(aL))

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

print(sum(aL))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(M):
  i = A.index(max(A))
  A[i] = A[i]//2
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):
  i = A.index(max(A))
  A[i] = A[i]/2
ans = 0
for i in range(N):
  ans += int(A[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    n, m = MI()
    a = LI()
    if n == 1:
        while m > 0:
            a[0] = a[0] // 2
            m -= 1
        print(a[0])
        return
    a.sort()
    a.reverse()
    while m > 0:
        while a[0] >= a[1]:
            a[0] = a[0] // 2
            m -= 1

        a.sort()
        a.reverse()
    print(sum(a))


main()

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A,reverse=True)
for i in range(M):
    maxindex = A.index(max(A))
    A[maxindex] = A[maxindex]//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):
    maxindex = A.index(max(A))
    A[maxindex] = A[maxindex]//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 = sorted(A,reverse=True)
    A[0] = A[0]//2
print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify,heappush,heappop

def main():
    N,M = map(int,input().split())
    A = [ -x for x in map(int,input().split()) ]

    for i in range(M):
        heapify(A)
        #print(A)
        tmp = -heappop(A)
        #print(tmp)
        tmp = tmp//2
        #print(tmp)
        heappush(A,-tmp)


    ans = 0
    for i in range(N):
        ans += A[i]

    ans = abs(ans)
    return ans

print(main())

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
ans = sum(a[min(n, m):])
a = a[:min(n, m)]

if len(a) == 1 and n == 1:
    print(a[0]//2**m)
elif len(a) == 1:
    print(a[0]//2**m+ans)
else:
    for i in range(m):
        a[0] //= 2
        a = sorted(a, reverse=True)
    print(ans+sum(a))

Submission status: Time Limit Exceeded

Solution code:
import heapq
from fractions import Fraction

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

a = list(map(lambda x: Fraction(1, int(x)), input().split()))

heapq.heapify(a)

for i in range(m):
    x = heapq.heappop(a)
    heapq.heappush(a, Fraction(x.numerator * 2, x.denominator))

s = 0


for j in range(n):
    s += int(Fraction(a[j].denominator, a[j].numerator))

print(s)

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
  for j in range(1,n):
    if a[0]>a[j]:
      a.insert(j,a[0])
      del a[0]
      break
import math
ans=0
for i in range(n):
  ans=ans+math.floor(a[i])
print(ans)

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(reverse=True)
  a[0]=a[0]/2
import math
ans=0
for i in range(n):
  ans=ans+math.floor(a[i])
print(ans)

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:
import bisect
N, M = map(int, input().split())
A = sorted(map(int, input().split()))
for _ in range(M):
    x = A.pop()
    y = x // 2
    i = bisect.bisect_left(A, y)
    A.insert(i, y)
ans = sum(A)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
    num=max(a)
    a.remove(num)
    a.append(num//2)
print(sum(a))

Submission status: Time Limit Exceeded

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

from bisect import insort_right
from collections import deque

n, m, *a = map(int, open(0).read().split())

a = deque(sorted(a))
for _ in range(m):
    insort_right(a, a.pop() >> 1)
print(sum(a))

Submission status: Time Limit Exceeded

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

from bisect import insort_right

n, m, *a = map(int, open(0).read().split())

a.sort()
for _ in range(m):
    insort_right(a, a.pop() >> 1)
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:
import numpy as np
N, M = map(int, input().split())
A_list = list(map(int, input().split()))
A_ar = np.array(A_list)
for i in range(M):
    max_pos = np.argmax(A_ar)
    A_ar[max_pos] = A_ar[max_pos]//2
print(sum(A_ar))

Submission status: Time Limit Exceeded

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

B.append(A.pop(0)//2)
for i in range(1,M):
    if A == []:
        B[0] = B[0]//2
        B = sorted(B, reverse=True)
    else:
        if A[0] > B[0]:
            B.append(A.pop(0)//2)
        else:
            B[0] = B[0]//2
            B = sorted(B, reverse=True)

print(sum(A)+sum(B))

Submission status: Time Limit Exceeded

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

for i in range(m):
  a.sort()
  tmp = a[-1] // 2
  a.pop()
  #bisect.insort(a,tmp)
  a.append(tmp)
  

print(sum(a))

Submission status: Time Limit Exceeded

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

for i in range(m):
  tmp = a[-1] // 2
  a.pop()
  bisect.insort(a,tmp)

print(sum(a))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(m):
  tmp = a[-1] // 2
  a.pop(-1)
  bisect.insort(a,tmp)

print(sum(a))

Submission status: Time Limit Exceeded

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

for i in range(m):
  a.sort(reverse=True)
  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()))
ticket_num = m
a_sorted = sorted(a, reverse=True)

if n > 1:
    while ticket_num > 0:
        first = a_sorted[0]
        second = a_sorted[1]
        fi_bin = bin(first)
        se_bin = bin(second)
        sa = len(fi_bin)-len(se_bin)
        if sa == 0:
            sa = 1
        first = first >> sa
        ticket_num -= sa
        if first == second:
            first = first >> 1
            ticket_num -= 1
        index = 1
        while index < n and a_sorted[index] > first:
            index += 1
        a_sorted[:index-1] = a_sorted[1:index]
        a_sorted[index-1] = first
else:
    a_sorted[0] = a_sorted[0]>>m

print(sum(a_sorted))

Submission status: Time Limit Exceeded

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

if n > 1:
    while ticket_num > 0:
        first = a_sorted[0]
        second = a_sorted[1]
        fi_bin = bin(first)
        se_bin = bin(second)
        sa = len(fi_bin)-len(se_bin)
        if sa == 0:
            sa = 1
        first = first >> sa
        ticket_num -= sa
        if first == second:
            first = first >> 1
            ticket_num -= 1
        a_sorted[0] = first
        a_sorted.sort(reverse=True)
else:
    a_sorted[0] = a_sorted[0]>>m

print(sum(a_sorted))

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M = map(int,input().split())
list_A = list(map(lambda x: int(x)*(-1),input().split()))	

#print(list_A)

for i in range(M):
  heapq.heapify(list_A)
  target = heapq.heappop(list_A)
  #print("after heappop",list_A)
  
  '''負の要素の切り捨て除算は切り捨てがマイナスの方に
  行くため少しだけややこしい。'''
  heapq.heappush(list_A, (-1)*((-target) // 2))  # 要素の挿入
  #print("No.",i,"change finished",list_A)

print(-sum(list_A))

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M = map(int,input().split())
list_A = list(map(lambda x: int(x)*(-1),input().split()))	

#print(list_A)

for i in range(M):
  heapq.heapify(list_A)
  target = heapq.heappop(list_A)
  #print("after heappop",list_A)
  
  '''負の要素の切り捨て除算は切り捨てがマイナスの方に
  行くため少しだけややこしい。'''
  target = -1*((-1 *target) // 2)
  
  heapq.heappush(list_A, target)  # 要素の挿入
  #print("No.",i,"change finished",list_A)

print(sum(list_A)*-1)

Submission status: Time Limit Exceeded

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

list_A = list(map(lambda x: x*(-1), list_A))

#print(list_A)

for i in range(M):
  heapq.heapify(list_A)
  target = heapq.heappop(list_A)
  #print("after heappop",list_A)
  
  '''負の要素の切り捨て除算は切り捨てがマイナスの方に
  行くため少しだけややこしい。'''
  target = -1*((-1 *target) // 2)
  
  heapq.heappush(list_A, target)  # 要素の挿入
  #print("No.",i,"change finished",list_A)

print(sum(list_A)*-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
 
N,M = map(int,input().split())
Price_List = list(map(lambda x:x*(-1),map(int,input().split())))
heapq.heapify(Price_List)
for i in range(M):
    heapq.heapify(Price_List)
    val = heapq.heappop(Price_List)* -1 // 2 * -1
    heapq.heappush(Price_List,val)
print(-sum(Price_List))

Submission status: Time Limit Exceeded

Solution code:
import bisect
 
N,M = map(int,input().split())
Price_List = list(map(int,input().split()))
Price_List.sort()
for i in range(M):
    New_Price = Price_List.pop(-1)//2
    Price_List.insert(bisect.bisect(Price_List,New_Price),New_Price)
print(sum(Price_List))

Submission status: Time Limit Exceeded

Solution code:
import bisect

N,M = map(int,input().split())
Price_List = list(map(int,input().split()))
Price_List.sort()
for i in range(M):
    New_Price = Price_List.pop(-1)
    Price_List.insert(bisect.bisect(Price_List,New_Price//2),New_Price//2)
print(sum(Price_List))

Submission status: Time Limit Exceeded

Solution code:
import bisect

def ceil_number(n):
    return math.floor(n)

N,M = map(int,input().split())
Price_List = sorted(list(map(int,input().split())))
for i in range(M):
    New_Price = Price_List.pop(-1)
    Price_List.insert(bisect.bisect(Price_List,New_Price//2),New_Price//2)
print(sum(Price_List))

Submission status: Time Limit Exceeded

Solution code:
import heapq

N,M = map(int,input().split())
Price_List = list(map(lambda x:x*(-1),map(int,input().split())))
heapq.heapify(Price_List)
for i in range(M):
    heapq.heapify(Price_List)
    val = heapq.heappop(Price_List)* -1 // 2 * -1
    heapq.heappush(Price_List,val)
print(-sum(Price_List))

Submission status: Time Limit Exceeded

Solution code:
import math
import heapq

N,M = map(int,input().split())
Price_List = list(map(lambda x:x*(-1),map(int,input().split())))
heapq.heapify(Price_List)
for i in range(M):
    heapq.heapify(Price_List)
    val = heapq.heappop(Price_List)/2
    heapq.heappush(Price_List,val)
print(sum(map(lambda x:math.floor(x*(-1)),Price_List)))

Submission status: Time Limit Exceeded

Solution code:
def main():
    item_no, discount_no = [int(x) for x in input().split()]
    prices = [int(x) for x in input().split()]

    for _ in range(discount_no):
        prices.sort(reverse=True)
        prices[0] //= 2

    print(sum(prices))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect

def ceil_number(n):
    return math.floor(n)

N,M = map(int,input().split())
Price_List = sorted(list(map(int,input().split())))
for i in range(M):
    New_Price =  Price_List[-1]/2
    Price_List.pop(-1)
    Price_List.insert(bisect.bisect(Price_List,New_Price),New_Price)
print(sum(map(ceil_number,Price_List)))

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect
N,M = map(int,input().split())
Price_List = sorted(list(map(int,input().split())))
for i in range(M):
    New_Price =  Price_List[-1]/2
    Price_List.pop(-1)
    Price_List.insert(bisect.bisect(Price_List,New_Price),New_Price)
print(sum(map(lambda x:math.floor(x),Price_List)))

Submission status: Time Limit Exceeded

Solution code:
import math
N,M = map(int,input().split())
Price_List = sorted(list(map(int,input().split())))
for i in range(M):
    Price_List[-1] = Price_List[-1]/2
    Price_List = sorted(Price_List)
print(sum(map(lambda x:math.floor(x),Price_List)))

Submission status: Time Limit Exceeded

Solution code:
import math
N,M = map(int,input().split())
Price_List = list(map(int,input().split()))
for i in range(M):
    Price_List[Price_List.index(max(Price_List))] = Price_List[Price_List.index(max(Price_List))]/2
print(sum(map(lambda x:math.floor(x),Price_List)))

Submission status: Time Limit Exceeded

Solution code:
import math
N,M = map(int,input().split())
Price_List = list(map(int,input().split()))
for i in range(M):
    Price_List[Price_List.index(max(Price_List))] = Price_List[Price_List.index(max(Price_List))]/2
print(sum(map(lambda x:math.floor(x),Price_List)))

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(reverse=True)
  a[0]=a[0]/2
ans=0
for i in range(n):
  ans+=int(a[i])
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, M = [int(x) for x in input().split()]
A = list([int(x) * - 1 for x in input().split()])

while M > 0:
    heapq.heapify(A)
    count = (heapq.heappop(A) * -1 // 2) * -1

    heapq.heappush(A, count)
    M -= 1

print(sum(A) * -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

stack = deque()
stack.appendleft((0, M, 0))

min_money = 10**9*10**5

while stack:
    i_t = stack.popleft()
    item_number = i_t[0]
    tickets = i_t[1]
    need_money = i_t[2]

    for use_tickets in range(tickets+1):
        if item_number + 1 <= N:
            money = A[item_number] // 2**use_tickets
            stack.appendleft((item_number+1, tickets-use_tickets,
                              need_money + money))

        else:
            min_money = min(need_money, min_money)

        if money == 0:
            break

print(min_money)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,M = map(int, input().split())
A = sorted(map(int, input().split()))
for i in range(M):
    bisect.insort(A, A.pop()//2)
print(sum(A))

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):
    A[A.index(max(A))] = max(A)/2

for i in range(N):
    A[i] = math.floor(A[i])

print(int(sum(A)))

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

for i in range(N):
    A[i] = math.floor(A[i])

print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for _ in range(M):
    x=math.floor(A.pop(N-1)/2)
    bisect.insort(A,x)
print(sum(A))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

N,M = (int(x) for x in input().rstrip('\n').split())
As = [int(x) for x in input().rstrip('\n').split()]
ad = {x:As.count(x) for x in set(As)}
for _ in range(M):
  m = max(ad.keys())
  ad[m] -= 1
  if ad[m]==0:
    del ad[m]
  if m//2 in ad:
    ad[m//2] += 1
  else:
    ad[m//2] = 1
print(sum(x*y for x,y in ad.items()))