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:
class Heap:

    # 初期化
    def __init__(self):
        self.array = []

    def num(self):
        return len(self.array)
        
    # valを追加する
    def put(self, val):
        pos = len(self.array)
        # valを末尾に追加する
        self.array.append(val)
        # valを適当な位置まで上にあげる
        self.pop_up(pos)
        
    # 最大の要素を取り出す
    def get(self):
        assert len(self.array) > 0

        val = self.array[0]
        
        # 末尾の要素を0に移動してから下に下げる
        t_val = self.array[-1]
        self.array[0] = t_val
        del self.array[-1]
        self.push_down(0)
        return val

    # posの位置の要素を適当な位置まで上げる
    def pop_up(self, pos):
        while pos > 0:
            p_pos = (pos - 1) // 2
            val = self.array[pos]
            p_val = self.array[p_pos]
        
            if val > p_val:
                self.array[pos] = p_val
                self.array[p_pos] = val
                pos = p_pos
            else:
                break
            
    def push_down(self, pos):
        while True:
            l_pos = 2 * pos + 1
            r_pos = 2 * pos + 2
            n = len(self.array)
            
            if n <= l_pos:
                # 子がいない場合
                break
            
            elif n == r_pos:
                # 子が一人の場合
                val = self.array[pos]
                l_val = self.array[l_pos]
                
                if val < l_val:
                    self.array[pos] = l_val
                    self.array[l_pos] = val
                    
                break #
            
            else:
                # 子が二人いるとき
                val = self.array[pos]
                l_val = self.array[l_pos]
                r_val = self.array[r_pos]
                
                if l_val > r_val:
                    if val < l_val:
                        self.array[pos] = l_val
                        self.array[l_pos] = val
                        pos = l_pos
                    else:
                        break
                else:
                    if val < r_val:
                        self.array[pos] = r_val
                        self.array[r_pos] = val
                        pos = r_pos
                    else:
                        break

                        
h = heap()
sn,sm = input().split(" ")
n = int(sn)
m = int(sm)
sa_list = input().split(" ")
l = len(sa)

for sa in sa_list:
  a = int(sa)  
  h.put(a)
 
for i in range(m):  
    max_a = h.get()
    h.put(max_a // 2)

    

print(sum(h.array))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
lis=list(map(int,input().split()))
lis.sort()
t=0
a=0
c=0
for i in range (0,n):
  t=t+lis[i]
for i in range (0,m):
  k=lis[n-1]
  b=k//2
  a=a+k-b
  lis[n-1]=b
  del lis[n-1]
  while lis[c]<b:
    c+=1
  lis.insert(c-1,b)
print(t-a)

Submission status: Runtime Error

Solution code:
import copy
n,m=map(int,input().split())
lis=list(map(int,input().split()))
lis.sort()
t=0
a=0
for i in range (0,m):
  t=t+lis[i]
for i in range (0,m):
  k=lis[n-1]
  b=k//2
  a=a+k-b
  lis[n-1]=b
  lis.sort()
print(t-a)

Submission status: Runtime Error

Solution code:
N,M = [int(i) for i in input().split(' ')]
itemList = np.array([int(i) for i in input().split(' ')])

for _ in range(M):
    itemList[np.argmax(itemList)] //= 2        

print(sum(itemList))

Submission status: Runtime Error

Solution code:
import copy
n,m=map(int,input().split())
lis=list(map(int,input().split()))
lis.sort()
li=copy.copy(lis)
t=0
a=0
for i in range (0,m):
  t=t+li[i]
for i in range (0,m):
  lis[n-1]=li[n-1]//2
  a=a+li[n-1]-lis[n-1]
  li[n-1]=lis[n-1]
  li.sort()
  lis.sort()
print(t-a)

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort(reverse=True)
for _ in range(m):
    a[0] //= 2
    if a[0] < a[1]:
        a.sort(reverse=True)
print(sum(a))

Submission status: Runtime Error

Solution code:
N,M = map(int, raw_input().split())
A = list(map(int,raw_input().split()))	
ans = 0
for i in range(0,M):
  max_A_index = A.index(max(A))
  A[max_A_index] = max_A/2
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)

while m > 0:
    A[0] = A[0]//2
    m -= 1
    if A[0] < A[1]:
        A = sorted(A, reverse=True)

print(sum(A))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import numpy as np
import sys, math

class Heapque():
    
    def __init__(self):
        pass
        
    def pop(self, que):
        
        if len(que) >= 2:
            val = que.pop(1)
            
            return(que, val)
            
        else:
            
            return(0)
            
    def sort(self, que, i=1):
        
        print("sort", que)
        parent = que[i]
        
        if len(que) <= i*2:
            print("sort", que, type(que))
            
            return(que)
            
        elif len(que) <= i*2+1:
            left_child = que[i*2]
            if parent < left_child:
                que[i] = left_child
                que[i*2] = parent
            print("sort", que, type(que))
            
            return(que)
            
        else:
            left_child = que[i*2]
            right_child = que[i*2+1]
        
        max_val = max(parent, max(left_child, right_child))
        
        if max_val == parent:
            
            pass
            
        elif max_val == left_child:
            
            que[i] = left_child
            que[i*2] = parent
            que = self.sort(que, i*2)
        
        else:
            que[i] = right_child
            que[i*2+1] = parent
            que = self.sort(que, i*2+1)
            
        return(que)
    
    def add(self, que, val):
        print("def add: que", que)
        que.insert(1, val)
        que = self.sort(que, 1)
        
        return(que)
        
if __name__ == "__main__":
    n, m = map(int, input().split())
    A_list = list(map(int, input().split()))
    
    print("A_list", A_list)
    hq = Heapque()
    que = [0]
    
    for i in range(n):
        print(A_list[i])
        que = hq.add(que, A_list[i]) 
        print(que)
        
    print(que)
    
    for i in range(m):
        que, val = hq.pop(que)
        val = math.floor(val/2)
        que = hq.add(que, val)
        
    print(sum(que))

Submission status: Runtime Error

Solution code:
#141d
from collections import deque

N,M = map(int, input().split()) #1≤N,M≤10^5
A = list(map(int, input().split()))
A.sort()
discounted = deque()
#高橋くんは N 個の品物を 1個ずつ順番に買う予定です。
#i番目に買う品物の値段は Ai円です。
#高橋くんは M枚の割引券を持っています。品物を買う際に割引券を好きな枚数使うことができます。
#X円の品物を買う際に Y 枚の割引券を使った場合、その品物を X/(2^Y)円(小数点以下切り捨て)で買うことができます。
#最小で何円あれば全ての品物を買うことができるでしょうか。

#→高額なものに割引券を使った方が良い

highest = A.pop(-1)
discounted.append(highest/2)

for i in range(M-1):
    if len(A)>0:
        if discounted[0] > A[-1]:
            discounted.append((discounted.popleft())/2)
        else:
            discounted.append((A.pop(-1))/2)
    else:
        discounted.append((discounted.popleft())/2)

discounted = [math.floor(discounted_price) for discounted_price in list(discounted)]

print(sum(A)+sum(discounted))

Submission status: Runtime Error

Solution code:
class SegmentTree:
    def __init__(self, value, N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            if self.comp(left_v, right_v):
                self.node[i] = left_i
            else:
                self.node[i] = right_i

    def set_input(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            if self.comp(left_v, right_v):
                new_i = left_i
            else:
                new_i = right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def get_input(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def get_output(self, a=0, b=-1):
        return self.get_input(self.get_output_index(a,b))

    def get_output_index(self,
                         a=0, b=-1,
                         k=0, l=0, r=-1):
        if b < 0:
            b = self.N
        if r < 0:
            r = self.N
        if a <= l and r <= b:
            return self.node[k]
        elif r <= a or b <= l:
            return None
        else:
            left_i = self.get_output_index(a,b,2*k+1,l,(l+r)//2)
            right_i = self.get_output_index(a,b,2*k+2,(l+r)//2,r)
            left_v, right_v = self.get_input(left_i), self.get_input(right_i)
            if left_v is None and right_v is None:
                return None
            elif self.comp(left_v, right_v):
                return left_i
            else:
                return right_i

inpl = lambda: list(map(int,input().split()))

if __name__ == '__main__':
    N, M = inpl()
    A = inpl()
    segt = SegmentTree(A, reverse=True)
    for _ in range(M):
        i = segt.get_output_index()
        v = segt.get_input(i)
        segt.set_input(i, v//2)
    print(sum(segt.value))

Submission status: Runtime Error

Solution code:
class SegmentTree:
    def __init__(self, value, N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            if self.comp(left_v, right_v):
                self.node[i] = left_i
            else:
                self.node[i] = right_i

    def set_input(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            if self.comp(left_v, right_v):
                new_i = left_i
            else:
                new_i = right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def get_input(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def get_output(self, a=0, b=-1):
        return self.get_input(self.get_output_index(a,b))

    def get_output_index(self,
                         a=0, b=-1,
                         k=0, l=0, r=-1):
        if b < 0:
            b = self.N
        if r < 0:
            r = self.N
        if a <= l and r <= b:
            return self.node[k]
        elif r <= a or b <= l:
            return None
        else:
            left_i = self.get_output_index(a,b,2*k+1,l,(l+r)//2)
            right_i = self.get_output_index(a,b,2*k+2,(l+r)//2,r)
            left_v, right_v = self.get_input(left_i), self.get_input(right_i)
            if left_v is None and right_v is None:
                return None
            elif self.comp(left_v, right_v):
                return left_i
            else:
                return right_i

inpl = lambda: list(map(int,input().split()))

if __name__ == '__main__':
    N, M = inpl()
    A = inpl()
    segt = SegmentTree(A, reverse=True)
    for _ in range(M):
        i = segt.get_output_index()
        v = segt.get_input(i)
        segt.set_input(i, v//2)
    print(sum(segt.value)

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
import heapq
A = list(map(int, input().split()))
A = [(-x,x) for x in A]
heapq.heapify(A)
def conf(A, M):
    if M > 0:
        a = heapq.heappop(A)[1]
        heapq.heappush(A, (-int(a/2), int(a/2)))
    else:
        return A
    return conf(A, M-1)
conf(A, M)
B = [a[1] for a in A]
print(sum(B))

Submission status: Runtime Error

Solution code:
import heapq

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

for i in range(n[1]):
  x=-m[0]//2
  heapq.heappop(m)
  heapq.heappush(m, -x)

ans=0
for i in range(n[1]):
  ans+=-m[i]
print(ans)

Submission status: Runtime Error

Solution code:
import heapq

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

for i in range(n[1]):
  x=m[0][1]//2
  heapq.heappop(m)
  heapq.heappush(m, (-x, x))
  
ans=0

for i in range(n[1]):
  ans+=m[i][1]
  
print(ans)

Submission status: Runtime Error

Solution code:
from copy import deepcopy
import sys
from itertools import combinations_with_replacement
def input():
    return sys.stdin.readline()[:-1]
# input
N, M = map(int, input().split())
As = list(map(int, input().split()))
ind = [i for i in range(N)]

min_val = None
for combo in combinations_with_replacement(ind, M):
    price = deepcopy(As)
    for i in combo:
        price[i] = math.floor(price[i]/2)
    if min_val is None:
        min_val = sum(price)
    else:
        if sum(price) <= min_val:
            min_val = sum(price)

print(min_val)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
price_list = sorted(list(map(int,input().split())),reverse = True)for num in range(m):
    price_list[0] = price_list[0]//2
    price_list = sorted(price_list,reverse = True)
sum(price_list)

Submission status: Runtime Error

Solution code:
from heapq import _heapify_max, _heapreplace_max

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

_heapify_max(a)

for i in range(m):
    _heapreplace_max(a, a[0] // 2)
    
print(sum(a))

Submission status: Runtime Error

Solution code:
import heapq
 
def FUNCTION(A, M):
    heapq.heapify(A)
    for i in range(M):
        heapq.heappush(A, int(heapq.heappop(A) / 2))
        print (A)
    return -sum(A)

N = list(map(int, (input().split(' '))))
A = list(map(lambda x: x*(-1), map(int, (input().split(' ')))))
print(FUNCTION(A, N[1]))

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):
    for j in range(len(a)):
        if a[m - j - 1] == max(a):
            a[m - j - 1] = a[m - j - 1] // 2
            if a[m - j - 1] < a[m - j - 2]:
                a[m - j - 1], a[m - j - 2] =a[m - j - 2], a[m - j - 1]
        #print(a)
        break
print(sum(a))

Submission status: Runtime Error

Solution code:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApp2 {
	class Program {
		static void Main(string[] args) {
			var nm = Console.ReadLine().Split(' ').Select(ngo => int.Parse(ngo)).ToArray();
			var arr = Console.ReadLine().Split(' ').Select(ngo => int.Parse(ngo)).ToArray();

			var queue = new PriorityQueue<long>(nm[0], 1);
			for (int i = 0; i < arr.Length; ++i) queue.Push(arr[i]);

			for (int i = 0; i < nm[1]; ++i) {
				queue.Push(queue.Pop() / 2);
			}

			Console.WriteLine(queue.ToArray().Sum());
		}
	}


	public class PriorityQueue<T> where T : IComparable {
		private IComparer<T> _comparer = null;
		private int _type = 0;

		private T[] _heap;
		private int _sz = 0;

		private int _count = 0;

		/// <summary>
		/// Priority Queue with custom comparer
		/// </summary>
		public PriorityQueue(int maxSize, IComparer<T> comparer) {
			_heap = new T[maxSize];
			_comparer = comparer;
		}

		/// <summary>
		/// Priority queue
		/// </summary>
		/// <param name="maxSize">max size</param>
		/// <param name="type">0: asc, 1:desc</param>
		public PriorityQueue(int maxSize, int type = 0) {
			_heap = new T[maxSize];
			_type = type;
		}

		private int Compare(T x, T y) {
			if (_comparer != null) return _comparer.Compare(x, y);
			return _type == 0 ? x.CompareTo(y) : y.CompareTo(x);
		}

		public void Push(T x) {
			_count++;

			//node number
			var i = _sz++;

			while (i > 0) {
				//parent node number
				var p = (i - 1) / 2;

				if (Compare(_heap[p], x) <= 0) break;

				_heap[i] = _heap[p];
				i = p;
			}

			_heap[i] = x;
		}

		public T Pop() {
			_count--;

			T ret = _heap[0];
			T x = _heap[--_sz];

			int i = 0;
			while (i * 2 + 1 < _sz) {
				//children
				int a = i * 2 + 1;
				int b = i * 2 + 2;

				if (b < _sz && Compare(_heap[b], _heap[a]) < 0) a = b;

				if (Compare(_heap[a], x) >= 0) break;

				_heap[i] = _heap[a];
				i = a;
			}

			_heap[i] = x;

			return ret;
		}

		public int Count() {
			return _count;
		}

		public T Peek() {
			return _heap[0];
		}

		public bool Contains(T x) {
			for (int i = 0; i < _sz; i++) if (x.Equals(_heap[i])) return true;
			return false;
		}

		public void Clear() {
			while (this.Count() > 0) this.Pop();
		}

		public IEnumerator<T> GetEnumerator() {
			var ret = new List<T>();

			while (this.Count() > 0) {
				ret.Add(this.Pop());
			}

			foreach (var r in ret) {
				this.Push(r);
				yield return r;
			}
		}

		public T[] ToArray() {
			T[] array = new T[_sz];
			int i = 0;

			foreach (var r in this) {
				array[i++] = r;
			}

			return array;
		}
	}
}

Submission status: Runtime Error

Solution code:
import heapq

n, m = map(int, input().split())
a = map(int, input().split())
a = map(lambda x: -x, a)
heapq.heapify(a)

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

print(-sum(a))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
N, M=map(int, input().split())
A=list(map(int, input().split()))
A.sort()
while M>0:
  while M>0 and A[-1]>A[-2]:
    A[-1]=A[-1]//2
    M-=1
  idx=bisect_left(A, A[-1])
  A.insert(idx, A[-1])
  A.pop()
print(sum(A))

Submission status: Runtime Error

Solution code:
one = input()
two = input()
 
# one = '3 3'
# two = '2 13 8 12'
 
N, M = map(int, one.split())
Ar = map(int, two.split())
Ar = sorted(Ar , reverse=True)
 
for i in range(M):
    Ar[0] = Ar[0] / 2
    # Ar = sorted(Ar , reverse=True)
    for i in range(len(Ar)):
        if Ar[i] < Ar[i+1]:
            temp = Ar[i]
            Ar[i] = Ar[i+1]
            Ar[i+1] = temp
        else:
            break
 
 
Ar = map(int, Ar)
print(sum(Ar))

Submission status: Runtime Error

Solution code:
import heapq as hq

def solve(m,a):
    v=hq.heapify(a)
    for _ in range(m):
        x=hq.heappop(v)
        x//=-2
        hq.heappush(v,x)
        return -sum(v)

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

Submission status: Runtime Error

Solution code:
import heapq
 
itemCount, ticketCount = map(int, input().split(' '))
prices = map(int, input().split(' '))
 
h = []
for price in prices:
    heapq._heappush_max(h, price)
 
for i in range(ticketCount):
    price = _heappop_max(h)
    heapq._heappush_max(h, price // 2)
total = 0
for price in h:
    total += price
 
print(total)

Submission status: Runtime Error

Solution code:
import heapq

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

heap = heapq.heapify(a)
for t in range(m):
  discount = heapq.heappop(heap) / 2.
  heapq.heappush(heap, discount)
    
print(sum(map(lambda x: int(-x), heap)))

Submission status: Runtime Error

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

a.sort()
for t in range(m):
  discount = a.pop() / 2.
  inserted = False
  for i in range(n):
    if a[i] > discount:
      a.insert(i, discount)
      inserted = True
      break
  if not inserted:
    a.append(discount)
    
print(sum(map(int, a)))

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

def count_sort(arr):
    max_num = max(arr)
    min_num = min(arr)
    count = [0] * (max_num - min_num + 1)
    for ele in arr:
        count[ele - min_num] += 1
    return [ele for ele, cnt in enumerate(count, start=min_num) for __ in range(cnt)]


N, M = [int(i) for i in input().split()]
A = count_sort([int(i) for i in input().split()])
for i in range(M):
    A[-1] = A[-1]//2
    A = count_sort(A)
print(sum(A))

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):
  a[-1] = int(a[-1] / 2)
  if a[-1] < max(a[0:n-2]):
    a[-1], a[a.index(max(a[0:n-2]))] = a[a.index(max(a[0:n-2]))], a[-1]
    
print(sum(a))

Submission status: Runtime Error

Solution code:
import heapq
N, M = map(int, input().split())
A = [-i for i in map(int, input().split())]
heapq.heapify(A)
for _ in xrange(M):
    cur = -(-heapq.heappop(A) // 2)
    heapq.heappush(A, cur)
print(-sum(A))

Submission status: Runtime Error

Solution code:
import heapq
N, M = map(int, input().split())
A = map(int, input().split())
A = [-x for x in A]
heapq.heapify(A)
for _ in xrange(M):
    cur = -(-heapq.heappop(A) // 2)
    heapq.heappush(A, cur)
print(-sum(A))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [int(i) for i in input().split()]
while M > 0:
    A.sort()
    while A[-1] >= A[-2]:
        A[-1] //= 2
        M -= 1
print(sum(A))

Submission status: Runtime Error

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

a = sorted(a, reverse=True)

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

print(sum(a))

Submission status: Runtime Error

Solution code:
n, k, q = map(int, input().split())
p = [k - q] * n
for _ in range(q):
    p[int(input()) - 1] += 1

for p in p:
    print("Yes" if p > 0 else "No")

Submission status: Runtime Error

Solution code:
import math
 
s=list(map(int,input().split()))
t=list(map(int,input().split()))
a=0
b=0
c=0
d=s[1]
t.sort(reverse=True)
if s[0]==1:
  for i in range(s[1]):
    t[0]=math.floor(t[0]/2)
else:
  c=t[0]/2
  for j in range(s[1]):
    print(t)
    for l in range(s[0]):
      if d>0:
        if c<t[l]:
          t[l]=math.floor(t[l]/2)
          d=d-1
        else:
            t.sort(reverse=True)
            c=t[0]/2
            break
      else:
        break
e=sum(t)
print(e)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop

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

hq = heapq.heapify(a)

for i in range(N):
    heappush(hq, -a[i])

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

print(-sum(hq))

Submission status: Runtime Error

Solution code:
import heapq

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

for i in range(M):
  num = (heapq.heappop(value)*(-1)//2)*(-1)
  heapq.heappush(value,num)

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

Submission status: Runtime Error

Solution code:
import math
 
s=list(map(int,input().split()))
t=list(map(int,input().split()))
a=0
t.sort(reverse=True)
for i in range(s[1]):
  t[0]=math.floor(t[0]/2)
  if s[1]>=2:
    if t[0]<t[1]:
      t.sort(reverse=True)
  else:
    continue
a=sum(t)
print(a)

Submission status: Runtime Error

Solution code:
import math

s=list(map(int,input().split()))
t=list(map(int,input().split()))
a=0
b=int(s[1])
for i in range(s[1]):
  for j in range(s[0]):
    if max(t)==t[j] and 0<b:
      t[j]=math.floor(t[j]/2)
      b=b-1
    elif: b<=0:
        break
for l in range(s[0]):
  a=a+t[l]
print(a)

Submission status: Runtime Error

Solution code:
import heapq

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

q = []
for i in range(M):
    # 最も大きい値を取り出して1/2したいので、ここで反転させておき、最終的に足す時に戻す
    heapq.heappush(q, -a[i])
for i in range(M):
    l = heapq.heappop(q)
    heapq.heappush(q, -(-l//2))
print(-sum(q))

Submission status: Runtime Error

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

for i in range(m):
    if list_A[-2] > list_A[-1]:
        list_A = sorted(list_A)
    list_A[-1] = int(list_A[-1]/2)

            # print(i, j, list_A[j])

print(sum(list_A))

Submission status: Runtime Error

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

def discount(M, A):
    A.sort(reverse=True)
    for _ in range(M):
        if A[0] < A[1]: A.sort(reverse=True)
        A[0] = int(A[0]/2)
    return sum(A)

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def discount(M, A):
    for _ in range(M):
        A.sort(reverse=True)
        A[0] = int(A[0]/2)
    return sum(A)

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def discount(M, A):
    for _ in range(M):
        A.sort(reverse=True)
        A[0] = int(A[0]/2)
    return sum(A)

def main():
    N, M = filter(int, input().split())
    A = filter(int, input().split())
    discount(M, A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self,data,parent):
        self.data = data
        self.left = None
        self.right = None
        self.parent = parent
        self.same = 1

class BST:
    def __init__(self):
        self.root = None
    
    def insert(self,data):
        n = self.root
        if n == None:
            self.root = Node(data,None)
            return
        else:
            while True:
                if n.data > data:
                    if n.left is None:
                        n.left = Node(data,n)
                        return
                    n = n.left
                elif n.data < data:
                    if n.right is None:
                        n.right = Node(data,n)
                        return
                    n = n.right
                elif n.data == data:
                    n.same += 1
                    return
    
    def delete_max(self):
        n = self.root
        while True:
            if n.right == None:
                break
            else:
                n = n.right
        tmp = n.data//2
        if n.same > 1:
            n.same -= 1
        else:
            if n.left == None:
                n.parent.right = None
            else:
                n.parent.right = n.left
                n.left.parent = n.parent
        self.insert(tmp)
    
    def sum_bst(self,node):
        if node.left == None and node.right == None:
            return node.data*node.same
        else:
            s = node.data*node.same
            if node.left != None:
                s += self.sum_bst(node.left)
            if node.right != None:
                s += self.sum_bst(node.right)
            return s

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

bst = BST()
for a in list(map(int,input().split())):
    bst.insert(a)
for i in range(M):
    bst.delete_max()
print(bst.sum_bst(bst.root))

Submission status: Runtime Error

Solution code:
import math
import sys

N, M = map(int,input().split())
A = list(map(int,input().split()))
if N == 1:
    while A[0] > 0:
        A[0] = A[0]//2
    print(0)
    sys.exit()

list.sort(A,reverse = True)
a = A[0]
b = A[1]
x = 0
for _ in range(M):
    a = A[0]
    b = A[1]
    x = max(math.ceil(math.log2(a/b)),1)
    if M >= x:
        if x <= 3:
            a = a//(2**x)
            _ += x
        else:
            a = 0
            _ += x
    else:
        if M <= 3:
            a = a//(2**M)
            _ = M
        else:
            a = 0
            _ = M
    A[0] = a
    for i in range(0,N-1):
        if A[i] < A[i+1]:
            A[i] , A[i+1] = A[i+1] , A[i]

print(sum(A))

Submission status: Runtime Error

Solution code:
import math
import sys

N, M = map(int,input().split())
A = list(map(int,input().split()))
if N == 1:
    while A[0] > 0:
        A[0] = A[0]//2
    print(0)
    sys.exit()

list.sort(A,reverse = True)
a = A[0]
b = A[1]
x = 0
for _ in range(M):
    a = A[0]
    b = A[1]
    x = max(math.ceil(math.log2(a/b)),1)
    if M >= x:
        a = a//(2**x)
        _ += x
    else:
        a = a//(2**M)
        _ = M
    A[0] = a
    for i in range(0,N-1):
        if A[i] < A[i+1]:
            A[i] , A[i+1] = A[i+1] , A[i]

print(sum(A))

Submission status: Runtime Error

Solution code:
import numpy as np

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

def sorte(x):
  tmp = x[0] // 2
  j=0
  del x[0]
  if n != 1:
    while tmp<x[j] and j<n-2:
      j += 1
  x.insert(j,tmp)
  
 
a.sort(reverse = True)

while k > 0:
  sorte(a)
  k -= 1

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

print(sum)

Submission status: Runtime Error

Solution code:
x, y = map(int,input().split())

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

lis.sort(reverse = True)
i = 0
while y>0:
  if lis[i%x]>2:
    lis[i%x] = lis[i%x]//2
    y-=1
  i+=1
  print(lis)


print(sum(lis))

Submission status: Runtime Error

Solution code:
import sys

N, M = map(int,input().split())
A = list(map(int,input().split()))
if N == 1:
    while A[0] > 0:
        A[0] = A[0]//2
    print(0)
    sys.exit()

list.sort(A,reverse = True)
for i in range(M):
    while A[0] >= A[1]:
        A[0] = A[0]//2
    for i in range(0,M-1):
        if A[i] < A[i+1]:
            A[i] , A[i+1] = A[i+1] , A[i]

print(sum(A))