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: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = sorted([int(i) for i in input().split()],reverse=True)
tmp = 0
for i in range(n-1):
    if tmp >= a[i] - a[i]//2:
        i -= 1
    if m > 0 and ((a[i] - a[i]//2) >= (a[i+1] - a[i+1]//2)):
        a[i] //= 2
        m -= 1
    if (a[i] - a[i]//2) < (a[i+1] - a[i+1]//2):
        tmp = a[i] - a[i]//2
    if m == 0:
        break
if m > 0:
    a[0] //= (2**m)
print(sum(a))

Submission status: Wrong Answer

Solution code:
import heapq
import math

n, m = map(int, input().split())
a = list(map(int, input().split()))
q = []
heapq.heapify(q)

for i in range(n):
    heapq.heappush(q, -a[i])

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

print(math.floor(sum(q) * -1))

Submission status: Wrong Answer

Solution code:
import heapq

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [int(_) for _ in input().split()]

if N <= M:
  A = [n // 2 for n in A]
  M = M - N
  
while M != 0:
  ind = A.index(max(A))
  A[ind] = A[ind] // 2
  M -= 1
  
print(sum(A))

Submission status: Wrong Answer

Solution code:
import heapq as hq
n,m=map(int,input().split())
a=[-int(x) for x in input().split()]
hq.heapify(a)

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

Submission status: Wrong Answer

Solution code:
import heapq as hq
n,m=map(int,input().split())
a=[-int(x) for x in input().split()]
hq.heapify(a)

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

Submission status: Wrong Answer

Solution code:
import heapq as hq
n,m=map(int,input().split())
a=[-int(x) for x in input().split()]
hq.heapify(a)

for i in range(m):
  x=hq.heappop(a)
  x=int(x//2)
  hq.heappush(a,-x)
 
print(sum(a))

Submission status: Wrong Answer

Solution code:
import heapq as hq
n,m=map(int,input().split())
a=list(map(int,input().split()))
hq.heapify(a)

for i in range(m):
  x=hq.heappop(a)
  x=int((-x)//2)
  hq.heappush(a,-x)
 

print(sum(a))

Submission status: Wrong Answer

Solution code:
import heapq as hq
n,m=map(int,input().split())
a=list(map(int,input().split()))
hq.heapify(a)

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

while m > 0:
    discount = heapq.heappop(ar)
    heapq.heappush(ar, discount/2)
    m -= 1

print(math.floor(-sum(ar)))

Submission status: Wrong Answer

Solution code:
#powerful discount tickets
import bisect
n,m=map(int,input().split())
lists=list(map(int,input().split()))
lists=sorted(lists)
for _ in range(m):
    #m回この作業を繰り返す
    maxi=lists[-1]
    del lists[-1]
    bisect.insort(lists,maxi/2)
import math
print(math.floor(sum(lists)))

Submission status: Wrong Answer

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

while M > 0:
  A[0] = A[0]/2
  #A.sort(reverse = True)
  M -= 1

A = list(map(math.floor, A))
print(sum(A))

Submission status: Wrong Answer

Solution code:
import numpy as np
import collections
import copy

N,M=map(int,input().split(' '))
A=np.array(list(map(int,input().split(' '))))
tops=[]
A2=copy.copy(A)
for i in range(M):
  Amax=max(A2)
  idx=list(A2).index(Amax)
  tops.append(idx)
  A2[idx]=A[idx]//2**(i+1)

c = collections.Counter(tops)
res=0
for i in range(N):
  res+=A[i]//2**c[i]
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import math
 
N, M = map(int, input().split())
A = list(map(int, input().split()))

class FibonacciTree:
    def __init__(self, key):
        self.key = key
        self.children = []
        self.order = 0

    def add_at_end(self, t):
        self.children.append(t)
        self.order = self.order + 1

class FibonacciHeap:
    def __init__(self):
        self.trees = []
        self.least = None
        self.count = 0

    def insert(self, key):
        new_tree = FibonacciTree(key)
        self.trees.append(new_tree)
        if (self.least is None or key < self.least.key):
            self.least = new_tree
        self.count = self.count + 1

    def get_all(self):
        all_list = []
        for i in range(len(self.trees)):
            all_list.append(self.trees[i].key)
            for j in range(len(self.trees[i].children)):
                all_list.append(self.trees[i].children[j].key)
        return all_list

    def get_min(self):
        if self.least is None:
            return None
        return self.least.key

    def extract_min(self):
        smallest = self.least
        if smallest is not None:
            for child in smallest.children:
                self.trees.append(child)
            self.trees.remove(smallest)
            if self.trees == []:
                self.least = None
            else:
                self.least = self.trees[0]
                self.consolidate()
            self.count = self.count - 1
            return smallest.key

    def consolidate(self):
        aux = (floor_log2(self.count) + 1)*[None]

        while self.trees != []:
            x = self.trees[0]
            order = x.order
            self.trees.remove(x)
            while aux[order] is not None:
                y = aux[order]
                if x.key > y.key:
                    x, y = y, x
                x.add_at_end(y)
                aux[order] = None
                order = order + 1
            aux[order] = x

        self.least = None
        for k in aux:
            if k is not None:
                self.trees.append(k)
                if (self.least is None
                    or k.key < self.least.key):
                    self.least = k

def floor_log2(x):
    return math.frexp(x)[1] - 1

fheap = FibonacciHeap()

for i in range(N):
    fheap.insert(-A[i])

for i in range(M):
    Q_max = fheap.extract_min()
    Q_max = -(-Q_max//2)
    fheap.insert(Q_max)

print(-sum(fheap.get_all()))

Submission status: Wrong Answer

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

li_w = sorted(li_a, reverse=True)
idx = 0
counter = 0
while (counter < m):
    if all(y == li_w[0] for y in li_w):
        li_w[idx] = li_w[idx] // 2
        counter += 1
    else:
        if idx != 0:
            if li_w[idx - 1] < li_w[idx]:
                li_w[idx] = li_w[idx] // 2
                counter += 1
            elif li_w[idx - 1] == li_w[idx]:
                idx += 1
            else:
                idx = 0
        else:
            if li_w[idx] > li_w[idx + 1]:
                li_w[idx] = li_w[idx] // 2
                counter += 1
            elif li_w[idx] == li_w[idx + 1]:
                idx += 1
            else:
                idx += 1

print(sum(li_w))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

import heapq
a = [-i for i in a]

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

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

def main():
    N, M = map(int, input().split())
    A = []
    
    for a in list(map(int, input().split())): heappush(A, -a)
    
    if not N-1:
        A[0] = (-A[0]) // 2 ** M
    else:
        while M:
            a = heappop(A)
            b = heappop(A)
    
            while a >= b and M:
                a = int(a//2)
                M -= 1
                
            heappush(A, a)
            heappush(A, b)
            
    print(-sum(A))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

def primeFactrization(n):
    i = 2
    table = []
    while i*i <= n:
        if  n % i ==0:
            table.append(i)
            while n % i == 0:
                n /= i
        i += 1
    if n > 1:
        table.append(n)
    return table

a,b = map(int, input().split())
c = gcd(a,b)
d = primeFactrization(c)
print(len(d)+1)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int,input().split())
A = list(map(int,input().split()))
for _ in range(M):
    t = max(A)
    A.remove(t)
    A.append(np.floor_divide(t,2))

Submission status: Wrong Answer

Solution code:
from enum import Enum
from queue import Queue

import numpy as np

import collections
import bisect
import sys
import math
import heapq

from scipy.sparse.csgraph import floyd_warshall

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

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
li = list(map(int, input().split()))
for i in range(M):
  a = max(li)
  li.remove(a)
  li.append(a/2)
for j in range(N):
  li[j] = li[j]//1
print(sum(li))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
li = list(map(int, input().split()))
for i in range(M):
  li.append((max(li))/2)
  li.remove(max(li))
for j in range(N):
  li[j] = li[j]//1
print(sum(li))

Submission status: Wrong Answer

Solution code:
import heapq, math
N, M = tuple(int(elem) for elem in input().split())
Ai = [-int(elem) for elem in input().split()]
Ai.sort()
if N == 1:
  print(Ai[0]//(2**M))
  quit()
while M > 0:
  l, r = 0, M
  largest = heapq.heappop(Ai)
  nex = heapq.heappop(Ai)
  while l < r:
    mid = l + (r-l) // 2
    if math.ceil(largest/(2**mid)) <= nex:
      l = mid + 1
    else:
      r = mid
  heapq.heappush(Ai, math.ceil(largest/(2**l)))
  heapq.heappush(Ai, nex)
  M = M - l
print(-sum(Ai))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

for i in range(m):

    v=a.index(max(a))
    a[v] = a[v]/2


print(int(sum(a)))

Submission status: Wrong Answer

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


for i in range(M):
  A_n[-1] /= 2 
  A_n.sort()
  
print(sum(list(map(int,A_n))))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
if len(a) == 1:
    print(a[0] / 2 ** m)
else:
    a.sort()
    for i in range(m):
        a[-1] //= 2
        if a[-1] < a[-2]:
            a.sort()
    print(sum(a))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

a=sum(list1)

b=a//(2**m)

print(b)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

if len(A) ==1:
  print(int(A[0]/(2**M)))
else:
  while(M>0):
    A[-1]=int(A[-1]/2)
    M -=1
    if A[-1] < A[-2] and M >0:
      A[-1]=int(A[-1]/2)
      M -=1
      A.sort()
  print(sum(A))

Submission status: Wrong Answer

Solution code:
from math import log2
from bisect import bisect_right
n, m = map(int, input().split())
a = [int(ai) for ai in input().split()]
a.sort()
b = [log2(ai) for ai in a]
ma = int(b[-1])
c = 0
tmp = 0
for t in range(ma+1)[::-1]:
  i = bisect_right(b, t)
  d = n - i
  if c + d <= m:
    c += d
    for j in range(i, n):
      a[j] = a[j] / 2.0
  else:
    a.sort(reverse=True)
    for j in range(m-c):
      a[j] = a[j] / 2.0
    break
print(sum([int(ai) for ai in a]))

Submission status: Wrong Answer

Solution code:
from math import log2
from bisect import bisect_right
n, m = map(int, input().split())
a = [int(ai) for ai in input().split()]
a.sort()
b = [log2(ai) for ai in a]
ma = int(b[-1])
c = 0
tmp = 0
for t in range(ma+1)[::-1]:
  i = bisect_right(b, t)
  d = n - i
  if c + d <= m:
    c += d
    for j in range(i, n):
      a[j] = a[j] / 2.0
  else:
    a.sort(reverse=True)
    for j in range(m-c):
      a[j] = a[j] / 2.0
print(sum([int(ai) for ai in a]))

Submission status: Wrong Answer

Solution code:
from math import log2
from bisect import bisect_right
n, m = map(int, input().split())
a = [int(ai) for ai in input().split()]
a.sort()
b = [log2(ai) for ai in a]
ma = int(b[-1])
c = 0
tmp = 0
for t in range(ma)[::-1]:
  i = bisect_right(b, t)
  d = n - i
  if c + d <= m:
    c += d
    for j in range(i, n):
      a[j] = a[j] / 2.0
  else:
    a.sort(reverse=True)
    for j in range(m-c):
      a[j] = a[j] / 2.0
print(sum([int(ai) for ai in a]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math

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

cost = 0
rest = m
for i in range(n):
    if rest < 1:
        cost += a[i]
        continue
    if i == n - 1:
        cost += a[i] // 2 ** rest
        break

    current = a[i]
    nextval = a[i + 1]
    optimal = math.floor(math.log(current - nextval, 2)) if current != nextval else 1
    y = min(optimal, rest)
    cost += a[i] // 2 ** y
    rest -= y


print(cost)

Submission status: Wrong Answer

Solution code:
import numpy as np
import heapq
n = list(map(int, input().split()))
h = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(h)
for i in range(n[1]):
    small = heapq.heappop(h)
    heapq.heappush(h, -1*(-small)//2)
print(-sum(h))

Submission status: Wrong Answer

Solution code:
import numpy as np
n = list(map(int, input().split()))
h = list(map(int, input().split()))
h = sorted(h, reverse = True)
i = 0
for i in range(n[1]):
    h[0] = h[0]/2
    h = sorted(h, reverse  = True)
    i = i + 1
h = np.floor(h)
print(round(sum(h)))

Submission status: Wrong Answer

Solution code:
N, M = [int(item) for item in input().split()]
price_list = sorted([int(item) for item in input().split()])

ticket_list = []
total_price_list = []
total_m = 0

def discount(price_list, ticket_num):
    total_ticket =0

    while total_ticket < ticket_num:
        price_list[-1] = int(price_list[-1]/2)
        price_list.sort()
        total_ticket += 1

    return price_list

res = discount(price_list, M)
print(res)
print(sum(res))

Submission status: Wrong Answer

Solution code:
N, M = [int(item) for item in input().split()]
price_list = sorted([int(item) for item in input().split()])

ticket_list = []
total_price_list = []
total_m = 0

def discount(price_list, ticket_num):
    total_ticket =0

    while total_ticket < ticket_num:
        temp_num = int(price_list[-1]/2)
        price_list.sort()
        price_list[-1] = temp_num 
        total_ticket += 1

    return price_list



# total_price  += int(price_list[n] / (2 ** m))
# break
res = discount(price_list, M)
# print(res)
print(sum(res))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

a_sorted = sorted(a)

while m > 0:
    maximum = a_sorted.pop(-1)
    if maximum % 2 == 0:
        bisect.insort_left(a_sorted, maximum//2)
    else:
        bisect.insort_left(a_sorted, maximum//2)
    m += -1
    print(a_sorted)
ans = sum(a_sorted)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import bisect
 
n, m = (int(x) for x in input().split())
item = sorted([int(x) for x in input().split()])
if n == 1:
    print(item[0] // (2**m))
else:
  while m > 0:
      a = item.pop()
      while a >= item[1] and m > 0:
          a = a // 2
          m -= 1
      bisect.insort_left(item,a)
  print(sum(item))

Submission status: Wrong Answer

Solution code:
import bisect

n, m = (int(x) for x in input().split())
item = sorted([int(x) for x in input().split()], reverse=True)
for _ in range(m):
    a = item.pop() // 2
    bisect.insort_left(item,a)
print(sum(item))

Submission status: Wrong Answer

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

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

a = list(map(lambda x: x*(-1), A_list))

import heapq
import math


heapq.heapify(a)

print(a)


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

res=0
for i in range(N):
        a[i] = -a[i]
        res += math.floor(a[i])

print(res)

Submission status: Wrong Answer

Solution code:
import heapq
 
N, M = map(int, input().split())
A = list(map(int, input().split()))
 
 
def solve():
    AA = [[-x, x] for x in A]
 
    heapq.heapify(AA)
 
    for i in range(M):
        x, y = heapq.heappop(AA)
        heapq.heappush(AA, [-(y//2), y//2])

Submission status: Wrong Answer

Solution code:
import math

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


def solve():
    sorted_list = A

    for index in range(0, M):
        sorted_list = sorted(sorted_list)
        sorted_list[-1] = math.ceil(sorted_list[-1] / 2)

    return sum(sorted_list)


print(solve())

Submission status: Wrong Answer

Solution code:
import math

def get_discount_num(item):
	if item == 0:
		return 0
	return int(math.log2(item))-1

n,m = map(int,input().split())
items = list(map(int,input().split()))
items.sort(reverse=True)
discount_nums = [0 for _ in range(n)]
total = 0

while m>0 :
	for i,item in enumerate(items):
		discount = get_discount_num(item)
		if discount > 0 and m >= discount :
			m -= discount
			discount_nums[i] += discount
		elif discount > m and m > 0 :
			discount_nums[i] += m
			m = 0
	if m >= 0:
		for i in range(n):
			discount = discount_nums[i]
			items[i] = int(items[i]/2**discount) if discount > 0 else items[i]
			discount_nums[i] = 0
		items.sort(reverse=True)
		for i in range(min(n,m)):
			discount_nums[i] += 1
		m -= min(n,m)

for i in range(n):
	discount = discount_nums[i]
	items[i] = int(items[i]/2**discount) if discount > 0 else items[i]
	discount_nums[i] = 0
print(sum(items))

Submission status: Wrong Answer

Solution code:
import math

def get_discount_num(item):
	return int(math.log2(item))-1

n,m = map(int,input().split())
items = list(map(int,input().split()))
items.sort(reverse=True)
discount_nums = [0 for _ in range(n)]
total = 0

for i,item in enumerate(items):
	discount = get_discount_num(item)
	if discount > 0 and m >= discount :
		m -= discount
		discount_nums[i] += discount
	elif discount > m and m > 0 :
		discount_nums[i] += m
		m = 0

for i in range(n):
	discount = discount_nums[i]
	items[i] = int(items[i]/2**discount)
	discount_nums[i] = 0

while m > 0:
	items.sort(reverse=True)
	for i in range(min(n,m)):
		discount_nums[i] += 1
	m -= min(n,m)

for i in range(n):
	discount = discount_nums[i]
	items[i] = int(items[i]/2**discount)
	discount_nums[i] = 0
	
print(sum(items))

Submission status: Wrong Answer

Solution code:

def get_discount_num(item):
	num = 2
	m = 0
	while num < item :
		num *= 2
		m += 1
	return m-1

n,m = map(int,input().split())
items = list(map(int,input().split()))
items.sort(reverse=True)
discount_items = []

for item in items:
	discount = get_discount_num(item)
	if discount > 0 and m >= discount :
		m -= discount
		discount_items.append(int(item/2**discount))
	else :
		if m > 0 :
			discount_items.append(int(item/2**m))
			m = 0
		else :
			discount_items.append(item)

while m > 0:
	for i in range(min(n,m)):
		discount_items[i] = int(discount_items[i]/2)
	m -= min(n,m)
print(sum(discount_items))

Submission status: Wrong Answer

Solution code:

def get_discount_num(item):
	num = 2
	m = 0
	while num < item :
		num *= 2
		m += 1
	return m-1

n,m = map(int,input().split())
items = list(map(int,input().split()))
items.sort(reverse=True)
discount_items = []

for item in items:
	discount = get_discount_num(item)
	if discount > 0 and m >= discount :
		m -= discount
		discount_items.append(int(item/2**discount))
	else :
		if m > 0 :
			discount_items.append(int(item/2**m))
			m = 0
		else :
			discount_items.append(item)

while m > 0:
	for i in range(n):
		discount_items[i] = int(discount_items[i]/2)
	m -= n
print(sum(discount_items))

Submission status: Wrong Answer

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

print(a)
 
for _ in range(m):
	a_min = heapq.heappop(a)
	heapq.heappush(a,(-(-a_min//2)))

print(-sum(a))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
lis = [[] for i in range(31)]
li = list(map(int,input().split()))
li.sort()
num = 0
for i in range(n):
  while 2**num < li[i]:
    num += 1
  lis[30-num].append(li[i])

for i in range(30):
  lis[i].sort(reverse=True)
  for nu in lis[i]:
    if m:
      p = lis[i].pop(0)
      lis[i+1].append(p//2)
      m -= 1
print(sum([sum(lis[i]) for i in range(30)]))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
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]


def solve(N: int, M: int, A: "List[int]"):
    hq = Heapq(A, desc=True)
    while M > 0:
        MD = hq.pop()
        M -= 1
        for i, a in enumerate(A):
            if a.val > MD//2 and M > 0:
                A[i] = Reverse(a.val//2)
                M -= 1
            else:
                break
        hq.push((MD//2))
        if MD <= 0:
            break
    ans = 0
    while A:
        a = hq.pop()
        ans += a
    print(ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]"):
    A = sorted(A, reverse=True)
    while M > 0:
        MD = A[0] // 2
        A[0] = MD
        M -= 1
        for i, ai in enumerate(A):
            if M <= 0:
                break
            if ai > MD:
                A[i] = ai//2
                M -= 1
        if A[0] == 0:
            break
    print(sum(A))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

n, m = map(int, input().split())
a_i = list(map(lambda x: math.log(int(x), 2), input().split()))
for _ in range(m):
    a_i.sort(reverse=True)
    a_i[0] -= 1
print(reduce(lambda acc, x: acc + int(2 ** x), a_i, 0))

Submission status: Wrong Answer

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

while M>0:
  A = sorted(A, reverse=True)
  a_ = A[0]//2
  if a_==0: break
  for i,a_i in enumerate(A):
    if a_i > a_ and M>0:
      A[i] = a_i//2
      M -= 1
    else: break
print(sum(A))

Submission status: Wrong Answer

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

dp = [[0]*(M+1) for _ in range(N+1)]
for i in range(N):
  for j in range(M+1):
    dp[i+1][j] = dp[i][j]+A[i] if j==0 else min([dp[i][j-j_]+A[i]//(2**j_) for j_ in range(1,j+1)])
    if dp[i+1][j]==0: break
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
#キューを使っている。ところどころマイナスにしているのはキューの性質のため。実行時間が全然違うのはソートが早いから
n,m = map(int,input().split())
a = list(map(lambda x: -int(x) ,input().split()))
print(a)
import heapq
heapq.heapify(a)
for _ in range(m):
  tmp = -heapq.heappop(a)
  tmp //= 2
  heapq.heappush(a,-tmp)
print(-sum(a))

Submission status: Wrong Answer

Solution code:
n,m=(int(x) for x in input().split())
import math as math
import numpy as np


A = [int(x) for x in input().split()]

for i in range(m):
    A.sort()
    A [-1] = A[-1]/2
for i in range(n):
   A[i] =  math.floor(A[i]) 
print(A[0])

Submission status: Wrong Answer

Solution code:
import numpy as np
n, m = map(int, input().split())
a = list(map(int, input().split()))
l = np.array(a)
for i in range(m):
    idx = l.argmax()
    print(idx)
    l[idx] = l[idx]//2
print(sum(l))

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy
import math

I = input().split(" ")
# goods 
N = int(I[0])
# discount tickets
M = int(I[1])

# price
A = input().split(" ")
for i in range(N):
    A[i] = int(A[i])

# Number of discount
B = [0] * N

# times of useing discount tickets
C = [0] * N

# answer

D = copy.copy(A)

# tmp

tmp1 = [0]*N
tmp2 = [0]*N

for j in range(N):
        tmp1[j] =  math.floor(A[j] / 2 )
        tmp2[j] = A[j] - tmp1[j]

for i in range(M):
        get = np.argmax(tmp2)
        if get == -1:
            break
        D[get] = tmp1[get]
        if tmp1[get] != 0:
            B[get] = B[get] +1
            tmp3 = tmp1[get]
            tmp1[get] = math.floor(D[get] / 2 ** B[get])
            tmp2[get] = tmp3 -tmp1[get]
        else:
            tmp2[get] = -1

# output answer 

print(int(sum(D)))

Submission status: Wrong Answer

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

import heapq
heapq.heapify(A)

for ticket_num in range(1,N+1):
    max_value = -1*heapq.heappop(A)
    heapq.heappush(A, -1*(max_value>>1))

print(-1*sum(A))