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: Runtime Error

Solution code:
co = list(map(int,input().split()))
A = list(map(int,input().split()))
N = co[0]
M = co[1]
A.sort()
A.reverse()
for i in range(M):
    
    tmp =A.pop(0) // 2
    j = N-2
    while A[j] < tmp:
        j -=1
    A.insert(j-1,tmp)
print(sum(A))

Submission status: Runtime Error

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

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

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

# ----- heapq ここから-----
import heapq
class Reverse:
    def __init__(self, val):
        self.val = val
        
    def __lt__(self, other):
        return self.val > other.val
        
    def __repr__(self):
        return repr(self.val)
    
class Heapq:
    def __init__(self, arr, desc = False):
        if desc:
            for i in range(len(arr)):
                arr[i] = Reverse(arr[i])
        self.desc = desc
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        if self.desc: return heapq.heappop(self.hq).val
        else: return heapq.heappop(self.hq)
 
    def push(self, a):
        if self.desc: heapq.heappush(self.hq, Reverse(a))
        else: heapq.heappush(self.hq, a)
 
    def top(self):
        if self.desc: self.hq[0].val
        else: return self.hq[0]
# ----- heapq ここまで-----

n,m = myinput()
a = list(myinput())

hq = Heapq(a,desc=True)

for i in range(m):
    M = hq.pop()
    hq.push(M//2)

ans = 0
for i in range(m):
    ans += hq.pop()
    
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
sa=sum(a)//n
c=0
if n==1:
    print(a[0]//(2**m))
    exit()
else:
    while True:
        a.sort()
        a1=a[:n//2]
        a2=a[n//2:]
        print(a1,a2)
        while True:
            if c==m:
                print(sum(a1)+sum(a2))
                exit()
            if len(a2)==0:
                a=a1
                break
            k=a2.pop(-1)
            while True:
                k=k//2
                c+=1
                if k<=sa:
                    a1.append(k)
                    print(a1,a2)
                    break

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
sa=sum(a)//n
c=0
if n==1:
    print(a[0]//(2**m))
    exit()
else:
    while True:
    a.sort()
    a1=a[:n//2]
    a2=a[n//2:]
    print(a1,a2)
    while True:
        if c==m:
            print(sum(a1)+sum(a2))
            exit()
        if len(a2)==0:
            a=a1
            break
        k=a2.pop(-1)
        while True:
            k=k//2
            c+=1
            if k<=sa:
                a1.append(k)
                print(a1,a2)
                break

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
c=0
while True:
    a.sort()
    a1=a[:n//2]
    a2=a[n//2:]
    while True:
        if c==m:
            print(sum(a1)+sum(a2))
            exit()
        if len(a2)==0:
            a=a1
            break
        k=a2.pop(-1)
        while True:
            k=k//2
            c+=1
            if k<=a1[-1]:
                a1.append(k)
                break

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy

def solution():
    n, m = map(int, input().split())
    a = [int(aa) for aa in input().split()]
    a.sort(reverse=True)
    for i in range(m):
        a[0] = a[0] // 2
        numpy.np.sort(a)[::-1]
    print(sum(a))

solution()

Submission status: Runtime Error

Solution code:
import numpy as np

# 初期入力
N,M = (int(x) for x in input().split())
A = np.array( list(map(int, input().split())) )

#
a_waribiki = np.zeros((N,M+1),dtype=np.int64)
a_waribiki[:,0] =A # 割引しない場合を代入

# 各商品を１からM回割引券使った場合の金額
for i in range(1,M+1): 
    a_waribiki[:,i] =a_waribiki[:,i-1] //2

# 各商品に何枚割引券使うか
from itertools import combinations
n_waribiki = [i for i in range(M+N-1)]
x_list_2 =[]
if N-1 ==0:
    x_list_2.append([M])
else:
    for t in combinations(n_waribiki, N-1):
        t_list = list(t)
        t_list.append(M+N-1)
        x_list=[]
        for i in range(1,len(t_list)):
            x= t_list[i] -t_list[i-1]-1
            x_list.append(x)
        x_list.append(t[0])
        x_list_2.append(x_list)
        #print(t_list)
        #print(t,end=" ")

#[割引券を何枚使うか」を利用し、金額計算
x_np = np.array(x_list_2)
kotae = []
for i in x_np:
    a_sum =0
    for j,v in enumerate(i):
        a_sum += a_waribiki[j,v]
    kotae.append(a_sum)
print(min(kotae))

Submission status: Runtime Error

Solution code:
import numpy as np

# 初期入力
N,M = (int(x) for x in input().split())
A = np.array( list(map(int, input().split())) )

#
a_waribiki = np.zeros((N,M+1),dtype=np.int64)
a_waribiki[:,0] =A # 割引しない場合を代入

# 各商品を１からM回割引券使った場合の金額
for i in range(1,M+1): 
    a_waribiki[:,i] =a_waribiki[:,i-1] //2

# 各商品に何枚割引券使うか
from itertools import combinations
n_waribiki = [i for i in range(M+N-1)]
x_list_2 =[]
for t in combinations(n_waribiki, N-1):
    t_list = list(t)
    t_list.append(M+N-1)
    x_list=[]
    for i in range(1,len(t_list)):
        x= t_list[i] -t_list[i-1]-1
        x_list.append(x)
    x_list.append(t[0])
    x_list_2.append(x_list)
    #print(t_list)
    #print(t,end=" ")

#[割引券を何枚使うか」を利用し、金額計算
x_np = np.array(x_list_2)
kotae = []
for i in x_np:
    a_sum =0
    for j,v in enumerate(i):
        a_sum += a_waribiki[j,v]
    kotae.append(a_sum)
print(min(kotae))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a_li = list(map(int,input().split()))
a_li.sort()
import bisect
import math
for _ in range(m):
    tmp = a_li.pop(-1)
    tmp = math.floor(tmp/2)
    if a_li != []:
        a_li.insert(bisect.bisect_left(a_li, tmp, 0, n), tmp)
    else:
        a_li.append(tmp)
        
print(sum(a_li))

Submission status: Runtime Error

Solution code:
import heapq
def main():
    n,m=map(int, input().split()) 
    a = [map(lambda x: int(x)*(-1), input().split())] 
    heapq.heapify(a)

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
N,M=map(int,input().split())
S=input().split()
Snum=[]
for i in range(0,N):
  Snum.append(int(S[i]))
Snum.sort()
Snum.reverse()
for i in range(0,M):
  j=1
  k=math.floor(Snum[0]/2)
  while k<Snum[j] and j<N-1:
    j=j+1
  for l in range(0,j-1):
    Snum[l]=Snum[l+1]
  Snum[j-1]=k
print(sum(Snum))

Submission status: Runtime Error

Solution code:
from collections import deque
import bisect
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = deque(sorted(a))
cnt = 0
while cnt < m:
    x = a.pop()
    x = x // 2
    cnt += 1
    if len(a) == 0 or x > a[-1]:
        a.append(x)
    else:
        bisect.insort_left(a, x)
print(sum(a))

Submission status: Runtime Error

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

mvals = list(np.array(As) * (-1))
import heapq
heapq.heapify(mvals)

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

res = (np.array(mvals) * (-1)).astype(int).sum()
print(res)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <queue>

using namespace std;

int main()
{
  int n, m; cin >> n >> m;
  
  priority_queue<int> pq;
  while (n--) {
    int a; cin >> a;
    pq.push(a);
  }
  
  while (m--) {
    pq.push(pq.top()/2);
    pq.pop();
  }
  
  long long ans = 0;
  while (pq.size()) {
    ans += pq.top();
    pq.pop();
  }
  
  cout << ans << endl;
  return 0;
}

Submission status: Runtime Error

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

input = sys.stdin.readline

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

BC = [tuple(map(int, input().split())) for _ in range(m)]

for b, c in BC:
    for _ in range(b):
        A.append(c)

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

answer = 0
for _ in range(n):
    answer += heappop(A)

print(-answer)

Submission status: Runtime Error

Solution code:
from heapq import (
    heapify,  # 優先度付きキューの生成
    heappop,
    heappush,
    heappushpop,
    heapreplace
    )

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

#heapqは最小値しか取り出さないので-1倍する
A = heapify([-i for i in map(int,input().split())])

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

print(-sum(A))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)

for _ in range(M):
    A[0] = int(A[0]/2)
    if A[0]<A[1]:
        A = sorted(A, reverse=True)

print(sum(A))

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    while 1:
        a[-1] = a[-1] / 2
        m -= 1
        if m==0:
            res = 0
            for j in a:
                res += int(i)
            print(res)
            exit()
        p = bisect_right(a, a[-1])
        for i in range(p, n-1):
            a[i] = a[i] / 2
            m -= 1
            if m==0:
                res = 0
                for j in a:
                    res += int(i)
                print(res)
                exit()
        a.sort()



if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import heapq

n,m = map(int,input().split())
li = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(li)
for _ in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))  # 計算誤差の関係で-1を2回かけてます
print(-sum(a))

Submission status: Runtime Error

Solution code:
# https://juppy.hatenablog.com/entry/2019/04/05/%E8%9F%BB%E6%9C%AC_Python_%E3%83%97%E3%83%A9%E3%82%A4%E3%82%AA%E3%83%AA%E3%83%86%E3%82%A3%E3%82%AD%E3%83%A5%E3%83%BC_2_heapq_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3
import heapq

n,m,*a = map(int, open(0).read().split())

# a = [1,7,3,5,4]

# #heapify
# #配列a = [1,7,3,5,4]をheapにする
hq = heapq._heapify_max(a)
# print(a) #[7, 5, 3, 1, 4]

# #heappop
# #最大値の取り出し
# print(_heappop_max(a)) #7
# print(a) #[5, 4, 3, 1]

# #heappush
# #要素(2)の挿入
# _heappush_max(a,2)
# print(a) #[5, 4, 3, 1, 2]

# #最大値の取り出し
# print(_heappop_max(a)) #5
s = sum(a)
d = 0
for i in range(m):
  t = heapq._heappop_max(a)
  d += t-t//2
  heapq._heapreplace_max(a, t//2)
  # print(a)

print(s-d)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import heapq

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

Submission status: Runtime Error

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

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

print(-sum(a))

Submission status: Runtime Error

Solution code:
import bisect
n,m=map(int,input().split())
a=list(map(int, input().split()))
if len(a)==1:
  print(int(a[0]/(2**m)))
  exit(0)
a=sorted(a)
while 0<m:
  x=a.pop(-1)
  y=x//a[-1]
  if y>m:
    y=m
  x=int(x/(2**y))
  bisect.insort_right(a, x)
  m-=y
print(sum(a))

Submission status: Runtime Error

Solution code:
from fractions import gcd
from math import ceil,sqrt
a, b = map(int, input().split())

g = gcd(a,b)

s = set()
for i in range(2,ceil(sqrt(g))+1):
    while g % i == 0:
        g //= i
        s.add(i)
if g != 1:
s.add(int(1e14))
#print(g)
#print(s)
print(len(s)+1)

Submission status: Runtime Error

Solution code:
import heapq

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

heapq.heapify(b)

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

print(-sum(b))

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = map(int,input().split())
L = list(map(int,input().split()))
a = np.array(L)
y_count = m
while y_count > 0:
    memo = np.argmax(a)
    a[memo] //= 2
    y_count -= 1
print(np.sum(a))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())#nは品物の数　mは割引券の数
a = sorted(list(map(int,input().split())),reverse = True)#値段一覧
for i in range(m):
    if a[0] >= a[1]:
        a[0] = a[0]//2
        a.sort(reverse = True)
print(sum(a))

Submission status: Runtime Error

Solution code:
import math

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

a = sorted(a, reverse=True)

for i in range(m):
    a[0] = math.floor(a[0] / 2)
    if a[0] < a[1]:
        a = sorted(a, reverse=True)

print(sum(a))

Submission status: Runtime Error

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


import sys
read = sys.stdin.readline


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


from bisect import bisect_left, bisect_right, insort_left
from collections import deque


class BinarySearchTree:
    def __init__(self, ls: list = []):
        '''
        C++でいうsetを実装する。二分探索木をガチで実装しようとすると大変なので、ここでは配列二分法を用いる。
        pythonの標準ライブラリがヨイショに抱っこしてくれるおかげで楽に実装できる。
        https://docs.python.org/ja/3/library/bisect.html


        ls ... 渡す初期配列
        '''
        self.bst = deque(sorted(ls))  # insertをO(1)にするためにlistの代わりにdequeを用います

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

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        insort_left(self.bst, x)

    def pop_right(self):
        x = self.bst[-1]
        del self.bst[-1]
        return x

    def pop_left(self):
        x = self.bst[0]
        del self.bst[0]
        return x

    def remove(self, x):
        '''
        xを取り除く。xがself.bstに存在することを保証してください。
        同一のものが存在した場合は左から消していく
        '''
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        '''
        ソートされた順序を保ったまま x を self.bst に挿入できる点を探し当てます。
        lower_bound in C++
        '''
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        '''
        bisect_left() と似ていますが、 self.bst に含まれる x のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。
        upper_bound in C++
        '''
        return bisect_right(self.bst, x)

    def find(self, x):
        '''
        xのidxを探索
        '''
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

    def insert_replace_left(self, x):
        '''
        xを挿入して、xの左の数字(次に小さい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) - 1
        if idx_del + 1 == 0:  # xがどの要素よりも小さい
            self.insert(x)
        if idx_del < len(self.bst):
            self.insert(x)
            del self.bst[idx_del]

    def insert_replace_right(self, x):
        '''
        xを挿入して、xの右の数字(次に大きい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_right(x) + 1  # xと同じ大きさも削除したいならbisect_left
        if idx_del - 1 == len(self.bst):  # xがどの要素よりも大きい
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


N, M = read_ints()
A = read_ints()
A.sort()
bst = BinarySearchTree(A)
for _ in range(M):
    x = bst.pop_right()
    x //= 2
    bst.insert(x)

print(sum(bst.bst))

Submission status: Runtime Error

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


import sys
read = sys.stdin.readline


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


from bisect import bisect_left, bisect_right, insort_left
from collections import deque


class BinarySearchTree:
    def __init__(self, ls: list = []):
        '''
        C++でいうsetを実装する。二分探索木をガチで実装しようとすると大変なので、ここでは配列二分法を用いる。
        pythonの標準ライブラリがヨイショに抱っこしてくれるおかげで楽に実装できる。
        https://docs.python.org/ja/3/library/bisect.html


        ls ... 渡す初期配列
        '''
        self.bst = deque(sorted(ls))  # insertをO(1)にするためにlistの代わりにdequeを用います

    def __repr__(self):
        return f'BST:{self.bst}'

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

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        insort_left(self.bst, x)

    def pop_right(self):
        x = self.bst[-1]
        del self.bst[-1]
        return x

    def pop_left(self):
        x = self.bst[0]
        del self.bst[0]
        return x

    def remove(self, x):
        '''
        xを取り除く。xがself.bstに存在することを保証してください。
        同一のものが存在した場合は左から消していく
        '''
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        '''
        ソートされた順序を保ったまま x を self.bst に挿入できる点を探し当てます。
        lower_bound in C++
        '''
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        '''
        bisect_left() と似ていますが、 self.bst に含まれる x のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。
        upper_bound in C++
        '''
        return bisect_right(self.bst, x)

    def find(self, x):
        '''
        xのidxを探索
        '''
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

    def insert_replace_left(self, x):
        '''
        xを挿入して、xの左の数字(次に小さい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) - 1
        if idx_del + 1 == 0:  # xがどの要素よりも小さい
            self.insert(x)
        if idx_del < len(self.bst):
            self.insert(x)
            del self.bst[idx_del]

    def insert_replace_right(self, x):
        '''
        xを挿入して、xの右の数字(次に大きい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_right(x) + 1  # xと同じ大きさも削除したいならbisect_left
        if idx_del - 1 == len(self.bst):  # xがどの要素よりも大きい
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


N, M = read_ints()
A = read_ints()
A.sort()
bst = BinarySearchTree(A)
for _ in range(M):
    x = bst.pop_right()
    x //= 2
    bst.insert(x)

print(sum(bst.bst))

Submission status: Runtime Error

Solution code:


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

S = input().split(" ")

arr =  [int(s) for s in S]
arr2 = arr.copy()
brr =  [0 for s in S]

def calculate(m,arr,brr):


    for i in range(m):
        maxValue = max(arr)
        maxIndex = arr.index(maxValue)
        arr[maxIndex] = arr[maxIndex]//2
        brr[maxIndex] = brr[maxIndex] + 1

    return brr

result = calculate(M,arr,brr)


for index,br in enumerate(brr):
    arr2[index] = arr2[index]//(2**br)

print(sum(arr2))

Submission status: Runtime Error

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

import math
import numpy as np

dp = np.zeros([N+1, M+1])
for i in range(0, N):
    for j in range(0, M+1):
        dp[i+1][j] = min(dp[i][j]+A[i], dp[i][0]+math.floor(A[i]/2**j))
        
print(int(dp[-1][-1]))

Submission status: Runtime Error

Solution code:
import scipy.misc

N=int(input())
X=list(map(int,input().split()))
SX=sorted(X)
M=SX.pop()
MV=10**9
ANS=0
for x in SX:
  z = M - x
  if MV > z:
    MV = z
    ANS = x
print("{} {}".format(M,ANS))

Submission status: Runtime Error

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(x, a)
print(-sum(a))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
i = 0
for _ in range(M):
    A[i] //= 2
    if A[i-1] < A[i+1]:
        i += 1
        continue
    elif A[i-1] > A[i+1]:
        i -= 1
        continue
    else:
        pass
print(sum(A))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
i = 1
A[0] //= 2
for _ in range(M):
    if A[i-1] < A[i+1]:
        A[i] //= 2
        i += 1
    elif A[i-1] > A[i+1]:
        A[i] //= 2
        i -= 1
    else:
        A[i] //= 2
print(sum(A))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
i = 0

for i in range(M):
    A[i] //= 2
    if A[i-1] < A[i+1]:
        i += 1
    elif A[i-1] > A[i+1]:
        i -= 1
    else:
        pass
print(sum(A))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import heapq

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

heapq.heapify(a)

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

Submission status: Runtime Error

Solution code:
import heapq

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

heapq.heapify(a)

for i in range(m)
    tmp_min = heap.heappop(a)
    heapq.heappush(a,tmp_min//2)
print(-sum(a))

Submission status: Runtime Error

Solution code:
import heapq

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

heapq.heapify(a)

for i in range(m)
    tmp_min = heap.heappop(a9
    heapq.heappush(a,tmp_min//2)
print(-sum(a))

Submission status: Runtime Error

Solution code:
import heapq

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

heapq.heapify(List)

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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
 
int main(){
  ll n, m, sum=0;
  cin >> n >> m;
  vector<ll> lst(n);
  for(int i=0; i<n; i++) cin >> lst[i];
  for(int i=0; i<m; i++){
    for(int j=0; j<n; j++){
      if(lst[j]==*max_element(lst.begin(), lst.end()))
        lst[j] /= 2;
      	break;
    }
  }
  for(int i; i<n; i++)sum+=lst[i];
  cout << sum << endl;
}

Submission status: Runtime Error

Solution code:
import heapq as hq

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

items = [-1*map(int, input().split()] 

hq.heapify(items)
             
for i in range(m):
	pop = hq.heapqpop(items)
    hq.heapqpush(items, pop//2)
              
return -1*sum(hq)

Submission status: Runtime Error

Solution code:
import heapq

K = input()
a = LI()

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

heapq.heapify(a)

for i in range(
print(heapq.heappop(a)*(-1))  # 最大値の取り出し
print(a)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse = True)
while M > 0:
    A[0] //= 2
    for i in range(1,M):
        if A[i] >= A[0]:
            A[i] //= 2
        else:
            M -= i
            A.sort(reverse = True)
            break
    else:
        break
print(sum(A))

Submission status: Runtime Error

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):
#Hは全部マイナスをつけたからaは最大値的なのはいる
    heapq.heapreplace((A, int(A[0]/2))
print(-sum(A))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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(m):
    heapq.heapify(a)
    b=heapq.heappop(a)
    b=b/2
    heapq.heappush(a,b)
ans=0
for i in c:
    ans-=int(i)
print(ans)

Submission status: Runtime Error

Solution code:
I=list(map(int,open(0).read().split()))
n,m=I[:2]
a=I[2:]
for i in range(m):
    a.sort()
    a[m-1]=a[m-1]//2
print(int(sum(a)))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split()
li = list(map(int, input().split()))
while  M > 0:
	li[li.index(max(li))] /= 2
	M -= 1
ans = 0
for i in range(len(li)):
	ans += int(li[i])
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split()
li = list(map(int, input()split()))
while  M > 0:
	li[li.index(max(li))] /= 2
	M -= 1
ans = 0
for i in range(len(li)):
	ans += int(li[i])
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n,m = map(int,input().split()) 
value_lis = list(map(int,input().split()))

value_lis.sort(reverse=True)

for i in range(m):
    value_lis[0] =int(value_lis[0] / 2)
    if value_lis[0] < value_lis[1]:
        value_lis.sort(reverse=True)

print(sum(value_lis))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
L=list(map(int,input().split()))
L.sort()
from collections import deque
Ld=deque(L)
A=[0]
Ad=deque(A)
for i in range(m):
    if Ld==deque([]):
        if Ad==deque([]):
            break
        else:
            if Ad[-1]!=0:
                x=Ad.pop()//2
                if x>=Ad[-1]:
                    Ad.append(x)
                else:
                    Ad.insert(0,x)
            else:
                break
    else:
        if Ld[-1] >=Ad[-1]:
            x=Ld.pop()//2
            if x>=Ad[-1]:
                Ad.append(x)
            else:
                Ad.insert(0,x)
        else:
            x=Ad.pop()//2
            if x>=Ad[-1]:
                Ad.append(x)
            else:
                Ad.insert(0,x)
print(sum(list(Ld))+sum(list(Ad)))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
L=list(map(int,input().split()))
L.sort()
from collections import deque
Ld=deque(L)
A=[0]
Ad=deque(A)
for i in range(m):
    if L[-1] >=A[-1]:
        x=L.pop()//2
        if x>=A[-1]:
            A.append(x)
        else:
            A.insert(0,x)
    else:
        x=A.pop()//2
        if x>=A[-1]:
            A.append(x)
        else:
            A.insert(0,x)
print(sum(L)+sum(A))

Submission status: Runtime Error

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

heapq.heapify(A)

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

print(-sum(A))

Submission status: Runtime Error

Solution code:
def main():
    n, m = map(int, input().split())
    a_list = list(map(int, input().split()))
    sorted_a_list = sorted(a_list, reverse=True)

    for _ in range(m):
        sorted_a_list[0] = int(sorted_a_list[0]/2)
        if sorted_a_list[0] < sorted_a_list[1]:
            sorted_a_list = sorted(sorted_a_list, reverse=True)

    print(sum(sorted_a_list))


if __name__ == '__main__':
    main()