/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は観葉植物を育てることが趣味で、自宅に多くの植物を置いています。
高橋君の家には N 個の部屋があり、それぞれの部屋にはエアコンが設置されています。i 番目の部屋の現在の室温は T_i 度です。
高橋君が育てている植物は、室温が L 度以上 R 度以下でないとうまく育ちません。そのため、植物を置く部屋の室温がこの範囲外の場合は、エアコンを使って室温を調整する必要があります。
i 番目の部屋にエアコンをかけると、その部屋の室温を好きな温度に変更できます。このとき、温度の変化量 1 度あたり 1 円の電気代がかかります。すなわち、室温を T_i 度から S 度に変更するコストは |T_i - S| 円です。室温がすでに L 度以上 R 度以下であれば、調整の必要はなくコストは 0 円です。
高橋君は N 個の部屋から異なる K 個の部屋を選び、それらの部屋すべての室温を L 度以上 R 度以下に調整して植物を置くことにしました。
K 個の部屋を適切に選んだとき、必要な電気代の総コストの最小値を求めてください。
制約
- 1 \leq K \leq N \leq 2 \times 10^5
- -10^9 \leq L \leq R \leq 10^9
- -10^9 \leq T_i \leq 10^9
- 入力はすべて整数
入力
N K L R T_1 T_2 \ldots T_N
- 1 行目には、部屋の数を表す整数 N 、選ぶ部屋の数を表す整数 K 、適切な室温の下限を表す整数 L 、適切な室温の上限を表す整数 R が、スペース区切りで与えられる。
- 2 行目には、各部屋の現在の室温を表す整数 T_1, T_2, \ldots, T_N が、スペース区切りで与えられる。
出力
K 個の部屋を選んで、それらすべての室温を L 度以上 R 度以下に調整するために必要な電気代の総コストの最小値を 1 行で出力してください。
入力例 1
5 3 18 22 15 18 25 21 30
出力例 1
3
入力例 2
4 2 0 0 -5 7 0 3
出力例 2
3
入力例 3
8 5 -2 4 -10 -2 0 3 5 8 -1 12
出力例 3
1
入力例 4
18 10 100 130 80 95 99 100 101 110 120 130 131 140 150 70 85 128 129 90 105 160
出力例 4
2
入力例 5
1 1 -1000000000 -1000000000 1000000000
出力例 5
2000000000
Score : 300 pts
Problem Statement
Takahashi's hobby is growing houseplants, and he keeps many plants in his home.
Takahashi's house has N rooms, each equipped with an air conditioner. The current temperature of the i-th room is T_i degrees.
The plants Takahashi is growing cannot thrive unless the room temperature is at least L degrees and at most R degrees. Therefore, if the temperature of a room where plants are placed is outside this range, the air conditioner must be used to adjust the temperature.
When the air conditioner is used in the i-th room, the room temperature can be changed to any desired temperature. The electricity cost is 1 yen per 1 degree of temperature change. That is, the cost of changing the temperature from T_i degrees to S degrees is |T_i - S| yen. If the room temperature is already at least L degrees and at most R degrees, no adjustment is needed and the cost is 0 yen.
Takahashi will select K distinct rooms from the N rooms, adjust the temperatures of all selected rooms to be at least L degrees and at most R degrees, and place plants in them.
Find the minimum total electricity cost required when the K rooms are chosen optimally.
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- -10^9 \leq L \leq R \leq 10^9
- -10^9 \leq T_i \leq 10^9
- All inputs are integers
Input
N K L R T_1 T_2 \ldots T_N
- The first line contains four space-separated integers: N representing the number of rooms, K representing the number of rooms to select, L representing the lower bound of the suitable temperature, and R representing the upper bound of the suitable temperature.
- The second line contains space-separated integers T_1, T_2, \ldots, T_N representing the current temperature of each room.
Output
Print in one line the minimum total electricity cost required to select K rooms and adjust all their temperatures to be at least L degrees and at most R degrees.
Sample Input 1
5 3 18 22 15 18 25 21 30
Sample Output 1
3
Sample Input 2
4 2 0 0 -5 7 0 3
Sample Output 2
3
Sample Input 3
8 5 -2 4 -10 -2 0 3 5 8 -1 12
Sample Output 3
1
Sample Input 4
18 10 100 130 80 95 99 100 101 110 120 130 131 140 150 70 85 128 129 90 105 160
Sample Output 4
2
Sample Input 5
1 1 -1000000000 -1000000000 1000000000
Sample Output 5
2000000000