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:
class Heap:
    def __init__(self,n):
        self.sz = 0
        self.list = []
    def push(self,x): #xを追加
        i = self.sz
        self.list.append(x)
        self.sz += 1
        while i > 0 :
            p = int((i-1)/2)
            if self.list[p] < x :
                self.list[i] = self.list[p]
                i = p
            else :
                break
        self.list[i] = x
    def pop2(self):
        ret = self.list[0]
        x = self.list[-1]
        self.list.pop()
        self.sz -= 1

        i = 0
        while (i*2)+1 < self.sz :
            a = 2 * i + 1
            b = 2 * i + 2
            if b < self.sz and self.list[a] < self.list[b]:
                a = b
            if self.list[a] <= x :
                break
            self.list[i] = self.list[a]
            i = a
        self.list[i] = x
        return ret


N ,M = map(int,input().split())
a = [int(i) for i in input().split()]
heap = Heap(N)
for i in range(N):
    heap.push(a[i])
for i in range(M):
    if len(heap.list) == 1 :
        heap.push(0)
    p = heap.pop2()
    heap.push(int(p/2))
print(sum(heap.list))

Submission status: Accepted

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

num_product, num_coupon = [int(s) for s in input().split()]
price_list = []
for s in input().split():
  heapq.heappush(price_list, int(s)*-1)

for i in range(num_coupon):
  min = price_list[0]
  heapq.heapreplace(price_list, (min*-1//2)*-1)

sum = 0
for price in price_list:
  sum -= price

print(sum)

Submission status: Accepted

Solution code:
import heapq

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

for i in range(n):
    num = a[i]*(-1)
    heapq.heappush(list,num)

for i in range(m):
    maximum = heapq.heappop(list)
    if maximum%2 == 0:
        maximum = maximum//2
    else:
        maximum = (maximum//2)+1
    heapq.heappush(list,maximum)
#    print(list)

ans = 0
minimum = 0

for i in range(n):
    minimum = heapq.heappop(list)
    minimum = minimum*(-1)
    ans = ans + minimum

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

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

for discount_i in range(m):
  target = -1*(-1*heapq.heappop(item_list)//2)
  heapq.heappush(item_list, target)

print(-1*sum(item_list))

Submission status: Accepted

Solution code:
import heapq

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

for aa in A:
    heapq.heappush(q,-aa)

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

print(sum(-int(x) for x in q))

Submission status: Accepted

Solution code:
import sys
import os
import math
import heapq

N, M = map(int,input().split())
A = list(map(int,input().split()))
#大きいものから取り出したいので-1倍してqueueに入れる

Q = []
for a in A:
    heapq.heappush(Q,-a)

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

print(-sum(Q))

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

Solution code:
import heapq

N, M = [int(n) for n in input().split()]
A = [-1*int(n) for n in input().split()]
heapq.heapify(A)
[heapq.heappush(A, -1*(-1*heapq.heappop(A)//2)) for _ in range(M)]   
print(-1*sum(A))

Submission status: Accepted

Solution code:
import heapq

N, M = [int(n) for n in input().split()]
hq = []
[heapq.heappush(hq, v) for v in [-1*int(n) for n in input().split()]]
[heapq.heappush(hq, -1*(-1*heapq.heappop(hq)//2)) for _ in range(M)]
print(-1*sum(hq))

Submission status: Accepted

Solution code:
import heapq

N, M = [int(n) for n in input().split()]
hq = []
[heapq.heappush(hq, v) for v in [-1*int(n) for n in input().split()]]
for _ in range(M):
   heapq.heappush(hq, -1*(-1*heapq.heappop(hq)//2))
print(-1*sum(hq))

Submission status: Accepted

Solution code:
import heapq

N, M = [int(n) for n in input().split()]
A = [-1*int(n) for n in input().split()]
hq = []
[heapq.heappush(hq, v) for v in A]
for _ in range(M):
   heapq.heappush(hq, -1*(-1*heapq.heappop(hq)//2))
print(-1*sum(hq))

Submission status: Accepted

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

Submission status: Accepted

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

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):
    Min=heapq.heappop(a)
    Min=(-Min//2)*-1
    heapq.heappush(a,Min)
print(sum(a)*-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 i in range(m):
  a_min = heapq.heappop(a)
  heapq.heappush(a,(-1)*(-a_min // 2))
print(-sum(a))

Submission status: Accepted

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

a_list = [(-a,a) for a in a_list]

import heapq

heapq.heapify(a_list)
for i in range(M):
#     print(a_list)
    max_a = heapq.heappop(a_list)[1]
    tpl = (-(max_a//2),max_a//2)
    heapq.heappush(a_list, tpl)

print(sum([a for _,a in a_list]))

Submission status: Accepted

Solution code:
from heapq import *
n,m,*a=map(lambda x:-int(x),open(0).read().split())
heapify(a)
for i in range(-m):heappush(a,int(heappop(a)/2))
print(-sum(a))

Submission status: Accepted

Solution code:
import heapq,math
n,m=map(int,input().split())
def aaa(x):
    return -1.0*float(x)
a=list(map(aaa,input().split()))
heapq.heapify(a)
for _ in range(m):
    x=heapq.heappop(a)*-1
    x/=2
    heapq.heappush(a,x*-1)

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

for i in range(n):
    a[i]=math.floor(a[i])

print(sum(a))

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
li = list(map(lambda x:int(x) * (-1), input().split()))
heapq.heapify(li)
for i in range(M):
  max_price = heapq.heappop(li)*(-1)
  heapq.heappush(li, (-1) * (max_price // 2))
print(-sum(li))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#abc141_d
import heapq

n,m = [int(i) for i in input().split()]
a = [-1 * int(i) for i in input().split()]
heapq.heapify(a)    
#print(a)

for _ in range(m): 
    big = heapq.heappop(a)
    big = int(big/2)    
    heapq.heappush(a, big)
    #print(a)

print(-1*sum(a))

Submission status: Accepted

Solution code:
import numpy as np
import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
A = [x*(-1) for x in A]
heapq.heapify(A)
for i in range(M):
  heapq.heapreplace(A,int(A[0]/2))
print(-sum(A))

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
from math import floor
n, m = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
a = [x*(-1) for x in a]
heapify(a)
for _ in range(m):
    x = floor(-heappop(a)/2)*(-1)
    heappush(a, x)

print(-sum(a))

Submission status: Accepted

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

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

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())
price_list =list(map(lambda x : -int(x),input().split()))
heapq.heapify(price_list)

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

Submission status: Accepted

Solution code:
import heapq
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

heapq.heapify(A)

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

print(-1*sum(A))

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split(' '))
prices = list(map(lambda x: x * (-1), map(int, input().split(' '))))

# 優先度付きキューに変換
heapq.heapify(prices)

for i in range(M):
    # 最大のものを半額にしてまたキューに突っ込む
    heapq.heappush(prices, ((heapq.heappop(prices) * (-1)) // 2) * -1)

print(sum(prices) * -1)

Submission status: Accepted

Solution code:
import heapq
import sys
def input():
    return sys.stdin.readline()[:-1]

# input
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:
import heapq
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
for i in range(n):
  a[i] *= -1

heapq.heapify(a)
for i in range(m):
    heapq.heapreplace(a, int(a[0] / 2))

print(sum(a)*-1)

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import bisect, heapq
n,m=map(int,input().split())
a=list(map(lambda s: -int(s),input().split()))
heapq.heapify(a)
for i in range(m):
    e=-heapq.heappop(a)
    e=e//2
    heapq.heappush(a,-e)
print(-sum(a))

Submission status: Accepted

Solution code:
import heapq


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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import math
 
N,M = [int(i) for i in input().split(' ')]
inputList = [int(i) for i in input().split(' ')]
list = []
 
for i in inputList:
    heappush(list, -i)
 
for _ in range(M):
    heappush(list, math.ceil(heappop(list)/2))
    
print(-sum(list))

Submission status: Accepted

Solution code:
import sys
import heapq
sys.setrecursionlimit(100002)
input=sys.stdin.readline
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]=-a[i]
heapq.heapify(a)
for i in range(m):
  heapq.heappushpop(a,-(-a[0]//2))
print(-sum(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: x*(-1), A))

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 math
import heapq
n,m = map(int,input().split())

a = input()
list1 = list(map(int,a.split()))
list1 = [i*-1 for i in list1]
heapq.heapify(list1)

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

print(int(math.fabs(sum(list1))))

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)
while(m):
    heapq.heapreplace(a, -(-a[0] // 2))
    m -= 1
res = -sum(a)
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
heapq.heapify(a)
while(m):
    heapq.heapreplace(a, int(a[0] / 2))
    m -= 1
res = -sum(a)
print(res)

Submission status: Accepted

Solution code:
from heapq import*;n,m,*a=eval(',-'.join(open(0).read().split()));x=0;a.sort();exec('x=heappushpop(a,-~x//2);'*-~-m);print(-x-sum(a))

Submission status: Accepted

Solution code:
from heapq import*;n,m,*a=eval(',-'.join(open(0).read().split()));x=0;a.sort();exec('x=heapreplace(a,-~x//2);'*-m);print(x//-2-sum(a))

Submission status: Accepted

Solution code:
from heapq import*;n,m,*a=eval(',-'.join(open(0).read().split()));a.sort();exec('heappush(a,-~heappop(a)//2);'*-m);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 _ in range(M):
    t = -heapq.heappop(A) // 2
    heapq.heappush(A, -t)

print(-sum(A))

Submission status: Accepted

Solution code:
from heapq import*;n,m,*a=[-int(i)for i in open(0).read().split()];a.sort();exec('heappush(a,-~heappop(a)//2);'*-m);print(-sum(a))

Submission status: Accepted

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

numbers = [int(i) * -1 for i in input().split()]
heapq.heapify(numbers)

for i in range(m):
    maxout = heapq.heappop(numbers)
    insnumber = -(-maxout//2)
    heapq.heappush(numbers, insnumber)

numbers = list(map(lambda x: x*-1, numbers))

print(sum(numbers))

Submission status: Accepted

Solution code:
import heapq
a, b = map(int,input().split())
l = list(map(int,input().split()))
for i in range(a):
    l[i] = -l[i]
heapq.heapify(l)

def cal(t,T):
    return -(-t//T)
for _ in range(b):
    heapq.heappush(l,cal(heapq.heappop(l),2))
s = 0
for x in l:
    s += -x
print(s)

Submission status: Accepted

Solution code:
from heapq import*;n,m,*a=[-int(i)for i in open(0).read().split()];heapify(a);exec('heappush(a,-~heappop(a)//2);'*-m);print(-sum(a))

Submission status: Accepted

Solution code:
def main():
  from heapq import heapify,heappush,heappop
  n,m,*a=[-i for i in map(int,open(0).read().split())]
  heapify(a)
  for _ in range(-m):heappush(a,0--heappop(a)//2)
  print(-sum(a))
main()

Submission status: Accepted

Solution code:
def main():
  from heapq import heapify,heappush,heappop
  n,m,*a=[-int(i)for i in open(0).read().split()]
  heapify(a)
  for _ in range(-m):heappush(a,0--heappop(a)//2)
  print(-sum(a))
main()

Submission status: Accepted

Solution code:
from heapq import*
n,m,*a=[-int(i)for i in open(0).read().split()]
heapify(a)
while m:heappush(a,0--heappop(a)//2);m+=1
print(-sum(a))

Submission status: Accepted

Solution code:
import heapq

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

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

# 最小値（最大値）の値を半分にしていく
for i in range(M):
    tmp = -heapq.heappop(A) // 2
    heapq.heappush(A, -tmp)

print(-sum(A))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N,M=map(int,input().split())
A=list(map(int,input().split()))
import heapq
A=[-1*i for i in A]
heapq.heapify(A)
for _ in range(M):
    a=heapq.heappop(A)
    a=-1*a
    a=a//2
    a=-1*a
    heapq.heappush(A,a)
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):
        heapq.heappush(a,heapq.heappop(a)/2)
 
print(sum([int(i) for i in a])*-1)

Submission status: Accepted

Solution code:
from heapq import *

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

h = []
for aa in a:
    heappush(h, -aa)

for i in range(m):
    x = heappop(h)
    x = -x
    x = x //2
    heappush(h, -x)

s = 0
for hh in h:
    s += (-hh)
print(s)

Submission status: Accepted

Solution code:
import heapq
N, M = [int(_) for _ in input().split()]
H = [-int(_) for _ in input().split()]
heapq.heapify(H)
ans = 0
for _ in range(M):
    a = heapq.heappop(H)
    heapq.heappush(H, a / 2)
print(-sum(int(a) for a in H))

Submission status: Accepted

Solution code:
import heapq

def main():
	n,m = map(int,input().split())
	res = 0
	h = []
	for i in input().split():
		heapq.heappush(h, -int(i))
	for j in range(m):
		x = heapq.heappop(h)
		y = -((-x) // 2)
		heapq.heappush(h, y)
	
	res = -sum(h)
	print(res)
	return 0;

if __name__ == "__main__":
	main()

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 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))  # 計算誤差の関係で-1を2回かけてます
print(-sum(a))

Submission status: Accepted

Solution code:
import heapq

N,M=( int(x) for x in input().split())
A=[int(s)*-1 for s in input().split()]

heapq.heapify(A)

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

Submission status: Accepted

Solution code:
import heapq

N, M = map(int,input().split())
A = []
for x in list(map(int, input().split())):
    heapq.heappush(A, -x)

for i in range(M):
    heapq.heapreplace(A, (A[0]+1)//2)
#    print(A)
ans = -sum(A)
print(ans)

Submission status: Accepted

Solution code:
#ABC-141-D
def main():
    n,m=map(int,input().split(" "))
    s=list(map(int,input().split(" ")))
    
    s.sort(reverse=True)
    while m!=0:
        tmp=s[0]//2
        s[0]=tmp
        m-=1
        for j in range(1,n):
            if m==0:
                break
            else:
                if s[j]>=tmp:
                    s[j]=s[j]//2
                    m-=1
                else:
                    break
        s.sort(reverse=True)
        if s[0]==0:
            break
    print(sum(s))
    
main()

Submission status: Accepted

Solution code:
import heapq

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

# 割引は出来るだけする
for i in range(M):
	temp_min = heapq.heappop(item_list)
	heapq.heappush(item_list, (-1)*(-temp_min//2))
print(-sum(item_list))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import math

N,M = [int(i) for i in input().split(' ')]
itemList = [int(i) for i in input().split(' ')]
heap = []

for i in itemList:
    heappush(heap, -i)

for _ in range(M):
    heappush(heap, math.ceil(heappop(heap)/2))
print(-sum(heap))

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):
    tmax = heapq.heappop(a)
    tmax = -(-tmax //2)
    heapq.heappush(a,tmax)

print(-1*sum(a))

Submission status: Accepted

Solution code:
from heapq import *
n, m = map(int,input().split())
a = map(int,input().split())
q = []
for i in a:
  heappush(q,-i)
#print(q)
for j in range(m):
  temp = -heappop(q)
  temp //= 2
  heappush(q,-temp)
  #print(q)
print(-(sum(q)))

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 i in range(m):
    tar = heapq.heappop(a)
    ins = ((tar*-1) // 2)*-1
    heapq.heappush(a, ins)
a = list(map(lambda x: x*-1, a))
print(sum(a))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import heapq
from math import ceil


def input(): return sys.stdin.readline().strip()


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

    for _ in range(M):
        heapq.heapreplace(A, ceil(A[0] / 2))

    ans = -sum(A)

    print(ans)


if __name__ == "__main__":
    main()

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 i in range(m):
  heapq.heappush(a, heapq.heappop(a) / 2)

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

print(int(ans))

Submission status: Accepted

Solution code:
import heapq

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

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

for j in range(m):
  tmp = -heapq.heappop(lis)
  heapq.heappush(lis, -int((tmp/2)))

print(-sum(lis))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

N, M = map(int, input().split())
price = list(map(int, input().split()))
he = []
for i in price:
  heappush(he, -i)
for i in range(M):
  max = heappop(he)
  heappush(he, -(-max//2))
print(-sum(he))

Submission status: Accepted

Solution code:
class Heap:

    # 初期化
    def __init__(self):
        self.array = []

    def num(self):
        return len(self.array)
        
    # valを追加する
    def put(self, val):
        pos = len(self.array)
        # valを末尾に追加する
        self.array.append(val)
        # valを適当な位置まで上にあげる
        self.pop_up(pos)
        
    # 最大の要素を取り出す
    def get(self):
        assert len(self.array) > 0

        val = self.array[0]
        
        # 末尾の要素を0に移動してから下に下げる
        t_val = self.array[-1]
        self.array[0] = t_val
        del self.array[-1]
        self.push_down(0)
        return val

    # posの位置の要素を適当な位置まで上げる
    def pop_up(self, pos):
        while pos > 0:
            p_pos = (pos - 1) // 2
            val = self.array[pos]
            p_val = self.array[p_pos]
        
            if val > p_val:
                self.array[pos] = p_val
                self.array[p_pos] = val
                pos = p_pos
            else:
                break
            
    def push_down(self, pos):
        while True:
            l_pos = 2 * pos + 1
            r_pos = 2 * pos + 2
            n = len(self.array)
            
            if n <= l_pos:
                # 子がいない場合
                break
            
            elif n == r_pos:
                # 子が一人の場合
                val = self.array[pos]
                l_val = self.array[l_pos]
                
                if val < l_val:
                    self.array[pos] = l_val
                    self.array[l_pos] = val
                    
                break #
            
            else:
                # 子が二人いるとき
                val = self.array[pos]
                l_val = self.array[l_pos]
                r_val = self.array[r_pos]
                
                if l_val > r_val:
                    if val < l_val:
                        self.array[pos] = l_val
                        self.array[l_pos] = val
                        pos = l_pos
                    else:
                        break
                else:
                    if val < r_val:
                        self.array[pos] = r_val
                        self.array[r_pos] = val
                        pos = r_pos
                    else:
                        break

                        
h = Heap()
sn,sm = input().split(" ")
n = int(sn)
m = int(sm)
sa_list = input().split(" ")


for sa in sa_list:
  a = int(sa)  
  h.put(a)
 
for i in range(m):  
    max_a = h.get()
    h.put(max_a // 2)

    

print(sum(h.array))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

n,m=map(int,input().split())
a=map(int,input().split())
hp=[]
for i in a:
    heappush(hp,-i)
for i in range(m):
    max=heappop(hp)
    heappush(hp, -(-max//2))
print(-sum(hp))

Submission status: Accepted

Solution code:
import heapq

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

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 i in range(m):
        maxVal = heapq.heappop(a)*(-1)
        heapq.heappush(a, (maxVal//2)*(-1))

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

Submission status: Accepted

Solution code:
from sys import stdin
import heapq

n,m = map(int, input().split())
a = [int(x)*(-1) for x in stdin.readline().rstrip().split()]
heapq.heapify(a)

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

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

Submission status: Accepted

Solution code:
import math
 
s=list(map(int,input().split()))
t=list(map(int,input().split()))
a=0
b=0
c=0
d=s[1]
t.sort(reverse=True)
if s[0]==1:
  for i in range(s[1]):
    t[0]=math.floor(t[0]/2)
else:
  c=t[0]/2
  for j in range(s[1]):
    for l in range(s[0]):
      if d>0:
        if c<t[l]:
          t[l]=math.floor(t[l]/2)
          d=d-1
        else:
            t.sort(reverse=True)
            c=t[0]/2
            break
      else:
        break
e=sum(t)
print(e)

Submission status: Accepted

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

heapq.heapify(A)

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

cost = 0
for a in A:
    cost -= a
print(cost)

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)

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

print sum(A)*(-1)

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
la=list(map(lambda x:-int(x),input().split()))
heapq.heapify(la)
#la.sort()
for i in range(M):
    ll=heapq.heappop(la)/2
    heapq.heappush(la,ll)
ans=0
for i in range(N):
    ans+=int(-heapq.heappop(la))
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import numpy as np
import copy
import heapq
import queue

# Pythonのheapqはmin-heapを提供する
# max-heapを利用するにはどうすればよいか？→数値であれば、マイナスを入れればよい。
def main():
    n, m = [int(t) for t in input().split()]
    a = [int(t) for t in input().split()]
    b = [-x for x in a]
    heapq.heapify(b)
    for i in range(m):
        x = heapq.heappop(b) * -1
        heapq.heappush(b, (x // 2) * -1)
    print(-1 * sum(b))
    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
Alist = list(map(lambda x: int(x) * (-1), input().split()))

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

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

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 _ in range(M):
    a = heapq.heappop(A) * (-1)
    a = a // 2
    heapq.heappush(A, a * (-1))

print(sum(A) * (-1))

Submission status: Accepted

Solution code:
import heapq

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

#output
A2 = [-a for a in A]
heapq.heapify(A2)

for i in range(M):
    temp_min = A2[0] + 1
    heapq.heappushpop(A2, temp_min//2)

print(-sum(A2))

Submission status: Accepted

Solution code:
# ABC141D - Powerful Discount Tickets
from heapq import heapify, heapreplace


def main():
    N, M, *A = map(int, open(0).read().split())
    H = [-i for i in A]
    heapify(H)
    for _ in range(M):
        x = H[0]
        heapreplace(H, x // 2 + x % 2)
    ans = -sum(H)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
import math
[N, M] = list(map(int,input().split()))
A = list(map(int,input().split()))
for i in range(N):
    A[i] = -A[i]
heapq.heapify(A)
for i in range(M):
    x = heapq.heappop(A)
    heapq.heappush(A, x/2)
sum = 0
for i in range(N):
    sum += math.floor(abs(A[i]))
print(sum)

Submission status: Accepted

Solution code:
import heapq

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

while M > 0:
    maxPrice = -heapq.heappop(priceList)
    maxPrice = maxPrice // 2
    M -= 1
    heapq.heappush(priceList, -maxPrice)

sum = 0
for i in range(N):
    sum += priceList[i]

print(-sum)

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(a)

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

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(price_list)
for n in range(M):
    max_price = heapq.heappop(price_list)*(-1)
    devided_price = max_price // 2
    heapq.heappush(price_list, (-1)*devided_price)

print((-1)*sum(price_list))

Submission status: Accepted

Solution code:
import heapq
 
N, M = [int(item) for item in input().rstrip().split()]
hp = [-1 * int(item) for item in input().rstrip().split()]
heapq.heapify(hp)

for i in range(M):
    _t = heapq.heappop(hp)
    heapq.heappush(hp, -1 * (-1 * _t // 2))
    
_sum = sum([-1 * int(item) for item in hp])
print(_sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
from functools import reduce

n, m = map(int, input().split())
h = list(map(lambda a: -int(a), input().split()))
heapq.heapify(h)  # input().split()))

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

print(-reduce(lambda a, b: a+b, h))