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 itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce
sys.setrecursionlimit(4100000)
from functools import lru_cache
INF = 1 << 60

#ここから書き始める
n, m = map(int, input().split())
a = [int(i) * -1 for i in input().split()]
# print(a)
heapq.heapify(a)
for i in range(m):
    maximum = heapq.heappop(a) * -1
    heapq.heappush(a, (maximum // 2) * -1)
print(sum(a) * -1)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import heapq

def main():
  MAX = 10**9
  n, m = map(int, input().strip().split())
  As = sorted(list(map(lambda x:-int(x), input().strip().split())))
  hq = heapq.heapify(As)
  for _ in range(m):
    x = heapq.heappop(As)
    x = -(-x//2)
    x = heapq.heappush(As, x)
  print(-sum(As))
    
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import heapq
n,m = map(int,input().split())#nは品物の数　mは割引券の数
a = sorted(list(map(int,input().split())),reverse = True)#値段一覧
a = list(map(lambda x: x*(-1), a))  
heapq.heapify(a)#リストを優先度付きキューへ入れる
highest = 0
ans = []
for i in range(m):
    highest = heapq.heappop(a)*(-1)#heappopでとりだし　heappop(リスト名)*(リストのインデックス)本来最小値を取り出すものである
    heapq.heappush(a,highest//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):
  n = heapq.heappop(a)
  n = -1*n//2
  heapq.heappush(a,(-1)*n)
print(-sum(a))

Submission status: Accepted

Solution code:
import bisect
n,m = map(int,input().split())
a = list(map(int,input().split()))
while m != 0:
    a.sort()
    where = bisect.bisect_left(a,a[-1]//2)
    where = abs(where-(n+1))
    for i in range(1,min(where,m+1)):
        a[-i] = a[-i]//2
        m = 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)*(-1), input().split()))
heapq.heapify(a)

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

print(-sum(a))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def divisor(n):
        i = 1
        table = []
        while i * i <= n:
            if n % i == 0:
                table.append(i)
                table.append(n // i)
            i += 1
        table = list(set(table))
        return table


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)

    def list(self):
        return self.__q


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    # sys.stdin = open("Sample.txt")
    N, M = Scanner.map_int()
    A = Scanner.map_int()
    A = PriorityQueue([-x for x in A])
    for _ in range(M):
        A.push(Math.roundUp(A.pop(), 2))
    print(-sum(A.list()))
    return


if __name__ == "__main__":
    main()

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

print(-sum(a))

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

Solution code:
import sys
import heapq

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N,M = MI()
	A = LI()
	A = list(map(lambda x : x*(-1), A))
	heapq.heapify(A)
	for i in range(M):
		discnt_price = (heapq.heappop(A) * -1)//2
		heapq.heappush(A,discnt_price*-1)
	print(sum(A)*-1)


main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc141/tasks/abc141_d
# 割引券は半額にする操作
# 値段が大きいものに貪欲に使っていきたい
# 割って逐一挿入して最大のものをまた割る？
# 配列平衡二分木で実装←atcoderの環境が古くて使えなかった！


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


from heapq import heapify, heappop, heappush, heappushpop


class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)


N, M = read_ints()
A = read_ints()
que = PriorityQueue([-a for a in A])
for _ in range(M):
    x = -que.pop()
    x //= 2
    que.push(-x)

print(-sum(que.heap))

Submission status: Accepted

Solution code:
import heapq

def func(x):
    return -x

def main():
    N, M = map(int, input().split())
    A = list(map(func,map(int, input().split())))
    heapq.heapify(A)
    cnt = 0
    while cnt < M:
        cnt += 1
        tmp = -heapq.heappop(A)
        heapq.heappush(A,-(tmp//2))
    
    print(-sum(A))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

S = input().split(" ")
N = int(S[0])
M = int(S[1])
S = input()

arr = [-int(s) for s in S.split(" ")]

heapq.heapify(arr)

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

print(-sum(arr))

Submission status: Accepted

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

heapq.heapify(a)
for _ in range(m):
    tmp=heapq.heappop(a)
    cal=math.ceil(tmp/2)
    heapq.heappush(a,cal)
    
print(sum(a)*-1)

Submission status: Accepted

Solution code:
import heapq

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

heap = []
heapq.heapify(heap)
for a in A:
    heapq.heappush(heap, -1*a)

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

ans = 0
for y in heap:
    y = -1 * y
    ans += y // 1

print(int(ans))

Submission status: Accepted

Solution code:
import heapq
N,M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
for i in range(len(A)):
    A[i] = A[i]*(-1)
heapq.heapify(A)
for i in range(M):
    maxa = heapq.heappop(A)
    maxa = -1 * maxa
    maxa = maxa//2
    maxa = -1 * maxa
    heapq.heappush(A,maxa)
print(-sum(A))

Submission status: Accepted

Solution code:
import heapq


def main():
    N, M = [int(x) for x in input().split()]
    heap = [-int(x) for x in input().split()]
    heapq.heapify(heap)

    for _ in range(M):
        x = heapq.heappop(heap)
        x = -x
        x = x // 2
        x = -x
        heapq.heappush(heap, x)
    print(-sum(heap))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq


def main():
    N, M = [int(x) for x in input().split()]
    heap = [-int(x) for x in input().split()]
    heapq.heapify(heap)

    for _ in range(M):
        x = heapq.heappop(heap)
        x = -x
        x = x // 2
        x = -x
        heapq.heappush(heap, x)
    print(sum(map(lambda x: -x, heap)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()

class Heap(object):
    def __init__(self, A):
        self._heap = A[:]
        # heapify in linear time
        for i in range((len(A))//2-1,-1,-1): self._descend(i)

    def __len__(self):
        return len(self._heap)

    def __bool__(self):
        return bool(self._heap)

    def _descend(self, i):
        heap = self._heap
        now = i
        # i の子は 2i+1, 2i+2
        while(1):
            if now*2+1 >= len(self): break # 子が存在しない
            # 子がひとつだけのとき、必要なら入れ替えて終わり
            if now*2+1 == len(self)-1:
                if heap[now] > heap[now*2+1]:
                    heap[now], heap[now*2+1] = heap[now*2+1], heap[now]
                break
            # 子が複数のとき
            else:
                # 親、子1、子2のうち、親が最小であれば終わり
                if min(heap[now], heap[2*now+1], heap[2*now+2]) == heap[now]: break
                # そうでないとき、子のうち小さい方を親と入れ替える
                next = min((heap[2*now+1],2*now+1), (heap[2*now+2],2*now+2))[1]
                heap[now], heap[next] = heap[next], heap[now]
                now = next

    def front(self):
        assert self
        return self._heap[0]

    def append(self, x):
        self._heap.append(x)
        now = len(self)-1
        heap = self._heap
        # i の親は (i-1)//2
        while now!=0 and heap[now] < heap[(now-1)//2]:
            heap[now], heap[(now-1)//2] = heap[(now-1)//2], heap[now]
            now = (now-1)//2

    def pop(self):
        assert self
        if len(self)==1: return self._heap.pop()
        res, self._heap[0] = self._heap[0], self._heap.pop()
        self._descend(0)
        return res

def resolve():
    n, m = map(int,input().split())
    A = list(map(lambda x:-int(x),input().split()))
    heap = Heap(A)
    for _ in range(m):
        x = -heap.pop()
        x //= 2
        heap.append(-x)

    print(-sum(heap._heap))
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()

class Heap(object):
    def __init__(self, A):
        self._heap = A[:]
        for i in range((len(A))//2-1,-1,-1): # heapify in linear time
            self._descend(i)

    def __len__(self):
        return len(self._heap)

    def __bool__(self):
        return bool(self._heap)

    def _descend(self, i):
        heap = self._heap
        # i の子は 2i+1, 2i+2
        while(1):
            if i*2+1 >= len(self): break # 子が存在しない
            # 子がひとつだけのとき、必要なら入れ替えて終わり
            if i*2+1 == len(self)-1:
                if heap[i] > heap[i*2+1]:
                    heap[i], heap[i*2+1] = heap[i*2+1], heap[i]
                break
            # 子が複数のとき
            else:
                # 親、子1、子2のうち、親が最小であれば終わり
                if min(heap[i], heap[2*i+1], heap[2*i+2]) == heap[i]: break
                # そうでないとき、子のうち小さい方を親と入れ替える
                next = min((heap[2*i+1],2*i+1), (heap[2*i+2],2*i+2))[1]
                heap[i], heap[next] = heap[next], heap[i]
                i = next

    def front(self):
        assert self
        return self._heap[0]

    def append(self, x):
        self._heap.append(x)
        now = len(self)-1
        heap = self._heap
        # i の親は (i-1)//2
        while now!=0 and heap[now] < heap[(now-1)//2]:
            heap[now], heap[(now-1)//2] = heap[(now-1)//2], heap[now]
            now = (now-1)//2

    def pop(self):
        assert self
        if len(self)==1: return self._heap.pop()
        res, self._heap[0] = self._heap[0], self._heap.pop()
        self._descend(0)
        return res

def resolve():
    n, m = map(int,input().split())
    A = list(map(lambda x:-int(x),input().split()))
    heap = Heap(A)
    for _ in range(m):
        x = -heap.pop()
        x //= 2
        heap.append(-x)

    print(-sum(heap._heap))
resolve()

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(a_list)
for _ in range(m):
  min_n = heapq.heappop(a_list)
  heapq.heappush(a_list, (min_n//2 if min_n%2 == 0 else min_n//2+1))
print(sum(a_list) * (-1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()

class Heap(object):
    def __init__(self, A):
        self._heap = []
        # heapify は O(n) でできるらしいが、O(nlogn) で妥協
        # cf. https://github.com/python/cpython/blob/3.8/Lib/heapq.py
        for a in A:
            self.append(a)

    def __len__(self):
        return len(self._heap)

    def __bool__(self):
        return bool(self._heap)

    def front(self):
        assert self
        return self._heap[0]

    def append(self, x):
        self._heap.append(x)
        now = len(self)-1
        heap = self._heap
        # n の親は (n-1)//2
        while now!=0 and heap[now] < heap[(now-1)//2]:
            heap[now], heap[(now-1)//2] = heap[(now-1)//2], heap[now]
            now = (now-1)//2

    def pop(self):
        assert self
        if len(self)==1:
            return self._heap.pop()

        heap = self._heap
        res, heap[0] = heap[0], heap.pop()
        # n の子は 2*n+1, 2*n+2
        now = 0
        while(1):
            if now*2+1 >= len(self): break # 子が存在しない
            # 子がひとつだけのとき、必要なら入れ替えて終わり
            if now*2+1 == len(self)-1:
                if heap[now] > heap[now*2+1]:
                    heap[now], heap[now*2+1] = heap[now*2+1], heap[now]
                break
            # 子が複数のとき
            else:
                # 親、子1、子2のうち、親が最小であれば終わり
                if min(heap[now], heap[2*now+1], heap[2*now+2]) == heap[now]: break
                # そうでないとき、子のうち小さい方を親と入れ替える
                next = min((heap[2*now+1],2*now+1), (heap[2*now+2],2*now+2))[1]
                heap[now], heap[next] = heap[next], heap[now]
                now = next

        return res

    def sort(self):
        return [self.pop() for _ in range(len(self))]

def resolve():
    n, m = map(int,input().split())
    A = list(map(lambda x:-int(x),input().split()))
    heap = Heap(A)
    for _ in range(m):
        x = -heap.pop()
        x //= 2
        heap.append(-x)

    print(-sum(heap._heap))
resolve()

Submission status: Accepted

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

class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)
      
N,M=map(int,input().split())
L = list(map(lambda s:int(s) * -1,input().split()))
#print(L)
pq = PriorityQueue(L)
import math
for _ in range(M):
  m = pq.pop()
  #print(m)
  pq.push(math.ceil(m / 2))
ANS=0
for _ in range(N):
  k = pq.pop()
  #print(k)
  ANS += k
print(ANS * -1)

Submission status: Accepted

Solution code:
import heapq

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

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

Submission status: Accepted

Solution code:
import heapq

n,m = list(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)
  mx= -(-mx//2)
  heapq.heappush(a,mx)

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

Submission status: Accepted

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

heapq.heapify(price)
for _ in range(m):
    max_price = -heapq.heappop(price)
    heapq.heappush(price, -(max_price//2))

ans = -sum(price)
print(ans)

Submission status: Accepted

Solution code:
import math
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):
    max = heapq.heappop(a)
    max = max/2
    heapq.heappush(a,max)

a = list(map(lambda x:x*(-1),a))
a = list(map(math.floor,a))

print(sum(a))

Submission status: Accepted

Solution code:
import heapq

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

def func():
   n=-heapq.heappop(A)
   n//=2
   heapq.heappush(A,-n)

for i in range(M):
   func()

print(-sum(A))

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify

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

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

print(-sum(q))

Submission status: Accepted

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

print(main())

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

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

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

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

for _ in range(M):
    _max = heappop(A)*(-1)
    x = _max / 2
    heappush(A, floor(_max/2)*(-1))

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

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

print(-sum(a))

Submission status: Accepted

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

import heapq  # heapqライブラリのimport
heapq.heapify(a_list)  # リストを優先度付きキューへ

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

print(sum(a_list) * -1)

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
A = sorted(list(map(lambda x: int(x)*(-1), input().split())))

heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

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

import heapq

heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

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

nums = [n * -1 for n in nums]
heapq.heapify(nums)

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

print(-sum(nums))

Submission status: Accepted

Solution code:
import heapq
from math import ceil
n, m = map(int, input().split())
nums = [-int(i) for i in input().split()]
heapq.heapify(nums)

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

nums = [-n for n in nums]
print(sum(nums))

Submission status: Accepted

Solution code:
import heapq
import math
import sys
from functools import reduce
input = sys.stdin.readline

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

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

    print(reduce(lambda total, x: math.floor(-x) + total, A, 0))

main()

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

Submission status: Accepted

Solution code:
import heapq

N,M = map(int, input().split())
List1=list(map(int,input().split()))
List=[]

for i in range(N):
  a = List1[i]
  List.append(-a)

heapq.heapify(List)

for i in range(M):
  a = (-heapq.heappop(List)) // 2
  heapq.heappush(List, -a)
  
print(int(-sum(List)))

Submission status: Accepted

Solution code:
#優先度付きque
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):
    #最大値の取り出し
    tem_num=heapq.heappop(a)*(-1)
    #最大値に割引券を使いheapqへ入れる
    heapq.heappush(a,(-1)*(tem_num//2))
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):
    heapq.heappushpop(a, -(-a[0] // 2))
print(-sum(a))

Submission status: Accepted

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

for i in range(M):
    buf = heapq.heappop(heap)
    buf = -buf
    buf = buf//2
    heapq.heappush(heap,-buf)
    
print(-sum(heap))

Submission status: Accepted

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

Submission status: Accepted

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

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)
    ans = 0
    while M > 0:
        heapq.heappush(A, (heapq.heappop(A)*-1) // 2 * -1)
        M -= 1
    for i in range(N):
        ans += -A[i]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import heapq
N,M=map(int, input().split())
A=list(map(int, input().split())) #N個
for i,item in enumerate(A):
  A[i]=(-1)*item
  
heapq.heapify(A)

for m in range(M):
  tmp1=heapq.heappop(A)
  tmp2=(-1)*(math.floor((-1)*tmp1/2))
  heapq.heappush(A,tmp2)
  
print((-1)*sum(A))

Submission status: Accepted

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

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

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

ans = -sum(int(a) for a in A)
print(ans)

Submission status: Accepted

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

def solve(N: int, M: int, A: "List[int]"):

    while True:
        tmp = heapq.heappop(A) * -1
        heapq.heappush(A,tmp // 2 * -1)
        M -= 1
        if M == 0:
            break
    
    print(sum(A) * -1)

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 = []
    heapq.heapify(A)
    for i in range(N):
        heapq.heappush(A,int(next(tokens)) * -1)

    solve(N, M, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(2e5+3)
heap_arr, heap_size = [0] * N, 0

def heap_push(x):
    global heap_size
    heap_arr[heap_size] = x
    i = heap_size
    while i > 0 and heap_arr[i] > heap_arr[(i-1)//2]:
        heap_arr[i], heap_arr[(i-1)//2] = heap_arr[(i-1)//2], heap_arr[i]
        i = (i-1)//2
    heap_size += 1

def get_max():
    global heap_size
    if heap_size == 0:
        return -2e9
    return heap_arr[0]

def heap_pop():
    global heap_size
    if heap_size == 0:
        return
    heap_size -= 1
    heap_arr[0], heap_arr[heap_size] = heap_arr[heap_size], heap_arr[0]
    i, j = 0, -1
    while i != j:
      j = i
      l = 2*i+1
      r = 2*i+2
      if l < heap_size and heap_arr[l] > heap_arr[i]:
          i = l
      if r < heap_size and heap_arr[r] > heap_arr[i]:
          i = r
      heap_arr[i], heap_arr[j] = heap_arr[j], heap_arr[i]

n, m = map(int, input().split())
arr = list(map(int, input().split()))
for i in arr:
    heap_push(i)
while m >= 1:
    x = get_max() // 2
    heap_pop()
    heap_push(x)
    m -= 1    
print(sum(heap_arr))

Submission status: Accepted

Solution code:
import heapq as hp
n,m=map(int,input().split())
a=list(map(int,input().split()))
a=[-x for x in a]
hp.heapify(a)

for i in range(m):
    t=hp.heappop(a)
    hp.heappush(a,-(-t//2))

print(-sum(a))

Submission status: Accepted

Solution code:
N = int(2e5+3)
heap_arr, heap_size = [0] * N, 0

def heap_push(x):
    global heap_size
    heap_arr[heap_size] = x
    i = heap_size
    while i > 0 and heap_arr[i] > heap_arr[(i-1)//2]:
        heap_arr[i], heap_arr[(i-1)//2] = heap_arr[(i-1)//2], heap_arr[i]
        i = (i-1)//2
    heap_size += 1

def get_max():
    global heap_size
    if heap_size == 0:
        return -2e9
    return heap_arr[0]

def heap_pop():
    global heap_size
    if heap_size == 0:
        return
    heap_size -= 1
    heap_arr[0], heap_arr[heap_size] = heap_arr[heap_size], heap_arr[0]
    i, j = 0, -1
    while i != j:
      j = i
      l = 2*i+1
      r = 2*i+2
      if l < heap_size and heap_arr[l] > heap_arr[i]:
          i = l
      if r < heap_size and heap_arr[r] > heap_arr[i]:
          i = r
      heap_arr[i], heap_arr[j] = heap_arr[j], heap_arr[i]

n, m = map(int, input().split())
arr = list(map(int, input().split()))
for i in arr:
    heap_push(i)
while m >= 1:
    x = get_max() // 2
    heap_pop()
    heap_push(x)
    m -= 1    
print(sum(heap_arr))

Submission status: Accepted

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

print(-sum(A))

Submission status: Accepted

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

while m >= 1:
    a = (heapq.heappop(price) + 1) // 2
    heapq.heappush(price, a)
    m -= 1
    
print(sum(price) * (-1))

Submission status: Accepted

Solution code:
## 2020/01/19 Not yet
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 _ in range(M):
    x = heapq.heappop(A)
    heapq.heappush(A, (-x//2)*(-1))  

print(-sum(A))