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 sys import stdin
import heapq
import math

N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [-int(x) for x in stdin.readline().rstrip().split()]

heapq.heapify(A)

while M > 0:
    h = heapq.heappop(A)
    h = math.ceil(h / 2)
    heapq.heappush(A, h)
    M -= 1

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

print(-sum(A))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq
n,m = map(int, input().split())
q = []
s = 0
for a in input().split():
    a = int(a)
    s += a
    q.append(-a)

heapq.heapify(q)

for _ in range(m):
    x = q[0]
    heapq.heappop(q)
    heapq.heappush(q,-1*((-x)//2))

print(-1*sum(q))

Submission status: Accepted

Solution code:
import sys
from collections import Counter
import math
import heapq
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

n, m = na()
a = na()
li = [a[i] * (-1) for i in range(n)]
heapq.heapify(li)
for i in range(m):
    num = heapq.heappop(li) * (-1)
    num = math.floor(num / 2)
    heapq.heappush(li, num * (-1))
ans = 0
for i in range(n):
    ans += (heapq.heappop(li) * (-1))
print(ans)

Submission status: Accepted

Solution code:
import heapq
import math

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


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

q = Heapq(a, desc=True)

for i in range(m):
    qi = q.pop()
    q.push(math.floor(qi/2))

ans = 0

for i in range(n):
    ans += q.pop()

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 m in range(M):
    t = heapq.heappop(A)
    t = (-t)//2
    heapq.heappush(A,-t)
print(-sum(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 j in range(m):
    x=heapq.heappop(B)
    if x//2==0:
        heapq.heappush(B,x//2)
    else:
        heapq.heappush(B,(x+1)//2)
print(-sum(B))

Submission status: Accepted

Solution code:
import sys
import heapq

input = sys.stdin.readline

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

A = map(int, input().split())
pq = []
heappush = heapq.heappush
for a in A:
    heappush(pq, -a)

heappushpop = heapq.heappushpop
now_t = heapq.heappop(pq)

for i in range(M):
    now_t = heapq.heappushpop(pq, -(-now_t//2))

ans = now_t + sum(pq)

print(-ans)

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

Submission status: Accepted

Solution code:
import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return((list(sys.stdin.readline()))[:-1])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def main():
    N,M = LI()
    A = [-1*int(x) for x in sys.stdin.readline().split()]


    heapq.heapify(A)

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

    return(-1 * sum(A))



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

Submission status: Accepted

Solution code:
import heapq
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
A = inpl()
q = []
for a in A:
    heapq.heappush(q,-a)
for _ in range(M):
    a = -heapq.heappop(q)
    a //= 2
    heapq.heappush(q,-a)
print(-sum(q))

Submission status: Accepted

Solution code:
import heapq
n,m = map(int,input().split())
d = [0] * m
a = list(map(int,input().split()))
s = sum(a)
for i in range(n):
  c = a[i]
  while True:
    c,p = c//2,c
    if p-c > d[0]:
      heapq.heappushpop(d,p-c)
    else:
      break
print(s-sum(d))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
from heapq import heappop,heappush
q=[]
for a in A:
    heappush(q,(-a,a,0))
while M>0:
    _,X,n=heappop(q)
    n+=1
    heappush(q,(-(X//2**n),X,n))
    M-=1
r=0
for _,X,n in q:
    r+=X//2**n
print(r)

Submission status: Accepted

Solution code:
import heapq
import math

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

h = []

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

for i in range(0, M):
    v = heapq.heappop(h)
    discounted = v / 2
    heapq.heappush(h, discounted)

res = 0
for i in range(0, N):
    res = res + math.floor(-h[i])

print(res)

Submission status: Accepted

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

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

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

print(-sum(Q))

Submission status: Accepted

Solution code:
import heapq

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

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

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq as hq

N, M = [int(_) for _ in input().split()]
A = []
for a in [int(_) for _ in input().split()]:
    hq.heappush(A, -a)

for _ in range(M):
    v = hq.heappop(A)
    hq.heappush(A, v / 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()))
h=[]
for i in range(N):
    heapq.heappush(h, (-A[i], A[i]))

for i in range(M):
    a = heapq.heappop(h)[1]//2
    heapq.heappush(h, (-a, a))

ans = 0
for i in range(N):
    ans += heapq.heappop(h)[1]

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] = -A[i]

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:
# -*- coding: utf-8 -*-
"""
Created on Sun Sep 15 20:38:23 2019

@author: Yamazaki Kenichi
"""
import heapq

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

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

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

ans = 0
for c in q:
    ans += int(-c)
print(ans)

Submission status: Accepted

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


def solve(N: int, M: int, A: "List[int]"):
    H = [(-a, a) for a in A]
    heapq.heapify(H)
    for i in range(M):
        mx = heapq.heappop(H)
        mx = mx[1] >> 1
        heapq.heappush(H, (-mx, mx))
    print(sum([e[1] for e in heapq.nlargest(N, H)]))
    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:
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):
  x=(-1)*((heapq.heappop(a)*(-1))//2)
  heapq.heappush(a,x)
for i in range(n):
  a[i]*=-1
print(sum(a))

Submission status: Accepted

Solution code:
from math import floor
from heapq import heappush, heappop
n, m = map(int, input().split())
a = []
for i in map(int, input().split()):
    heappush(a, -i)
dis = lambda x,y: x // 2**y

for _ in range(m):
    heappush(a, -dis(-heappop(a), 1))
print(-sum(a))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(nums)

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

print(-sum(nums))

Submission status: Accepted

Solution code:
import heapq

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

h=[]

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

for i in range(m):
  t=heapq.heappop(h)
  heapq.heappush(h,(t+1)//2)

print(-1*sum(h))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import floor
import heapq
def main():
    n,m = map(int,input().split())
    a  = [ -int(x) for x in input().split()]
    heapq.heapify(a)
    for i in range(m):
        now = -heapq.heappop(a)
        now = floor(now/2)
        heapq.heappush(a,-now)
    print(-sum(a))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

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

for s in S:
	heapq.heappush(A, s * -1)
	
for _ in range(M):
	tmp = heapq.heappop(A)
	if tmp > 0:
		tmp //= 2
	else:
		tmp *= -1
		tmp //= 2
		tmp *= -1
	heapq.heappush(A, tmp)
	
print(sum(A) * -1)

Submission status: Accepted

Solution code:
from heapq import heapify,heappop,heappush
N,M = map(int,input().split())
A = list(map(lambda x:-int(x),input().split()))
heapify(A)

# while(A): print(heappop(A))

for i in range(M):
    t = -heappop(A) // 2
    heappush(A,-t)
    # print(A)

# while(A): print(heappop(A))

print(-sum(A))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
n,m=map(int,input().split())
a=list(map(int,input().split()))
h=[]
for x in a:
    heappush(h,-x)
for _ in [0]*m:
    k=-heappop(h)
    heappush(h,-(k//2))
ans=0
for _ in [0]*n:
    ans+=-heappop(h)
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)
ans = 0

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

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

Submission status: Accepted

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

s = sum([int(-v) for v in h])
print(s)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from heapq import heappop, heappush

sys.setrecursionlimit(10 ** 7)


def solve(N: int, M: int, A: "List[int]"):
    pool = []
    for a in A:
        heappush(pool, -a)
    for _ in range(M):
        v = heappop(pool)
        heappush(pool, v / 2)
    result = 0
    for i in pool:
        result += int(i)
    print(-result)

# 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:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

import heapq
from math import floor, ceil

def main():
    n, m = LI()
    a_s = LI()
    minus_as = [-i for i in a_s]
    heapq.heapify(minus_as)
    ans = 0
    for i in range(m):
        v = heapq.heappop(minus_as)
        v = ceil(v / 2)
        heapq.heappush(minus_as, v)
    print(-1 * int(sum(minus_as)))





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import *
import sys
inp = raw_input

def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]


N, M = nl()
A = nl()

from heapq import *

pq = []
for a in A:
    heappush(pq, -a)

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

tot = 0
for _ in range(N):
    v = heappop(pq)
    tot += -v
print(tot)

Submission status: Accepted

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

A=[]
for i in range(N):
    A.append(a[i]*(-1))
heapq.heapify(A)

for i in range(M):
    q=(A[0])*(-1)
    heapq.heappop(A)
    heapq.heappush(A,(q//2)*(-1))
    
ans=0
for i in range(N):
    ans+=heapq.heappop(A)
    
print(-ans)

Submission status: Accepted

Solution code:
import heapq
import math

N,M=map(int,input().split())
h=[]

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

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

print(-sum(h))

Submission status: Accepted

Solution code:
nums = list(map(int, input().split()))
N, M = nums[0], nums[1]
A = list(map(int, input().split()))
A = [(-x, x) for x in A]
import heapq
heapq.heapify(A)

for _ in range(M):
    b = heapq.heappop(A)[1]
    b = b // 2
    heapq.heappush(A, (-b, b))

ans = 0
for i in range(N):
    ans += A[i][1]
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

hq = []
for a in A:
  heappush(hq, -a)
for i in range(M):
  price = heappop(hq)
  heappush(hq, -(-price//2))
print(-sum(hq))

Submission status: Accepted

Solution code:
import sys
from heapq import heappop as hpp, heappush as hp
readline = sys.stdin.readline
N, M = map(int, readline().split())
A = list(map(int, readline().split()))
mA = [(-a, -a, 0) for a in A]
mA.sort()
for _ in range(M):
  k, j, l = hpp(mA)
  hp(mA, (-(-j//pow(2, l+1)), j, l+1))
print(-sum(ai[0] for ai in mA))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    import heapq
    n,m=map(int,input().split())
    a=list(map(lambda x:-int(x),input().split()))
    heapq.heapify(a)
    import heapq
    for i in range(m):
        h=heapq.heappop(a)
        heapq.heappush(a,h/2)
    s=0
    for i in a:
        s+=int(-i)
    print(s)

if __name__ == '__main__':
    main()

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

print(-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)
for i in range(M):
    a = -heapq.heappop(A)
    heapq.heappush(A, -(a // 2))
print(-sum(A))

Submission status: Accepted

Solution code:
import heapq
n, m = [ int(v) for v in input().split() ]
a_list = [ -int(v) for v in input().split() ]
a_list = sorted(a_list)

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

print(-sum(a_list))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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

q = []

for v in a:
    heapq.heappush(q, -v)

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

ans = 0
for i in range(len(q)):
    ans -= q[i]

print(ans)

Submission status: Accepted

Solution code:

import heapq
N,K=  list(map(int,input().split(" ")))
nums = list(map(int,input().split(" ")))
nums = list(map(lambda x:-x , nums))
heapq.heapify(nums)
for _ in range(K):
    temp = heapq.heappop(nums)
    temp *= -1
    temp //= 2
    temp *= -1
    heapq.heappush(nums,temp)
nums = list(map(lambda x:-x , nums))
print(sum(nums))

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
A = [[-int(x), i] for i, x in enumerate(input().split())]
heapq.heapify(A)
for _ in range(M):
  a, i = heapq.heappop(A)
  _a = (-a) // 2
  heapq.heappush(A, [-_a, i])
print(sum([-a[0] for a in 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)]
heapq.heapify(A)

for i in range(M):
    a = heapq.heappop(A)
    if a == 0:
        heapq.heappush(A, 0)
    else:
        heapq.heappush(A, a/2)
A = [int(-A[i]) for i in range(N)]
print(sum(A))

Submission status: Accepted

Solution code:
#
import sys
sys.setrecursionlimit(12345678)
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop, heapify


def main():
    n, m = map(int, input().split())
    al = list(map(int, input().split()))
    for i in range(len(al)):
        al[i] = -al[i]

    heapify(al)

    for _ in range(m):
        val = heappop(al)
        val *= -1
        val //= 2
        val *= -1

        heappush(al, val)

    print(-sum(al))


if __name__ == '__main__':
    main()

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


for i in range(M):

    now = heapq.heappop(Q)
    now *= -1

    heapq.heappush(Q,-1 * (now // 2))

ans = 0

for i in Q:
    ans -= i
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)

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

Submission status: Accepted

Solution code:
import heapq as hq

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

p=[]
for i in range(N):
  hq.heappush(p,-A[i])
#print(p)

for i in range(M):
  tmp=-hq.heappop(p)//2
  hq.heappush(p,-tmp)
#print(p)
p=list(map(lambda x:-x, p))
print(sum(p))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, A):
    q = [-v for v in A]
    heapq.heapify(q)
    for _ in range(M):
        v = -heapq.heappop(q)
        v /= 2
        heapq.heappush(q, -v)
    
    return -sum(map(int, q))


def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M, 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()))

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

heapq.heapify(negA)

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

print(-sum(negA))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import queue
import re
import math
import functools

def s_raw():
    return input().rstrip("\r")

def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return list(map(int, ss_raw()))


INF = 1 << 29


def make1d_arr(n, val=INF):
    return [val for i in range(n)]


def make2d_arr(h, w, val=INF):
    return [[val for i in range(w)]for i in range(h)]


def gcd(a, b):
    if(b == 0):
        return a
    return gcd(b, a % b)


def BFord(n,es):
    v_cost = [INF]*n
    v_cost[0] = 0
    for v in range(n*2):
        for e in es:
            frm = e[0]
            to = e[1]
            if v_cost[to] > v_cost[frm]+e[2]:
                v_cost[to] = v_cost[frm]+e[2]
                if v >= n:
                    v_cost[to] = -INF
        if v == n-1:
            prev = v_cost[:]
    v_cost = [-INF if prev[idx]!=v_cost[idx] else v_cost[idx] for idx in range(n)]
    return v_cost
    

def main():
    N,M = ints_raw()
    As = ints_raw()
    As = [-a for a in As]
    As.sort()
    for i in range(M):
        a = heappop(As)
        heappush(As,-((-a)//2))
    return -sum(As)

    


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

Submission status: Accepted

Solution code:
import heapq

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

h = []
for i in range(n):
    heapq.heappush(h, -a[i])

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

print(-sum(h))

Submission status: Accepted

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

a_new = []
for _a in a:
    a_new.append(-1 * _a)

a = sorted(a_new)
import heapq
heapq.heapify(a)

# print(a)

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

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()
  l=LI()

  q=[]
  for x in l:
    heapq.heappush(q,-x)

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

  return -sum(q)

# main()
print(main())

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
As = list(map(int, input().split()))
import heapq
q = []
heapq.heapify(q)
for a in As:
    heapq.heappush(q,-a)
for i in range(M):
    a = heapq.heappop(q)
    a = (-a)//2*-1
    # print(a)
    heapq.heappush(q,a)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
import heapq
def main():
    N, M = map( int, input().split())
    A = list( map( lambda x:-x, map( int, input().split())))
    heapq.heapify(A)
    for _ in range(M):
        a = heapq.heappop(A)
        a = -((-a)//2)
        heapq.heappush(A, a)
    print( -sum(A))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

for t in tmp:
    heappush(A, -t)

for m in range(M):
    p = -heappop(A)
    p //= 2
    heappush(A, -p)

print(-sum(A))

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

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

PQ = [-A for A in As]
heapify(PQ)

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

ans = 0
while PQ:
    A = -heappop(PQ)
    ans += int(A)

print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a_list=list(map(int,input().split()))
import heapq
A=[]
for i in a_list:
    heapq.heappush(A,-i)
for i in range(m):
    now=heapq.heappop(A)
    now=-now
    now=now//2
    now=-now
    heapq.heappush(A,now)
ans=0
for i in range(n):
    now=heapq.heappop(A)
    ans-=now
print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop, heapify
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M = MI()
    A = LI()
    for i,a in enumerate( A):
        A[i] = - a

    heapify(A)
    for _ in range(M):
        a = heappop(A)
        heappush(A,a/2)
    
    ans = 0
    for h in A:
        ans += int(-h)
    print(ans)
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()]
# print(A)

heapq.heapify(A)  # リストaのheap化
# heapq.heappush(a, x)  # heap化されたリストaに要素xを追加
# heapq.heappop(a)  # heap化されたリストaから最小値を削除＆その最小値を出力

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

print(-sum(A))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

def getlist():
	return list(map(int, input().split()))

N, M = getlist()
A = getlist()

Q = []
for i in range(N):
	heappush(Q, -A[i])

for i in range(M):
	val = heappop(Q)
	if val % 2 == 0:
		heappush(Q, val // 2)
	else:
		heappush(Q, (val + 1) // 2)

print(-sum(Q))

Submission status: Accepted

Solution code:
import math
import heapq
from bisect import bisect_right, bisect_left
from collections import defaultdict, Counter
import itertools
import sys
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7
INF = float("inf")


def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    aa = []
    for i in range(n):
        aa.append(-a[i])
    heapq.heapify(aa)
    ans = 0
    for i in range(m):
        t = heapq.heappop(aa)
        t = math.ceil(t / 2)
        heapq.heappush(aa, t)
    print(-sum(aa))


if __name__ == '__main__':
    main()