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: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
# import collections

# import bisect
# import math
# import numpy as np
# from fractions import gcd

"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)

    def lcm(self, x, y):
        return (x * y) // self.gcd(x, y)


"""ここからメインコード"""


def main():
    # 1文字に省略
    r, e = range, enumerate
    ip = IP()
    id = Idea()

    """この下から書いてね"""
    n, m = ip.IL()
    a = ip.IL()
    y_count = m
    for _ in range(10 ** 5):
        a[a.index(max(a))] //= 2
        y_count -= 1
        if y_count == 0:
            break
    print(sum(a))


main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
# import collections

# import bisect
# import math
# import numpy as np
# from fractions import gcd

"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)

    def lcm(self, x, y):
        return (x * y) // self.gcd(x, y)


"""ここからメインコード"""


def main():
    # 1文字に省略
    r, e = range, enumerate
    ip = IP()
    id = Idea()

    """この下から書いてね"""
    n, m = ip.IL()
    a = ip.IL()
    y_count = m
    while y_count > 0:
        a[a.index(max(a))] //= 2
        y_count -= 1
    print(sum(a))


main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
# import collections

# import bisect
# import math
import numpy as np
# from fractions import gcd

"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)

    def lcm(self, x, y):
        return (x * y) // self.gcd(x, y)


"""ここからメインコード"""


def main():
    # 1文字に省略
    r, e = range, enumerate
    ip = IP()
    id = Idea()

    """この下から書いてね"""
    n, m = ip.IL()
    a = np.array(ip.IL())
    y_count = m
    while y_count > 0:
        memo = np.argmax(a)
        a[memo] //= 2
        y_count -= 1
    print(np.sum(a))


main()

Submission status: Accepted

Solution code:
def input_int():
    return(int(input()))

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

def input_int_map():
    return(map(int,input().split()))

import heapq

def run():
    n, ticket_count = input_int_map()

    nums = input_int_list()


    nums = list(map(lambda x: x * (-1), nums))  # 各要素を-1倍

    heapq.heapify(nums)



    for _ in range(ticket_count):
        num = (heapq.heappop(nums) * (-1))

        num = num // 2

        heapq.heappush(nums, num * (-1))

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

run()

# 2 4 3

# 3 4 3

# 2 6 3

Submission status: Accepted

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

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

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

Submission status: Accepted

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

for i in range (0, N):
	A[i] = -1*A[i]

A = sorted(A)

heapq.heapify(A)

import math

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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

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

for j in range(m):
  highest = heapq.heappop(a)
  heapq.heappush(a, -(-highest // 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 for a in A]
heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq


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

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

print(-sum(A))

Submission status: Accepted

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

Submission status: Accepted

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

abc141d()

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)  # aを優先度付きキューに

for _ in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))  # 負数の剰余演算を避けるため一時的に0以上の整数にしています
print(-sum(a))

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

def main():

    # Aをpriority qにつっこむ
    # 大きい順にM回discountする
    # 最後に総計を計算する

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

    while M > 0:
        a = -heappop(A)
        a //= 2
        heappush(A, -a)
        M -= 1
    
    ans = 0
    for a in A:
        ans -= a

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

def main():
    N, M = map(int, input().split())
    A = [-v for v in list(map(int, input().split()))]
    heapq.heapify(A)
    for _ in range(M):
        v = heapq.heappop(A)
        heapq.heappush(A, v / 2)
    print(sum([int(-v) for v in 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)*(-1), input().split()))
heapq.heapify(a)
for i in range(m):
  d=heapq.heappop(a)*(-1)
  heapq.heappush(a,(-1)*(d//2))
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 i in range(M):
    a = heapq.heappop(A)*(-1)
    if a ==0:#最大値が0になったら終了
        break
    a//=2
    heapq.heappush(A, -a)
print(-sum(A))

Submission status: Accepted

Solution code:
import heapq

# 優先度付きキューは「最も値が小さいもの」を出すことに注意

prio = []

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

for num in nums:
    heapq.heappush(prio, -num)

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

print(-sum(prio))

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=heapq.heappop(A)
    tmp=-tmp//2
    heapq.heappush(A,-tmp)

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

print(-sum(A))

Submission status: Accepted

Solution code:
from bisect import bisect_left as b
n,m= map(int,input().split())
a=list(map(int,input().split()))
a.sort()
while m>0:
  i=a.pop(-1)//2
  a.insert(b(a,i),i)
  m-=1
print(sum(a))

Submission status: Accepted

Solution code:
from bisect import bisect_left as bs
#ソート順序を保ったまま値を挿入する
N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

while M > 0:
  i = A.pop(-1) // 2
  A.insert(bs(A, i), i)
  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):
    tmp=heapq.heappop(A)
    tmp=-tmp//2
    heapq.heappush(A,-tmp)

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
ls = []
for item in A:
  heapq.heappush(ls, -item)
for m in range(M):
  tmp = -heapq.heappop(ls)
  tmp = tmp // 2
  heapq.heappush(ls, -tmp)
print(-sum(ls))

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
A = sorted(map(lambda x: -int(x), input().split()))
for _ in range(m):
    a = heapq.heappop(A)
    a = -(-a//2)
    heapq.heappush(A, a)

print(-sum(A))

Submission status: Accepted

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

Submission status: Accepted

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

A = deque(sorted(a,reverse=True))
B = deque([])

for _ in range(m):
    #if _ % (m//10) == 0: print(A, B)
    if A:
        if B:
            if (A[0] > B[0]):
                B.append(A.popleft()//2)
                continue
        else:
            B.append(A.popleft()//2)
            continue
    b = B.popleft()
    B.append(b//2)

print(sum(A)+sum(B))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Sep 16 17:42:18 2020

@author: liang
"""
"""
【優先度付きキュー】
・ヒープ構造の部分順序付き木
・挿入、削除、最大値（最小値）の取り出し、要素の値の変更
　⇒　O(log n)
・ヒープ生成
　⇒O(n)
 【使い方】
  import heapq
  ●heapq.heapify(list) #最小値
  ●heapq.heapify(list(map(lambda x:int(x)*(-1),list))) #最大値は値をひっくり返す
  ●heapq.heappop(a)
  ●heapq.heappush(a,1)
"""

import heapq
N, M = map(int, input().split())
# -1倍する
A = [int(x)*(-1) for x in input().split()]
heapq.heapify(A)

#O(M) * O(log N)
for i in range(M):
    Max = heapq.heappop(A) * (-1)
    Max //= 2
    heapq.heappush(A, Max*(-1))
print(-sum(A))

Submission status: Accepted

Solution code:
import heapq 

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

Submission status: Accepted

Solution code:
from heapq import *

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

heapify(a)

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


print(sum(a)*-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Sep 16 12:35:58 2020

@author: liang
"""

N, M = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort(reverse=True)
#print(A)
count = 0
while count != M:
    A[0] //= 2
    count += 1
    tmp = A[0]
    for i in range(1,N):
        if count == M:
            break
        if A[i] > tmp:
            A[i] //= 2
            count += 1
        ##   break
    A.sort(reverse=True)
ans = sum(A)
#print(A)
print(ans)

Submission status: Accepted

Solution code:
import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

from heapq import heapify, heappop, heappush
def Main():
    n, m = read_ints()
    a = read_int_list()
    a = [-x for x in a]
    heapify(a)
    
    while m:
        cost = heappop(a)
        if cost == 0:
            break
        heappush(a, -(-cost//2))
        m -= 1
    print(-sum(a))

if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
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):
    a = heapq.heappop(A)
    a *= -1
    a //= 2
    a *= -1    
    heapq.heappush(A,a)

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq
import sys

lines = sys.stdin.readlines()

N, M = [int(n) for n in lines[0].strip().split()]
prices = [-int(n) for n in lines[1].strip().split()]

heapq.heapify(prices)

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

print(-sum(prices))

Submission status: Accepted

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

Submission status: Accepted

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

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

result = -sum([int(p) for p in hq])
print(result)

Submission status: Accepted

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

for m in range(M):
  heappush(A,int(heappop(A)/2))

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq
import math

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

for i in range(m):
    high=heapq.heappop(a)
    heapq.heappush(a,-math.floor(-high/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()))

B = [-A[i] for i in range(N)]
heapq.heapify(B)
while M:
    p = heapq.heappop(B)
    p /= 2
    heapq.heappush(B, p)
    M -= 1

ans = 0
for i in range(N):
    ans += math.floor(-B[i])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import heapq

def main():
    line1 = input()
    line2 = input()

    n, m = list(map(int, line1.split()))
    l = list(map(int, line2.split()))
    ans = sum(l)
    for i in range(len(l)):
        l[i] *= -1
    heapq.heapify(l)
    for i in range(m):
        price = heapq.heappop(l) * (-1)
        new_price = price // 2
        heapq.heappush(l, new_price * (-1))
        ans -= (price - new_price)
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
import heapq
a = list(map(lambda x: x*(-1), A))  # 各要素を-1倍

heapq.heapify(a)
for i in range(K):
  num = heapq.heappop(a)*(-1)
  heapq.heappush(a, -1*(int(num/2)))
  #print(num,a)
  if num == 0:
    break
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)

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

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]*=-1
heapq.heapify(A)
for i in range(M):
  n=heapq.heappop(A)
  heapq.heappush(A,-((-n)//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:
    a_max = heapq.heappop(a)
    if a_max == 0:
        break
    heapq.heappush(a, (-1)*(-a_max // 2))
    m -= 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=[-i for i in a]
heapq.heapify(a)
for _ in range(m):
     b=heapq.heappop(a)
     heapq.heappush(a,-((-b)//2))

print(-sum(a))

Submission status: Accepted

Solution code:
from heapq import heapify,heappush,heappop

def main():
    N,M = map(int,input().split())
    A = [-x for x in map(int,input().split())]
    heapify(A)
    for i in range(M):
        tmp = -heappop(A)
        tmp2 = tmp//2
        heappush(A,-tmp2)
    ans = 0
    for i in range(N):
        ans += A[i]

    ans = abs(ans)
    return ans

print(main())

Submission status: Accepted

Solution code:
import heapq

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

T = list(map(int,input().split()))

memo = []
for t in T:
    memo.append(-t)
memo.sort()

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

Submission status: Accepted

Solution code:
import copy

def bi_search(money,M,N):
    money.sort()
    #list = []
    #for i in range(0,money[N-1]+2,1):
        #list.append(i)
    left = 0
    right = money[N-1]+1
    mid = 0
    #print(list,left,right)
    while True:
        mid = int( (left+right)/2 )
        cnt = 0
        #print(left,right,mid)
        #print(money)
        money_tmp = copy.copy(money)
        for i in range(N):
            while True:
                #print(money_tmp[i],i)
                if money_tmp[i] <= mid:
                    break
                else:
                    money_tmp[i] //= 2
                    cnt += 1
        #print(cnt)
        if cnt == M:
            return mid,cnt
        elif cnt < M:
            right = mid
            tmp = cnt
        elif cnt > M:
            left = mid + 1

        if left == right:
            return right,tmp

def main():
    N,M = map(int,input().split())
    A = list(map(int,input().split()))
    max_money,cnt = bi_search(A,M,N)
    #print (cnt)
    cnt = M-cnt
    ans = 0
    for i in range(N):
        if max_money >= A[i]:
            continue
            #ans += A[i]
        else:
            while True:
                A[i] //= 2
                if max_money >= A[i]:
                    #ans += A[i]
                    break
    A.sort(reverse = True)
    j = 0
    if A[j] == 0:
        return 0
    for i in range(cnt):
        A[j] //= 2
        j += 1

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

    return ans

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

Submission status: Accepted

Solution code:
from heapq import *

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

for _ in range(m):
    max_a = heappop(A)*(-1)
    max_a //= 2
    heappush(A, -max_a)
print(-sum(A))