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:
import sys
from math import log

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

a = sorted(a, reverse=True)
flag = True

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

for i in range(n-1):
  if a[i] > a[i+1] * (10*3):
    s = int(log(a/b, 2))
    m -= s
    a[i] //= 2**s


while flag == True:
  index = 0
  if a[0]/2 < a[n-1]:
    index = n
  else:
    for i in range(1, n):
      if a[0]/2 > a[i]:
        index = i
        break
  if index < m:
    for i in range(index):
      a[i] //= 2
    a = sorted(a, reverse=True)
    m -= index
  else:
    for i in range(m):
      a[i] //= 2
    flag = False

print(sum(a))

Submission status: Runtime Error

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


for i in range(m):
  a[0] //= 2
  if a[0] < a[1]:
    for j in range(n-1):
      a[j: j+2] = [a[j+1], a[j]]
      if j < n-2 and a[j+1] > a[j+2]:
        break

print(sum(a))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
for i in range(0,M):
    A[A.index(max)]=int(A[A.index(max)])

print(sum(A))

Submission status: Runtime Error

Solution code:
def bin_tree( pri , li_pri , len_li ):
    #pri: どこに入れていいかわからない値段
    #li_pri: 値段のリスト(昇順)
    #len_li: リストの長さ
    lo = 0
    hi = len_li - 1
    while hi - lo > 1:
        mid = lo + (hi - lo) // 2
        guess = li_pri[mid]
        if guess >= pri:
            hi = mid
        else:
            lo = mid
    return lo

I = input().split()
N = int(I[0])
M = int(I[1])
# N: 品物の数
# M: 割引券の数
# A: 品物の値段行列
A = list(map(int , input().split()))
A.sort()

while M > 0:
    M -= 1
    pri = A.pop( N - 1 )
    pri = pri // 2
    if (pri < A[0]):
        ans = 0
    else:
        ans = bin_tree( pri , A , N - 1 ) + 1
    # ans: pri以上となる値段のうち最小のインデックス
    A[ans:ans] = [pri]    

F_pri = 0
for i in range(N):
    F_pri += A[i]
print(F_pri)

Submission status: Runtime Error

Solution code:
def bin_tree( pri , li_pri , len_li ):
    #pri: どこに入れていいかわからない値段
    #li_pri: 値段のリスト(昇順)
    #len_li: リストの長さ
    lo = 0
    hi = len_li - 1
    while hi - lo > 1:
        mid = lo + (hi - lo) // 2
        guess = li_pri[mid]
        if guess >= pri:
            hi = mid
        else:
            lo = mid
    return lo

I = input().split()
N = int(I[0])
M = int(I[1])
# N: 品物の数
# M: 割引券の数
# A: 品物の値段行列
A = list(map(int , input().split()))
A.sort()

print(A)

while M > 0:
    M -= 1
    pri = A.pop( N - 1 )
    pri = pri // 2

    ans = bin_tree( pri , A , N - 1 ) + 1
    # ans: pri以上となる値段のうち最小のインデックス
    A[ans:ans] = [pri]

    print(A)
    

F_pri = 0
for i in range(N):
    F_pri += A[i]
print(F_pri)

Submission status: Runtime Error

Solution code:
def bin_tree( pri , li_pri , len_li ):
    #pri: どこに入れていいかわからない値段
    #li_pri: 値段のリスト(昇順)
    #len_li: リストの長さ
    lo = 0
    hi = len_li - 1
    while hi - lo > 1:
        mid = lo + (hi - lo) // 2
        guess = li_pri[mid]
        if guess >= pri:
            hi = mid
        else:
            lo = mid
    return lo

I = input().split()
N = int(I[0])
M = int(I[1])
# N: 品物の数
# M: 割引券の数
# A: 品物の値段行列
A = list(map(int , input().split()))
A.sort()

print(A)

while M > 0:
    M -= 1
    pri = A.pop( N - 1 )
    pri = pri // 2

    ans = bin_tree( pri , A , N - 1 )
    A[ans:ans] = [pri]

    print(A)
    

F_pri = 0
for i in range(N):
    F_pri += A[i]
print(F_pri)

Submission status: Runtime Error

Solution code:
def bin_tree( pri , li_pri , len_li ):
    #pri: どこに入れていいかわからない値段
    #li_pri: 値段のリスト(昇順)
    #len_li: リストの長さ
    lo = 0
    hi = len_li - 1
    while hi - lo > 1:
        mid = lo + (hi - lo) // 2
        guess = li_pri[mid]
        if guess >= pri:
            hi = mid
        else:
            lo = mid
    return lo

I = input().split()
N = int(I[0])
M = int(I[1])
# N: 品物の数
# M: 割引券の数
# A: 品物の値段行列
A = list(map(int , input().split()))
A.sort()

print(A)

while M > 0:
    M -= 1
    pri = A.pop( N - 1 )
    pri = pri // 2
    if ( pri < A[0] ):
        ans = 0
    else:
        ans = bin_tree( pri , A , N - 1 )
    A[ans:ans] = [pri]

    print(A)
    

F_pri = 0
for i in range(N):
    F_pri += A[i]
print(F_pri)

Submission status: Runtime Error

Solution code:
def bin_tree( pri , li_pri , len_li ):
    #pri: どこに入れていいかわからない値段
    #li_pri: 値段のリスト(昇順)
    #len_li: リストの長さ
    lo = 0
    hi = len_li - 1
    while hi - lo > 1:
        mid = (lo + hi) // 2
        guess = li_pri[mid]
        if guess == pri:
            hi = mid
        if guess > pri:
            hi = mid
        else:
            lo = mid
    return lo

I = input().split()
N = int(I[0])
M = int(I[1])
# N: 品物の数
# M: 割引券の数
# A: 品物の値段行列
A = list(map(int , input().split()))
A.sort()

print(A)

while M > 0:
    M -= 1
    pri = A.pop( N - 1 )
    pri = pri // 2
    if ( pri < A[0] ):
        ans = 0
    else :
        ans = bin_tree( pri , A , N - 1 ) + 1
    A[ans:ans] = [pri]

    print(A)
    

F_pri = 0
for i in range(N):
    F_pri += A[i]
print(F_pri)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

for i in range(M):
    if A[0]<A[1]:
        A = sorted(A,reverse=True)
    A[0] = A[0]//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)
for i in range(m):
  a[0]=a[0]/2
  for j in range(1,n):
    if a[0]>a[j]:
      a.insert(j,a[0])
      del a[0]
      break
  print(a)
import math
ans=0
for i in range(n):
  ans=ans+math.floor(a[i])
print(ans)

Submission status: Runtime Error

Solution code:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var NM = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        var (N, M) = (NM[0], NM[1]);
        var A = ReadLine().Split(' ').Select(s => int.Parse(s)).OrderByDescending(x => x).ToArray();

        var priorityQueue = new PriorityQueue<int>();

        foreach (var a in A)
            priorityQueue.Push(a);

        for (int i = 0; i < M; i++)
        {
          int nip = priorityQueue.Pop()/2;
          priorityQueue.Push(nip);
          
        }

        var ans = priorityQueue.Sum(x => (long)x);

        WriteLine(ans);

    }
}
public class PriorityQueue<T> : IEnumerable<T>
    where T : IComparable<T>
{
    private List<T> buffer;
    public int Count { get => buffer.Count; }
    public bool IsDescending { get; }
    private int Compare(T a, T b) => IsDescending ? a.CompareTo(b) : b.CompareTo(a);

    public PriorityQueue(bool isDescending = true)
    {
        buffer = new List<T>();
        IsDescending = isDescending;
    }

    public void Push(T item)
    {
        buffer.Add(item);

        var root = 0;
        var child = buffer.Count - 1;

        while (root < child)
        {
            var parent = (child - 1) / 2;

            if (Compare(buffer[parent], buffer[child]) < 0)
                (buffer[parent], buffer[child]) = (buffer[child], buffer[parent]);

            child = parent;
        }
    }

    public T Pop()
    {
        var item = buffer[0];
        buffer[0] = buffer[^1];
        buffer.RemoveAt(buffer.Count - 1);

        var root = 0;
        var parent = root;
        var child = 1;

        while(child < buffer.Count)
        {
            if (child < buffer.Count - 1)
            {
                var leftChild = child;
                var rightChild = child + 1;

                if (Compare(buffer[leftChild], buffer[rightChild]) < 0)
                    child = rightChild;
            }

            if (Compare(buffer[parent], buffer[child]) < 0)
                (buffer[parent], buffer[child]) = (buffer[child], buffer[parent]);

            parent = child;
            child = 2 * parent + 1;
        }

        return item;
    }

    public IEnumerator<T> GetEnumerator()
    {
        return buffer.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}

Submission status: Runtime Error

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

while M:
    A[-1]//=2
    M-=1
    i=-2
    while M and (-N<=i and A[i]>=A[-1]):
        A[i]//=2
        M-=1
        print(A)
        i-=1
    A.sort()

print(sum(A))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
*A,=map(int,input().split())
A=sorted(A)[::-1]
count=0
now=0
while M:
    i=0
    while i<=now and M:
        if count<N-1:
            while A[i]<A[count+1]:
                A[count+1]//=2
                count+=1
                M-=1
                if M==0:
                    break
        if M==0:
            break
        A[i]//=2
        i+=1
        M-=1
    now=count
        
print(sum(A))

Submission status: Runtime Error

Solution code:
import heapq

def cin():
    in_ = list(map(int,input().split()))
    if len(in_) == 1:  return in_[0]
    else:  return in_

N, M = cin()
A = cin()
x = []
for i in range(N):
    heapq.heappush(x, -A[i])
for i in range(M):
    p = -heapq.heappop(x)
    heapq.heappush(x, -(p // 2))
ans = -sum(x)
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
N, M = cin()
A = cin()
x = []
for i in range(N):
    heapq.heappush(x, -A[i])
for i in range(M):
    p = -heapq.heappop(x)
    heapq.heappush(x, -(p // 2))
ans = -sum(x)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
A_list = sorted(list(map(int, input().split())))
A_ar = np.array(A_list)[::-1]
for i in range(M):
    A_ar[0] = A_ar[0]//2
    if A_ar[0] < A_ar[1]:
        A_ar = np.sort(A_ar)[::-1]
print(sum(A_ar))

Submission status: Runtime Error

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

if n > 1:
    while ticket_num > 0:
        first = a_sorted[0]
        second = a_sorted[1]
        fi_bin = bin(first)
        se_bin = bin(second)
        sa = len(fi_bin)-len(se_bin)
        if sa == 0:
            sa = 1
        first = first >> sa
        ticket_num -= sa
        if first == second:
            first = first >> 1
            ticket_num -= 1
        index = 1
        while index < n or a_sorted[index] > first:
            index += 1
        a_sorted[:index-1] = a_sorted[1:index]
        a_sorted[index-1] = first
else:
    a_sorted[0] = a_sorted[0]>>m

print(sum(a_sorted))

Submission status: Runtime Error

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

if n > 1:
    while ticket_num > 0:
        first = a_sorted[0]
        second = a_sorted[1]
        fi_bin = bin(first)
        se_bin = bin(second)
        sa = len(fi_bin)-len(se_bin)
        if sa == 0:
            sa = 1
        first = first >> sa
        ticket_num -= sa
        if first == second:
            first = first >> 1
            ticket_num -= 1
        index = 1
        while a_sorted[index] > first:
            index += 1
        a_sorted[:index-1] = a_sorted[1:index]
        a_sorted[index-1] = first
else:
    a_sorted[0] = a_sorted[0]>>m

print(sum(a_sorted))

Submission status: Runtime Error

Solution code:
import math
import heapq

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

Submission status: Runtime Error

Solution code:
from math import log

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

B = [log(A[i]) for i in range(N)]
sumB=sum(B)
C = [B[i]/sumB*M for i in range(N)]
intC = [int(C[i]) for i in range(N)]
r = M - sum(intC)

res = [A[i]//(2**intC[i]) for i in range(N)]

res = sorted(res,reverse=True)

for i in range(r):
  res[i] //= 2

print(sum(res))

Submission status: Runtime Error

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

N,M = (int(x) for x in input().rstrip('\n').split())
As = [int(x) for x in input().rstrip('\n').split()]
ad = {x:As.count(x) for x in set(As)}
rest = M
for _ in range(M):
  m = max(x for x,y in ad.items() if y>0)
  x = ad[m]
  if x < rest:
    if m//2 in ad:
      ad[m//2] += x
    else:
      ad[m//2] = x
    rest -= x
    ad[m] = 0
  else:
    ad[m] -= rest
    if m//2 in ad:
      ad[m//2] += rest
    else:
      ad[m//2] = rest
    break
  if all(x==0 for x in ad):
    break
print(sum(x*y for x,y in ad.items()))

Submission status: Runtime Error

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

N,M = (int(x) for x in input().rstrip('\n').split())
As = [int(x) for x in input().rstrip('\n').split()]
ad = {x:As.count(x) for x in set(As)}
rest = M
for _ in range(M):
  m = max(ad.keys())
  x = ad[m]
  if x < rest:
    if m//2 in ad:
      ad[m//2] += x
    else:
      ad[m//2] = x
    del ad[m]
    rest -= x
  else:
    ad[m] -= rest
    if m//2 in ad:
      ad[m//2] += rest
    else:
      ad[m//2] = rest
    break
print(sum(x*y for x,y in ad.items()))

Submission status: Runtime Error

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

for i in range(M):
    ind = A.index(max(A))
    A[ind] = A[ind]//2

print(sum(A))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

a = list(map(int,input().split()))
res = sum(a)
dis = 0
a.sort(reverse=True)
i = 0
while 0 < M:
    dis += a[0] - a[0]//2
    a[0] //= 2
    M -= 1
    while a[i] < a[i+1] and M != 0:
        a[i+1],a[i] = a[i],a[i+1]
        i += 1
        if len(a) < i:break
    i = 0
print(res-dis-M)

Submission status: Runtime Error

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

def find(a, k):
    l = len(a)
    p = l // 2
    i = p
    if k <= a[l - 1]:
        return l
    else:
        while not (a[i] >= k >= a[i + 1]):
            if a[i] < k:
                i -= p // 2 + 1
            elif a[i + 1] > k:
                i += p // 2 
        return i + 1

for i in range(m):
    a[0] //= 2
    if (len(a) > 1):
        if (a[0] < a[1]):
            temp = a[0]
            del a[0]
            index = find(a, temp)
            a.insert(index, temp)

s = 0
for i in range(n):
    s += a[i]

print(s)

Submission status: Runtime Error

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

Solution code:
def main():
    N, K, Q = input_int_tuple()
    A = []
    for i in range(Q):
        A.append(input_int())

    points = [0] * (N+1)

    for a in A:
        points[a] += 1

    for point in points[1:]:
        if K - (Q - point) > 0:
            print('Yes')
        else:
            print('No')


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


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


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


main()

Submission status: Runtime Error

Solution code:
import bisect

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

for _ in range(M):
    max_value = max(A)
    max_index = bisect.bisect_left(A,max_value)
    A[max_index] = max_value // 2

print(sum(A))

Submission status: Runtime Error

Solution code:
import bisect, collections

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

def ii():
    return int(input())

def main():
    N, M = mi()
    A = list(mi())
    A.sort()
    d = collections.deque(A)
    for i in range(M):
        t = d.pop()
        t = t>>1
        bisect.insort_left(d, t)
    print(sum(d))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from heapq import heapify, heappop, heappush


N, M = map(int, input().split())
A = list(map(lambda x: -int(x), input().split()))
if N == 1:
    print(N >> M)
    exit()
heapify(A)
for i in range(M):
    a = -heappop(A)
    while a >= -A[0]:
        a >>= 1
    heappush(A, -a)
    print(A)
print(-sum(A))

Submission status: Runtime Error

Solution code:
import heapq

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

    heapq.heappush(a,-temp)
ans = 0
for _ in range(n):
    ans -= heapq.heappop(a)
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
aabs = [i if i>=0 else i*(-1) for i in a]
MIN = min(aabs)
ans = 0
mcount = 0

for i in range(n):
  if a[i] < 0:
    mcount += 1
    
if mcount%2 == 0:
  for i in a:
    ans += abs(i)
    print(ans)
else:
  for i in a:
    ans += abs(i)
  print(ans - 2*MIN)

Submission status: Runtime Error

Solution code:
import heapq

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

a = []#数字のリスト
a = list(map(lambda x: x*(-1), a))  # 各要素を-1倍することで，最小最大を逆転

heapq.heapify(a)#優先度付きキューに変換

for i in range(m):
  tmp = heapq.heappop(a)
  heapq.heappush(a,(-tmp//2)*(-1))#負の剰余では切り捨て方向が異なってしまうので，いったんプラスにする．
  
print(-sum(a))

Submission status: Runtime Error

Solution code:
def main():
    n, m = list(map(int, input().split()))
    t = list(map(int, input().split()))
    t = list(map(lambda x: x*(-1), t))
    heapq.heapify(t)
    while m > 0:
        v = heapq.heappop(t) * -1
        heapq.heappush(t, (v // 2)* -1)
        m -= 1

    print(sum(t)*-1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, m = list(map(int, input().split()))
    t = list(map(int, input().split()))
    while m > 0:
        idx = 0
        t.sort(reverse=True)
        # print(t)
        t[0] //= 2
        m -= 1
        if m != 0:
            if t[0] > t[1]:
                t[0] //= 2
            else:
                t[1] //= 2
            m -= 1

    print(sum(t))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from heapq import heapify, heappop, heappush
 
N, M = map(int, input().split())
A = [-1*int(i) for i in input().split()]

heapify(A)

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

Submission status: Runtime Error

Solution code:
import math
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
for i in ragne(m):
  c=math.floor(max(a)/2)
  a.remove(a[-1])
  a.append(c)
  a.sort()
 
sum=0
for i in range(n):
  sum+=a[i]
  
print(sum)

Submission status: Runtime Error

Solution code:
import math
import heapq
n,m = map(int, raw_input().split(' '))

heap = [-e for  e in map(int, raw_input().split(' '))]
heapq.heapify(heap)
while(m):
	u = heapq.heappop(heap)
	u *= -1
	u /=2
	if u:
		heapq.heappush(heap, -u)
	m-=1
	"""

	q = int(math.ceil(math.log(u,2)))
	if 2 ** q <= u: q +=1
	if q <= m:
		m-= q
	else:
		u /= 2
		m -=1
		if u:
			heapq.heappush(heap, -u)

	"""
print -sum(heap or [0])

Submission status: Runtime Error

Solution code:
import bisect
from collections import deque

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

arr.sort()
arr = deque(arr)

for _ in range(m):
    q = arr.pop()
    bisect.insort_right(arr, q // 2)

print(sum(arr))

Submission status: Runtime Error

Solution code:
import bisect
from collections import deque

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

arr.sort()

for _ in range(m):
    q = arr.pop()
    bisect.insort_right(arr, q // 2)

print(sum(arr))

Submission status: Runtime Error

Solution code:
import bisect
import math

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

A.sort()
if len(A) < 2:
    ans = int(A[0] / (2**M))
else:
    fst = A[-1]
    scd = A[-2]

    while M > 0:
        if fst == scd:
            Y = 1
        else:
            Y = math.ceil(math.log2(fst/scd))
        print(Y)
        largest = A.pop(-1)
        largest = int(largest / (2**Y))
        print(largest)
        M = M - Y
        bisect.insort(A, largest)
        fst = A[-1]
        scd = A[-2]
        print(A)
    ans = sum(A)

print(ans)

Submission status: Runtime Error

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

def rev():
  global A
  for i in range(N):
    a, b = A[-(2+i)], A[-(1+i)]
    if a > b:
      A[-(2+i)] = b
      A[-(1+i)] = a
    else:
      break

for _ in range(M):
  A[-1] = A[-1]//2
  rev()

print(sum(A))

Submission status: Runtime Error

Solution code:
#import numpy as np
#import math
import heapq

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

for _ in range(m):
    MAX = heapq.heappop(a)  # −１かけたリストのMin　＞Max
    heapq.heappush(a, (-1) * (-MAX // 2))
    print(a)

ans = (sum(a)) * (-1)  # そのままリストでOK
print(ans)

Submission status: Runtime Error

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

for _ in range(m):
    MAX = heapq.heappop(a)  # −１かけたリストのMin　＞Max
    heapq.heappush(a, (-1) * (-MAX // 2))

ans = (sum(a)) * (-1)  # そのままリストでOK
print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
for i in range(M):
    A=sorted(A,reverse=True)
    while 1:
        b=bin(A[0]>>1)
        A[0]=int(b,0)
        if A[0]<A[1]:
            break
        i+=1
print(sum(A))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
for i in range(M):
    A=sorted(A,reverse=True)
    A[0]=A[0]/2
sum=0
for i in range(M):
    sum+=int(A[i])
print(sum)

Submission status: Runtime Error

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

A.sort(reverse = True)

n = 0
if N > 1:
    while not M == 0:

        while A[0] >= A[1]:
            A[n] //= 2
            M -= 1
            if M == 0:
                break
                
        if M == 0:
            break

        i = 0
        while A[i] < A[i+1]:
            A[i], A[i+1] = A[i+1], A[i]
            i += 1
            if i == N:
                break


else:
    A[0] //= (2**M)


result = sum(A)
print(result)

Submission status: Runtime Error

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

A.sort(reverse = True)

n = 0
if N > 1:
    while not M == 0:

        while A[0] >= A[1]:
            A[n] //= 2
            M -= 1
            if M == 0:
                break
        i = 0
        while A[i] < A[i+1]:
            A[i], A[i+1] = A[i+1], A[i]
            i += 1
            if i == N:
                break 

        if M == 0:
            break

else:
    A[0] //= (2**M)


result = sum(A)
print(result)

Submission status: Runtime Error

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

A.sort(reverse = True)

n = 0
if N > 1:
    while not M == 0:

        while A[0] >= A[1]:
            A[n] //= 2
            M -= 1
            if M == 0:
                break
        i = 0
        while A[i] < A[i+1]:
            A[i], A[i+1] = A[i+1], A[i]
            i += 1

        if M == 0:
            break

else:
    A[0] //= (2**M)


result = sum(A)
print(result)

Submission status: Runtime Error

Solution code:
import heapq

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

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

sum(map(lambda x: int(-1 * x), hpq)

Submission status: Runtime Error

Solution code:
# D - Powerful Discount Tickets

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

def quick_sort(ls):
    left = []
    right = []
    if len(ls) <= 1:
        return ls

    ref = ls[0]
    ref_count = 0

    for el in ls:
        if el < ref:
            left.append(el)
        elif el > ref:
            right.append(el)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right

for i in range(M):
    price = A.pop()
    A.append(price // 2)
    A = quick_sort(A)

print(sum(A))

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
dp = [[0 for i in range(5001)] for j in range(5001)]

for i in range(n-1,-1,-1):
	for j in range(n-1,-1,-1):
		if s[i] != s[j]:
			dp[i][j] = 0
		else:
			dp[i][j] = dp[i+1][j+1] + 1

res = 0
for i in range(n):
	for j in range(n):
		if i >= j:
			continue
		x = min(dp[i][j], j-i)
		res = max(x,res)
print (res)

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):
  max_ = a.heappop()
  d = max_ // 2
  a.heappush(d)

print(sum(a))

c = 0
for i in range(len(a)):
  c += a.heappop()
print(c)

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):
  max_ = a.heappop()
  d = max_ // 2
  a.heappush(d)

print(sum(a))

Submission status: Runtime Error

Solution code:
#標準入力からソートまで
import numpy as np
N, M = map(int, input().split())
A = list(map(lambda x : int(x) * (-1), input().split()))
#Aの中で一番でかいのをdiscountしてまた並び替え
#優先度付きqueuemを使う
import heapq
heapq.heapify(A)
for i in range(M):
    tmp = (-1) * heapq.heapop(A) // 2
    heapq.heappush(A, tmp * (-1))
print(-sum(A))

Submission status: Runtime Error

Solution code:
#標準入力からソートまで
import numpy as np
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
#Aの中で一番でかいのをdiscountしてまた並び替え
import bisect
for i in range(M):
    tmp = A.pop(N-1) // 2
    if A[N-2] <= tmp:
        A.append(tmp)
    else:
        bisect.insort_left(A, tmp)
print(sum(A))

Submission status: Runtime Error

Solution code:
#標準入力からソートまで
import numpy as np
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
A = np.array(A)
#Aの中で一番でかいのをdiscountしてまた並び替え
import bisect
for i in range(M):
    tmp = A.pop(N-1) // 2
    if A[N-2] <= tmp:
        A.append(tmp)
    else:
        bisect.insort_left(A, tmp)
print(sum(A))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = a
ans = 0
for i in range(m):
    cnt = 0
    while a[cnt] <= a[cnt+1]:
        cnt += 1
        if cnt == n-1:
            break
    a[cnt] /= 2
    b[cnt] = int(a[cnt])
print(sum(b))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = a
ans = 0
for i in range(m):
    cnt = 0
    while a[cnt] < a[cnt+1]:
        cnt += 1
        if cnt == n-1:
            break
    a[cnt] /= 2
    b[cnt] = int(a[cnt])
print(sum(b))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = a
ans = 0
for i in range(m):
    if a[0] > a[1]:
        a[0] /= 2
        b[0] = int(a[0])
    else:
        a.sort(reverse=True)
        a[0] /= 2
        b[0] = int(a[0])
print(sum(b))

Submission status: Runtime Error

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

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

while m > 0:
    a.sort(reverse = True)
    mid = a[0] // 2
    i = 0
    while a[i] >= mid:
        if i == n:
            break
        if m > 0:
            a[i] //= 2
            m -= 1
            i += 1
        else:
            break
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)
d=[max(a)//2]
a.pop(0)
for i in range(m-1):
  if a[0]>=d[0]:
    d.append(a[0]//2)
    a.pop(0)
  else:
    d.append(d[0]//2)
    d.pop(0)
print(sum(d)+sum(a))

Submission status: Runtime Error

Solution code:
import heapq

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

heapq.heapify(A)

for i in range(M):
    a=((-1*heapq.heappop(A))//2)*(-1)
    print(A)
    heapq.heappush(A,a)
    print(A)
sum=0
for i in range(N):
    sum+=A[i]
print(-sum)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

int main(){
    int N,M;cin>>N>>M;
    priority_queue<long> q;
    for(int i=0;i<M;i++){
        long a;q.push(a);
    }
    for(int i=0;i<N;i++){
        q.top()=q.top()/2
    }
    long res=0;
    for(int i=0;i<M;i++){
        res+=q.top();
        q.pop();
    }
}