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:
import heapq
def main():
    N, M = map(int, input().split())
    a = list(map(lambda x: -int(x), input().split()))

    heapq.heapify(a)
    for i in range(M):
        temp = heapq.heappop(a)
        heapq.heappush(a, -(-temp//2))
    print(-sum(a))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

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

A = list(map(lambda x:-x,A))

heapq.heapify(A)

for i in range(M):
    x = heapq.heappop(A)
    heapq.heappush(A,x/2)

ans = 0

for i in range(N):
    x = heapq.heappop(A)
    ans += int(-x)

print(ans)

Submission status: Accepted

Solution code:
import heapq  # heapqライブラリのimport

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

heapq.heapify(A)  # リストを優先度付きキューへ

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

Submission status: Accepted

Solution code:
# coding: utf-8
import heapq

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

prices = [-int(x) for x in input().split(" ")]

heapq.heapify(prices)

for i in range(M):
    maxp = heapq.heappop(prices)
    heapq.heappush(prices, -((-maxp) // 2))

total = 0
for x in prices:
    total += -x

print(total)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

n,m = list(map(int,input().split()))
a = list(map(lambda x : int(x) * (-1) ,input().split()))

from heapq import heappush, heappop, heapify

heapify(a)
for i in range(m):
    tmp_min = (-1)*heappop(a)//2*(-1)
    heappush(a,tmp_min)

print(sum(list(map(lambda x : int(x * (-1)),a))))

Submission status: Accepted

Solution code:
import heapq
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A = [-i for i in A]
    heapq.heapify(A)
    for _ in range(M):
        t = heapq.heappop(A)
        heapq.heappush(A, t/2)
    return sum(int(-i) for i in A)
print(main())

Submission status: Accepted

Solution code:
import heapq


def main():
    n, m = map(int, input().split())
    a_list = list(map(lambda x: -int(x), input().split()))

    heapq.heapify(a_list)
    for _ in range(m):
        a = heapq.heappop(a_list)
        heapq.heappush(a_list, -(-a // 2))

    print(-sum(a_list))


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) * a[i]

heapq.heapify(a)

for i in range(m):
    d = heapq.heappop(a)
    heapq.heappush(a,d/2)

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

print(ans)

Submission status: Accepted

Solution code:
import heapq as hq
N, M = map(int, input().split())
A = list(map(lambda x: -int(x), input().split()))

hq.heapify(A)

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

print(-sum(A))

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] = A[i]*(-1)

heapq.heapify(A)

for i in range(m):
    value = heapq.heappop(A)
    value /= 2
    heapq.heappush(A, value)

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

Submission status: Accepted

Solution code:
import heapq

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

ma = []
for i in a:
    ma.append(-i)

heapq.heapify(ma)
for i in range(m):
    b = (-heapq.heappop(ma) // 2)
    heapq.heappush(ma, -b)

ans = 0
for i in ma:
    ans -= i

print(ans)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
a = list(map(lambda x: -int(x), input().split()))
heapq.heapify(a)
for _ in range(m):
  heapq.heappush(a, -(-heapq.heappop(a) // 2))
print(-sum(a))

Submission status: Accepted

Solution code:
import heapq as H

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

for _ in range(M):
    x = H.heappop(A)
    H.heappush(A, int(x / 2))

print(-sum(A))

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [-a for a in A]
heapify(A)
for _ in range(M):
    a = heappop(A)
    heappush(A, -(-a//2))
print(-sum(A))

Submission status: Accepted

Solution code:
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):
  x=heapq.heappop(A)
  y=(((-1)*x)//2)*(-1)  
  heapq.heappush(A,y)
print((-1)*sum(A))

Submission status: Accepted

Solution code:
# dequeにinsert追加されたのは 3.5 から
from heapq import heappop,heappush,heapify
n,m = map(int,input().split())
aa = list(map(int,input().split()))
aa = list(map(lambda x:-x,aa))

heapify(aa)
for i in range(m):
  tmp = heappop(aa)  
  heappush(aa,-(-tmp//2))

print(-sum(aa))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, heapq


def main():
    
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    value = [-int(inp) for inp in input().split()]

    heapq.heapify(value)

    for _ in range(M):
        elem = heapq.heappop(value)
        if elem == 0:
            break
        if elem % 2 == 0: 
        	elem //= 2
        else:
        	elem = elem // 2 + 1
        heapq.heappush(value, elem)

    print(- sum(value))
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys, heapq


def main():
    
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    value = [-int(inp) for inp in input().split()]

    heapq.heapify(value)

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

    print(- sum(value))
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys, heapq


def main():
    
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    value = []
    heapq.heapify(value)
    for inp in input().split():
        heapq.heappush(value, -int(inp))

    for _ in range(M):
        new_elem = -(- heapq.heappop(value) // 2)
        heapq.heappush(value, new_elem)

    print(- sum(value))
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys, heapq


def main():
    
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    value = [-int(inp) for inp in input().split()]

    heapq.heapify(value)

    for _ in range(M):
        new_elem = -(- heapq.heappop(value) // 2)
        heapq.heappush(value, new_elem)

    print(- sum(value))
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

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

targets = [int(value) for value in targets]
rev = [num * -1 for num in targets]
heapq.heapify(rev)
for i in range(m):
    tmp = -1 * heapq.heappop(rev) // 2
    heapq.heappush(rev,-1 * tmp)

targets = [num * -1 for num in rev]
print(sum(targets))

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(a)
for i in range(m):
    max = heapq.heappop(a)
    heapq.heappush(a,int(max/2))

print(sum(a) * (-1))

Submission status: Accepted

Solution code:
import heapq

N, M = map(int,input().strip().split())
alist = map(int, input().strip().split())

nalist = [-i for i in alist]
heapq.heapify(nalist)
for _ in range(M):
    a = int((heapq.heappop(nalist)+1)//2)
    heapq.heappush(nalist, a)

print(-sum(nalist))

Submission status: Accepted

Solution code:
# coding:utf-8
import heapq

N, M = map(int, input().split(' '))
A_rev = [int(n) * -1 for n in input().split(' ')]

heapq.heapify(A_rev)

for i in range(M):
    d, m = divmod(heapq.heappop(A_rev), 2)
    if m != 0: d += 1
    heapq.heappush(A_rev, d)

print(-sum(A_rev))

Submission status: Accepted

Solution code:
import heapq

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

minus_a_list = [-a for a in a_list]
heapq.heapify(minus_a_list)

for _ in range(M):
    value = -(heapq.heappop(minus_a_list))
    heapq.heappush(minus_a_list, -(value//2))

print(-sum(minus_a_list))

Submission status: Accepted

Solution code:
import heapq as hq
n,m=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(lambda x: x*(-1),A))
hq.heapify(B)
for i in range(m):
  x=hq.heappop(B)
  hq.heappush(B,(x+1)//2)

print(sum(B)*(-1))

Submission status: Accepted

Solution code:
import heapq

N,M=map(int,input().split())
A=[-int(a) for a in input().split()]

heapq.heapify(A)

for _ in range(M):
  a=-(-heapq.heappop(A)//2)
  heapq.heappush(A,a)
print(-sum(A))

Submission status: Accepted

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

import heapq
import math

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

heapq._heapify_max(a)

for i in range(m):
  temp=math.floor(_heappop_max(a)/2)
  _heappush_max(a,temp)

print(sum(a))

Submission status: Accepted

Solution code:
import sys
import heapq

N, M = map(int, sys.stdin.readline().split())
A = list(map(lambda x: int(x) * -1, sys.stdin.readline().split()))

heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

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

import heapq

q = [(-Ai, i) for i, Ai in enumerate(A)]
heapq.heapify(q)

M_tmp = M
while M_tmp > 0:
    penalty, i = heapq.heappop(q)
    #
    Ai_tmp = (-penalty) // 2
    heapq.heappush(q, (-Ai_tmp, i))
    M_tmp -= 1

ans = sum([-penalty for penalty, i in q])
print(ans)

Submission status: Accepted

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

n,m = map(int, input().split(' '))
a_list = [-1 * int(i) for i in input().split() ]
heapq.heapify(a_list)
 
for _ in range(m):
    p = heapq.heappop(a_list)
    q = (-1*p //2) * (-1)
    heapq.heappush(a_list, q)    
    
print(-sum(a_list))

Submission status: Accepted

Solution code:
import heapq

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

for i in input().split():
    heapq.heappush(a,-int(i))

for j in range(m):
    highest = heapq.heappop(a)
    heapq.heappush(a,-(-highest//2))

print(-(sum(a)))

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

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

for i in range(M):
    heappush(A, -(-heappop(A) // 2))

print(-sum(A))

Submission status: Accepted

Solution code:
from queue import PriorityQueue

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

for a in A:
    queue.put(-a)

for i in range(M):
    a = -queue.get()
    a /= 2
    queue.put(-a)

ans = 0
for i in range(N):
    ans += int(-queue.get())
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(1)][0]
A = [-1*x for x in A]

import heapq
heapq.heapify(A)

while M != 0:
    x = heapq.heappop(A)
    y = -x // 2
    heapq.heappush(A, -y)
    M -= 1

A = [-1*x for x in A]
print(sum(A))

Submission status: Accepted

Solution code:
import heapq

N , M = map(int,input().split())
A = [-int(i) for i in input().split()]
heapq.heapify(A)
for _ in range(M):
    a = -heapq.heappop(A) >> 1
    heapq.heappush(A,-a)
print(-sum(A))

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

[N,M] = inpl()
Alist = inpl()

minusA = [-x for x in Alist]
heapq.heapify(minusA)
for i in range(M):
    temp = heapq.heappop(minusA)
    heapq.heappush(minusA,-(-temp//2))

ans = - sum(minusA)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
ind=[0]*N
import bisect
t=A[-1]
k=0
while(1):
  if k==M:
    break
  t=t/2
  a=bisect.bisect_right(A,t)
  b=N-a
  if b+k>M:
    break
  for j in range(b):
    j1=j+1
    ind[-j1]+=1
  k+=b
if k!=M:
  S=0
  for i in range(N):
    A[i]=(A[i]/(2**ind[i]))
  A.sort()
  ind2=[0]*N
  for j in range(M-k):
    ind2[-1-j]=1
  for i in range(N):
    S+=(A[i]//(2**ind2[i]))
  print(int(S))
else:
  S=0
  for i in range(N):
    S+=(A[i]//(2**ind[i]))
  print(S)

Submission status: Accepted

Solution code:
import heapq 
import math 
n,m = map(int,input().split())
a = list(map(lambda x:int(x)*(-1), input().split()))
heapq.heapify(a)
for i in range(m):
    p = heapq.heappop(a)
    p = math.ceil(p/2)
    heapq.heappush(a,p)
print(sum(a)*(-1))

Submission status: Accepted

Solution code:
import heapq

n,m=map(int,input().split())
a=[-int(i) for i in input().split()]

heapq.heapify(a)
for i in range(m):
 max=-heapq.heappop(a)
 heapq.heappush(a,-1*(max//2))

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq

n,m=map(int,input().split())
a=[-int(i) for i in input().split()]

heapq.heapify(a)
for i in range(m):
 max=-heapq.heappop(a)
 heapq.heappush(a,-1*(max//2))

print(sum([-int(i) for i in a]))

Submission status: Accepted

Solution code:
# 最大値を見つけ、それを２で割るをチケットがなくなるまで繰り返す
# 普通にやると、最大値の選定でO(n)、それをチケット数分だけ繰り返すのでO(n*m)。
# 間に合わないので、優先度付きキューを用いる
import math
import heapq

n, m = map(int, input().split())
a = [0] * n
a = list(map(int, input().split()))

a = list(map(lambda x: x*(-1), a))
heapq.heapify(a)
for _ in range(m):
    tmp = heapq.heappop(a) * (-1)
    tmp = math.floor(tmp / 2) * (-1)
    heapq.heappush(a, tmp)

print(sum(list(map(lambda x: x*(-1), a))))

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l_ = list(map(int, input().split()))
l = [(-1)*l_[i] for i in range(n)]

import heapq
heapq.heapify(l)

for i in range(m):
  x = (-1)*heapq.heappop(l)
  heapq.heappush(l, (x//2)*(-1))

print(sum(l)*(-1))

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))

heapq.heapify(a)

for _ in range(m):
	tmp_min = heapq.heappop(a)
	heapq.heappush(a, (-1)*(-tmp_min//2))

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq
n,m = map(lambda x: int(x), input().split())
a = list(map(lambda x: int(x)*(-1),input().split()))
heapq.heapify(a)

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = []
for a in A:
    B.append(-a)

# 最大値を取り出せば良い → プライムキュー
import heapq
heapq.heapify(B)
for i in range(M):
    b = heapq.heappop(B)
    b = -b // 2
    b = -b
    heapq.heappush(B, b)

res = -sum(B)
print(res)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    import bisect
    import math
    import sys
    import heapq
    def f(s):
        return -int(s)

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

    for i in range(m):
        tmp=heapq.heappop(a)
        tmp=math.ceil(tmp/2)
        heapq.heappush(a,tmp)

    print(-sum(a))
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
A=[-int(i) for i in input().split()]
heapq.heapify(A)
for _ in range(M):
    s = heapq.heappop(A)
    if s % 2 == 0:
        heapq.heappush(A, s//2)
    else:
        heapq.heappush(A, s//2 + 1)
print(-sum(A))

Submission status: Accepted

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

while M>0:
    A.sort(reverse=True)
    if A[0]==0:
        break
    judge=A[0]//2
    for i in range(len(A)):
        if A[i]>judge and M>0:
            A[i]=A[i]//2
            M-=1
        else:
            break
print(sum(A))

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
li = [-int(x) for x in input().split()]
heapq.heapify(li)
for i in range(m):
  a = heapq.heappop(li)
  heapq.heappush(li, a/2)
print(-sum(int(x) for x in li))

Submission status: Accepted

Solution code:
import heapq

class PriorytyQueue(object):

    def __init__(self, arr, target='min'):
        self.arr = arr
        self.target = target
        self._heapify()
    
    def _heapify(self):
        if self.target == 'max':
            self.arr = list(map(lambda x:x*(-1), self.arr))
        heapq.heapify(self.arr)
    
    def push(self, x):
        if self.target == 'max':
            x *= -1
        heapq.heappush(self.arr, x)

    def pop(self):
        res = heapq.heappop(self.arr)
        if self.target == 'max':
            return res*(-1)
        else:
            return res
    
    def get_arr(self):
        if self.target == 'max':
            return list(map(lambda x:x*(-1), self.arr))
        else:
            return self.arr

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

A = PriorytyQueue(A, target='max')

for i in range(M):
    max_A = A.pop()
    A.push(max_A//2)

print(sum(A.get_arr()))

Submission status: Accepted

Solution code:
import heapq

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

A = list(map(lambda x:x*(-1), A))
heapq.heapify(A)

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

print(sum(A) * -1)

Submission status: Accepted

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

N,M = map(int,input().split())
A = [-int(i) for i in input().split()]
heapq.heapify(A)

for _ in range(M):
    tmp = heapq.heappop(A)
    # 計算誤差を減らすためにtmpを正に直してシフト演算している
    heapq.heappush(A, (-1)*(-tmp >> 1))

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(hp)

for i in range(m):
    tmp = heapq.heappop(hp)
    heapq.heappush(hp, int(tmp / 2))

print(-sum(hp))

Submission status: Accepted

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

N, M = list(map(int, input().strip().split()))
A = [-int(x) for x in input().strip().split()]
heapq.heapify(A)
for m in range(M):
    a = heapq.heappop(A)
    heapq.heappush(A, a / 2)
print(sum([int(-a) for a in A]))

Submission status: Accepted

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

import heapq

pq = [-1 * x for x in nums]
heapq.heapify(pq)
for _ in range(M):
    x = -heapq.heappop(pq)
    heapq.heappush(pq, -(x//2))

print(-sum(pq))

Submission status: Accepted

Solution code:
# 毎回ソートしても別にいいんじゃないの -> ダメでした
# 毎回最大のものがほしいならheapq使うか
import heapq

n, m = map(int, input().split())
# heapは最小のものを取り出すので予め-1をかけて大小を見かけ上逆転しておく
arr = list(map(lambda x: int(x) * -1, input().split()))
heapq.heapify(arr)
for _ in range(m):
    a = heapq.heappop(arr)
    # 負数にしたときの誤差がめんどくさい
    a *= -1
    a //= 2
    heapq.heappush(arr, a * -1)
print(sum(arr) * -1)

Submission status: Accepted

Solution code:
import heapq
N,M =map(int,input().split())
A=[-int(x) for x in input().split()]#大きい順で扱う為にマイナスを付ける

heapq.heapify(A)#Aを優先度付キューへ変換

for i in range(M):
  saitakane = heapq.heappop(A)#最高値を取り出す
  heapq.heappush(A,-(-saitakane//2))#切り捨ての為に正の数にしてから半分にして戻す（追加）
print(-sum(A))

Submission status: Accepted

Solution code:
import sys
import heapq
sys.setrecursionlimit(10**6)
def MAP(): return [int(s) for s in input().split()]

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline

N, M = MAP()
# heapq.heappop（優先度『最小』の品物をO(logN)で取得）のため入力値をマイナスに変換
A = [int(s)*-1 for s in input().split()]

# 品物のリストをheapqのオブジェクトに変換
heapq.heapify(A)

while M > 0:
	# 以下、heapq　の計算誤差を防ぐため、(1) も (2) もそれぞれ -1 をかける
	# (1) 最小値を取り出す
	discount = heapq.heappop(A)*-1
	# (2) 最小値を2で切り捨て割ったものをAに戻す
	heapq.heappush(A, discount//2*-1)
	M -= 1

print(sum(A)*-1)

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)
for _ in range(M):
    heapq.heappush(A, -1 * (-1 * heapq.heappop(A) // 2))

print(-1 * sum(A))

Submission status: Accepted

Solution code:
import heapq

n,m=map(int,input().split())
a=[-int(i) for i in input().split()]
heapq.heapify(a)

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

Submission status: Accepted

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

heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect

MOD = 10**9+7

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

# 複数個の数値を、intの配列として取得
A = list(map(int, input().split()))
A = list(map(lambda x: x * (-1),A))

heapq.heapify(A)
for i in range(M):
    x = heapq.heappop(A)
    heapq.heappush(A,x/2)

ans=0
for a in A:
    ans+=math.floor(-a)

print(ans)

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
    
heapq.heapify(a)
#print(a)

for i in range(m):  
    t=heapq.heappop(a)
    t*=-1
    t//=2
    t*=-1
    heapq.heappush(a,t)
    
ans=0
for i in range(n):
    ans-=a[i]
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)

# print(A) #DB

for i in range(M):
    x=heapq.heappop(A)
    heapq.heappush(A,(x+1)//2)
    # print(A) #DB

ans=-sum(A)

print(ans)

Submission status: Accepted

Solution code:
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):
    tmp_min = heapq.heappop(A)
    heapq.heappush(A, (-1)*(-tmp_min//2))
print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)

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

Submission status: Accepted

Solution code:
import heapq
n,m = map(int, input().split())
a =list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)

used = 0
for _ in range(m):
  tmp = heapq.heappop(a)
  heapq.heappush(a, -1*(-tmp//2))
print(-sum(a))

Submission status: Accepted

Solution code:
#import numpy as np
import sys
import heapq #優先度付きキュー
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
a = [int(i)*(-1) for i in input().split()] #各要素*(-1)
heapq.heapify(a)
for i in range(m):
    """
    k = np.argmax(a)
    if a[k] == 0:
        break
    a[k] = int(a[k]/2)
    """
    tmp = heapq.heappop(a) #最小値を抜き取る(最大値*(-1)を抜き取る）
    heapq.heappush(a, (-1)*(-tmp//2)) #要素を追加
ans = -sum(a)
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

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

    print(-sum(A))
    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
import math

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

a = list(map(lambda x: x*(-1), a))
heapq.heapify(a)

for i in range(m):
    max = heapq.heappop(a)
    heapq.heappush(a, math.ceil(max/2))

print(-sum(a))

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
heapq.heapify(a)
for i in range(m):
  heapq.heappush(a,(heapq.heappop(a)+1)//2)
print(-sum(a))

Submission status: Accepted

Solution code:
import heapq

n, m = map(int,input().split())
price = list(map(int, input().split()))
price = list(map(lambda x: x*(-1), price))
heapq.heapify(price)
while m != 0:
    maxv = heapq.heappop(price)
    heapq.heappush(price, (maxv+1) // 2)
    m -= 1
print(sum(price) * (-1))

Submission status: Accepted

Solution code:
import heapq

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

que = []
for a in A:
  heapq.heappush(que, -1*a)
 
for a in range(M):
  maxvalue = -1 * heapq.heappop(que)
  maxvalue /= 2
  heapq.heappush(que, -1*maxvalue)
 
print(sum([int(-1*a) for a in que]))

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
a = [int(_) for _ in input().split()]
que = []
for _ in a:
  heapq.heappush(que, -1*_)

for _ in range(m):
  maxvalue = -1 * heapq.heappop(que)
  maxvalue /= 2
  heapq.heappush(que, -1*maxvalue)

print(sum([int(-1*_) for _ in que]))

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
al = list(map(lambda x: (-1) * int(x), input().split()))
heapq.heapify(al)

for _ in range(m):
    al_min = heapq.heappop(al)
    heapq.heappush(al, (-1) * (-al_min // 2))

print(-sum(al))