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:
from heapq import *
n, m = [int(x) for x in input().split()]
As = [int(x) for x in input().split()]
heap = []
[heappush(heap, -a) for a in As]
for _ in range(m):
    big = -heappop(heap)
    heappush(heap, -(big//2))
print(-sum(heap))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heappop,heappush,heapify

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

que=list(map(lambda x: -int(x),input().split()))
heapify(que)

while m:
    res=-heappop(que)
    res>>=1
    heappush(que,-res)
    m-=1

print(-sum(que))

Submission status: Accepted

Solution code:
import heapq

N, M = map(int,input().split())
As = list(map(int,input().split()))
As = [-1*e for e in As]
heapq.heapify(As)
for i in range(M):
    value = -heapq.heappop(As)
    heapq.heappush(As,-(value//2))
print(-sum(As))

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
import math

def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A = [-a for a in A]
    heapify(A)

    while M:
        m = heappop(A)
        heappush(A, math.ceil(m/2))
        M -= 1
    print(-sum(A))

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
hq=[]
from heapq import heappush,heappop
for i in range(n):
	heappush(hq,-a[i])
ans=0
import math
for i in range(m):
	k=heappop(hq)
	ans+=math.ceil(-k/2)
	heappush(hq,(-k+k//2)*-1)
print(sum(a)-ans)

Submission status: Accepted

Solution code:
from heapq import heappush as push, heappop as pop
N, M = [int(v) for v in raw_input().split()]
items = [- int(v) for v in raw_input().split()]
q = []
for i in items:
    push(q, i)
for ticket in range(M):
    price = -pop(q)
    push(q, -(price//2))
tot= -sum(q)
print(tot)

Submission status: Accepted

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

if __name__ == "__main__":
    f_d()

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]

heapq.heapify(A)
#print(A)

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

for i in range(N):
    A[i] = (-A[i])//1

#print(A)
print(int(sum(A)))

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
A = [-A[i] for i in range(N)]
A = sorted(A)
cnt = 0
while cnt<M:
    a = heapq.heappop(A)*(-1)
    a = a/2
    heapq.heappush(A,-a)
    cnt += 1
A = [int(-A[i]) for i in range(N)]
print(sum(A))

Submission status: Accepted

Solution code:
import heapq

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

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

valueheap = [x * (-1) for x in a]

heapq.heapify(valueheap)

for _ in range(M):

    maxvalue = heapq.heappop(valueheap) * (-1)

    maxvalue //= 2

    maxvalue *= -1

    heapq.heappush(valueheap, maxvalue)

print(sum(valueheap) * (-1))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import heapq

def solve(N: int, M: int, A: "List[int]"):
    # A.sort()
    # for i in range(M):
    #     A[-1] = A[-1] // 2
    #     A.sort()

    mA = [-1*i for i in A]
    heapq.heapify(mA)
    # print(mA)

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

    print(-1*sum(mA))
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import heapq
import math


def main():
    n, m = [int(s) for s in sys.stdin.readline().strip().split()]
    a = [int(s) for s in sys.stdin.readline().strip().split()]

    q = []
    for ai in a:
        heapq.heappush(q, - ai)

    for i in range(m):
        value = heapq.heappop(q)
        discounted = math.ceil(value / 2)
        heapq.heappush(q, discounted)

    print(- sum(q))


main()

Submission status: Accepted

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

import heapq

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

    heapq.heapify(A)

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

        heapq.heappush(A, -a)        
    
    print(-sum(A))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys; from collections import deque; readline = sys.stdin.readline;

from heapq import heappush, heappop

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

heap = []

for a in A:
    heappush(heap, -a)

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

total = -sum(heap)

print(total)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify

n, m = map(int, input().split())
q = []
for x in input().split():
    heappush(q, -int(x))

for i in range(m):
    item = (-heappop(q))//2
    heappush(q, -item)

print(-sum(q))

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
A = [-i for i in list(map(int, input().split()))]
heapq.heapify(A)
for m in range(M):
    A_max = -heapq.heappop(A)  # Aの最大値を削除して取り出す
    heapq.heappush(A, -(A_max // 2))
print(-sum(A))

Submission status: Accepted

Solution code:
import heapq
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort(reverse = True)
que = []
def div(a,b):
    if a % b == 0:
        return a//b
    else:
        return a//b + 1
for i in range(n):
    heapq.heappush(que,-a[i])
for i in range(m):
    p = heapq.heappop(que)
    p = div(p,2)
    heapq.heappush(que,p)
print(-sum(que))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
import heapq
input=sys.stdin.readline
def resolve():
    n,m=map(int,input().split())
    A=list(map(lambda x:-(int(x)),input().split()))
    heapq.heapify(A)
    for _ in range(m):
        a=heapq.heappop(A)
        a=-a
        a=a>>1
        heapq.heappush(A,-a)
    print(-sum(A))

resolve()

Submission status: Accepted

Solution code:
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)
import heapq

# def floor(value):
#     if int(value) == value:
#         return value//2
#     else:
#         return (value + 1) // 2


def main():
    N, M = map(int, input().split())
    A = [int(c) for c in input().split()]
    queue = []


    for i in range(N):
        heapq.heappush(queue, - A[i])
    # print(queue)
    for i in range(M):
        max_ = heapq.heappop(queue)
        heapq.heappush(queue, (max_+1)//2)
        # print(queue)
    
    print(- sum(queue))




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [int(a) for a in input().split()]
X = []
C = [0] * N
for j in range(30):
    for i in range(N):
        X.append(((A[i]>>j)<<24) + (i << 6) + j)
X = sorted(X)[::-1]
ans = sum(A)
for a in X[:M]:
    x, i, j = a >> 24, (a >> 6) % (1<<18), a % (1<<6)
    if C[i] == j:
        C[i] += 1
        ans -= x - x//2
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()))
A = [- i for i in A]
heapify(A)
for i in range(M):
  s = - heappop(A)
  heappush(A, - (s // 2))
print(-sum(A))

Submission status: Accepted

Solution code:
import heapq
N, M = [int(x) for x in input().split()]
h = []
[heapq.heappush(h, -int(x)) for x in input().split()]
for _ in range(M):
    tmp = heapq.heappop(h)
    if (tmp == 0): break
    heapq.heappush(h, -1*(-tmp//2))
print(-1 * sum(h))

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict
n, m= [int(i) for i in input().split()]
a = [(-int(i), -int(i)) for i in input().split()]
heapq.heapify(a)

for _ in range(m):
  n, r = heapq.heappop(a)
  rnew = float(r)/2
  nnew = -1 * (-1 * r // 2) 
  heapq.heappush(a, (nnew, rnew))

ans = 0
for an, ar in a:
  ans += -1 * an
print(int(ans))

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)
    heapq.heappush(A, a / 2)
print(sum(int(-a) for a in A))

Submission status: Accepted

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

for i in range(M):
    x = -heapq.heappop(B)
    if x == 0:
      break
    x = x//2
    heapq.heappush(B,-x)

print(-sum(B))

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] *= -1

heapq.heapify(a)

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

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
import math

N, M = map(int, input().split())
A = list(map(lambda x: int(x) * -1, input().split()))
heapify(A)
hh = []
for _ in range(M):
    heappush(A, math.ceil(heappop(A) / 2))
print(sum(A) * -1)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
ts=time.time()
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
show_flg=True

an=0
n,m=MI()
a=LI()
q=[]
for i in a:
    heappush(q,-i)

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

Submission status: Accepted

Solution code:
import math
import heapq

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

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

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

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline

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

sumA = -sum(A)
heapify(A)

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

print(sumA)

Submission status: Accepted

Solution code:
import heapq

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

h = []
for v in A:
    heapq.heappush(h, -v)

for i in range(M):
    v = heapq.heappop(h)
    # print(v)
    heapq.heappush(h, -(-v // 2))

print(-sum(h))

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n, m = LI()
L = LI()
for i in range(n):
    L[i] *= -1


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



print(-sum(L))

Submission status: Accepted

Solution code:
rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())

import heapq
def solve(N, M, A):
    pq = [-x for x in A]
    heapq.heapify(pq)

    for _ in xrange(M):
        x = -heapq.heappop(pq)
        x /= 2
        heapq.heappush(pq, -x)
    return -sum(pq)


N, M = rrm()
print solve(N, M, rrm())

Submission status: Accepted

Solution code:
import sys
import collections
import copy
import math
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
N,M =map(int,input().split())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
count = 0
while count != M:
    chk =A[0]//2
    for i in range(len(A)):
        if A[i] >= chk:
            A[i] = A[i]//2
            count += 1
            if count == M:
                break
        else:
            A.sort(reverse=True)
            break
print(sum(A))

Submission status: Accepted

Solution code:

# Setup
import sys
import collections
import heapq
sys.setrecursionlimit(4100000)
import math
n,m = [int(i) for i in input().split()]
b = [-int(i) for i in input().split()]
heapq.heapify(b)
for i in range(m):
    temp = heapq.heappop(b)

    temp = temp/2

    heapq.heappush(b,math.ceil(temp))
print(-sum(b))

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):
    a = heapq.heappop(A)
    if a%2 == 0:
        a = a//2
    else:
        a = a//2+1
    heapq.heappush(A,a)
print(sum(A)*(-1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappop, heappush

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    H = []
    for i in A:
        heappush(H, -i)
    for _ in range(M):
        j = heappop(H)
        j = - ( -j // 2)
        heappush(H, j)
    ans = - sum(H)
    print(ans)

if __name__ == '__main__': main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
aa = []
for i in range(len(a)):
    aa.append(-a[i])
from heapq import heappop,heappush
h_que = []
ans = 0 
for i in range(n):
    heappush(h_que,aa[i])
for _ in range(m):
    tmp = heappop(h_que)
    tmp = -tmp
    tmp = tmp // 2
    tmp = -tmp
    heappush(h_que,tmp)
for i in range(n):
    tmp = heappop(h_que) * (-1)
    ans += tmp
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
    a[i]*=-1
import heapq
heapq.heapify(a)
for i in range(m):
    # print(a)
    tmp=heapq.heappop(a)
    tmp=tmp*-1
    tmp=tmp//2
    tmp*=-1
    heapq.heappush(a,tmp)

print(sum(a)*-1)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
N,M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = sorted(A,reverse = True)
hq = []
ans = 0
for i in range(N):
  heappush(hq,-A[i])
for i in range(M):
  heappush(hq,int(heappop(hq)/2))
print(-sum(hq))

Submission status: Accepted

Solution code:
import heapq as hq
n,m = map(int,input().split())

ls = list(map(int,input().split()))
ls = [-1*a for a in ls]

hq.heapify(ls)

for _ in range(m):
  t = -1*hq.heappop(ls)
  hq.heappush(ls,t//2*(-1))
  
print(-1*sum(ls))

Submission status: Accepted

Solution code:
import sys, math
import heapq
class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign

def main():
    def input():
        return sys.stdin.readline()[:-1]
    N, M = map(int,input().split())
    A = sorted(list(map(int,input().split())))[::-1]
    Q = Heapq(A, True)
    for k in range(M):
        now = Q.pop()
        Q.push(now//2)
    ans = 0
    for k in range(N):
        ans += Q.pop()
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import heapq
    n,m = map(int,input().split())
    a = list(map(int,input().split()))
    a = sorted([-i for i in a])
    for i in range(m):
        x = heapq.heappop(a)
        if x%2 == 0:
            x = int(x//2)
        else:
            x = int(x//2)+1
        heapq.heappush(a,x)
    print(sum(a)*(-1))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

product = [-1*a for a in A]

import heapq

# ヒープ化
heapq.heapify(product)
# ヒープから取り出す

for _ in range(M):
    min_val = heapq.heappop(product)
    discount_val = int(min_val / 2)

    # ヒープに要素を追加する
    heapq.heappush(product, discount_val)
    
print(-1*sum(product))

Submission status: Accepted

Solution code:

# Setup
import sys
import collections
import heapq
sys.setrecursionlimit(4100000)
import math
n,m = [int(i) for i in input().split()]
b = [-int(i) for i in input().split()]
heapq.heapify(b)
for i in range(m):
    temp = heapq.heappop(b)
    # print(temp)
    temp = temp/2
    # print(math.ceil(temp))
    heapq.heappush(b,math.ceil(temp))
print(-sum(b))

Submission status: Accepted

Solution code:
import math
import heapq
from itertools import product, permutations,combinations

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

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)
	x /= 2
	x = heapq.heappush(A, x)

total = 0
for i in range(N):
	total -= math.ceil(A[i])

print(total)

Submission status: Accepted

Solution code:
import heapq as hq
def main():
    n,m=map(int,input().split(' '))
    a=[-1*i for i in list(map(int,input().split(' ')))]
    hq.heapify(a)
    for i in range(m):
        a_max = hq.heappop(a)
        a_max = (-1*a_max)//2
        hq.heappush(a,-1*a_max)
    print(-1*sum(a))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#D問題
import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))

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

for j in range(M):
    b = -heapq.heappop(B)
    b = b//2
    heapq.heappush(B,-b)
    
print(-sum(B))

Submission status: Accepted

Solution code:
from queue import PriorityQueue
N, M = map(int, input().split())  # N件のアルバイト, M日後までに欲しい

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


pq = PriorityQueue()

for i in range(len(A)):
    pq.put(-A[i])

ans = 0

for i in range(M):
    tmp = -(pq.get())
    tmp = tmp//2
    pq.put(-tmp)

# for jobs in jobs_list:
#     for job in jobs:
#         pq.put(-job)  # min-heapであるから、マイナスにして追加する
#     if not pq.empty():  # pqに要素があるなら仕事を一つ行う
#         ans += -(pq.get())

while not pq.empty():
    ans += -pq.get()

print(ans)

Submission status: Accepted

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

import sys
from heapq import heappush, heappop, heapify

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
A  = [-a for a in LIST()]

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

print(-sum(A))

Submission status: Accepted

Solution code:
from heapq import heapify, heappop as pop, heappush as push
import math

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

heapify(A)


for _ in range(M):
    m = pop(A)
    push(A, math.ceil(m / 2))

print(-sum(A))

Submission status: Accepted

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

import heapq

heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
import numpy as np
import bisect
import heapq

n,m=map(int,input().split())
a=np.array([int(i) for i in input().split()])
a=a*(-1)
a.sort()
a=list(a)

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

Submission status: Accepted

Solution code:
import sys
import math
import bisect
MAX_INT = int(10e12)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

import sys
from collections import deque
import heapq
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = IL()
a = IL()

hpop = heapq.heappop
hpush = heapq.heappush
data = []

for i in a:
    hpush(data, -i)

for i in range(M):
  tmp = math.ceil(hpop(data)/2)
  hpush(data, tmp)
  #print(data)

print(-sum(data))

Submission status: Accepted

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

import heapq

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

cnt = M
while cnt>0:
    a=heapq.heappop(q)
    a=-a
    a=a//2
    heapq.heappush(q,-a)
    
    cnt-=1
print(-sum(q))

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split(" ")))
h = []
for aa in a:
    heapq.heappush(h, -aa)
for i in range(m):
    x = heapq.heappop(h)
    heapq.heappush(h, x / 2)

ans = 0
for x in h:
    ans += int(-x)
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    heap = []
    for a in A:
        heappush(heap, -a)

    for _ in range(K):
        price = heappop(heap)
        heappush(heap,-(- price//2))

    return -sum(heap)


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

Submission status: Accepted

Solution code:
from heapq import heappush as hpush, heappop as hpop

n, m = map(int, raw_input().strip().split())
a = map(int, raw_input().strip().split())

heap = []
for num in a:
    hpush(heap, -num)

while m > 0:
    x = hpop(heap)
    if x == 0: break
    x = -x
    x /= 2
    hpush(heap, -x)
    m -= 1

ans = 0
while heap:
    x = hpop(heap)
    ans -= x

print ans

Submission status: Accepted

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

q = []
for i in range(N):
    heapq.heappush(q, -A[i])

for j in range(M):
    tmp = heapq.heappop(q)
    tmp = - (-tmp // 2)
    heapq.heappush(q, tmp)

ans = -sum(q)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]

# データ構造：ヒープ
import heapq
class heapque:
    def __init__(self, *args):
        self.que = []
        for arg in args:
            self.push(arg)
    def push(self, v):
        heapq.heappush(self.que, v)
    def pop(self):
        return heapq.heappop(self.que)

# エントリーポイント
def main():
    N, M = input([int, 2])
    A = input([int, N])

    que = heapque()
    for a in A:
        que.push(-a)
    
    for _ in range(M):
        que.push(-(-que.pop() // 2))

    print(-sum(que.que))
    
    return

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

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

q = [-ai for ai in a]
heapify(q)

for i in range(m):
    v = heappop(q)
    v = -(abs(v) // 2)
    heappush(q, v)

print(-sum(q))

Submission status: Accepted

Solution code:
import heapq
import math

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

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

print(-1 * sum(A))

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

N, M, *A = map(int, open(0).read().split())

Q = [-a for a in A]
heapify(Q)
for _ in range(M):
    a = heappop(Q)
    heappush(Q, -(-a // 2))
print(-sum(Q))

Submission status: Accepted

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

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

heapq.heapify(As)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)


def solve():
    N, M = LI()
    a_list = LI()

    # 最小を取り出すのでマイナスにする
    a_list = [-1*a for a in a_list]

    import heapq
    heapq.heapify(a_list)

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

    print(-1*sum(list(a_list)))


solve()

Submission status: Accepted

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)
import heapq
def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    N, M = [int(n) for n in input().split()]
    A = [-int(n) for n in input().split()]
    heapq.heapify(A)
    while(M):
        targ = heapq.heappop(A)
        targ /= 2
        heapq.heappush(A,targ)
        M-=1

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



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
A = list(map(lambda x: -int(x), input().split()))
# sort_A = sorted(A, reverse=True)
heapq.heapify(A)
for m in range(M):
    ma = heapq.heappop(A)
    # print(ma, ma//2)
    heapq.heappush(A, -(-ma // 2))

# print(A)
print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
nums = list(map(int, input().split()))
hp = []
for i in range(N):
  heapq.heappush(hp, -nums[i])
ans = sum(nums)
for _ in range(M):
  num = -heapq.heappop(hp)
  t = num//2
  ans -= num-t
  heapq.heappush(hp, -t)
print(ans)

Submission status: Accepted

Solution code:
from heapq import*;N,M,*A=map(lambda x:-int(x),open(0).read().split());heapify(A)
for _ in range(-M):heappush(A,0-heappop(A)//-2)
print(-sum(A))