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 collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
a = inpl()
a = [-x for x in a]
heapify(a)
for _ in range(m):
    now = heappop(a)
    now /= 2
    heappush(a,now)
    # print(now)
res = 0
for x in a:
    res += int(-x)
print(res)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

N, M = map(int, input().split())
A = list(map(lambda x: -x, list(map(int, 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

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

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

while m>0:
    aa=heapq.heappop(q)
    heapq.heappush(q,-((-aa)//2))
    m-=1

print(-sum(q))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
'''
Created on 2020/09/09

@author: harurun
'''
def main():
  import heapq
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  N,M=map(int,pin().split())
  A=list(map(int,pin().split()))
  B=list(map(lambda x: -x ,A))
  heapq.heapify(B)
  for i in range(M):
    t=heapq.heappop(B)
    s=-((-t)//2)
    heapq.heappush(B,s)
  ans=0
  for j in range(N):
    q=heapq.heappop(B)
    ans+=(-q)
  print(ans)
  return
main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
As = list(mapint())
from heapq import heappush, heappop
Q = []

for a in As:
    heappush(Q, -a)

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

print(-sum(Q))

Submission status: Accepted

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

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

import heapq,math

heapq.heapify(a)

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

    heapq.heappush(a,b*(-1))

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify

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

heapify(arr)

for _ in range(m):
    a = heappop(arr)
    heappush(arr, -(-a // 2))

print(-sum(arr))

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from heapq import *

n,m=nii()
a=lnii()
a=[-i for i in a]
a.sort(reverse=True)

heapify(a)

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

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq
n, m, *a = map(int, open(0).read().split())
a = list(map(lambda x: -x, a))

heapq.heapify(a)
for i in range(m):
    b = -heapq.heappop(a)
    heapq.heappush(a, -(b >> 1))

print(-sum(a))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify
n,m = map(int, input().split())
al = list(map(int, input().split()))
alm = []
for a in al:
    alm.append(a*(-1))

heapify(alm)
for _ in range(m):
    poped = heappop(alm)
    val = (poped*(-1))//2
    heappush(alm, val*(-1))

ans = sum(alm)
print(-ans)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def perm(n,mod=None):
    ans = 1
    for i in range(1,n+1):
        ans *= i
        if mod!=None:
            ans %= mod
    return ans
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]

N,M=mint()
A=lint()
H=[-a for a in A]
heapify(H)
for _ in range(M):
    x = heappop(H)
    x = -(-x//2)
    heappush(H,x)
print(-sum(H))

Submission status: Accepted

Solution code:
def main():
	N, M = [int(x) for x in input().split(" ")]
	A = [int(a) for a in input().split(" ")]
	D = []
	for i in range(len(A)):
		tmp = A[i]
		while tmp > 0:
			half = int(tmp / 2)
			D.append(tmp - half)
			tmp = half
	D.sort(reverse=True)
	print(sum(A) - sum(D[:M]))

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

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

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline #文字列入力はするな！！
import heapq
n,m=map(int,input().split())
a=[]
for i in input().split():
    heapq.heappush(a,-int(i))
for i in range(m):
    p=-heapq.heappop(a)
    p=p//2
    heapq.heappush(a,-p)
print(-sum(a))

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
a=[int(x) for x in input().split()]
a=[-1*x for x in a]

import heapq

heapq.heapify(a)

for i in range(m):
    max_value = heapq.heappop(a) #最大値の取得
    heapq.heappush(a, (max_value/2)) #半額にして-1倍してからキューに戻す

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

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

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

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

heapify(A)
for i in range(m):
    x = heappop(A)
    x = (x + 1) // 2
    heappush(A, x)

print(-1 * sum(A))

Submission status: Accepted

Solution code:
# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np
# from collections import deque
import heapq

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
N, M = map(int, input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# A = sorted(A, reverse=True)
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr

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

A = map(lambda x: x*(-1), A)
print(sum(A))

Submission status: Accepted

Solution code:
# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np
from collections import deque

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
N, M = map(int, input().split())
A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

A = sorted(A, reverse=True)
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr


queue_A = deque(A)
queue_B = deque()

for i in range(M):
    if len(queue_B) > 0 and queue_B[0] >= queue_A[0]:
        queue_A.appendleft(queue_B.popleft())
    queue_A[0] //= 2
    if len(queue_A) > 1 and queue_A[0] < queue_A[1]:
        queue_B.append(queue_A.popleft())

print(sum(queue_A) + sum(queue_B))

Submission status: Accepted

Solution code:
import math

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


def is_ok(x):
    cnt = 0
    for a in A:
        while math.floor(a) > x:
            cnt += 1
            a /= 2
        # cnt += math.ceil(math.log(a / x))
    return cnt <= M

def bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

X = bisect(-1, max(A))
ans = 0
cnt = 0
for a in A:
    while math.floor(a) > X:
        cnt += 1
        a /= 2
    ans += math.floor(a)
ans -= math.ceil(X / 2) * (M - cnt)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

heapq.heapify(A)

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

print(abs(sum(A)))

Submission status: Accepted

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop, heapify
import copy
import numpy as np
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def main():
    n, m = LI()
    a = list(map(lambda x: -x, LI()))
    heapify(a)
    for i in range(m):
        highest = -heappop(a)
        heappush(a, -(highest // 2))
    print(-sum(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()))
heapq.heapify(a)
for i in range(m):
  heapq.heapreplace(a,a[0]/2)

print(-sum(map(int,a)))

Submission status: Accepted

Solution code:

import heapq as he

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

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

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

print(-sum(A))

Submission status: Accepted

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

while M>0:
    a=heapq.heappop(hq)    
    heapq.heappush(hq,a/2)
    M-=1
    #print(hq)
ans=0
for i in hq:    
    ans+=int(-i)
    
print(ans)

Submission status: Accepted

Solution code:
import heapq, math

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

Submission status: Accepted

Solution code:
[N,M] = list(map(int,input().split()))
A = list(map(int,input().split()))
out=sum(A)
import heapq
a = list(map(lambda x: x*(-1), A))  # 各要素を-1倍 最大値取り出すため
heapq.heapify(a)
# print(a)

for i in range(M):
    # saidai = max(A)
    saidai = heapq.heappop(a)*(-1)
    out-=saidai
    out+=saidai//2
    # A[A.index(saidai)] = saidai//2
    heapq.heappush(a, (saidai//2)*(-1))
    # print('dam,out,a:',saidai,out,a)

print(out)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math        # factorical（階乗) # hypot(距離)
import heapq
# from fractions import gcd # Python3.5以前 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # Python3.6以降
# --------------------------------------------------------------

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

price = [-i for i in price]

heapq.heapify(price)

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

price = [-i for i in price]

print(sum(price))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

n,m = map(int, stdin.readline().split())
an = [i*(-1) for i in map(int, stdin.readline().split())]
#print(an)
#print(sum(an))

import heapq
heapq.heapify(an)

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

#print(an)
ans = (-1)*sum(an)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq


input = sys.stdin.readline
n, m = map(int, input().split())
a_list = list(map(int, input().split()))
a_list = list(map(lambda x: x*(-1), a_list))
heapq.heapify(a_list)

while m > 0:
    max_a = heapq.heappop(a_list)
    heapq.heappush(a_list, (-1)*(-max_a//2))
    m -= 1

print(-sum(a_list))

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    import heapq
    mod=10**9+7
    N,M=MI()
    A=LI()
    for i in range(N):
        A[i]*=-1
    heapq.heapify(A)
    
    for i in range(M):
        a=heapq.heappop(A)
        heapq.heappush(A,a/2)
        
    ans=0
    for i in range(N):
        a=heapq.heappop(A) * -1
        ans+=int(a)
        
    print(ans)
        

main()

Submission status: Accepted

Solution code:
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
        
N,M=map(int,input().split())
A=list(map(int,input().split()))

q = Heapq(A, True)
    
for i in range(M):
    x=q.pop()
    q.push(x//2)

print(sum([q.pop() for _ in range(N)]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
sys.setrecursionlimit(10**6)


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


N, M = zz()
A = zz()
A = [-a for a in A]
heapq.heapify(A)

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

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
if n == 1:
    print(a[0] // (2 ** m))
    exit()
a = list(map(lambda x: x * (-1), a))
heapq.heapify(a)
while m > 0:
    m -= 1
    i = heapq.heappop(a) * (-1)
    i //= 2
    heapq.heappush(a, i * (-1))

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

Submission status: Accepted

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

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))  # 各要素を-1倍
heapq.heapify(a)  # リストを優先度付きキューへ
for _ in range(M):
    number=heapq.heappop(a)  # 最大値の取り出し
    if number%2==0:
        number=number//2
    else:
        number=number//2+1
    heapq.heappush(a, number)  # 要素の挿入
print(-sum(a))

Submission status: Accepted

Solution code:
import sys
import heapq


def main():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())
    a = list(map(lambda x: -int(x), input().split()))
    heapq.heapify(a)
    for _ in range(m):
        price = heapq.heappop(a)
        heapq.heappush(a, -((-price) // 2))
    print(-sum(a))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import heapq

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

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

Submission status: Accepted

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

lis = []
for i in a:
    lis.append(-1*i)

heapq.heapify(lis)

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

print(-sum(lis))

Submission status: Accepted

Solution code:
import heapq
N, M =map(int, input().split())
A=list(map(lambda x: int(x)*(-1), input().split())) #各要素を-1倍
heapq.heapify(A) #Aを優先度付きキューに

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
n,m = map(int,input().split())
a = list(map(lambda x: int(x)*(-1),input().split()))
heapq.heapify(a) #aを優先度付きキューにする
for _ in range(m):
    tmp = heapq.heappop(a)
    heapq.heappush(a,(-1)*(-tmp//2))
print((-1)*sum(a))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)

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

ans = -sum(A)

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
from heapq import heappop as hpp, heappush as hp
h = []
for num in a:
    hp(h, -num)
for _ in range(m):
    val = hpp(h)
    val *= -1
    hp(h, -(val//2))
ans = -sum(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)
for i in range(0,M):
    a=heapq.heappop(A)
    heapq.heappush(A,(-1)*(-a//2))
print(-sum(A))

#　優先度付きキューが難しい

Submission status: Accepted

Solution code:
import heapq
from collections import deque
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)
    if x%2==0:
        x//=2
    else:
        x=x//2 +1
    heapq.heappush(A,x)

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

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)

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

Submission status: Accepted

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

heap = []
for i in a:
    heappush(heap,-i)

for _ in range(m):
    tmp = heappop(heap)
    heappush(heap,-(-tmp//2))

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

Submission status: Accepted

Solution code:
import heapq

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

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

heapq.heapify(a)

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

print(sum(a)*-1)

Submission status: Accepted

Solution code:
import heapq

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

for i in range(m):
  item = -1*heapq.heappop(hp)
  # print('item',item)
  item = item //2
  heapq.heappush(hp, -item)
  
print(-1*sum(hp))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
from heapq import heapify, heappop, heappush
from math import ceil
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

heapify(A)

for i in range(M):
    min_A = heappop(A)
    heappush(A, ceil(min_A/2))

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

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

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

heapq.heapify(a)

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

print(-sum(a))

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353


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

print(-sum(A))

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
N, M = map(int, input().split())
A = list(map(int, input().split()))
q = []
for a in A:
    q.append((a//2-a, a, 1))
heapify(q)
ans = sum(A)
for _ in range(M):
    discount, a, n = heappop(q)
    ans += discount
    if ans==0:
        break
    heappush(q, (a//2**(n+1)-a//2**n, a, n+1))
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
from collections import deque
import heapq 

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():

    N, M = NMI()
    A = NLI()
    
    A = list(map(lambda x: x*(-1), A))
    
    heapq.heapify(A)
    
    for m in range(M):
        highest = (heapq.heappop(A)*(-1))
        discounted = math.floor(highest/2) * -1
        heapq.heappush(A, discounted)

        
    print(sum(A)*-1)
#

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import heapq
# input = stdin.readline

def solve(n,m,a):
  a = [-x for x in a]
  heapq.heapify(a)
  for _ in range(m):
    x = heapq.heappop(a)
    heapq.heappush(a,-(abs(x)//2))
  return abs(sum(a))


def main():
  N,M = map(int,input().split())
  a = list(sorted(map(int,input().split())))
  print(solve(N,M,a))
  pass

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

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq

from typing import List


def main():
    n, m = map(int, input().split())
    v = map(int, input().split())
    print(pdt(v, m))


def pdt(v: List[int], m: int) -> int:
    vv = [-a for a in v]
    heapq.heapify(vv)

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

    return -sum(vv)


if __name__ == '__main__':
    main()