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: Wrong Answer

Solution code:
import math
import sys
log2 = math.log2
n,m = map(int,input().split())
l = sorted(list(map(int,input().split())))
l.reverse()
if n == 1:
  print(l[0]//(2**m))
  sys.exit()
  
yl = [0]*n
flag = False
logl = [int(log2(i)) for i in l]
ans = 0
while True:
  for i in range(n-1):
    if logl[i]>logl[i+1]:
      logl[i] -= 1
      yl[i] += 1
      m -= 1
      if m == 0:
        flag = True
        break
  if flag:
    break
for i,j in zip(l,yl):
  ans += i//(2**j)
print(ans)

Submission status: Wrong Answer

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

n = 0
for _ in range(M):
    B[n] *= 2
    if n == N-1 or A[n]//B[n] >= A[n+1]:
        n = 0
    else:
        n += 1

print(sum([A[i]//B[i] for i in range(N)]))

Submission status: Wrong Answer

Solution code:
import sys
import math
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))[::-1]
max = math.floor(math.log2(a[0]))
counter = 0
for i in range(max,-2,-1):
    for j in range(n):
        if a[j] > 2**i:
            a[j] = math.floor(a[j]/2)
            counter += 1
            if counter >= m:
                print(sum(a))
                sys.exit()
        else:
            break
print(sum(a))

Submission status: Wrong Answer

Solution code:
import math


def change(B):
    for i in range(len(B)-1):
        if B[i] < B[i+1]:
            tmp = B[i]
            B[i] = B[i+1]
            B[i+1] = tmp
        else:
            return B
    return B

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

A = list(reversed(sorted(A)))

B = []
for a in A:
  B.append(float(math.log(a,2)))

for _ in range(M):
    B[0] -= 1
    if len(B) != 1:
        B = change(B)
cnt = 0
for b in B:
    cnt += math.floor(2**b)
  
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys,math
sys.setrecursionlimit(100000)

def ins(): return input().split()
def ii(): return int(input())
def iil(): return list(map(int,ins()))
def lin(): return list(input())
def iin(): return map(int,ins())

n, m=iin()
a = iin()
t = [[] for _ in range(30)]
for i in a:
    for j in range(30):
        if i < 2**(j+1):
            t[j].append(i)
            break
print(t)
t.reverse()
t.append([])
for i,j in enumerate(t):
    if len(j)<m:
        m -= len(j)
        try:
            t[i+1]+= list(map(lambda x:x/2,j))
        except IndexError:
            print(0)
            sys.exit()
    else:
        j.sort()
        for k in range(m):
            j[-1] /= 2
            j.sort()
        ans = 0
        for l in t[i:]:
            for r in l:
                ans += math.floor(r)
        print(ans)
        sys.exit()

Submission status: Wrong Answer

Solution code:
from collections import deque

#n:shinamono no kazu
#m:waribiki maisuu

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

a=sorted(list(map(int,input().split())))[::-1]

for _ in range(m):
  maxA=a[0]
  
  if len(a)>1:
    nextMaxA=a[1]
    if maxA/2.0>nextMaxA:
      a[0]=maxA/2.0
      a[1]=nextMaxA
    else:
      a[1]=maxA/2.0
      a[0]=nextMaxA
  else:
    a[0]=maxA/2.0

#print(a)
result=0
for item in a:
  result+=item//1
  
print(int(result))

Submission status: Wrong Answer

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

ticket = [M]+[0 for _ in range(N-1)]
#print(ticket)
price = [B[i]//(2**ticket[i]) for i in range(N)]
#print(price,sum(price))
p_sum = sum(price)
i = 0
while i < N-1:
    ticket[i]-=1
    ticket[i+1]+=1
    price = [B[i]//(2**ticket[i]) for i in range(N)]
    p_s = sum(price)
    #print(i,ticket,p_s)
    if p_s < p_sum:
        p_sum = p_s
    else:
        #next
        i += 1
print(p_sum)

Submission status: Wrong Answer

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

INF = float("inf")
dp = [[0,] * (M+1)]

for x in vA:
    nDP = [INF,] * (M+1)
    for j in range(0, M+1):
        xReduce = x
        for t in range(M+1-j):
            if xReduce == 0:
                nDP[j+t:] = nDP[j+t:]
                break
            nDP[j+t] = min(nDP[j+t], dp[-1][j] + xReduce)
            xReduce //= 2
    dp.append(nDP)

#print(dp)###
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
import bisect

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

a.sort

for i in range(m):
  x=a.pop(n-1)/2
  insert_index = bisect.bisect_left(a,x)
  a.insert(insert_index,x)


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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math
N,M=list(map(int,input().split()))
A=list(map(lambda x: math.log(int(x),2),input().split()))
#rec(N-1,M)
res=dict(Counter(A))
while M>0:
    #ex=max(list(map(float,res.keys())))
    ex=max(res.keys())
    n=res[ex]
    if (2**ex)//2>0:
        val=math.log((2**ex)//2,2)
    else:
        val=-2
    if n<=M:
        M-=n
        del res[ex]
        
        if val in res.keys():
            res[val]+=n
        else:
            res[val]=n
            
        
    else:
        n=M
        res[ex]-=n
        if val in res.keys():
            res[val]+=n
        else:
            res[val]=n
        M=0
    
ans=0
for i in res.keys():
    ans+=int(math.floor(2**i)*res[i])
print(int(ans))

Submission status: Wrong Answer

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

a = sorted(a)

if len(a) == 1:
    for j in range(m):
        a[0] = a[0] // 2
else:
    for j in range(m):
        max = a.pop(n-1)
        max = max // 2
        for i in range(n-2, -2, -1):
            if i == -1 or a[i] <= max:
                a.insert(i+1, max)

print(sum(a))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

#print(an)
for i in range(m):
    an[0] = an[0] // 2
    for ii in range(1, n-1):
        if an[0] < an[ii]:
            if an[0] < an[ii+1]:
                continue
            else:
                an[0], an[ii] = an[ii], an[0]
                break
        else:
            break
    #print(an)

print(sum(an))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import math
import bisect

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
if N > M:
  A_small = A[0:M]
  A = A[M:]
else:
  A_small = []

for i in range(M):
  if (len(A) > 1 and A[-1] < A[-2]):
    a = A.pop(-1)
    bisect.insort(A, a)
  A[-1] /= 2.0

A.extend(A_small)
amount = 0
for a in A:
  amount += math.floor(a)
print(amount)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = [int(i) for i in input().split()]
ans = sum(a)
a.sort()
a.reverse()
a = [0,0] + a + [0,0]
k = 2
for i in range(m):
    ans -= -(-a[k]//2)
    if ans == 0:
        break
    a[k] = a[k]//2
    k = k+max(enumerate(a[k-2:k+3]),key = lambda x:x[1])[0]-2
print(ans)

Submission status: Wrong Answer

Solution code:
#one = input()
#two = input()

one = '3 3'
two = '2 13 8 12'

N, M = map(int, one.split())
Ar = map(int, two.split())
Ar = sorted(Ar , reverse=True)

for i in range(M):
    Ar[0] = Ar[0] / 2
    # Ar = sorted(Ar , reverse=True)
    for i in range(len(Ar)):
        if Ar[i] < Ar[i+1]:
            temp = Ar[i]
            Ar[i] = Ar[i+1]
            Ar[i+1] = temp
        else:
            break


Ar = map(int, Ar)
print(sum(Ar))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

for i in range(m):
    p = max(a_list)
    a_list.remove(p)
    a_list.append(round(p / 2))
    
print(sum(a_list))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
use = 0
X = max(A)
Y = A.index(max(A))
for i in range(N):
    if use == M:
        break
    else:
        for j in range(M):
            if use == M:
                break
            elif A[Y]!= max(A):
                X = max(A)
                Y = A.index(max(A))
                break
            else:
                A[Y] = A[Y]//2
                use += 1
print(sum(A))

Submission status: Wrong Answer

Solution code:
import numpy as np

N,M=map(int,input().split())
# N,M=4,4
A = list(map(int,input().split()))
#dymmy
A.append(-1)
# A=[1,9,3,5]
# print(np.argmax(A))

# print(N,M,A)
Val = sorted(A,reverse=True)
# print("割引前",Val)

#Ｍ枚の商品券を持っているため
hoge =Val[0]

if N==1:
    print(Val[0]//(2**M))
    exit(0)
if M==1:
    Val[0]//=2
    print(sum(Val)+1)
    exit(0)
# for i in range(M):
#     # A[np.argmax(A)]= A[np.argmax(A)]//2
#     Val[0]//=2
#     for i in range(1,M):
#         if Val[0]<Val[i]:
#             Val[0],Val[i] = Val[i],Val[0]
#             break
#         else:
#             pass
i=0
while i<M:
    # A[np.argmax(A)]= A[np.argmax(A)]//2
    i+=1
    Val[0]//=2
    if i>=M:
        break
    for j in range(1,M):
        if Val[0]<Val[j]:
            Val[j]//=2
            i+=1
        else:
            Val = sorted(Val,reverse=True)
            break
    

# print(Val)
print(sum(Val)+1)

Submission status: Wrong Answer

Solution code:
import sys
import math
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))[::-1]
max = math.floor(math.log2(a[0]))
counter = 0
for i in range(max,0,-1):
    for j in range(n):
        if a[j] > 2**i:
            a[j] = math.floor(a[j]/2)
            counter += 1
            if counter >= m:
                print(sum(a))
                sys.exit()
        else:
            break
if a[0] == 1:
    print(0)
    sys.exit()
print(sum(a))

Submission status: Wrong Answer

Solution code:
# import heapq
# import collection
# import bisect
# import numpy


def binary_search(arry, target):
    result = None
    left = 0
    right = len(arry) - 1

    while left <= right:
        mid = (left + right) // 2
        if arry[mid] == target:
            result = mid
            break
        elif arry[mid] > target:
            right = mid - 1
        else:
            left = mid + 1

    # print(left, right)
    if result is None:
        return left
    else:
        return result


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

A = sorted(A)

# A = [i for i in range(10**5)]
# M = 10**5

while M > 0:
    index = binary_search(A, A[N-1] // 2)
    for i in range(index+1):
        if M <= 0:
            break
        A[N-1-i] = A[N-1-i] // 2
        M -= 1

print(sum(A))

Submission status: Wrong Answer

Solution code:
#one = input()
#two = input()

one = '3 3'
two = '2 13 8'

N, M = map(int, one.split())
Ar = map(int, two.split())
Ar = sorted(Ar , reverse=True)

for i in range(M):
    Ar[0] = Ar[0] / 2
    # Ar = sorted(Ar , reverse=True)
    for i in range(len(Ar)):
        if Ar[i] < Ar[i+1]:
            temp = Ar[i]
            Ar[i] = Ar[i+1]
            Ar[i+1] = temp
        else:
            break
    print(Ar)


Ar = map(int, Ar)
print(sum(Ar))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
li = list(map(int, input().split()))
for i in range(m):
    li.sort()
    if len(li) > 2:
        x = 10000
        if li[-2] <= li[-1] // (2 ** (x-1)) and i + x < m:
            li[-1] = li[-1] // (2 ** (x-1)) 
            i = +x
        x = 5000
        if li[-2] <= li[-1] // (2 ** (x-1)) and i + x < m:
            li[-1] = li[-1] // (2 ** (x-1)) 
            i = +x
        x = 2500
        if li[-2] <= li[-1] // (2 ** (x-1)) and i + x < m:
            li[-1] = li[-1] // (2 ** (x-1)) 
            i = +x
        x = 1250
        if li[-2] <= li[-1] // (2 ** (x-1)) and i + x < m:
            li[-1] = li[-1] // (2 ** (x-1)) 
            i = +x
        x = 625
        if li[-2] <= li[-1] // (2 ** (x-1)) and i + x < m:
            li[-1] = li[-1] // (2 ** (x-1)) 
            i = +x
        x = 312
        if li[-2] <= li[-1] // (2 ** (x-1)) and i + x < m:
            li[-1] = li[-1] // (2 ** (x-1)) 
            i = +x
        x = 156
        if li[-2] <= li[-1] // (2 ** (x-1)) and i + x < m:
            li[-1] = li[-1] // (2 ** (x-1)) 
            i = +x
        x = 78
        if li[-2] <= li[-1] // (2 ** (x-1)) and i + x < m:
            li[-1] = li[-1] // (2 ** (x-1)) 
            i = +x
        x = 39
        if li[-2] <= li[-1] // (2 ** (x-1)) and i + x < m:
            li[-1] = li[-1] // (2 ** (x-1)) 
            i = +x
        x = 19
        if li[-2] <= li[-1] // (2 ** (x-1)) and i + x < m:
            li[-1] = li[-1] // (2 ** (x-1)) 
            i = +x
            print(x)
        x = 9
        if li[-2] <= li[-1] // (2 ** (x-1)) and i + x < m:
            li[-1] = li[-1] // (2 ** (x-1)) 
            i = +x
            print(x)
        x = 4
        if li[-2] <= li[-1] // (2 ** (x-1)) and i + x < m:
            li[-1] = li[-1] // (2 ** (x-1)) 
            i = +x
            print(x)
        x = 2
        if li[-2] <= li[-1] // (2 ** (x-1)) and i + x < m:
            li[-1] = li[-1] // (2 ** (x-1)) 
            i = +x
        if i < m:
            li[-1] = li[-1] // (2 ** (x-1)) 
    else:
        print(li[0]//(2**m))
        exit()
print(sum(li))

Submission status: Wrong Answer

Solution code:
import bisect
from fractions import Fraction
import math

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

b = [0, 1]
num = 2
while num <= A[0]:
    b.append(num)
    num *= 2

AAA = [0] * N
for i in range(N):
    tmp = bisect.bisect_left(b, A[i])
    if A[i] == 1:
        AAA[i] = 1
    else:
        AAA[i] = tmp-1

total = sum(AAA)


rest = M
for i in range(N):
    
    A[i] = A[i] // (2 ** round(M*Fraction(AAA[i], total)))
    rest -= round(M*Fraction(AAA[i], total))



while rest > 0:
    for i in range(N):  
        A[i] = A[i] // (2 ** math.ceil(M*Fraction(AAA[i], total)))
        rest -= math.ceil(M*Fraction(AAA[i], total))
        if rest <= 0:
            break



print(sum(A))

Submission status: Wrong Answer

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

a = sorted(a)

for i in range(m):
    a[n-1] = a[n-1] // 2
    temp = a.pop()

    idx = -1
    for i in range(n-1):
        if a[i] > temp:
            idx = i
            break
    if idx == -1:
        a.insert(0, temp)
    else:
        a.insert(idx, temp)

'''
    left = 0
    right = n-2
    mid = 0
    while left < right:
        mid = (left + right) // 2
        if a[mid] > temp:
            right = mid - 1
            if right == left:
                a.insert(right+1, temp)
        elif a[mid] < temp:
            left = mid + 1
            if right == left:
                a.insert(right, temp)
        else:
            a.insert(right, temp)
            break
'''
    
print(sum(a))

Submission status: Wrong Answer

Solution code:
def one_sort(sorted_list):
    target = sorted_list.pop()
    left = 0
    right = len(sorted_list) - 1
    idx = right + 1
    while left <= right:
        mid = (left + right) // 2
        if sorted_list[mid] == target:
            idx = mid
            break
        elif sorted_list[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
            idx = left
    if(idx >= len(sorted_list)):
        sorted_list.append(target)
    else:
        sorted_list.insert(idx, target)
    #print(f"idx={idx}", sorted_list)
    return sorted_list

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

#import random
# import time
#max_range = 10**5
#max_num = 10**9
#a_list = [0] * max_range
#for i in range(max_range):
#    a_list[i] = random.randint(0, max_num)
#n = max_range
#m = max_range
#start = time.time()

a_list.sort()
for i in range(m):
    a_list[-1] = a_list[-1] // 2
    a_list = one_sort(a_list)
    # print(a_list)
answer = 0
for i in range(n):
    answer += a_list[i]
print(answer)

# print(time.time() - start)

Submission status: Wrong Answer

Solution code:
import math

N,M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
dic = {}
info = []
idx = 0
for i in A:
    idx = int(math.log(i,2))
    try:
        dic[idx] = dic[idx] + 1
    except:
        dic[idx] = 1

print(dic)

Submission status: Wrong Answer

Solution code:
import bisect

N,M =map(int,input().split())
A =[int(i) for i in input().split()]
N += 1
A.append(-10)
A.sort()
ans = [0]*N
num = 0
ma = A[-1]//2
while True:
    inde = bisect.bisect_left(A,ma)
    if num + (N-inde) < M:
        ans[-1] += 1
        ans[inde-1] -=1
        num += (N-inde)
        if ma == 0:
            break
    else:
        ans[-1] += 1
        ans[N-(M-num)-1] -= 1
        break
    ma = ma//2

A[0] = 0
answer = 0
for i in range(N):
    i = N-i-1
    answer += A[i]//(2**ans[i])
    ans[i-1] += ans[i]

print(int(answer))

Submission status: Wrong Answer

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

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

a_sum = sum(a)

if len(set(a)) == 1:
    max_a = max(a)
    a_discount = a_sum - int(max_a - (max_a / (2 ** m)))
else:
    a_discount = sum(int(ia / (2 ** round(m * (ia / a_sum)))) for ia in a)

print(a_discount)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

A.sort(reverse=True)
sumA = sum(A)
sumP = 0
tempM = copy.deepcopy(M)
for i, a in enumerate(A):
    if M == 1 and i == 0:
        sumP += a // 2
    elif M == 1 and i != 0:
        sumP += a
    elif M > 1 and tempM > 1:
        y = round(M * (a/sumA))
        sumP += a // (2**y)
        tempM -= y
    elif M > 1 and tempM == 1:
        sumP += a // 2
        tempM -= 1
    elif M > 1 and tempM == 0:
        sumP += a
print(sumP)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = [int(i) for i in input().split()]
a.sort(reverse=True)
c = 0
for i in range(n):
	if m > 0:
		t = a[i]//2
		bi = bin(t)
		if len(bi) == 3:
			b = len(bi) - 2
		elif bin(a[i])[2:].count("1") == 1:
			b = m
		else:
			b = len(bi) - 3
		if m > b:
			if i == n-1:
				c += a[i] // (2**m)
				m = 0
			else:
				c += a[i]//(2**b)
				m -= b
		else:
			c += a[i]//(2**m)
			m = 0
	else:
		c += a[i]
print(c)

Submission status: Wrong Answer

Solution code:
import bisect
import math

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

a.sort

for i in range(m):
  x=a.pop(n-1)/2
  insert_index = bisect.bisect_left(a,x)
  a.insert(insert_index,x)


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

Submission status: Wrong Answer

Solution code:
#S = input()
N,M = map(int,input().split())
A_list = list(map(int,input().split()))
#X1_list = [int(input()) for i in range(N)]
#X2_list = [list(map(int,input().split())) for i in range(N)]

'''
3 3 
8 6 5
4 4
8 7 6 5 
10 4
10 7 6 5 8 9 10 11 12 13
'''

import sys
sys.setrecursionlimit(20000000)
def swap(i):
    #print(A_list)
    #print(i)
    if i == N-1:
        tmp = A_list[0]
        A_list[0] = A_list[i]
        A_list[i] = tmp
        return
    if A_list[i] > A_list[i+1]:
        tmp = A_list[0]
        A_list[0] = A_list[i]
        A_list[i] = tmp
        return
    else:
        swap(i+1)

A_list.sort(reverse=True)
for i in range(M):
    #print(A_list)
    A_list[0] = A_list[0]//2
    if i == M-1:
        continue
    if N ==1:
        continue
    if A_list[0] > A_list[1]:
        continue
    else:
        swap(1)
print(sum(A_list))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=sorted(map(int,input().split()),reverse=True)
i=0
for _ in range(m):
    a[i]//=2
    if i+1==len(a): i=0
    elif a[i]<a[i+1]: i+=1
print(sum(a))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
prices = [int(p) for p in input().split()]
dp = [[0] * (m + 1) for _ in range(n)]
for i, p in enumerate(prices):
    for j in range(m + 1):
        dp[i][j] = min(dp[i - 1][j - k] + p // 2 ** k for k in range(m + 1) if j >= k)
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop
from math import ceil
n,m,*a=map(int,open(0).read().split())
if n==1:
	print(a[0]//(2**m))
	exit()
a=[(-1)*x for x in a]
x=heappop(a)
while m:
	y=heappop(a)
	while x<=y and m:
		x=ceil(x/2)
		m-=1
	heappush(a,x)
	x=y
heappush(a,x)
print((-1)*sum(a))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
def main():  
  n,m=map(int,input().split())
  a=list(map(int,input().split()))  
  if n==1:
    for i in range(m):
      a[0]=a[0]//2
    print(sum(a))
  else:
    a.sort(reverse=True)
    for i in range(m):
      a[0]=a[0]//2
      a[0],a[1]=max(a[0],a[1]),min(a[0],a[1])
    print(sum(a))
main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=[float(x) for x in input().split()]
sum=0
A.sort
for i in range(m):
    A[n-1]=A[n-1]/2
    if n!=1:
        v=A[n-1]
        j=n-2
        while j>=0 and A[j]>v:
            A[j+1]=A[j]
            j-=1
        A[j+1]=v

#A_int=[int(x) for x in A]
#print(sum(A_int))
for x in A:
    sum+=int(x)

print(sum)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right as br
from bisect import bisect_left  as bl
from bisect import insort_right as ir
from bisect import insort_left  as il
#-------------------------------------------------------------------

N, M = map(int, input().split())		# 5 7 2
A = sorted(list( map(int, input().split()) ))	# 1 2 3 4 5 ...(降順(逆順)ソート付き)


for _ in range(M):
	a = A.pop(-1)
	if int(a)==1: break
	b = a/2
	ir(A,b)
	
	#p("a,b,A ",a,b,A)
	

ans=0
for a in A:
	ans += int(a)

print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = [int(i) for i in input().split()]
ans = sum(a)
a.sort()
a.reverse()
a = [0,0] + a + [0,0]
k = 2
for i in range(m):
    ans -= -(-a[k]//2)
    a[k] = a[k]//2
    k = k+max(enumerate(a[k-2:k+3]),key = lambda x:x[1])[0]-2
    if ans == 0:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
n, t = map(int, input().split())
data = list(map(int, input().split()))

data = sorted(data)

b4 = 0
right = n-2
left = 0
#print(data[-1])
for i in range(t):
    data[-1] = int(data[-1]/2)
    while True:
        #print(data)
        #print(right, left)
        mid = int((right+left)/2)
        if(right<=left) or (right-left == 1):
            #print(list(data[0:right]), data[-1], list(data[right:-1]))
            if(n%2==1):data = list(data[0:right]) + [data[-1]] + list(data[right:-1])
            else:data = list(data[0:left]) + [data[-1]] + list(data[left:-1])
            break
        if(data[mid] > data[-1]):
            right = mid
        if(data[mid] < data[-1]):
            left = mid
    #print(data)
ans = 0
for i in data:
    ans+=i
print(ans)

Submission status: Wrong Answer

Solution code:
#one = input()
#two = input()

one = '4 4'
two = '1 9 3 5'

N, M = map(int, one.split())
Ar = map(int, two.split())
Ar = sorted(Ar , reverse=True)

for i in range(M):
    Ar[0] = int(Ar[0] / 2)
    # Ar = sorted(Ar , reverse=True)
    for i in range(len(Ar)):
        if Ar[i] < Ar[i+1]:
            temp = Ar[i]
            Ar[i] = Ar[i+1]
            Ar[i+1] = temp
        else:
            break

#Ar = map(int, Ar)
print(sum(Ar))

Submission status: Wrong Answer

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

for i in range(M):
	A_replace = [i // 2 if i == max(A) else i for i in A]
print(sum(A_replace))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
N,M = [int(x) for x in input().split()]
A = [-int(x) for x in input().split()]
for _ in range(M):
    # 最大の要素取り出し
    x = -heappop(A)
    x = x//2
    heappush(A, -x)
print(-sum(A))

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M=map(int,input().split())
A=list(map(int,input().split()))
for i in range(M):
    max_point = np.argmax(A)
    if max_point == 0:
        break
    A[max_point] = A[max_point]//2

    
print(sum(A))

Submission status: Wrong Answer

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

A = sorted(A, reverse=True)
A_ = []

for i in range(N):
  if A[i] / (2 ** M) == 0:
    A[i] = 0
    break;

  for j in range(M,0,-1):
    jou = 2 ** j
    if A[i] / jou >= 2:
      M = M - j
      A[i] = math.floor(A[i] / jou)
      break;

  if M == 0:
    break;

print(sum(A))

Submission status: Wrong Answer

Solution code:
import math

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

sorted_A = list(reversed(sorted(A)))

money = 0

for a in sorted_A:
    if M > 2:
        used = round(M/2)
    elif M != 0:
        used = 1
    else:
        used = 0

    if round(math.log(a,2)) <= used:
        used = int(math.log(a,2))+1

    money += a // 2**(used)
    M = M - used

print(money)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[69]:


#import copy
import numpy as np

N, M = map(int, input().split())
As = np.sort(np.array(list(map(int, input().split()))))[::-1]
"""
3 3
2 13 8

4 4
1 9 3 5
"""


# In[70]:


As


# In[71]:


#As[0] = As[0] // 2
#arg = 0
for i in range(M):
    if i == 0:
        arg = 0
    else:
        arg = np.argmax(As[:i+1])
    #print(arg)
    As[arg] = As[arg] // 2
    #As[:i+1] = np.sort(As[:i+1])[::-1]
    #As[0] = As[0] // 2


# In[72]:


print(As)
print(sum(As))


# In[ ]:

Submission status: Wrong Answer

Solution code:

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

index = 0
for m in range(M):
    A[index] //= 2
    if index == N-1:
        index = 0
    elif A[index] < A[index + 1]:
        index += 1
    else:
        index = 0
        
    
        
print(sum(A))

Submission status: Wrong Answer

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(int(sum(A)))

Submission status: Wrong Answer

Solution code:
mnum, gnum = map(int, input().split())
array = list(map(int, input().split()))

for i in range(gnum):
	array.sort()
	array[len(array)-1] = array[len(array)-1]/2

print(sum(array))

Submission status: Wrong Answer

Solution code:
import math

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

blist = [math.log2(alist[i]) for i in range(n)]


for i in range(m):
    maximum = max(blist)
    chnm = int(blist.index(maximum))
    blist[chnm] = blist[chnm]-1

print( sum([ math.floor(2**blist[i]) for i in range(n) ]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def one_sort(sorted_list):
    target = sorted_list.pop()
    left = 0
    right = len(sorted_list) - 1
    idx = right + 1
    while left <= right:
        mid = (left + right) // 2
        if sorted_list[mid] == target:
            idx = mid
            break
        elif sorted_list[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
            idx = left
    if(idx >= len(sorted_list)):
        sorted_list.append(target)
    else:
        sorted_list.insert(idx, target)
    #print(f"idx={idx}", sorted_list)
    return sorted_list



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

#import random
# import time
#max_range = 10**5
#max_num = 10**9
#a_list = [0] * max_range
#for i in range(max_range):
#    a_list[i] = random.randint(0, max_num)
#n = max_range
#m = max_range
#start = time.time()

a_list.sort()
for i in range(m):
    a_list[-1] = a_list[-1] // 2
    a_list = one_sort(a_list)
    # print(a_list)
answer = 0
for i in range(n):
    answer += a_list[i]
print(answer)

# print(time.time() - start)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=[float(x) for x in input().split()]
sum=0
A.sort
for i in range(m):
    A[n-1]=A[n-1]/2
    if m!=1:
        v=A[n-1]
        j=n-2
        while j>=0 and A[j]>v:
            A[j+1]=A[j]
            j-=1
        A[j+1]=v

#A_int=[int(x) for x in A]
#print(sum(A_int))
for x in A:
    sum+=int(x)

print(sum)