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: Accepted

Solution code:
import heapq
if __name__ == "__main__":
  n, m = list(map(int, input().split()))
  A = list(map(int, input().split()))
  A_inv = [-a for a in A]
  heapq.heapify(A_inv)
  for i in range(m):
    max_inv = heapq.heappop(A_inv)
    heapq.heappush(A_inv, -(-max_inv//2))
  print(-sum(A_inv))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify
n, m = map(int, input().split())
a = list(map(int, input().split()))
q = []
for x in a:
	heappush(q, -x)
for _ in range(m):
	l = heappop(q)
	heappush(q, -((-l)//2))
print(-sum(q))

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

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

def solve(N: int, M: int, A: "List[int]"):
    A = [-a for a in A]
    heapq.heapify(A)
    for m in range(M):
        largest = -1 * heapq.heappop(A)
        largest = int(largest / 2)
        heapq.heappush(A, -1 * largest)

    print(-1 * sum(A))
    return

def solve_slow(N: int, M: int, A: "List[int]"):
    """
    遅い実行
    """
    A = sorted(A, reverse=True)
    m = 0
    while m < M:
        m += 1
        A[0] = A[0] // 2
        while m < M and len(A) > m and A[0] > A[M-m-1]:
            m += 1
            A[0] = A[0] // 2

        if (len(A) >= 2) and (A[0] < A[1]):
            tmp = A[0]
            A = A[1:]
            for i, a in enumerate(A):
                if a <= tmp:
                    A.insert(i, tmp)
                    break
                if i == len(A)-1:
                    A.insert(len(A)-1, tmp)
                    break
    print(sum(A))
    return




# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Accepted

Solution code:
n,m=map(int,input().split())
lista = [int(i) for i in input().split()]


for i in range(len(lista)):
    lista[i]=lista[i]*-1

import heapq

heapq.heapify(lista)

for i in range(m):
        b=heapq.heappop(lista)
        b=b/2
        heapq.heappush(lista,b)
        
for i in range(n):
        lista[i]=int(lista[i]*-1)

ans=sum(lista)
print(ans)

Submission status: Accepted

Solution code:
import heapq
def _heappush_max(heap,item):
  heap.append(item)
  heapq._siftdown_max(heap,0,len(heap)-1)
def _heappop_max(heap):
  lastelt=heap.pop()
  if heap:
    returnitem=heap[0]
    heap[0]=lastelt
    heapq._siftup_max(heap,0)
    return returnitem
  return lastelt

n,m=map(int,input().split())
a=list(map(int,input().split()))
heapq._heapify_max(a)
for i in range(m):
    _heappush_max(a,_heappop_max(a)//2)
print(sum(a))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
import heapq
n, m = map(int, stdin.readline().rstrip().split())
ary = list(map(int, stdin.readline().rstrip().split()))

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


heapq._heapify_max(ary)

for i in range(m):
    temp = _heappop_max(ary) // 2
    _heappush_max(ary, temp)

res = sum([heapq.heappop(ary) for _ in range(n)])
print(res)

Submission status: Accepted

Solution code:
import heapq


N, M = map(int, input().split())
A = list(map(int, input().split()))
A_inv = [-a for a in A]
heapq.heapify(A_inv)
for _ in range(M):
    max_inv = heapq.heappop(A_inv)
    heapq.heappush(A_inv, -(-max_inv//2))

print(sum([-a for a in A_inv]))

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
A = [-int(x) for x in input().split()]
heapq.heapify(A)
for i in range(M):
    x = heapq.heappop(A)
    x = int(x / 2)
    heapq.heappush(A, x)  # pop minimum
print(-sum(A))

Submission status: Accepted

Solution code:
import math
import heapq

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

a_minus = [a[i] * (-1) for i in range(n)]

heapq.heapify(a_minus)

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

count = 0
for i in range(n):
    value = heapq.heappop(a_minus) * -1
    count += math.floor(value)

print(count)

Submission status: Accepted

Solution code:
import numpy as np
import math
import heapq

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

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

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

prices = []
for price in map(int, input().split(" ")):
    heappush(prices, -price)


for i in range(M):
    max_p = - (heappop(prices))
    half_p = max_p // 2
    heappush(prices, - half_p)

out = - sum(prices)
print(out)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop,heapify
N,M = map(int,input().split())


A_list = list(map(lambda a : -int(a),input().split()))
#print(A_list)
heapify(A_list)
#print(-heappop(A_list))
for i in range(M):
    tmp = -heappop(A_list)//2
    heappush(A_list,-tmp)
print(-sum(A_list))

'''
3 3 
8 6 5
4 4
8 7 6 5 
10 6
10 7 6 5 8 9 10 11 12 13
'''

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
al=list(map(int,input().split()))
hq=[]
for a in al:
    heapq.heappush(hq,-a)
for _ in range(m):
    t=heapq.heappop(hq)
    t=-(-t//2)
    heapq.heappush(hq,t)
print(-sum(hq))

Submission status: Accepted

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


def main():
    n, m = map(int, input().split())

    if n == 1:
        a = int(input())
        for i in range(m):
            a //= 2
        print(a)
        exit()

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

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

    a = [-1 * i for i in a]
    print(sum(a))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import heapq
from math import ceil

input = sys.stdin.readline

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

hq = []
for i in range(N):
    heapq.heappush(hq, -A[i])

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

print(-sum(hq))

Submission status: Accepted

Solution code:
import sys
import math
import numpy as np
from fractions import gcd

import heapq

# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

N,M = map(int, sys.stdin.readline().split())
list_A = list(map(int, sys.stdin.readline().split()))
# list_A.sort(reverse=True)

# list_A_np = np.array(list_A)

# hq = heapq.heapify(list_A)
for i in range(N):
    list_A[i] = -list_A[i]

heapq.heapify(list_A)
# print(list_A)
# print(int(-4.34))

for i in range(M):
    tmp = heapq.heappop(list_A)
    heapq.heappush(list_A, int(tmp/2))

# for i in range(M):
    # list_A.sort(reverse=True)
    # idx_max = list_A.index(max(list_A))
    # list_A[idx_max] = int(list_A[idx_max]/2)

    # if(list_A[0] > list_A[1]):
    #     list_A[0] = int(list_A[0]/2)
    # else:
    #     list_A.sort(reverse=True)
    #     list_A[0] = int(list_A[0]/2)


    # if(list_A_np[0] > list_A_np[1]):
    #     list_A_np[0] = int(list_A_np[0]/2)
    # else:
    #     # idx_max = list_A_np.argmax()
    #     # list_A_np[idx_max] = int(list_A_np[idx_max]/2)
    #     list_A_np = np.sort(list_A_np)[::-1]
    #     list_A_np[0] = int(list_A_np[0]/2)

    # idx_max = list_A_np.argmax()
    # list_A_np[idx_max] = int(list_A_np[idx_max]/2)

ans = 0

for i in range(N):
    # ans += list_A[i]
    # ans += list_A_np[i]
    # ans += hq.pop
    ans += heapq.heappop(list_A)

print(-ans)

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
A = list(-int(i) for i in input().split())

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

Submission status: Accepted

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

for i in range(len(a)):
    a[i] = a[i]*-1.0

heapq.heapify(a)
while m != 0:
    price = heapq.heappop(a)
    price = price/2
    m -= 1
    heapq.heappush(a, price)

for i in range(len(a)):
    a[i] = int(a[i])
    
print(sum(a) * (-1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

import numpy as np

def main():
    n, m = map(int, input().split())
    a = np.array([int(i) for i in input().split()])
    a.sort()

    while True:
        temp = a[-1]//2
        a[-1] //= 2
        a.sort()
        ind = np.where(a==temp)[0][0]
        m -= 1
        if m == 0:
            print(np.sum(a))
            break
        elif n - ind < m:
            a[ind:] = a[ind:]//2
            a.sort()
            m = m - (n-ind)
        else:
            a[-m:] = a[-m:]//2
            print(np.sum(a))
            break

main()

Submission status: Accepted

Solution code:
import heapq

x = map(int,raw_input().split())
n=x[0]
m=x[1]
a = map(int, raw_input().split())

def minus(n):
    return float(n*(-1))

def plus(n):
    return int(n*(-1))

a=list(map(minus, a))
heapq.heapify(a)

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

a=list(map(plus, a))

print(sum(a))

Submission status: Accepted

Solution code:
import sys
import heapq

input = sys.stdin.readline
N, M = map(int, input().split())

A = []
for x in input().split():
    heapq.heappush(A, int(x) * (-1))

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

Submission status: Accepted

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


def main():
    n, m = map(int, input().split())

    if n == 1:
        a = int(input())
        for i in range(m):
            a //= 2
        print(a)
        exit()

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import heapq


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
# import collection
# import bisect
# import numpy

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

# N = 10**5
# A = [10 for i in range(10**5)]
# M = 10**5

# A = sorted(A)
A = []
for i in input().split():
    heapq.heappush(A, -int(i))

while M > 0:
    heapq.heappush(A, -((-heapq.heappop(A))//2))
    M -= 1

print(-sum(A))

Submission status: Accepted

Solution code:
# sys.stdin.readline()
import sys
import time
input = sys.stdin.readline
import math
import heapq

N,M = (int(x) for x in input().split())
A = list(map(int, input().split()))
A = [-i for i in A]
# print(A)
heapq.heapify(A)
# print(heapq.heappop(A))

# t1 = time.time()
for i in range(M):
    a = -heapq.heappop(A) // 2
    heapq.heappush(A, -a)
    # j = A.index(max(A))
    # A[j] = a
    # A[0] = A[0]//2
    # A.sort(reverse=True)
    # if sum(A) <1:
    #     break

print(-sum(A))

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

def main():
    _,M,*A = map(int, open(0).read().split())

    A = [-x for x in A] # reverse max to min
    A.sort()

    for _ in range(M):
        a = int(heappop(A) / 2)
        heappush(A, a)
    print(-sum(A))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heapify,heappush,heappop

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

heapify(a)

for m in range(M):
  max_ = heappop(a)
  a_ = max_[1]//2
  heappush(a,(-a_,a_))

ans=0
for a_ in a:
  ans+=a_[1]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq as hp
n, m = map(int, input().split())
a = list(map(int, input().split()))
items = []
for ai in a:
    hp.heappush(items, (-ai, ai))

for i in range(m):
    item = hp.heappop(items)
    nv = item[1] >> 1
    hp.heappush(items, (-nv, nv))
count = 0
while len(items) > 0:
    v = hp.heappop(items)
    count += v[1]
print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort(reverse=True)

if n > 1:
    a.append(0)
    biggest = a[0]
    now = 0
    while m > 0:
        a[now] = a[now]//2
        m -= 1
        biggest = a[0]
        for i in range(n-1):
            if a[i+1] >= biggest and m > 0:
                a[i+1] = a[i+1]//2
                m -= 1
            else:
                a.sort(reverse=True)
                break
    else:
        quit

else:
  for j in range(m):
    a[0] //= 2

print(sum(a))

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = list(map(lambda x: x * (-1), a))
heapq.heapify(a)
while m != 0:
    price = heapq.heappop(a)
    price = price/2
    m -= 1
    heapq.heappush(a, price)

for i in range(len(a)):
    a[i] = int(a[i])
print(sum(a) * (-1))

Submission status: Accepted

Solution code:
from math import ceil
from heapq import heappush, heappop, heapify

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

for _ in range(m):
    price = heappop(a)
    heappush(a, price / 2)
print(sum(ceil(_) for _ in a) * -1)

Submission status: Accepted

Solution code:
from sys import stdin
import heapq


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    As = []
    for i in [int(x) for x in stdin.readline().rstrip().split()]:
        heapq.heappush(As, -i)
    for _ in range(M):
        x = heapq.heappop(As)
        heapq.heappush(As, x / 2)
    print(sum([-1 * int(x) for x in As]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
lisA = [int(i) for i in input().split()]
#print(n, m)
#print(lisA)
 
lisA.sort(reverse=True)
half0 = lisA[0] // 2
count = 0
for i in range(m):
	if (count > n - 1):
		count = 0
	if (lisA[count] < half0):
		lisA.sort(reverse=True)
		half0 = lisA[0] // 2
		count = 0
	lisA[count] //= 2
	count += 1
print(sum(lisA))

Submission status: Accepted

Solution code:
import heapq

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

q=[]
for l in L:
    heapq.heappush(q, -l)

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

print(-sum(q))

Submission status: Accepted

Solution code:
import heapq
import math
import numpy as np

N, M = map(int, input().rstrip().split(' '))
products = map(float, input().rstrip().split(' '))
#products.sort()

h = []
for value in products:
	heapq.heappush(h, -value)

while(M > 0):
  heapq.heappush(h, heapq.heappop(h) / 2)  
  M -= 1
  #print(h)
  
sum = -sum(map(math.ceil, h))
print(sum)

Submission status: Accepted

Solution code:
import bisect
import math

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

a.sort(reverse=True)

ans=[math.ceil(-a[0]/2)]
num = 0
now = 1

if n == 1:
    print(a[0] // 2**m)
    exit()
    
for i in range(m-1):
    #print(ans[0],a[now],now,ans)
    if now >= n:
        tmp = math.ceil(ans[0] / 2)
        idx = bisect.bisect_right(ans,tmp)
        #print(ans,idx,tmp)
        ans.insert(idx,tmp)
        del ans[0]
        continue
    if ans[0] <= -a[now]:
        tmp = math.ceil(ans[0] / 2)
        idx = bisect.bisect_right(ans,tmp)
        #print(ans,idx,tmp)
        ans.insert(idx,tmp)
        del ans[0]
    else:
        ans.append(math.ceil(-a[now]/2))
        now += 1
#print(ans,ans,ans,ans)
        
if len(ans) == len(a):
    print(-sum(ans))
    exit()
        
print(-sum(ans)+sum(a[len(ans):]))
exit()
for i in range(1,n):
 if num >= m:
   break
 if -a[i]>=ans[-1]: #i番目の要素がansの最小値以下であればansに付け加える
   ans.append(-a[i]//2)
   num+=1
 else:
   pos=bisect.bisect_right(ans,-a[i]) #i番目の要素以下の値で、最も大きい値の位置を求める
   ans[pos]=-a[i] #その位置の値をi番目の要素と置き換える

print(ans)
print(-sum(ans))
exit()

a = [-a]
print(a)
exit()

tmp = a[0] // 2

del a[0]

idx = bisect.bisect_right(a,tmp)
a.insert(idx,tmp)
print(a,idx)
exit()

if a[0] >= a[1]:
    a[0] = a[0] // 2
else:
    a[1] = a[1] // 2
    
print(a)

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools
import heapq


INF = 10 ** 10

# N, M <= 10^5
N, M = [int(x) for x in stdin.readline().rstrip().split()]
# 最大値のheapqにするために反転
A = [-(int(x)) for x in stdin.readline().rstrip().split()]

heapq.heapify(A)

while (M > 0):
    maxn = -(heapq.heappop(A))
    if maxn == 0:
        break

    num = maxn // 2
    heapq.heappush(A, -num)

    M -= 1

# マイナスを元に戻して出力
print(-sum(A))

Submission status: Accepted

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

heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
A=[-int(i) for i in input().split()]
heapq.heapify(A)
for i in range(m):
  a=heapq.heappop(A)
  a/=2
  heapq.heappush(A,a)
ans=0
for i in range(n):
  ans+=int(A[i])
print(-ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split(' ')))
A = list(map(int, input().split(' ')))
A_ = [-1 * num for num in A]

import heapq
import math

heapq.heapify(A_)

for k in range(M):
    maxA_ = heapq.heappop(A_)
    heapq.heappush(A_, math.ceil(maxA_ / 2))
    #print(maxA_, math.ceil(maxA_ / 2))
    #print(A_)
print(sum(A_) * (-1))

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [-a for a in A]
A = sorted(A)
heapq.heapify(A)
for _ in range(M):
    ma = heapq.heappop(A)
    ma = -((-ma)//2)
    heapq.heappush(A, ma)
    # print(A, ma)
print(-sum(A))

Submission status: Accepted

Solution code:
import heapq
readints = lambda: map(int, raw_input().split())

def solve(N, M, A):
    pq = [-x for x in A]
    heapq.heapify(pq)
 
    for _ in xrange(M):
        x = -heapq.heappop(pq)
        x /= 2
        heapq.heappush(pq, -x)
    return -sum(pq)

N, M = readints()
print solve(N, M, readints())

Submission status: Accepted

Solution code:


import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

import heapq

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

hq = []
for a in A:
    heapq.heappush(hq, -a)

while M > 0:
    high = -1 * heapq.heappop(hq)
    high //= 2
    M -= 1
    heapq.heappush(hq, -high)

ans = 0
for i in range(N):
    ans += heapq.heappop(hq)

print(-ans)

Submission status: Accepted

Solution code:
import sys
import heapq


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    for i in range(N):
        A[i] *= -1
    heapq.heapify(A)

    for i in range(M):
        maxa = -1 * heapq.heappop(A)
        if maxa == 0:
            print("0")
            exit()
        heapq.heappush(A,  maxa // 2 * (-1))
    print(sum(A) * (-1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

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

for m in range(M):
  x = heapq.heappop(A)
  x[1] //= 2
  x[0] = -x[1]
  heapq.heappush(A, x)
ans = 0
for a in A:
  ans += a[1]
print(ans)

Submission status: Accepted

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

h=[]
for i in l:
  heapq.heappush(h,-i)

for j in range(m):
  m=-((-heapq.heappop(h))//2)
  heapq.heappush(h,m)
print -sum(h)

Submission status: Accepted

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


def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


def main():
    n, m = map(int, input().split())

    if n == 1:
        a = int(input())
        for i in range(m):
            a //= 2
        print(a)
        exit()

    a = (list(map(int, input().split())))
    heapq._heapify_max(a)

    for i in range(m):
        tmp = _heappop_max(a) // 2
        _heappush_max(a, tmp)

    print(sum(a))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

tmp = list(map(int,(input().split())))
n = tmp[0]
m = tmp[1]

ai = []
tmp = list(map(int,(input().split())))
for i in range(n):
  heapq.heappush(ai, -tmp[i])

for i in range(m):
  maxp = - heapq.heappop(ai)
  maxp = maxp // 2
  heapq.heappush(ai, -maxp)
  
sum = 0
for i in range(n):
  sum += -ai[i]

#print(ai)
print(sum)

Submission status: Accepted

Solution code:
import math
import heapq

N, M = map(int, input().split())
tempA = list(map(int, input().split()))
A = []
for a in tempA:
    heapq.heappush(A, a * - 1)
for i in range(M):
    minNum = heapq.heappop(A)
    heapq.heappush(A, (minNum * -1 // 2) * - 1)
print(sum(A) * -1)

Submission status: Accepted

Solution code:
import heapq
n,m = map(int, input().split())
a = list(map(int, input().split()))
hq = []
for j in range(n):
    aa = a[j] * -1
    heapq.heappush(hq, aa)
for i in range(m):
    maxim = heapq.heappop(hq) * -1
    maxim //= 2
    maxim *= -1
    heapq.heappush(hq, maxim)
print(-1 * sum(hq))

Submission status: Accepted

Solution code:
from math import ceil
import heapq

N, M = map(int, input().split())
heap = [-x for x in list(map(int, input().split()))]
heapq.heapify(heap)

for i in range(M):
    h = heapq.heappop(heap)
    h = ceil(h/2)
    heapq.heappush(heap, h)

ans = 0
for _ in range(N):
    h = heapq.heappop(heap)
    ans += -h

print(ans)

Submission status: Accepted

Solution code:
import heapq

N,M = map(int, input().split())
A = list(-int(i) for i in input().split()) 

heapq.heapify(A)

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

print(-sum(A))

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

import heapq

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

if N == 1:
    A[0] //= (2**M)
    print(A[0])
    exit()

hq = []
for a in A:
    heapq.heappush(hq, -a)

while M > 0:
    high = -1 * heapq.heappop(hq)
    high //= 2
    M -= 1
    heapq.heappush(hq, -high)

ans = 0
for i in range(N):
    ans += heapq.heappop(hq)

print(-ans)

Submission status: Accepted

Solution code:
# 他参加者の回答を参考にした．現在のAtcoderでのpythonのバージョンではdequeにinsertできないので（全ての値に-1をかけて）heapqがよさそう？
import bisect
N, M = map(int, input().split())
B = [int(x) for x in input().split()]
A = sorted(B, reverse=True)
ite = 0
for i in range(M):
    A[ite] //= 2
    if ite < N - 1:
        if A[ite] < A[ite + 1] and A[0] < A[ite+1]:
            ite += 1
        else:
            A = sorted(A, reverse=True)
            ite = 0
    else:
        A = sorted(A, reverse=True)
        ite = 0

ans = sum(A)
print(ans)

Submission status: Accepted

Solution code:
# priority queueで楽勝だった
import heapq

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

for _ in range(m):
    x = -(-a[0] // 2)
    heapq.heapreplace(a, x)
    #print(a)
print(sum(a) * -1)

Submission status: Accepted

Solution code:
import heapq

n,m = map(int,input().split())
As = [-i for i in list(map(int,input().split()))]
heapq.heapify(As)
for i in range(m):
  a = -heapq.heappop(As)
  heapq.heappush(As,-int(a/2))
print(-sum(As))

Submission status: Accepted

Solution code:
from sys import stdin
import heapq

s=stdin.readline().rstrip().split()
N=int(s[0])
M=int(s[1])

a=stdin.readline().rstrip().split()
for i in range(N):
  a[i]=int(a[i])*(-1)
  
heapq.heapify(a)
for i in range(M):
  t=-(-heapq.heappop(a)//2)
  heapq.heappush(a,t)
print(sum(a)*(-1))

Submission status: Accepted

Solution code:
import heapq

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

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

print(-sum(A))

Submission status: Accepted

Solution code:
import sys
import math
from fractions import gcd
from collections import deque
from copy import deepcopy
import heapq
# import queue
# from collections import Counter
# from itertools import accumulate
from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())

## 数値
 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""


N, M = map(int, sys.stdin.readline().split())
L = list(map(int, sys.stdin.readline().split()))

L = list(map(lambda x : x * -1, L))
heapq.heapify(L)
for _ in range(M):
    x = heapq.heappop(L)
    x = math.ceil(x / 2)
    heapq.heappush(L, x)

print(-1 * sum(L))

Submission status: Accepted

Solution code:
import heapq


def neg_int(a):
    return -1 * int(a)


n, m = map(int, input().split())
a = sorted(list(map(neg_int, input().split())))
heapq.heapify(a)

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

print(sum(a) * -1)

Submission status: Accepted

Solution code:
# ABC141D - Powerful Discount Tickets
from heapq import heapify, heappop, heappush


def main():
    N, M, *A = map(int, open(0).read().split())
    B = [-i for i in A]
    heapify(B)
    for _ in range(M):
        x = -heappop(B) // 2
        heappush(B, -x)
    ans = -sum(B)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
import queue

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

#優先度付きキューの作成とpush
q=queue.PriorityQueue()
for i in A:
    q.put(-i)

#最大値を取り出し,1/2倍した後push
for i in range(M):
    num = - q.get()
    #print(num)
    num=num//2
    q.put(-num)

total=0
for i in A:
    total+= - q.get()

print(total)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush

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

H = []

for i in A:
    heappush(H, -i)

for _ in range(M):
    heappush(H, -((-heappop(H)//2)) )

print(-sum(H))