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:
def solve(N, M, A):
    from math import log, ceil
    from heapq import heappush, heappop, heapify
    Q = [-a for a in A]
    heapify(Q)

    if len(A) == 1:
        return A[0]>>M

    while Q and M:
        a = - heappop(Q)
        b = - Q[0]
        if a == 0:
            continue
        if b == 0:
            k = M
        elif b < a:
            k = min(M, ceil(log(a,2) - log(b, 2)))
        else:
            k = min(M, 1)
        c = a >> k
        #print("prev=%d, dis=%d, %d - %d = %d" % (a, c, M, k, M-k))
        M -= k
        heappush(Q, -c)
    return sum(-a for a in Q)


def main():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    A = sorted([int(x) for x in input().split()], reverse=True)

    print(solve(N, M, A))

def gen():
    import random
    with open("9", "w") as f:
        print(10**5, 10**5, file=f)
        print(*[random.randint(1, 10**9) for i in range(10**5)],file=f)

main()

Submission status: Accepted

Solution code:
### D

import heapq

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

Submission status: Accepted

Solution code:
import heapq as hq

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

for _ in range(m):
    saidai = -hq.heappop(ai)
    saidai = -1*(saidai //2)
    
    hq.heappush(ai,saidai)

print(-1*sum(ai))

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from heapq import heappush,heappop
import math



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

Hn = []
for a in An:
  heappush(Hn,-a)
for _ in range(M):
  h1 = -heappop(Hn)
  h1 = h1 >> 1
  heappush(Hn,-h1)
print(-sum(Hn))

Submission status: Accepted

Solution code:
import sys
import heapq


class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign


if __name__ == '__main__':
    # input = sys.stdin.readline()
    N, M = map(int, input().split())
    A = Heapq(list(map(int, input().split())), desc=True)

    for i in range(M):
        A.push(A.pop() / 2)
    print(-sum([int(i) for i in A.hq]))