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


def calc_dis(X, Y):
    Z = X / pow(2, Y)
    return math.floor(Z)


N, M = (int(x) for x in input().split())
A = ([int(x) for x in input().split()])
A = sorted(A, reverse=True)
T = [0] * N
T[0] = M
minM = -1
j = 0

while True:
    Money = 0
    for i in range(0, N):
        Money += calc_dis(A[i], T[i])
    if (minM == -1) or (minM > Money):
        minM = Money
    if j == N - 1:
        break
    if T[j] - T[j+1] > 1:
        T[j] -= 1
        T[j+1] += 1
    else:
        j += 1

print(minM)

Submission status: Wrong Answer

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

a.sort()

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

Submission status: Wrong Answer

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

if n == 1:
    for _ in range(m):
        a[0] //=2
    print(a[0])
    exit()

temp = []
temp.append(a.pop())

while m > 0:
    if len(a) != 0 and temp[-1] < a[-1]:
        temp.append(a.pop())
        temp[-1] //= 2
        m -=1
    else:
        temp = sorted(temp)
        temp[-1] //= 2
        m -= 1

print(sum(temp)+sum(a))

Submission status: Wrong Answer

Solution code:
import numpy as np
n, m = map(int, input().split())
a = [int(i) for i in input().split(" ")]
a = np.sort(a)
b = np.log2(a)
if np.sum(b//1)+n < m:
    print(0)
else:
    t = b.copy()
    c = m
    ind = n-1
    while c>0:
        if (b[ind] - b[ind-1] + 1)//1*(n-ind) <= c:
            c -= (b[ind] - b[ind-1] + 1)//1*(n-ind)
            b[ind:] -= (b[ind] - b[ind-1] + 1)//1
            ind -= 1
        else:
            for i in range(int(c)):
                b[b.argmax()] -= 1
            c = 0
    tm = [2**int(i) for i in t-b]
    print(int(np.sum(np.array(a, dtype="object")/tm//1)))

Submission status: Wrong Answer

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

top = 0

for i in range(gnum):
	top = 0
	for j in range(mnum):
		if array[top] < array[j]:
			top = j
	array[top] = array[top]/2

print(sum(array))

Submission status: Wrong Answer

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

A=[""]*N

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

A.sort()
#print(A)

for i in range(M):
    A[N-1]=math.floor(A[N-1]/2)        
    for j in range(N-2,-1,-1):
        if A[j-1]<=A[N-1] and A[j]>=A[N-1]:
            A[j],A[N-1]=A[N-1],A[j]
            break
    #A.sort()
    #print(A)


print(sum(A))

Submission status: Wrong Answer

Solution code:
import bisect

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

for m in range(M):
    A[N-1] = round( A[N-1]/2 )
    temp = A[N-1]
    del A[N-1]
    # 挿入    
    bisect.insort(A, temp)
    
print(sum(A))

Submission status: Wrong Answer

Solution code:
import bisect
from fractions import Fraction
import math
def main():
    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))


    M = rest
    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))

if __name__ == "main":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

if N == 1:
  print(round(money[0]//(2**M)))

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]/=2
    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

for x in A:
    sum+=int(x)

print(sum)

Submission status: Wrong Answer

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

if N == 1:
    print(A[0]//2**M)
    exit()

TEMPBIG = 0
dp = [[TEMPBIG for x in range(M+1)] for y in range(N+1)]

for _ in range(M+1):
    dp[0][_] = 0

tmp = 0
dp[0][0] = 0

for _ in range(1, N+1):
    tmp += A[_-1]
    dp[_][0] = tmp

for num in range(1, N+1):
    for coupon in range(1, M+1):
        # print(num, ",", coupon)
        minv = 2 << 64
        col = 0
        while col < coupon or col == 0:
            temp = dp[num-1][col] + A[num-1]//2**(coupon-col)
            # print("dp[num-1][col] + A[num-1]//2**col=", dp[num-1][col], "+", A[num-1]//2**(coupon-col))
            if minv > temp:
                dp[num][coupon] = temp
                minv = temp

            col += 1
            # pprint(dp)

# pprint(dp)

# ans
print(dp[N][M])

Submission status: Wrong Answer

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

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()
        # print(a,counter,2**i)
        elif a[j] == 1 and a[j-1] < a[j]:
            a[j] = math.floor(a[j]/2)
            counter += 1
            if counter >= m:
                print(sum(a))
                sys.exit()

print(sum(a))

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)
Y = []
for x in A:
    if round(M * (x / sumA)) <= tempM:
        y = round(M * (x / sumA))
        Y.append(y)
        tempM -= y
    elif round(M * (x / sumA)) > tempM:
        Y.append(tempM)
        break

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 i <= len(Y)-1:
        sumP += a // (2**Y[i])
    elif M > 1 and i > len(Y)-1:
        sumP += a
print(sumP)

Submission status: Wrong Answer

Solution code:
import bisect
from fractions import Fraction
import math
def main():
    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))

if __name__ == "main":
    main()

Submission status: Wrong Answer

Solution code:
import math
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
a = list(map(lambda x: math.log2(x), a))
print(a)
for i in range(m):
    a[-1] -= 1
    if a[-1] != max(a):
        a = sorted(a)
print(sum(list(map(lambda x: int(2 ** x), a))))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

a_dic = {}
for i, a in enumerate(A):
    a_dic[i-1] = a

for m in range(M):
    max_a = max(a_dic, key=a_dic.get)
    a_dic[max_a] = a_dic[max_a] // 2

ans = sum(a_dic)
if ans < 0:
    ans = 0
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
num ,m =map(int,input().split())
if num == 1:
    s = int(input())
    print(s//(2**m))
    
else:
    arr = sorted(list(map(int,input().split())),reverse=True)

    for i in range(m):
        for j in range(len(arr)-1):
            if arr[j]//2 >= arr[j+1]:
                arr[j] = arr[j]//2
                break
            elif arr[j]//2 < arr[j+1]:
                arr[j] = arr[j] //2
                
                if arr[j] < arr[j+1]:
                    arr[j],arr[j+1] = arr[j+1],arr[j]
                    if len(arr) >= j+3:
                        if arr[j+1] < arr[j+2]:
                            arr[j+1],arr[j+2] = arr[j+2],arr[j+1]
                break

    print(sum(arr))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
l = sorted(list(map(int,input().split())))
l.reverse()
yl = [0]*n
r = [-(-l[0]//i) for i in l]
chk = 1
flag = False
while True:
  #group 1
  for i in range(n):
    if r[i] > chk:
        break
    elif r[i] > chk//2 :
        yl[i]+=1
        m-=1
        if m == 0:
            flag = True
        break
  if flag:
     break
  #group 2
  for i in range(n):
    if r[i] > chk//2:
      break
    else:
      yl[i]+=1
      m-=1
      if m == 0:
        flag = True
        break
  if flag:
    break
  chk *= 2
ans = 0
for i,j in zip(l,yl):
  ans += i//(2**j)
print(ans)

Submission status: Wrong Answer

Solution code:
tmp = list(map(int,(input().split())))
n = tmp[0]
m = tmp[1]

ai = list(map(int,(input().split())))
ai.sort(reverse=True)

sum = 0

for i in range(n-1):
  cnt = 0
  while (m - cnt > 0) and (ai[i] >= ai[i+1] // (2 ** cnt)) and cnt < 2:
    m -= 1
    ai[i] = ai[i] // 2
    cnt += 1

  sum += ai[i]
    
for i in range(m):
  ai[n-1] = ai[n-1] // 2
  
sum += ai[n-1]

# print(ai)
print(sum)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# submission # - User: herp_sy
# https://atcoder.jp/contests/
#
# lang: Python3 (3.4.3)

import math
import statistics
import numpy as np

def qsort(seq):
  if len(seq) < 1:
      return seq
  pivot = seq[0]
  left = []
  right = []
  for x in range(1, len(seq)):
    if seq[x] <= pivot:
        left.append(seq[x])
    else:
        right.append(seq[x])
  left = qsort(left)
  right = qsort(right)
  foo = [pivot]
  return (left + foo + right)

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

ans = 0
while m > 0:
  qsort(a)
  a[-1] = a[-1] // 2;
  m -= 1

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

print(ans)

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

price = [B[i]//(2**ticket[i]) for i in range(N)]
p_sum = sum(price)
#print(ticket,p_sum)
i = 0
while i < N-2:
    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:
import numpy as np
from copy import copy

N, M = input().split()
N = int(N)
M = int(M)

A = list(map(int, input().split(" ")))
A = np.array(A)
A = np.sort(A)[::-1]

B = np.array([0.0] * N)
i = M
j = 0
C = copy(A)

ind = 0
while i > 0:
    # print(C)
    # print(B)
    # print(A)
    B[0] += 1
    print(C[0], A[0], B[0])
    C[0] = A[0] / (2 ** B[0])
    i -= 1
    ind = np.argsort(C)[::-1]
    C = C[ind]
    B = B[ind]
    A = A[ind]
    # for ind in range(N-1):
    #     if C[0] < C[ind]:
    #         C[ind] = C[ind+1]
    #         B[ind] = B[ind+1]
    #         A[ind] = A[ind+1]
    #     else:
    #         if ind < N:
    #             C[ind] = tmp
    #             B[ind] = tmp_B
    #             A[ind] = tmp_A
    #         break

for i in range(N):
    C[i] = A[i] // (2 ** B[i])
print(sum(C))
# print(B)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=list(map(int, input().split()))
X=0
if sum(A)>= 2**M:

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

    print(sum(A))
else:
    print(X)

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,0] + a + [0,0,0]
k = 3
for i in range(m):
    ans -= -(-a[k]//2)
    if ans == 0:
        break
    a[k] = a[k]//2
    k = k+max(enumerate(a[k-3:k+4]),key = lambda x:x[1])[0]-3
print(ans)

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,-1,-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 heapq
N ,M = list(map(int,input().split()))
A = [int(x) for x in input().split()]
h = []
for i in range(N):
  heapq.heappush(h,-A[i])
for i in range(M):
  x = heapq.heappop(h)
  heapq.heappush(h,x//2)
print(-sum(h))

Submission status: Wrong Answer

Solution code:
import bisect

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

price.sort()

if m < n:
    add = sum(price[:n-m])
    price = price[n-m:]
else:
    add = 0

while m:
    p = price.pop()//2
    if len(price) < m:
        price.insert(bisect.bisect(price, p//2), p)
    elif len(price) == 0 and price[0] >= p:
        add += p
    else:
        price.insert(bisect.bisect(price, p//2), p)
    m -= 1

print(sum(price)+add)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M =map(int, input().split())
A = np.array(list(map(int, input().split())))
#print(A)
log_A = np.log2(A)

for i in range(M):
    maximum =  log_A.argmax()
    log_A[maximum] = log_A[maximum]-1
    #print(A)
A = np.power(2, log_A)
A = np.trunc(A)
print(int(A.sum()))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
M=M-1
A[0]=A[0]//2
i=0
while M>0:
    i=i+1
    if i>N-1:
        A=[0]
        break
    if A[i]>A[0]:
        A[i]=A[i]//2
        M=M-1
    else:
        A[0]=A[0]//2
        M=M-1
        A.sort(reverse=True)
        i=0
print(sum(A))

Submission status: Wrong Answer

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

a.sort()

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

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

price = [B[i]//(2**ticket[i]) for i in range(N)]
p_sum = sum(price)
print(ticket,p_sum)
i = 0
while i < N-2:
    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:
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 or a[j] == 1:
            a[j] = math.floor(a[j]/2)
            counter += 1
            if counter >= m:
                print(sum(a))
                sys.exit()
        # print(a,counter,2**i)
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:
        A[N-1]=A[N-1]//2
        A.sort(reverse = True)
        it = 0
#    print(A)
print(sum(A))

Submission status: Wrong Answer

Solution code:
#D
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
i=0
l=0
for k in range(m-1):
    if i==n-1:
        for j in range(n):
            a[j]=a[j]//2
            l+=1
    elif a[i]//2<a[i+1]:
        i+=1
    else:
        for j in range(i+1):
            a[j]=a[j]//2
            l+=1
for j in range(m-l):
    a[j]=a[j]//2
print(sum(a))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import heapq
n,m=map(int,input().split())
q=[]
a=[-int(i) for i in input().split()]
for i in a:
    heapq.heappush(q,(i,i,0))
ans=chk=0
if n==1:
    print((-a[0])//(2**m))
    exit()
while 1:
    f=1
    for i in range(m):
        x=heapq.heappop(q)
        j=-x[1]
        k=-q[0][1]
        if (i==m-1) or (j//(2**(i+1+x[2]))<k):
            f=0
            heapq.heappush(q,(-(j//(2**(i+1+x[2]))),x[1],x[2]+i+1))
            m-=(i+1)
            break
    if f:
        break
for i in q:
    ans+=-i[0]
print(ans)

Submission status: Wrong Answer

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

a[0]//=2
for i in range(1,m):
    a[a.index(max(a[:i]))] //=2
print(sum(a))

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 = map(int,input().split())
a = [int(i) for i in input().split()]
a = sorted(a)[::-1]

if len(a)>=2:
  while m>=1 and a[0] >= a[1]:
    a[0] //= 2
    m -= 1



for i in range(2,n+1):
  if m == 0:
    break
  a = sorted(a)[::-1]
  #もしこれなら、これの一つ前までを順番に半分にしていく。
  if (a[0]//2)//2 <= a[i-1]//2 and m != 0:

    #一つずつ半分に。
    for j in range(i-1):
      a[j] //= 2
      m -= 1
      if m == 0:
        break
  



print(sum(a))

Submission status: Wrong Answer

Solution code:
import math
n,m = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort(reverse = True)
discount = [] #各商品に何枚使うか
remain = m #残り枚数
if n==1:
  ans = math.floor(a[0]/(2**m))
  print(ans)
else:
  for i in range (n-1):
    if remain>0:
      left = remain
      right = 0
      while a[i+1] > a[i]*(2**(right-left+1)):
        left -= 1
        right += 1
      discount.append(left)
      remain -= left
    else:
      break
    
  ans = 0
  for i in range(len(discount)):
    ans += math.floor(a[i]/(2**(discount[i])))
  for i in range(len(discount),n):
    ans += a[i]
  print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import time

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

a_dic = {}
for i, a in enumerate(A):
    a_dic[i-1] = a

for m in range(M):
    max_a = max(a_dic, key=a_dic.get)
    a_dic[max_a] = a_dic[max_a]/2

print(sum(a_dic))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N,M = inputMap()
	A = inputList()

	if len(A) == 1:
		print(A[0] // (2**M))
		sys.exit()

	A.sort()
	A = A[::-1]
	ans = 0
	A_new = []
	mimi = -1

	for i in range(10):
		for i,val in enumerate(A):
			if i == len(A)-1:
				A_new.append(val)
				break

			if mimi < val and M > 0:
				flg = False
				for j in range(1,M+1):
					if M - j != 0:
						tmp = val // (2**j)
						if tmp < A[i+1] or tmp < mimi:
							M -= j
							A_new.append(tmp)
							flg = True
							if mimi == -1:
								mimi = tmp
							break

				if flg == False:
					tmp = val // (2**M)
					M = 0
					A_new.append(tmp)

			else:
				A_new.append(val)

		#print(A_new)
		#A = copy.deepcopy(A_new)
		A = A_new
		A.sort()
		A = A[::-1]
		A_new = []
		mimi = -1

		if M == 0:
			break

	#print(A)

	ans = 0
	for i in A:
		ans += i

	print(ans)


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
import heapq
A = list(map(int, input().split()))
A = [(-x,x) for x in A]
heapq.heapify(A)
def conf(A, M):
    if M > 0:
        a = heapq.heappop(A)[1]
        heapq.heappush(A, (-int(a/2), int(a/2)))
    else:
        return A
    return conf(A, M-1)
B = [a[1] for a in A]
print(sum(B))

Submission status: Wrong Answer

Solution code:
N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()] 
C= sum(A)
print(int(C/(C/N/M)))

Submission status: Wrong Answer

Solution code:
N,M=[int(thing) for thing in input().split(" ")]
A_list=[int(thing) for thing in input().split(" ")]
A_list.sort(reverse=True)
for aaaaa in range(M):
    com=A_list.pop(0)/2
    for i in range(len(A_list)):
        if A_list[i]<=com:
            A_list.insert(i,com)
            break
    else:A_list.append(com)

print(sum([thing//1 for thing in A_list]))

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
A = np.array(np.log2(sorted(list(map(int, input().split())), reverse=True)).astype(np.float64))
#print(A)
while True:
    A_m = np.where(A >= int(A[0]))
    if len(A_m[0]) <= M:
        A[A_m] -= 1.
        A = np.sort(A)[::-1]
        M -= len(A_m[0])
        #print(A, M)
    else:
        A[:M] -= 1.
        break
    if (2 ** A[0]).astype(np.int64) == 0:
        break
#print(A)
A = (2 ** A).astype(np.int64)
#print(A)
print(np.sum(A))

Submission status: Wrong Answer

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

A.sort(reverse=True)
A.append(0)
i=0

while M>0:
    ss=1
    while ss==1:
        if A[i]>A[i+1] and M>i:
            for j in range(i+1):
                A[j]=A[j]//2
                M-=1
        elif A[i]>A[i+1]:
            for j in range(M):
                A[j]=A[j]//2
                M-=1
            ss=0
        else:
            ss=0
    if M>0:
        for j in range(i,-1,-1):
            if A[j]<A[j+1]:
                tmp=A[j]
                A[j]=A[j+1]
                A[j+1]=tmp
            else:
                break
    
    if A[0]==0 or i==N-1:
        M=0

    i+=1

print(sum(A))

Submission status: Wrong Answer

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

top = 0
for i in range(gnum):
	top = 0
	for j in range(mnum):
		if array[top] < array[j]:
			top = j
	array[top] = array[top]/2

print(sum(array))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
N,M = [int(x) for x in input().split()]
A = sorted([-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:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N,M = inputMap()
	A = inputList()

	if len(A) == 1:
		print(A[0] // (2**M))
		sys.exit()

	A.sort()
	A = A[::-1]
	ans = 0
	A_new = []
	mimi = -1

	for i in range(10):
		for i,val in enumerate(A):
			if i == len(A)-1:
				A_new.append(val)
				break

			if mimi < val and M > 0:
				flg = False
				for j in range(1,M+1):
					if M - j != 0:
						tmp = val // (2**j)
						if tmp < A[i+1] or tmp < mimi:
							M -= j
							A_new.append(tmp)
							flg = True
							if mimi == -1:
								mimi = tmp
							break

				if flg == False:
					tmp = val // (2**M)
					M = 0
					A_new.append(tmp)

			else:
				A_new.append(val)

		#print(A_new)
		#A = copy.deepcopy(A_new)
		A = A_new
		A.sort()
		A = A[::-1]
		A_new = []
		mimi = -1

	#print(A)

	ans = 0
	for i in A:
		ans += i

	print(ans)


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

a.sort(reverse=True, key=lambda x: x[0])

i1 = 0
if len(a) == 1:
    a[0][0] = a[0][0] // (2 ** m)
else:
    while m > 0:
        if i1 == len(a)-2:
            i1 = 0
            a.sort(reverse=True, key=lambda x: x[0] // (2 ** x[1]))
        if a[i1][0] // (2 ** a[i1][1]) >= a[i1+1][0] // (2 ** a[i1+1][1]):
            a[i1][1] += 1
            m -= 1
        if a[i1][0] // (2 ** a[i1][1]) < a[i1+1][0] // (2 ** a[i1+1][1]):
            i1 += 1

ans = 0
for i in range(len(a)):
    ans += a[i][0] // (2 ** a[i][1])
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, m = map(int, input().split())
a = [int(i) for i in input().split(" ")]
a = np.sort(a)
b = np.log2(a)
if np.sum(b//1)+n < m:
    print(0)
else:
    t = b.copy()
    c = m
    ind = n-1
    while c>0:
        if (b[ind] - b[ind-1] + 1)//1*(n-ind) <= c:
            c -= (b[ind] - b[ind-1] + 1)//1*(n-ind)
            b[ind:] -= (b[ind] - b[ind-1] + 1)//1
            ind -= 1
        else:
            for i in range(int(c)):
                b[b.argmax()] -= 1
            c = 0
    tm = [2**i for i in t-b]
    print(int(np.sum(np.array(a)/tm//1)))

Submission status: Wrong Answer

Solution code:
import numpy as np

def test():
    n,m = map(int,input().split())
    a = np.array(list(map(int,input().split())))
    for i in range(m):
        b = max(a)
        a[a==b] = b//2
    print(sum(a))


if __name__ == "__main__":
    test()

Submission status: Wrong Answer

Solution code:
import math

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

A = sorted(A, reverse=True)

x = M
a = []
while x!=1:
    a.append(math.ceil(x/2))
    x = math.floor(x/2)

a.append(1)

ans = 0

a += [0]*(N - len(a))

for y, z in zip(a, A):
    ans += math.floor(z / 2**y)

print(ans)