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 sys
from collections import Counter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def upsqrt(x):
    k = x ** 0.5
    res = 1
    while res < k:
        res <<= 1
    return res


def botsqrt(x):
    k = x ** 0.5
    res = 1
    while res <= k:
        res <<= 1
    return res >> 1


class VanEmdeBoasTree:
    def __init__(self, size):
        self.universe_size = 1
        while self.universe_size < size:
            self.universe_size <<= 1
        self.minimum = -1
        self.maximum = -1
        self.summary = None
        self.cluster = {}
    
    def __high(self, x):
        return x // botsqrt(self.universe_size)
    
    def __low(self, x):
        return x % botsqrt(self.universe_size)
    
    def __generate_index(self, x, y):
        return x * botsqrt(self.universe_size) + y
    
    def min(self):
        return self.minimum
    
    def max(self):
        return self.maximum
    
    def __empinsert(self, key):
        self.minimum = self.maximum = key
    
    def insert(self, key):
        if self.minimum == -1:
            self.__empinsert(key)
        else:
            if key < self.minimum:
                self.minimum, key = key, self.minimum
            if 2 < self.universe_size:
                if self.__high(key) not in self.cluster:
                    self.cluster[self.__high(key)] = VanEmdeBoasTree(botsqrt(self.universe_size))
                    if self.summary is None:
                        self.summary = VanEmdeBoasTree(upsqrt(self.universe_size))
                    self.summary.insert(self.__high(key))
                    self.cluster[self.__high(key)].__empinsert(self.__low(key))
                else:
                    self.cluster[self.__high(key)].insert(self.__low(key))
            if self.maximum < key:
                self.maximum = key
    
    def is_member(self, key):
        if self.minimum == key or self.maximum == key:
            return True
        elif self.universe_size == 2:
            return False
        else:
            if self.__high(key) in self.cluster:
                return self.cluster[self.__high(key)].is_member(self.__low(key))
            else:
                return False
    
    def successor(self, key):
        if self.universe_size == 2:
            if key == 0 and self.maximum == 1:
                return 1
            else:
                return -1
        elif self.minimum != -1 and key < self.minimum:
            return self.minimum
        else:
            max_incluster = -1
            if self.__high(key) in self.cluster:
                max_incluster = self.cluster[self.__high(key)].max()
            if max_incluster != -1 and self.__low(key) < max_incluster:
                offset = self.cluster[self.__high(key)].successor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                succ_cluster = self.summary.successor(self.__high(key))
                if succ_cluster == -1:
                    return -1
                else:
                    offset = self.cluster[succ_cluster].min()
                    return self.__generate_index(succ_cluster, offset)
    
    def predecessor(self, key):
        if self.universe_size == 2:
            if key == 1 and self.minimum == 0:
                return 0
            else:
                return -1
        elif self.maximum != -1 and self.maximum < key:
            return self.maximum
        else:
            min_incluster = -1
            if self.__high(key) in self.cluster:
                min_incluster = self.cluster[self.__high(key)].min()
            if min_incluster != -1 and min_incluster < self.__low(key):
                offset = self.cluster[self.__high(key)].predecessor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                pred_cluster = -1
                if self.summary is not None:
                    pred_cluster = self.summary.predecessor(self.__high(key))
                if pred_cluster == -1:
                    if self.minimum != -1 and self.minimum < key:
                        return self.minimum
                    else:
                        return -1
                else:
                    offset = self.cluster[pred_cluster].max()
                    return self.__generate_index(pred_cluster, offset)
    
    def delete(self, key):
        if self.minimum == self.maximum:
            self.minimum = self.maximum = -1
            return True
        elif self.universe_size == 2:
            if key == 0:
                self.minimum = 1
            else:
                self.minimum = 0
            self.maximum = self.minimum
            return False
        else:
            if key == self.minimum:
                first_cluster = self.summary.min()
                key = self.__generate_index(first_cluster, self.cluster[first_cluster].min())
                self.minimum = key
            flg0 = self.cluster[self.__high(key)].delete(self.__low(key))
            if flg0:
                del self.cluster[self.__high(key)]
                flg1 = self.summary.delete(self.__high(key))
                if key == self.maximum:
                    if flg1:
                        self.maximum = self.minimum
                    else:
                        max_insummary = self.summary.max()
                        self.maximum = self.__generate_index(max_insummary, self.cluster[max_insummary].max())
            elif key == self.maximum:
                self.maximum = self.__generate_index(self.__high(key), self.cluster[self.__high(key)].max())


def solve():
    N, M = map(int, rl().split())
    A = list(map(int, rl().split()))
    
    veb = VanEmdeBoasTree(10 ** 9)
    for ai in A:
        veb.insert(ai)
    
    counter = Counter(A)
    for _ in range(M):
        maximum = veb.max()
        counter[maximum] -= 1
        if counter[maximum] == 0:
            veb.delete(maximum)
        if counter[maximum // 2] == 0:
            veb.insert(maximum // 2)
        counter[maximum // 2] += 1
    
    ans = 0
    for key, val in counter.items():
        ans += key * val
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import heapq
import math
from heapq import heappop
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:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

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

heapify(a)
while m > 0:
    m -= 1
    heappush(a, (-1)*(-heappop(a)//2))
print(-sum(a))

Submission status: Accepted

Solution code:
import heapq
import 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 _ in range(M):
    tmp = heapq.heappop(A)*(-1)
    heapq.heappush(A, (tmp/2)*(-1))
ans = 0
for _ in range(N):
    ans += math.floor(heapq.heappop(A)*(-1))
print(ans)

Submission status: Accepted

Solution code:
# from pprint import pprint
import math

# import collections

# n = int(input())
n, m = map(int, input().split(' '))
a = list(map(lambda x: int(x) * (-1), input().split(' ')))
# a = sorted(a, reverse=True)
# b = [math.log2(_a) for _a in a]


import heapq

q_a = heapq.heapify(a)

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from math import log

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

table = [[0]*(int(log(a[-1],2))+2) for i in range(n)]

for i in range(n):
    for y in range(int(log(a[-1],2))+2):
        table[i][y] = a[i]//pow(2,y)
        if a[i]//pow(2,y) == 0:
            break

s_table = [[0]*(int(log(a[-1],2))+2) for i in range(n)]
for i in range(n):
    s_table[i][0] = table[i][0]

import heapq
hq = []
heapq.heapify(hq)
h_push = heapq.heappush
h_pop = heapq.heappop

for i in range(n):
    for y in range(1,int(log(a[-1],2))+2):
        s_table[i][y] = table[i][y]-table[i][y-1]
        h_push(hq,table[i][y]-table[i][y-1])
        if table[i][y]-table[i][y-1] == -1:
            break


ans = sum(a)

for i in range(m):
    if not hq:
        print(0)
        exit()
    ans += h_pop(hq)
    
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
#input
N,M=map(int,input().strip().split())
A=list(map(int,input().strip().split()))

#M回全て、その時点で一番高価な商品に割引を
#適用した時、支払金額が最小となる。

#安い順にソート
A.sort()

#割引券を一回でも使った商品を格納
dp=deque([])
#割引未適用品(A)と、適用済み品(dp)の最高値を比較し、大きい方に割引を適用
for m in range(M):
    if len(dp)==0:
        tmp=A.pop()
    elif len(A)==0:
        tmp=dp.popleft()
    else:
        if A[-1]>=dp[0]:
            tmp=A.pop()
        else:
            tmp=dp.popleft()
    dp.append(tmp//2)
print(sum(A)+sum(dp))

Submission status: Accepted

Solution code:
# ABC141D - Powerful Discount Tickets
from heapq import heapify, heappop, heappush


def main():
    _, M = map(int, input().split())
    A = [-i for i in map(int, input().split())]
    heapify(A)

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

    print(-sum(A))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC141D - Powerful Discount Tickets
from heapq import heapify, heappop, heappush


def main():
    _, M = map(int, input().split())
    A = [-i for i in map(int, input().split())]
    heapify(A)

    heappop_max = lambda heap: -heappop(heap)
    heappush_max = lambda heap, x: heappush(heap, -x)
    discount = lambda: heappush_max(A, heappop_max(A) // 2)

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from decimal import Decimal
from bisect import bisect
n,m=map(int,input().split())
lst=sorted(map(Decimal, input().split()))

while m>0:
    p=lst[-1]
    index=bisect(lst,p/2)
    for i in range(n-1,index-1,-1):
        if m>0:
            lst[i]=lst[i]/2
            m-=1
    lst=sorted(lst)
    if lst[-1]<1:
        break

ans=0
for i in lst:
    ans+=i//1
print(ans)

Submission status: Accepted

Solution code:
from decimal import Decimal
from bisect import bisect
n,m=map(int,input().split())
lst=sorted(map(Decimal, input().split()))

while m>0:
    p=lst[-1]
    index=bisect(lst,p/2)
    for i in range(n-1,index-1,-1):
        if m>0:
            lst[i]=lst[i]/2
            m-=1
    lst=sorted(lst)
    if lst[-1]<1:
        break

ans=0
for i in lst:
    ans+=i//1
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import heapq
n,m = map(int, input().split())
al = list(map(int, input().split()))
al = [(-1)*a for a in al]
al.sort()

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

print(sum(al)*(-1))

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
alst = list(map(int, input().split()))
heap = [-1 * num for num in alst]
ans = sum(alst)
heapq.heapify(heap)

num = heapq.heappop(heap)
for _ in range(m):
    num *= -1
    tmp = num // 2
    ans -= num - tmp
    tmp *= -1
    num = heapq.heappushpop(heap, tmp)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[18]:


import heapq


# In[23]:


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


# In[24]:


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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify

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):
    temp = int(heappop(A)/2)
    heappush(A, temp)

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

Submission status: Accepted

Solution code:
#<D>wa
#(Point)
#優先度付きキューを使いこなす！
#最大値を1/2するのをＭ回繰り返せばいいけどリストやと最大値の選定にO(N),
#それをＭ回やからO(MN)でＴＬＥ
#heapqやったらO(MlogN)なのでおｋ
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):
    value_min = heapq.heappop(A)
    heapq.heappush(A, (-1) * (-value_min//2)) #負数の剰余演算避けるために
    #一時的に０以上の整数にしている
    #*(-1)してやらんと挿入した後の次の最大値を探す作業ができなくなる
    #heapqは最小値しかみつけれんから
    #print(A)
print(-sum(A))

Submission status: Accepted

Solution code:
from heapq import *
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):
    t=heappop(a)
    heappush(a,int(t/2))
print(-1*sum(a))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

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

Submission status: Accepted

Solution code:
# heapqでは最小値の取得しかできない。
# heapqで最大値を取得したい場合は，全要素を-1倍してから最小値を取得し，再度-1倍する。
import heapq

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

# 最大値を取り出すため、リストの要素を全てマイナスにする
A = list(map(lambda x: -int(x), input().split()))

heapq.heapify(A)

# 割引券の枚数分だけforを回す
for _ in range(M):
    # リストの最大値を取り出す、2で割って挿入
    # マイナスになっているので一旦正負逆転させてから２で割る、挿入するときにもう一度反転
    heapq.heappush(A, ((heapq.heappop(A) * (-1)) // 2) * (-1))

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

print(-sum(A))

Submission status: Accepted

Solution code:
import sys
from collections import deque
import itertools
from collections import deque
sys.setrecursionlimit(10 ** 9)
import heapq
import numpy as np

# map(int, sys.stdin.read().split())


def input():
    return sys.stdin.readline().rstrip()


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

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




    pass



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import heapq

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

print(-sum(a))

Submission status: Accepted

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

print((-1)*sum(list_A))

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(A)

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIM(): return [-int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N, M = LI()
    A = LIM()
    heapq.heapify(A)
    for _ in range(M):
        x = -heapq.heappop(A)
        heapq.heappush(A, -(x // 2))
    print(-sum(A))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq as hp

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

hp.heapify(a)

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

Submission status: Accepted

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

A = list(map(lambda x: x*(-1), A))  # 各要素を-1倍
heapq.heapify(A)

while M>0:
    a = heapq.heappop(A)*(-1)
    heapq.heappush(A, -int(a/2))
    M -= 1

print(-sum(A))

Submission status: Accepted

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time,heapq
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################

def solve():
    n,m = invr()
    a = inlt()
    a = list(map(lambda x : x * (-1),a))
    heapq.heapify(a)
    for i in range(m):
      heapq.heappush(a,-(-heapq.heappop(a) // 2))
    print(-sum(a))
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1],1
    return(q)
 
def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)

def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))

def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))
#-----------------------------------------------------------------------#
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
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):
  s=heapq.heappop(a)*(-1)
  heapq.heappush(a, (s//2)*(-1))

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

Submission status: Accepted

Solution code:
#　解説確認後AC
#　問題解説参考サイト 「けんちょんの競プロ精進記録」 より
#  URL: https://drken1215.hatenablog.com/entry/2019/09/16/032000
#　優先度付きキュー 参考記事　「【Python】優先度付きキューの使い方【heapq】」
#　URL: https://qiita.com/ell/items/fe52a9eb9499b7060ed6

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):
    heapq.heappush(a,((heapq.heappop(a)*(-1))//2)*(-1)) # リストの最大値を取り出して割る2して挿入
print(abs(sum(a))) # abs()してマイナスを取り除く

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

Submission status: Accepted

Solution code:
import heapq

def readinput():
    n,m=list(map(int,input().split()))
    a=list(map(int,input().split()))
    return n,m,a

def main(n,m,a):
    #print(a)
    hq=[]
    for i in a:
        heapq.heappush(hq,-i)
    #print(hq)
    for i in range(m):
        a=(-heapq.heappop(hq))//2
        heapq.heappush(hq,-a)
        #print(hq)

    sum=0
    for i in hq:
        sum+=i
    
    return -sum

if __name__=='__main__':
    n,m,a=readinput()
    ans=main(n,m,a)
    print(ans)

Submission status: Accepted

Solution code:
import queue

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

q = queue.PriorityQueue()
for i in a:
    q.put(-i)

for _ in range(m):
    i = -(q.get())
    q.put(-(i >> 1))

answer = 0
for _ in range(n):
    answer -= q.get()

print(answer)

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

Submission status: Accepted

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

Submission status: Accepted

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

n,m = map(int,input().split())
l = list(map(int,input().split()))
s = sum(l)
for i in range(n):
    l[i] *= (-1)

heapq.heapify(l)

discount = 0

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

print(s-discount)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N ,M = map(int, input().split())
A_list = [int(i) * (-1) for i in input().split()]


import heapq

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

print(-sum(A_list))

Submission status: Accepted

Solution code:
from fractions import Fraction
from math import log, ceil
import heapq

(n, m), aa = [list(map(int, s.split())) for s in open(0)]
aa = [-Fraction(a) for a in aa]

heapq.heapify(aa)

while m:
    m1 = heapq.heappop(aa)
#     print(f'{m=},{m1=}')
    if len(aa):
        m2 = aa[0]
        use = min(max(ceil(log(m1/m2)/log(2)), 1), m)
#         print(f'{m2=},{use=}')
    else:
        use = min(max(ceil(log(-m1)/log(2)), 1), m)
#         print(f'else, {use=}')
#         print(f'{ceil(log(-m1)/log(2))=}')
#     print(f'{m1/Fraction(2**use)}')
    heapq.heappush(aa, m1 / Fraction(2**use))
    m -= use
    if -(aa[0]) < 1:
        break

aa = [int(-a) for a in aa]

print(sum(aa))

Submission status: Accepted

Solution code:
import heapq
class HeapQ:
    def __init__(self, L, desc=False):
        if desc:
            L = [-l for l in L]
        self.sign = -1 if desc else 1
        self.HQ = L
        heapq.heapify(self.HQ)
    def pop(self):
        return heapq.heappop(self.HQ) * self.sign
    def push(self, x):
        heapq.heappush(self.HQ, x * self.sign)
    def get_list(self):
        return list([-hq for hq in self.HQ]) if self.sign == -1 else list(self.HQ)

n, m = map(int, input().split())
A = list(map(int, input().split()))
hq = HeapQ(A, desc=True)
for _ in range(m):
    hq.push(hq.pop() // 2)

print(sum(hq.get_list()))

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

def main():
    n, m = map(int, input().split())
    a = [int(x)*-1 for x in input().split()]
    ans = sum(a)*-1
    diff = 0
    
    heapify(a)
    for _ in range(1, m+1):
        _h_a = heappop(a) * -1
        diff += _h_a - _h_a // 2
        heappush(a, (_h_a // 2)*-1)
    ans -= diff
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


n, m = LI()
a = LI()
a = list(map(lambda x: -1 * x, a))
heapq.heapify(a)
for _ in range(m):
    price = -1 * heapq.heappop(a)  # 現時点での最大値をO(log N)で取得
    heapq.heappush(a,  -1 * (price // 2))
print(-1 * sum(a))

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *A = map(int, read().split())

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

    for _ in range(M):
        a = heappop(hq)
        a = int(a / 2)
        heappush(hq, a)

    print(-sum(hq))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

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

    A = [-1 * a for a in A]
    heapify(A)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

heapify(a)

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

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), input().split()))
heapify(A)
for i in range(M):
  tmp = heappop(A)
  heappush(A,-((-tmp)//2))
A = list(A)

print(-sum(A))

Submission status: Accepted

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

Submission status: Accepted

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