/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君の会社には N 台の機器があり、それぞれが電力を消費しています。
i 番目の機器 (1 \leq i \leq N) の現在の消費電力は A_i ワットです。高橋君はこれらの N 台の機器の中から、ちょうど K 台を選んで「省エネモード」に設定しなければなりません。
省エネモードに設定された機器の消費電力は、元の消費電力を半分にした値の小数部分を切り捨てた値になります。すなわち、消費電力が A_i ワットの機器を省エネモードに設定すると、その消費電力は \lfloor A_i / 2 \rfloor ワットになります。ここで \lfloor x \rfloor は x 以下の最大の整数を表します。省エネモードに設定されなかった機器の消費電力は A_i ワットのまま変わりません。
各機器は省エネモードに設定するかしないかのいずれかであり、同じ機器を複数回選ぶことはできません。
高橋君は、省エネモードに設定する K 台の機器をうまく選ぶことで、全機器の消費電力の合計を最小化したいと考えています。
消費電力の合計の最小値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N K A_1 A_2 \cdots A_N
- 1 行目には、機器の台数を表す整数 N と、省エネモードに設定する機器の台数を表す整数 K が、空白区切りで与えられる。
- 2 行目には、各機器の消費電力を表す整数 A_1, A_2, \ldots, A_N が、空白区切りで与えられる。
出力
ちょうど K 台の機器を省エネモードに設定したときの、全機器の消費電力の合計の最小値を 1 行で出力せよ。
入力例 1
5 2 10 7 3 8 5
出力例 1
24
入力例 2
4 4 100 50 30 20
出力例 2
100
入力例 3
8 3 1000000000 999999999 500000000 123456789 987654321 111111111 222222222 333333333
出力例 3
2783950614
Score : 300 pts
Problem Statement
Takahashi's company has N devices, each of which consumes electric power.
The current power consumption of the i-th device (1 \leq i \leq N) is A_i watts. Takahashi must select exactly K devices from these N devices and set them to "energy-saving mode".
The power consumption of a device set to energy-saving mode becomes the original power consumption halved, with the fractional part discarded. That is, if a device with power consumption A_i watts is set to energy-saving mode, its power consumption becomes \lfloor A_i / 2 \rfloor watts. Here, \lfloor x \rfloor denotes the largest integer not exceeding x. The power consumption of devices not set to energy-saving mode remains A_i watts.
Each device is either set to energy-saving mode or not, and the same device cannot be selected more than once.
Takahashi wants to minimize the total power consumption of all devices by choosing the K devices to set to energy-saving mode wisely.
Find the minimum total power consumption.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- 1 \leq A_i \leq 10^9
- All inputs are integers
Input
N K A_1 A_2 \cdots A_N
- The first line contains an integer N representing the number of devices and an integer K representing the number of devices to set to energy-saving mode, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the power consumption of each device, separated by spaces.
Output
Print in one line the minimum total power consumption of all devices when exactly K devices are set to energy-saving mode.
Sample Input 1
5 2 10 7 3 8 5
Sample Output 1
24
Sample Input 2
4 4 100 50 30 20
Sample Output 2
100
Sample Input 3
8 3 1000000000 999999999 500000000 123456789 987654321 111111111 222222222 333333333
Sample Output 3
2783950614