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: Accepted

Solution code:
D = input().split(' ')
N = int(D[0])
M = int(D[1])
D2 = input().split(' ')

A = []
for i in D2:
  A.append(int(i))

A.sort(reverse=True)

used = 0

while True:
  max = A[0]
  n = 0
  while True:
    if A[n] >= int(max / 2):
      A[n] = int(A[n] / 2)
      used = used + 1
    else:
      break
      
    n = n + 1

    if n == N or used == M:
      break
      
  if used == M:
    break
    
  A.sort(reverse=True)
    
sum = 0
for i in range(N):
  sum = sum + A[i]
  
print(sum)

Submission status: Accepted

Solution code:
# from bisect import bisect_left
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

resid = M
i = 0
pi = 0
pif = True
while resid:
    A[i] //= 2
    resid -= 1
    if i < N-1 and A[i] < A[i+1]:
        if A[pi] > A[i+1]:
            A.sort(reverse=True)
            i = 0
            pi = 0
            pif = True
            continue
        if pif:
            pi = i
            pif = False
        i += 1
    else:
        i = pi
        pif = True

print(sum(A))

Submission status: Accepted

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(10000000000000000000):
		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: Accepted

Solution code:
import heapq

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

for _ in range(M):
    v = heapq.heappop(A)
    if v == 0:
        break
    v = -(-v // 2)
    heapq.heappush(A, v)

print(-1*sum(A))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
N, M = map(int, input().split())
A = list(map(int, input().split()))
h = []
for a in A:
    heappush(h, a*-1)

for i in range(M):
    val = heappop(h)*-1
    heappush(h, (val//2)*-1)

print(sum(h)*-1)

Submission status: Accepted

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: Accepted

Solution code:
import math

n, m = (int(i) for i in input().split())
alist = list(int(i) for i in input().split())
alist=sorted(alist)
blist=[]
clist=[]
for al in alist:
    blist.append(math.floor(math.log(al, 2)))
    clist.append(0)

#print(blist)
nowcount=0
now=n-1
while nowcount<=m:
    #print(clist, now, nowcount)
    if now!=0:
        if blist[now-1]==blist[now]-clist[now]:
            now-=1
        else:
            if nowcount+n-now<=m:
                nowcount+=(n-now)
                clist[now]+=1
            else:
                amari=(m-nowcount)
                #print("!")
                nowcount+=(n-now)
    else:
        if nowcount+n-now<=m:
            nowcount+=(n-now)
            clist[now]+=1
        else:
            amari=(m-nowcount)
            #print("!")
            nowcount+=(n-now)
answer=0
now=0
option=0
dlist=[]
for i in range(n):
    nowat=alist[i]
    now+=clist[i]
    for i in range(now+option):
        nowat=nowat//2
    dlist.append(nowat)

dlist=sorted(dlist)
for i in range(amari):
    dlist[n-i-1]=dlist[n-i-1]//2

print(sum(dlist))

Submission status: Accepted

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 i<M and Val[0]<Val[j]:
            Val[j]//=2
            i+=1
        else:
            Val = sorted(Val,reverse=True)
            break
    

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

Submission status: Accepted

Solution code:
import heapq
n,m = map(int,input().split())
a = list(map(int,input().split()))
arr = []
for v in a:
    v*=-1
    heapq.heappush(arr,v)
cur=0
while(m>0 and len(arr)>0):
    next = heapq.heappop(arr)
    next = abs(next)
    next//=2
    if next>0:
        next*=-1
        heapq.heappush(arr,next)
    m-=1
for v in arr:
    cur+=abs(v)
print(cur)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
import heapq
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, M = map(int, input().split())
        hq = []
        for c in input().split():
            heapq.heappush(hq, -1 * int(c))

        for _ in range(M):
            heapq.heappush(hq, int(heapq.heappop(hq) / 2))

        print(-1 * sum(hq))


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Accepted

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


for i in range(m):
    minusaa, aa  = heapq.heappop(a)
    ans -= aa
    heapq.heappush(a, (-(aa//2), aa//2))
    ans += aa//2

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math

def main():
    N, M = map(int,input().split())
    A = list(map(int,input().split()))
    B = [[] for _ in range(40)]

    Bmax = 1
    for Ai in A:
        Bi = int(math.log2(Ai)) + 1
        B[Bi].append(Ai)
        Bmax = max(Bmax, Bi)

    while M >= 0 and Bmax > 0:
        B[Bmax].sort(key=lambda x:-x)
        count = len(B[Bmax])
        Bcur = min(M, count)
        for i in range(Bcur):
            B[Bmax][i] = B[Bmax][i] // 2 
            
        Bmax -= 1
        B[Bmax].extend(B[Bmax+1])
        B[Bmax+1] = []
        M -= count

    Total = 0
    for Bi in B:
        for Ai in Bi:
            Total += Ai

    print(Total)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import numpy as np

# n, m = 4,4
# a_list = np.array([1,9,3,5])

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

a_list = np.sort(a_list)

a_logs = np.log2(a_list).astype('int64')

max_num = max(a_logs)
num = max_num*1

count_num = 0
flag = True
while(flag):
    count_num_temp = sum(a_logs>=num) + count_num
    if(count_num_temp > m):
        flag = False
        remain = m - count_num
    else:
        count_num = count_num_temp
        num -= 1
        if(num == -1):
            print('0')
            exit()

a_list = a_list // 2**((a_logs > num) * (a_logs - num))

if(remain > 0):
    a_list = np.sort(a_list)
    a_list[(n-remain):] = a_list[(n-remain):] //2

ans = sum(a_list)
print(ans)

Submission status: Accepted

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

As = input().split()
A = [0]*N

for n in range(N): 
  A[n] = float(int(As[n]))+0.1
A.sort()

tid = [0]*M
ct = -1
cid = -1
ms = 0

for m in range(M):
  if ct==-1:
    A[N-1] = A[N-1]/2.0
    tid[0] = N-1
    ct = 1
    cid = 0
  else:
    if N-1-m+ms<0 or A[tid[cid]]>A[N-1-m+ms]:
      A[tid[cid]] = A[tid[cid]]/2.0
      tid[ct] = tid[cid]
      ct += 1
      cid += 1
      ms+=1
    else:
      A[N-1-m+ms] = A[N-1-m+ms]/2.0
      tid[ct] = N-1-m+ms
      ct += 1

Asum = 0
for n in range(N):
  Asum += int(A[n])
print(Asum)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
  a[i] = a[i]*-1
heapq.heapify(a)
for _ in range(m):
  t = heapq.heappop(a)
  t = int(t/2)
  heapq.heappush(a, t)
print(sum(a)*-1)

Submission status: Accepted

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

while 1:
    a.sort(reverse=True)
    if m > 0:
        a[0] //= 2
        tmp_max = a[0] 
        m -=1
    if m == 0:
        break
    for i in range(1,n):
        if tmp_max <= a[i]:
            a[i] //= 2
            m -= 1
        if m == 0:
            break
print(sum(a))

Submission status: Accepted

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

from math import floor
import heapq

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

h = []
for ele in a:
	heapq.heappush(h, ele)

for _ in range(m):
	mx = heapq.heappop(h)
	mx /= 2
	heapq.heappush(h, mx)

ans = 0
for ele in h:
	ans += floor(-ele)

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify

n, m = [int(v) for v in input().split()]
values = [-int(v) for v in input().split()]
heapify(values)

for _ in range(m):
    v = -((-heappop(values)) >> 1)
    heappush(values, v)

print(-sum(values))

Submission status: Accepted

Solution code:
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))
    exit()

a.sort()
i = 0
while i < m:
    a[n-1] = a[n-1] // 2
    i+=1
    num = len([1 for x in a[:n-1] if x > a[n-1]])
    hoge = min(m-i, num)
    for j in range(hoge):
        a[n-2-j] = a[n-2-j] // 2
    i += hoge
    a.sort()

print(sum(a))

Submission status: Accepted

Solution code:
import heapq


def main():
    N, M = map(int, input().split())
    A_i = list(map(lambda x: -int(x), input().split()))
    heapq.heapify(A_i)
    for i in range(M):
        m = -heapq.heappop(A_i)
        m = m//2
        heapq.heappush(A_i, -m)
    print(-sum(A_i))


main()

Submission status: Accepted

Solution code:
# coding: utf-8


def idx(n):
    i = 0
    while True:
        if 2**i > n:
            return i - 1
        i += 1


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

    a_max = max(A)
    K = idx(a_max) + 1

    pow_list = [[] for _ in range(K)]
    for a in A:
        pow_list[idx(a)].append(a)

    # print(pow_list)

    no_k0 = False
    for k in range(K-1, 0, -1):  # k=1までの処理
        # print("-------")
        # print(M)
        # print(k)
        # print(pow_list)
        if len(pow_list[k]) <= M:
            tmp = [p // 2 for p in pow_list[k]]
            pow_list[k-1].extend(tmp)
            M -= len(pow_list[k])

            if M == 0:
                limit = k
                no_k0 = True
                break
        else:  # len(...) > M
            pow_list[k] = sorted(pow_list[k], reverse=True)
            pow_list[k-1].extend([p // 2 for p in pow_list[k][0:M]])
            for i in range(M):
                pow_list[k][i] = 0
            limit = k + 1
            no_k0 = True
            break

    if not no_k0:
        if len(pow_list[0]) <= M:
            return 0
        else:
            pow_list[0] = sorted(pow_list[0], reverse=True)
            for m in M:
                pow_list[0][m] = 0
            return sum(pow_list[0])

    ans = 0
    for i in range(limit):
        ans += sum(pow_list[i])

    return ans


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
A = map(int, input().split())
AA = [-1 * x for x in A]
#print(AA)
heapq.heapify(AA)

for i in range(M):
  a = heapq.heappop(AA)
  #print(a, -a>>1)
  heapq.heappush(AA, -(-a >> 1))

print(-sum(AA))

Submission status: Accepted

Solution code:
import sys, math
sys.setrecursionlimit(5 * 10**5)
input=sys.stdin.readline

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

groups = [list() for _ in range(31)]

for a in A:
    for i in range(31):
        if a < 2**i:
            groups[i].append(a)
            break

for i in range(30, 0, -1):
    if len(groups[i]) > 0:
        if len(groups[i]) <= M:
            M -= len(groups[i])
            for e in groups[i]:
                groups[i-1].append(e / 2)
            groups[i].clear()
        else:
            groups[i].sort()
            for j in range(len(groups[i])-1, len(groups[i])-1-M, -1):
                groups[i-1].append(groups[i].pop(j) / 2)
            break

ans = 0

for group in groups:
    for e in group:
        ans += math.floor(e)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N, M=map(int, input().split())
A=np.sort(np.array(list(map(int, input().split()))))
P=np.array([int(np.log2(A[i])) for i in range(N)])

maxp=P[-1]
while M>0:
  temp=np.sum(P==maxp)
  if temp<=M:
    P[-temp:]=P[-temp:]-1
    A[-temp:]=A[-temp:]//2
    M-=temp
  else:
    A=np.sort(A)
    A[-M:]=A[-M:]//2
    M=0
    
  if np.sum(A)==0:
    break
  maxp-=1
    
print(np.sum(A))

Submission status: Accepted

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

A = sorted(A,reverse=True)
#print(A)
X = M
for i in range(M):
    A[0] //= 2
    X -= 1
    count = 0
    for j in range(min(N-1,M)):
        if A[j] < A[j+1]:
            x = A[j]
            A[j] = A[j+1]
            A[j+1] = x
            count += 1
        else:
            break
            
    if count >= X:
        for j in range(X):
            A[j] //= 2
        break
    else:
        for j in range(count):
            A[j] //= 2
        X -= count
        A = sorted(A,reverse=True)
        
        
ans = 0
for i in A:
    ans += i

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
nums = list(map(int, input().split()))
tik = 0
while tik < M:
    nums.sort(reverse=True)
    nums[0] = nums[0] // 2 
    tik += 1
    if tik == M:
        break
    for i in range(1,N):
        if tik == M:
            break
        if nums[i] > nums[0]:
            nums[i] = nums[i] // 2
            tik += 1
        else:
            break
print(sum(nums))

Submission status: Accepted

Solution code:
# 2019/09/15
# AtCoder Beginner Contest 141 - D

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

# Sort
a.sort()
a.reverse()

divlist = list()
divlist.append(int(a[0] / 2)) # Case 0
idx = 1
zflg = False

for i in range(1, m):
    if idx < n:
        if divlist[0] < a[idx]:
            # 元のリストの値 > 割ったリストの先頭
            divlist.append(int(a[idx] / 2))
            idx = idx + 1
    
        else:
            # 元のリストの値 <= 割ったリストの先頭
            popval = divlist.pop(0)
            divlist.append(int(popval / 2))
    else:
        # 全て割引券を使っても余っているケース
        if divlist[0] <= 0:
            zflg = True
            break
        else:
            # 元のリストの値 <= 割ったリストの先頭
            popval = divlist.pop(0)
            divlist.append(int(popval / 2))

ans = 0
if zflg == False:
    # 割引券を使ったもの
    for i in range(len(divlist)):
        ans = ans + divlist[i]
    
    # 割引券を使わなかったもの
    for i in range(idx, n):
        ans = ans + a[i]

# Output
print(ans)

Submission status: Accepted

Solution code:
import heapq

def solve(N, M, A):
    q = []
    for a in A:
        heapq.heappush(q, -a)
    for i in range(M):
        a = heapq.heappop(q)
        heapq.heappush(q, a / 2)
    return -sum([int(v) for v in q])

def main():
    N, M = map(int, input().strip().split())
    A = map(int, input().strip().split())
    print(solve(N, M, A))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

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

tmp = 0
heapq.heapify(A)
for i in range(M):
    tmp = heapq.heappop(A) * (-1) // 2
    heapq.heappush(A, (-1) * tmp)
print(sum(A) * (-1))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
A = list(map(int, input().split()))
hp = []
for i in range(N):
    heappush(hp, A[i] * -1)
for i in range(M):
    tmp = heappop(hp)
    heappush(hp, -(-tmp // 2))
print(sum(hp) * -1)

Submission status: Accepted

Solution code:
import math
import heapq
from heapq import heapify

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

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    lastelt = heap.pop() 
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

for _ in range(M):
  x = math.floor(_heappop_max(A)/2)
  _heappush_max(A,x)
print(sum(A))