Problem:


Score : 400 points

Problem Statement

Takahashi is going to buy N items one by one.

The price of the i-th item he buys is A_i yen (the currency of Japan).

He has M discount tickets, and he can use any number of them when buying an item.

If Y tickets are used when buying an item priced X yen, he can get the item for \frac{X}{2^Y} (rounded down to the nearest integer) yen.

What is the minimum amount of money required to buy all the items?

Constraints

All values in input are integers.

1 \leq N, M \leq 10^5

1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_N

Output

Print the minimum amount of money required to buy all the items.

Sample Input 1

3 3
2 13 8

Sample Output 1

9

We can buy all the items for 9 yen, as follows:

Buy the 1-st item for 2 yen without tickets.

Buy the 2-nd item for 3 yen with 2 tickets.

Buy the 3-rd item for 4 yen with 1 ticket.

Sample Input 2

4 4
1 9 3 5

Sample Output 2

6

Sample Input 3

1 100000
1000000000

Sample Output 3

0

We can buy the item priced 1000000000 yen for 0 yen with 100000 tickets.

Sample Input 4

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 4

9500000000



Sample input:
3 3
2 13 8


Sample output:
9

Submission status: Accepted

Solution code:
import heapq

# 「優先度付きキュー」の練習問題

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

# 各要素を-1倍する。最大値の取り出しができるように
a = list(map(lambda x: x*(-1), a))
# aの優先度付きキューに
heapq.heapify(a)

# 割引m回分ループ
for _ in range(m):
    popNum = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-popNum//2))

# 負で出力されているので戻す
print(-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]

a = sorted(a,reverse=True)
heapq.heapify(a)

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

print(sum(a) * -1)

Submission status: Accepted

Solution code:
#date: 2020-03-15 21:28
import sys
stdin = sys.stdin
from heapq import heappop, heappush, heapify

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, m = na()
    a = na()
    aminus = [-ai for ai in a]
    heapify(aminus)
    for i in range(m):
        amax = heappop(aminus)
        heappush(aminus, -((-amax)//2))
    print(-sum(aminus))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import heapq

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

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

Submission status: Accepted

Solution code:
import heapq

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

for i in range(0, M, 1):
	heapq.heappush(A, -(-heapq.heappop(A) >> 1))

print(-sum(A))

Submission status: Accepted

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

import heapq
heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
import sys
import heapq


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


if __name__ == "__main__":
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A = [-v for v in A]
    heapq.heapify(A)
    for m in range(M):
        v = heapq.heappop(A)
        heapq.heappush(A, -(-v // 2))
    ans = 0
    for a in A:
        ans -= a
    print(ans)

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

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

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

print(sum(i for _, i in h))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import heapq
n,m = map(int,input().split())
a = [-int(_) for _ in input().split()]
heapq.heapify(a)
ans = 0
for _ in range(m):
    min_ = heapq.heappop(a)
    min_ /= 2
    heapq.heappush(a,min_)
print(-sum(int(i) for i in a))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(lambda x:(-1)*int(x), input().split()))
import heapq  # heapqライブラリのimport

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

# 最小値の取り出し

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

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

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

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

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

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

Submission status: Accepted

Solution code:
"""
 SpeedForces
 Ah shit here we go again

"""

from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
import heapq

def solve():
    n,m = vv()
    a = ll()
    a = [-i for i in a]
    heapq.heapify(a)
    for i in range(m):
        x = -heapq.heappop(a)
        # pr(x,x//2)
        x//=2
        heapq.heappush(a,-x)
    ans = 0
    # pr(a)
    for i in a:
        ans+=(-i)
    pr(ans)


    return
















def main():
    # for _ in range(int(input())):
        solve()

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()
pr = print
if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")
ll = lambda : list(map(int,input().split()))
vv = lambda :map(int,input().split())
# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

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

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

print(-sum(a))

Submission status: Accepted

Solution code:
#141_D
import heapq
n,m=map(int,input().split())
a=list(map(lambda x:-1*int(x),input().split()))
heapq.heapify(a)
for _ in range(m):
    x=heapq.heappop(a)
    heapq.heappush(a,-(-x//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)

while M != 0:
    nim = heapq.heappop(A)
    heapq.heappush(A,-(-nim//2))
    M -= 1
    
print(-sum(A))

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
a = [int(x)*(-1) for x in input().split()]
# for _ in range(n):
#     x = int(input())
#     a.append(-1*x)
# print(a)
heapq.heapify(a)
# print(heapq.heappop(a)*(-1))  # 最大値の取り出し
# print(a)
for i in range(m):
    v = heapq.heappop(a)*(-1)
    heapq.heappush(a, (v//2)*(-1))

ans = 0
for i in range(n):
    ans += heapq.heappop(a)*(-1)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N, M = MAP()
    A = LIST()

    minus_A = list(map(lambda x: x*(-1), A))
    heapify(minus_A)
    for i in range(M):
        temp = heappop(minus_A) * (-1)
        heappush(minus_A, temp//2 * (-1))

    print(sum(minus_A) * (-1))


if __name__ == '__main__':
        main()

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

import heapq
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = LIST()

for i in range(N):
    A[i] = -1 * A[i]
heapq.heapify(A)
for i in range(M):
    m = heapq.heappop(A) * (-1)
    m = m // 2
    heapq.heappush(A, -1 * m)
A = list(map(lambda x: x * (-1), A))
print(sum(A))

Submission status: Accepted

Solution code:
import heapq
import sys

input = sys.stdin.readline


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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math 
import bisect
import heapq
from collections import deque

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

a = list(map(lambda x: x*(-1), a))
sum =0
for i in range(n):
    sum += int( heapq.heappop(a) )

print(sum)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(lambda x: -int(x) , input().split()))
import math
import heapq
heapq.heapify(a) # リストを変換
for _ in range(m):
    ai = -heapq.heappop(a) # => 1
    heapq.heappush(a, -(ai//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)
cnt=0
for i in range(m):
    ma=heapq.heappop(a)
    heapq.heappush(a,(-1)*(-ma//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), input().split()))
heapq.heapify(a)

if n == 1:
    print(-a[0]//2**m)
    exit()

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

print(-sum(a))

Submission status: Accepted

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

for i in range(M):
    b = heappop(B)
    heappush(B, b / 2)
result = 0
for b in B:
    result = result + int(-b)
print(result)

Submission status: Accepted

Solution code:
import heapq

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
A = [-i for i in A]
A.sort()
import heapq
while M:
    a = -heapq.heappop(A)
    a = a//2
    M -= 1
    heapq.heappush(A, -a)
print(-sum(A))

Submission status: Accepted

Solution code:
# Author: cr4zjh0bp
# Created: Fri Mar  6 04:56:50 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

from heapq import *
from math import floor

q = []

N, M = na()
a = na()
q = []
for i in range(N):
    heappush(q, -a[i])

for i in range(M):
    p = heappop(q)
    p = -((-p) // 2)
    heappush(q, p)

print(abs(sum(q)))

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

print(-sum(a))

Submission status: Accepted

Solution code:
f=lambda:input().split()
_,m=map(int,f())
l=[-int(i) for i in f()]
from heapq import *
heapify(l)
for _ in range(m):
  heappush(l,-(-heappop(l)//2))
print(-sum(l))

Submission status: Accepted

Solution code:
f = lambda:map(int,input().split())
_,m = f()
l = list(map(lambda x:-x,f()))
import heapq as hq
hq.heapify(l)
for i in range(m):
  p = -hq.heappop(l)//2
  hq.heappush(l,-p)
print(-sum(l))

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

Submission status: Accepted

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(map(int,ipti().split()))
    a = list(map(int,ipti().split()))
    a = list(map(lambda x: -1 * x, a))
    heapify(a)

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

    print(-sum(a))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(a)

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

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq

def main():
    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 _ in range(m):
        x = heapq.heappop(a)
        x = (x+1) // 2
        heapq.heappush(a, x)
    print(sum(a) * -1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
from queue import PriorityQueue

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

sinamono = [int(i) * -1 for i in input().rstrip().split(" ")]

q = PriorityQueue()
for i in sinamono:
    q.put(i)

for i in range(m):
    item = q.get()
    q.put(int(item/2))

ans = 0
while not q.empty():
    ans += q.get()
print(ans * -1)

Submission status: Accepted

Solution code:
import math
n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
b = [[]]
s = 1
for i in a:
  while i >= 2*s:
    s *= 2
    b.append([])
  b[-1].append(i-s)
while m > 0 and b != []:
  size = len(b[-1])
  for i in range(min(m,size)):
    if len(b) > 1:
      b[-2].append(b[-1].pop()//2)
    else:
      b[-1].pop()
  if len(b) > 1:
    b[-2].sort()
  if size <= m:
    b.pop()
  m -= size
ans = 0
for i in range(len(b)):
  ans += len(b[i])*(2**i)
  for j in b[i]:
    ans += j
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = [-int(i) for i in input().split()]
import heapq
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:
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 i in range(m):
    tmp = heapq.heappop(a)*(-1)   # 最大値の取り出し
    heapq.heappush(a, (-1)*(tmp//2)) # 1/2倍して最大値更新
print(-sum(a))

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)
import heapq

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,m = get_nums_l()
aaa = get_nums_l()
h = []

for a in aaa:
    heapq.heappush(h, -1 * a)

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

print(-1 * sum(h))

Submission status: Accepted

Solution code:
import heapq

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

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

for m in range(M):
    tmp = abs(heapq.heappop(H)) // 2
    heapq.heappush(H, -tmp)

SUM_A = 0
for h in H:
    SUM_A += int(h)
print(-SUM_A)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
a=[ -int(i) for i in input().split()]

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

Submission status: Accepted

Solution code:
class PriorityQueue():
    def __init__(self,arr,op=min):
        self.arr = arr
        self.op = op
        for i in range(len(arr)//2)[::-1]:
            self._siftup(i)

    def push(self,item):
        self.arr.append(item)
        self._siftdown(0,len(self.arr)-1)

    def pop(self):
        lastelt = self.arr.pop()
        if self.arr:
            returnitem = self.arr[0]
            self.arr[0] = lastelt
            self._siftup(0)
            return returnitem
        return lastelt

    def _siftdown(self,startpos,pos):
        newitem = self.arr[pos]
        while pos > startpos:
            parentpos = (pos - 1) >> 1
            parent = self.arr[parentpos]
            if self.op(newitem,parent) == newitem:
                self.arr[pos] = parent
                pos = parentpos
                continue
            break
        self.arr[pos] = newitem

    def _siftup(self,pos):
        endpos = len(self.arr)
        startpos = pos
        newitem = self.arr[pos]
        childpos = 2*pos + 1
        while childpos < endpos:
            rightpos = childpos + 1
            if rightpos < endpos and not self.op(self.arr[childpos],self.arr[rightpos])==self.arr[childpos]:
                childpos = rightpos
            self.arr[pos] = self.arr[childpos]
            pos = childpos
            childpos = 2*pos + 1
        self.arr[pos] = newitem
        self._siftdown(startpos,pos)

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

P = PriorityQueue(A,max)

for i in range(M):
    x = P.pop()
    x //= 2
    P.push(x)

print(sum(P.arr))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[ -int(i) for i in input().split()]
import heapq
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:
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
pq = []
for i in range(n):
    pq.append((-a[i], -a[i], 0))
heapq.heapify(pq)
for i in range(m):
    if len(pq) == 0: break
    mx = heapq.heappop(pq)
    if -mx[1] >= (2 ** (mx[2] + 1)): heapq.heappush(pq, (-(-mx[1] // (2 ** (mx[2] + 1))), mx[1], mx[2] + 1))
ans = 0
while len(pq) != 0:
    ans -= heapq.heappop(pq)[0]
print(ans)

Submission status: Accepted

Solution code:
from math import floor
import heapq

n, m = map(int, input().split())
A = [-a for a in map(int, input().split())]
heapq.heapify(A)
for _ in range(m):
  num = heapq.heappop(A) / 2
  heapq.heappush(A, num)

print(sum(floor(-a) for a in A))

Submission status: Accepted

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


heapq.heapify(A)


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

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

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

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

print(-sum(A))

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
l = sorted(list(map(int, input().split())), reverse=True)

def analyze(m):
    maximum = -1
    i = 0
    while m > 0 and i < n:
        if l[i] >= maximum:
            l[i] //= 2
            maximum = max(maximum, l[i])
            i += 1
            m -= 1
        else:
            return m
    return m



while m > 0:
    m = analyze(m)
    l.sort(reverse=True)

print(sum(l))

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)

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

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

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(b)

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

print(-sum(b))

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = LIST()
A = list(map(lambda x: x * (-1), A))

heapq.heapify(A)
# print(A)

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

Submission status: Accepted

Solution code:
import heapq

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

#heapqでは最小値しか取り出せないので，*(-1)することで最大値を取り出す
for i in range(len(a)):
    a[i] *= -1

#リストを優先度付きキューにする
heapq.heapify(a)

for i in range(n[1]):
    #最小値(実際には最大値であるはずの値)を取り出す
    tmp = heapq.heappop(a)

    #取り出した値を2で割って切り下げで優先度付きキューに挿入
    heapq.heappush(a, int(tmp/2))

print(-sum(a))

'''
max()はO(N)．heapqはO(logN)
これだと発想はあっているが，O(NM)となるので間に合わない
for i in range(n[1]):
    a[a.index(max(a))] = int(max(a) / 2)

print(sum(a))
'''

Submission status: Accepted

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

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

for i in range(n):
    a[i] *= -1
heapify(a)
#print(a)
for i in range(m):
    maxa = heappop(a)
    heappush(a, -(-maxa//2))
#print(a)
print(-(sum(a)))

Submission status: Accepted

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


    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

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

print(-sum(h))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

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

print(-sum(h))