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:
n,m = map(int,input().split())
a = sorted(map(int,input().split()))

import bisect

for i in range(m):
    a[-1] //= 2
    
    if 1 < len(a):
        if a[-2] > a[-1]:
            bisect.insort(a,a[-1])
            a = a[:-1]
    
print(sum(a))

Submission status: Wrong Answer

Solution code:
import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
ls = []
for item in A:
  heapq.heappush(ls, -item)
for m in range(M):
  tmp = -heapq.heappop(ls)
  tmp = tmp // 2
  heapq.heappush(ls, -tmp)
print(sum(ls))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Sep 16 12:35:58 2020

@author: liang
"""

N, M = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort(reverse=True)
#print(A)
count = 0
while count != M:
    A[0] //= 2
    count += 1
    tmp = A[0]
    for i in range(1,N):
        if count == M:
            break
        if A[i] > tmp:
            A[i] //= 2
            count += 1
        ##   break
    A.sort()
ans = sum(A)
#print(A)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Sep 16 12:35:58 2020

@author: liang
"""

N, M = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort(reverse=True)
#print(A)
count = 0
while count != M:
    A[0] //= 2
    count += 1
    tmp = A[0]
    for i in range(1,N):
        if count == M:
            break
        if A[i] > tmp:
            A[i] //= 2
            count += 1
        ##   break
ans = sum(A)
#print(A)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import heapq

N, M = map(int,input().split())
A = list(map(lambda x:int(x) * (-1),input().split()))
heapq.heapify(A)

for i in range(M):
    a = heapq.heappop(A)
    a *= -1
    a /= 2
    a *= -1    
    heapq.heappush(A,a)

print(-sum(A))

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import heapq

N, M = map(int,input().split())
A = list(map(lambda x:int(x) * (-1),input().split()))
heapq.heapify(A)

for i in range(M):
    a = heapq.heappop(A)
    a *= -1
    a /= 2
    a *= -1    
    heapq.heappush(A,a)

price = 0
for a in A:
    price += (-1) * a

print(price)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import heapq

N, M = map(int,input().split())
A = list(map(int,input().split()))
A = [(-1)*num for num in A]
heapq.heapify(A)

ans = 0
for i in range(M):
    a = heapq.heappop(A)
    a *= -1
    a /= 2
    a *= -1    
    heapq.heappush(A,a)

price = 0
for a in A:
    price += (-1) * a

print(price)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import heapq

N, M = map(int,input().split())
A = list(map(int,input().split()))
A = [(-1)*num for num in A]
heapq.heapify(A)

ans = 0
for i in range(M):
    a = heapq.heappop(A)
    a *= -1
    a /= 2
    a *= -1    
    heapq.heappush(A,a)

price = 0
for a in A:
    price += (-1) * a

print(price)

Submission status: Wrong Answer

Solution code:
import heapq
import sys

lines = sys.stdin.readlines()

N, M = [int(n) for n in lines[0].strip().split()]
prices = [-int(n) for n in lines[1].strip().split()]

heapq.heapify(prices)

for _ in range(M):
    price = -heapq.heappop(prices)
    print(price)
    heapq.heappush(prices, -1 * (price // 2))

print(-sum(prices))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
a = [0]+list(map(int,input().split()))
a.sort(reverse=True)
for i in range(N):
    while M > 0 and 2*a[i]>=a[i+1]:
        a[i] //= 2
        M -= 1
    if M == 0:
        break
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)

for i in range(m):
    a[0] = a[0] // 2
    if sum(a) == 0:
        break
    for j in range(n):
        if a[0] < a[j]:
            a[0], a[j] = a[j], a[0]
            break
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)

for i in range(m):
    a[0] = a[0] // 2
    if sum(a) == 0:
        break
    if n < 2:
        for j in range(1, n):
            if a[0] < a[j]:
                a[0], a[j] = a[j], a[0]
                break
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)

for i in range(m):
    a[0] = a[0] // 2
    if sum(a) == 0:
        break
    for j in range(1, n):
        if a[0] < a[j]:
            a[0], a[j] = a[j], a[0]
            break
print(sum(a))

Submission status: Wrong Answer

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())]
    heapify(A)
    for i in range(M):
        tmp = heappop(A)
        tmp2 = tmp//2
        heappush(A,tmp2)
    ans = 0
    for i in range(N):
        ans += A[i]

    ans = abs(ans)
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
import math
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
log_a = [math.log2(x) for x in a]

if sum(log_a) < m:
    print(0)
else:
    for i in range(1, m+1):
        log_a[-1] = log_a[-1] - 1
        log_a.sort()
        b = [2 ** x for x in log_a]
        b = [math.floor(x) for x in b]
    print(sum(b))

Submission status: Wrong Answer

Solution code:
# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np
from collections import deque

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
N, M = map(int, input().split())
A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

A = sorted(A, reverse=True)
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

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


queue_A = deque(A)
queue_B = deque()

for i in range(M):
    if len(queue_B) > 0 and queue_B[0] >= queue_A[0]:
        queue_A.appendleft(queue_B.popleft())
    queue_A[0] //= 2
    if len(queue_A) > 1 and queue_A[0] < queue_A[1]:
        queue_B.append(queue_A.popleft())

print(queue_A)

print(queue_B)
print(sum(queue_A) + sum(queue_B))

Submission status: Wrong Answer

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)
        while a[0]>a[1]:
            a[0] //= 2
    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)
if n == 1:
    print(a[0]//(2**m))
else:
    while m > 0:
        i = 0
        a.sort(reverse = True)
        while (i < n-2) & (a[i] > a[i+1]) & (m > 0):
            a[i] //= 2
            m -= 1
            i += 1
        if i == 0:
            for s in range(m):
                a[s%n] //= 2
            break
    print(sum(a))

Submission status: Wrong Answer

Solution code:
import sys
import heapq
stdin = sys.stdin

n,m = map(int, stdin.readline().split())

# 最大値を取得するために、マイナス各値にマイナスをかける。
an = [i*(-1) for i in map(int, stdin.readline().split())]
#print(an)

# リストのheap化
heapq.heapify(an)

# heapから最大値を取り出して、半分にしてヒープに戻すことをｍ回。
for _ in range(m):
    b = heapq.heappop(an)
    heapq.heappush(an, b//2 + 1)

ans = (-1)*sum(an)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    a_list = list(map(int, input().split()))
    a_list = list(map(lambda x: x*(-1), a_list))
    heapq.heapify(a_list)

    while m > 0:
        max_a = heapq.heappop(a_list)
        heapq.heappush(a_list, (-1)*(-max_a//2))
        m -= 1
    
    print(-sum(a_list))

Submission status: Wrong Answer

Solution code:

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

for i in range(tickets_number):
  index = 0
  discount_item = sorted_items[0] // 2
  for i in range(items_number - index):
    if discount_item < sorted_items[index]:
      break
    index += 1

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

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

Submission status: Wrong Answer

Solution code:
import math
N,K=map(int,input().split())
A=list(map(int,input().split()))
whole=sum(A)
A=sorted(A,reverse=True)
per=[]
for a in A:
    per.append(int(K*a/whole))
if sum(per)>K:
    for k in range(N):
        A[k]=A[k]//2
    print(sum(A))
else:
    for k in range(N):
        A[k]=A[k]//(2**per[k])
    if sum(per)<K:
        for n in range(K-sum(per)):
            place=A.index(max(A))
            A[place]=A[place]//2
    print(sum(A))

Submission status: Wrong Answer

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 
  if a[n-1] == 0:
    break
  
print(sum(a))

Submission status: Wrong Answer

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()

for i in range(n-1):
  if a[i] > a[i+1] * (10*3):
    s = int(log(a[i]/a[i+1], 2))
    a[i] //= 2**(min(m, s))
    m = max(0, m-s)
    if m == 0:
      print(sum(a))
      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: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353


N, M = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: x*(-1), A))  # 各要素を-1倍

a = heapq.heappop(A)
heapq.heappush(A, a)

for i in range(M):
    a = heapq.heappop(A)
    a = a / 2.0
    heapq.heappush(A, 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 = list(map(int, input().split()))
for i in range(0,M):
    A[A.index(max(A))]=int(A[A.index(max(A))])

print(sum(A))

Submission status: Wrong Answer

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

ans = sum(A)
a_min, a_max = 0, max(A)

while a_min < a_max:
    k = 0
    v = 0
    f = 0
    a_mid = (a_min + a_max) // 2
    for i in range(N):
        a = A[i]
        while a > a_mid and k < M:
            a //= 2
            k += 1
        v += a
        f = max(f, a)
    if f > a_mid:
        a_min = a_mid + 1
        ans = min(ans, v)
    else:
        a_max = a_mid
        ans = min(ans, v)
print(ans)

Submission status: Wrong Answer

Solution code:
def bin_tree( pri , li_pri , len_li ):
    #pri: どこに入れていいかわからない値段
    #li_pri: 値段のリスト(昇順)
    #len_li: リストの長さ
    lo = 0
    hi = len_li - 1
    while hi - lo > 1:
        mid = lo + (hi - lo) // 2
        guess = li_pri[mid]
        if guess >= pri:
            hi = mid
        else:
            lo = mid
    return lo

I = input().split()
N = int(I[0])
M = int(I[1])
# N: 品物の数
# M: 割引券の数
# A: 品物の値段行列
A = list(map(int , input().split()))
A.sort()

while M > 0:
    M -= 1
    pri = A.pop( N - 1 )
    pri = pri // 2

    ans = bin_tree( pri , A , N - 1 ) + 1
    # ans: pri以上となる値段のうち最小のインデックス
    A[ans:ans] = [pri]    

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

Submission status: Wrong Answer

Solution code:
def bin_tree( pri , li_pri , len_li ):
    #pri: どこに入れていいかわからない値段
    #li_pri: 値段のリスト(昇順)
    #len_li: リストの長さ
    lo = 0
    hi = len_li - 1
    while hi - lo > 1:
        mid = (lo + hi) // 2
        guess = li_pri[mid]
        if guess == pri:
            return mid
        if guess > pri:
            hi = mid
        else:
            lo = mid
    return hi

I = input().split()
N = int(I[0])
M = int(I[1])
# N: 品物の数
# M: 割引券の数
# A: 品物の値段行列
A = list(map(int , input().split()))
A.sort()
while M > 0:
    M -= 1
    pri = A.pop( N - 1 )
    pri = pri // 2
    ans = bin_tree( pri , A , N - 1 )
    A[ans:ans] = [pri]

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

Submission status: Wrong Answer

Solution code:
def bin_tree( pri , li_pri , len_li ):
    #pri: どこに入れていいかわからない値段
    #li_pri: 値段のリスト(昇順)
    #len_li: リストの長さ
    lo = 0
    hi = len_li - 1
    while hi - lo > 1:
        mid = (lo + hi) // 2
        guess = li_pri[mid]
        if guess == pri:
            return guess
        if guess > pri:
            hi = mid
        else:
            lo = mid
    return hi

I = input().split()
N = int(I[0])
M = int(I[1])
# N: 品物の数
# M: 割引券の数
# A: 品物の値段行列
A = list(map(int , input().split()))
A.sort()
while M > 0:
    M -= 1
    pri = A.pop( N - 1 )
    pri = pri // 2
    ans = bin_tree( pri , A , N - 1 )
    A[ans:ans] = [pri]

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

Submission status: Wrong Answer

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

P=sorted(Po,reverse=True)

i=0
mc = m
maxp=0
maxpi=0
while mc>0 :
    if P[i]==0 and i==n-1 :
        break
    elif P[i]==0:
        i+=1
    elif i==n-1:
        P[i]//=2
        mc-=1
        i=0
    elif P[0]<maxp :
        i=maxpi
        P[i]//=2
        maxp=P[i+1]
        mc-=1
    elif P[0]>P[i+1] :
        P[0]//=2
        maxp=P[i+1]
        maxpi=i+1
        mc-=1
        i=0
    elif P[i]>P[i+1] :
        P[i]//=2
        mc-=1
    elif P[i]<=P[i+1] :
        P[i+1]//=2
        mc-=1
        i+=1
    else:
        i=0
        
        
print( sum(P) )

Submission status: Wrong Answer

Solution code:
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
ans = sum(a[min(n, m):])
a = a[:min(n, m)]
a = [x*(-1) for x in a]
heapq.heapify(a)

for i in range(m):
    c = (heapq.heappop(a)*(-1)//2)*(-1)
    heapq.heappush(a, c)
print(ans-sum(a))

Submission status: Wrong Answer

Solution code:
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
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:
    a = [x*(-1) for x in a]
    heapq.heapify(a)
    for i in range(m):
        c = (heapq.heappop(a)*(-1)//2)*(-1)
        heapq.heappush(a, c)
    print(ans-sum(a))

Submission status: Wrong Answer

Solution code:
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
ans = sum(a[min(n, m):])
a = [x*(-1) for x in a]
a = a[:min(n, m)]
heapq.heapify(a)

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):
        c = (heapq.heappop(a)*(-1)//2)*(-1)
        heapq.heappush(a, c)
    print(ans-sum(a))

Submission status: Wrong Answer

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):
        c = a[0]//a[1]
        d = 1
        while 2**d <= c and d < m:
            d += 1
        num = a[0]//2**d
        m = max(m-d, 0)
        a[0] = num
        a = sorted(a, reverse=True)
        if m == 0:
            print(sum(a))
            break

Submission status: Wrong Answer

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
  t=a[0]
  for j in range(1,n):
    if a[0]<a[j]:
      a.insert(j+1,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: Wrong Answer

Solution code:
from collections import deque


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

coupon = M
while coupon:
    try:
        if B:
            if A[-1] >= B[0]:
                B.append(A.pop() // 2)
            else:
                B.append(B.popleft() // 2)
        else:
            B.append(A.pop() // 2)
        coupon -= 1
    except IndexError:
        A, B = B, A


ans = sum(int(i) for i in A) + sum(int(i) for i in B)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


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

coupon = M
while coupon:
    try:
        if B:
            if A[-1] > B[0]:
                B.append(A.pop() / 2)
            else:
                B.append(B.popleft() / 2)
        else:
            B.append(A.pop() / 2)
        coupon -= 1
    except IndexError:
        A, B = B, A


ans = sum(int(i) for i in A) + sum(int(i) for i in B)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


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

coupon = M
while coupon:
    try:
        if B:
            if A[-1] >= B[0]:
                B.append(A.pop() / 2)
            else:
                B.append(B.popleft() / 2)
        else:
            B.append(A.pop() / 2)
        coupon -= 1
    except IndexError:
        A, B = B, A


ans = sum(int(i) for i in A) + sum(int(i) for i in B)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
*A,=map(int,input().split())
A=sorted(A)[::-1]
count=0
now=0
while M:
    i=0
    if M==0:
        break
    while i<=now and M:
        if count+1<N and A[i]<A[count+1]:
            while A[i]<=A[count+1]:
                #print(A)
                A[count+1]//=2
                count=min(count+1,N-2)
                M-=1
                if M==0:
                    break
            now=min(count+1,N-1)
        else:
            #print(A)
            A[i]//=2
            i+=1
            M-=1
        
print(sum(A))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
*A,=map(int,input().split())
A=sorted(A)[::-1]
count=0
now=0
while M:
    i=0
    while i<=now and M:
        if count+1<N and A[i]<=A[count+1]:
            while A[i]<=A[count+1]:
                #print(A)
                A[count+1]//=2
                count=min(count+1,N-2)
                M-=1
                if M==0:
                    break
            now=min(count+1,N-1)
        else:
            #print(A)
            A[i]//=2
            i+=1
            M-=1
        
print(sum(A))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
*A,=map(int,input().split())
A=sorted(A)[::-1]
count=0
now=0
while M:
    i=0
    while i<=now and M:
        if count+1<N and A[i]<A[count+1]:
            while A[i]<=A[count+1]:
                #print(A)
                A[count+1]//=2
                count=min(count+1,N-2)
                M-=1
                if M==0:
                    break
            now=min(count+1,N-1)
        else:
            #print(A)
            A[i]//=2
            i+=1
            M-=1
        
print(sum(A))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
*A,=map(int,input().split())
A=sorted(A)[::-1]
count=0
now=0
while M:
    i=0
    while i<=now and M:
        if count+1<N and A[i]<A[count+1]:
            while A[i]<A[count+1]:
                A[count+1]//=2
                count=min(count+1,N-2)
                M-=1
                if M==0:
                    break
            now=min(count+1,N-1)
        else:
            A[i]//=2
            i+=1
            M-=1
        
print(sum(A))

Submission status: Wrong Answer

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.heappush(a, heapq.heappop(a)//2)
print(sum(a)*-1)

Submission status: Wrong Answer

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

i=0
while M:
    A[i]//=2
    M-=1
    if A[i]<A[min(i+M,N-1)] or i==N-1:
        i+=1
    if i==N:
        A=sorted(A)[::-1]
        i=0

print(sum(A))

Submission status: Wrong Answer

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

i=0
while M:
    A[i]//=2
    M-=1
    if A[i]<A[min(i+M,N-1)]:
        i+=1
    if i==N:
        A=sorted(A)[::-1]
        i=0

print(sum(A))

Submission status: Wrong Answer

Solution code:
from math import log2

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

if N==1:print(A[0]//(2**M))
elif M==1:
  A = sorted(A,reverse=True)
  A[0] //= 2
  print(sum(A))
  
else:
  B = [log2(A[i]) for i in range(N)]
  sumB=sum(B)
  if sumB == 0:
    print(max(0,N-M))

  else:
    C = [B[i]/sumB*M for i in range(N)]

    intC = [int(C[i]) for i in range(N)]
    r = M - sum(intC)

    res = [A[i]/(2**intC[i]) for i in range(N)]

    res = sorted(res,reverse=True)

    for i in range(r):
      res = sorted(res,reverse=True)
      res[0] /= 2

    print(sum([int(re) for re in res]))

Submission status: Wrong Answer

Solution code:
from math import log2

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

if N==1:print(A[0]//(2**M))
elif M==1:
  A = sorted(A,reverse=True)
  A[0] //= 2
  print(sum(A))
  
else:
  B = [log2(A[i]) for i in range(N)]
  sumB=sum(B)
  if sumB == 0:
    print(max(0,N-M))

  else:
    C = [B[i]/sumB*M for i in range(N)]

    intC = [int(C[i]) for i in range(N)]
    r = M - sum(intC)

    res = [A[i]/(2**intC[i]) for i in range(N)]

    res = sorted(res,reverse=True)

    i = 0
    while 1:
      if i < N-1:
        if i > 0 and res[i-1]>res[i] and res[i-1]>res[i+1]:
          i -= 1
        elif res[i] > res[i+1]:
          res[i] /= 2
          r -= 1
        else:
          i += 1
      else:
        res[i] /= 2
        r -= 1
        i = 0
      if r == 0:break

    print(sum([int(re) for re in res]))

Submission status: Wrong Answer

Solution code:
from math import log2

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

if N==1:print(A[0]//(2**M))
elif M==1:
  A = sorted(A,reverse=True)
  A[0] //= 2
  print(sum(A))
  
else:
  B = [log2(A[i]) for i in range(N)]
  sumB=sum(B)
  if sumB == 0:
    print(max(0,N-M))

  else:
    C = [B[i]/sumB*M for i in range(N)]

    intC = [int(C[i]) for i in range(N)]
    r = M - sum(intC)

    res = [A[i]/(2**intC[i]) for i in range(N)]

    res = sorted(res,reverse=True)

    i = 0
    while 1:
      if i < N-1:
        if res[i] > res[i+1]:
          res[i] /= 2
          r -= 1
        else:
          i += 1
      else:
        res[i] /= 2
        r -= 1
        i = 0
      if r == 0:break

    print(sum([int(re) for re in res]))

Submission status: Wrong Answer

Solution code:
from math import log

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

if N==1:print(A[0]//(2**M))
elif M==1:
  A = sorted(A,reverse=True)
  A[0] //= 2
  print(sum(A))
  
else:
  B = [log(A[i]) for i in range(N)]
  sumB=sum(B)
  if sumB == 0:
    print(max(0,N-M))

  else:
    C = [B[i]/sumB*M for i in range(N)]

    intC = [int(C[i]) for i in range(N)]
    r = M - sum(intC)

    res = [A[i]/(2**intC[i]) for i in range(N)]

    res = sorted(res,reverse=True)

    i = 0
    while 1:
      if i < N-1:
        if res[i] > res[i+1]:
          res[i] /= 2
          r -= 1
        else:
          i += 1
      else:
        res[i] /= 2
        r -= 1
        i = 0
      if r == 0:break

    print(sum([int(re) for re in res]))

Submission status: Wrong Answer

Solution code:
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

N,M=list(map(int,input().split()))
A =list(map(bin,sorted(list(map(int,input().split())),reverse=1)))
Alen = list(map(len,A))
ticket =[0]*N

if N == 1:
    print(int(A[0],2)//(2**M))
else:
    while True:
        count = 0
        Blen = copy.copy(Alen)
        tB = copy.copy(ticket)
        for i in range(N-1):
            if Blen[i] >= Blen[i+1]:
                Blen[i] -= 1
                count += 1
                tB[i] += 1
        if Blen[-1] == Blen[-2]+1:
            Blen[-1] -= 1
            count += 1
            tB[-1] += 1
        #print(tB)
        #print(M)
        #print(count)
        if M-count > 0:
            Alen = copy.copy(Blen)
            ticket = copy.copy(tB)
            M -= count
            if sum(Alen) <=2*N:
                print(0)
                exit()

        elif M-count == 0:
            Alen = copy.copy(Blen)
            ticket = copy.copy(tB)
            M -= count
            if sum(Alen) <=2*N:
                print(0)
                exit()
            break
        else:
            break
            

    for i in range(N):
        A[i] = int(A[i],2)//pow(2,ticket[i])

    A = sorted(A,reverse = 1)

    ans = 0

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

Submission status: Wrong Answer

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()]
As = sorted(As,reverse = True)
rest = M
for _ in range(M):
  d = As[0]
  b = d//2 - d//4
  for i in range(N):
    a = As[i]
    check = 0
    if a-a//2<b:
      if rest > i:
        ad = [x//2 for x in As[:i]]
        As = As[i:]
        As.extend(ad)
        rest -= i
        check += 1
        As = sorted(As,reverse = True)
      else:
        ad = [x//2 for x in As[:rest]]
        As = As[rest:]
        As.extend(ad)
        rest = 0
        check += 2
        break
        break
#全部通った場合
    if i == N-1 and check == 0:
      if rest > N:
        As = [x//2 for x in As]
        rest -= N
      else:
        ad = [x//2 for x in As[:rest]]
        As = As[rest:]
        As.extend(ad)
        rest = 0
        break
        break
print(sum(As))

Submission status: Wrong Answer

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()]
As = sorted(As,reverse = True)
rest = M
for _ in range(M):
  d = As[0]
  b = d//2 - d//4
  for i in range(1,N):
    a = As[i]
    check = 0
    if a-a//2<b:
      ad = [x//2 for x in As[:i]]
      if rest > i:
        As = As[i:]
        As.extend(ad)
        rest -= i
        check += 1
        As = sorted(As,reverse = True)
      else:
        ad = [x//2 for x in As[:rest]]
        As = As[rest:]
        As.extend(ad)
        rest = 0
        check += 2
        break
    if i == N-1 and check == 0:
      if rest > N:
        As = [x//2 for x in As]
        rest -= N
      else:
        ad = [x//2 for x in As[:rest]]
        As = As[rest:]
        As.extend(ad)
        rest = 0
        break
print(sum(As))

Submission status: Wrong Answer

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()]
As = sorted(As,reverse = True)
rest = M
check = 0
for _ in range(M):
  d = As[0]
  b = d//2 - d//4
  if check ==2:
    break
  for i in range(N):
    a = As[i]
    check = 0
    if a-a//2<b:
      ad = [x//2 for x in As[:i]]
      if rest > i:
        As = As[i:]
        As.extend(ad)
        rest -= i
        check += 1
        As = sorted(As,reverse = True)
      else:
        ad = [x//2 for x in As[:rest]]
        As = As[rest:]
        As.extend(ad)
        rest = 0
        check += 2
        break
    if i == N-1 and check == 0:
      if rest > N:
        As = [x//2 for x in As]
        rest -= N
      else:
        ad = [x//2 for x in As[:rest]]
        As = As[rest:]
        As.extend(ad)
        rest = 0
        break
print(sum(As))

Submission status: Wrong Answer

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()]
As = sorted(As,reverse = True)
rest = M
for _ in range(M):
  if rest ==0:
    break
  d = As[0]
  b = d//2 - d//4
  for i in range(N):
    a = As[i]
    check = 0
    if a-a//2<b:
      ad = [x//2 for x in As[:i]]
      if rest > i:
        As = As[i:]
        As.extend(ad)
        rest -= i
        check += 1
        As = sorted(As,reverse = True)
      else:
        ad = [x//2 for x in As[:rest]]
        As = As[rest:]
        As.extend(ad)
        rest = 0
        check += 1
        break
    if i ==N-1 and check == 0:
      if rest > N:
        As = [x//2 for x in As]
        rest -= N
      else:
        ad = [x//2 for x in As[:rest]]
        As = As[rest:]
        As.extend(ad)
        rest = 0
        break
print(sum(As))