提示: 欢迎访问OurACM平台。
Problem 1858 Super Girl

Accept: 86    Submit: 444
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description

Hunan TV’s Super Girl may made a deep impression on you ,but what we care about is not how pretty the zhang or how man the lee . It is known to all that when we judge a participant, we remove the highest x(one two or more) scores and the lowest x(one two or more) scores , so that the average of the remaining is the participant’s final score. Now give you an array of size N which stands for referee’s scores.What you should do is to remove two scores whose sum is highest ,and then remove two scores whose sum is lowest from the given array , at last you should calculate the average of the remaining . But iyixiang think it is so easy ,he want to add a limit to it: The selected two scores (highest or lowest) --array[i] and array[j] (we suppose i < j) . we define the distance between i and j is |i-j| which must be smaller than D which we’ll give you in the input.if there are more than one solution whose sum are equal ,first choose the smaller i ,then choose the smaller j.

Input

There are multiply test cases. For each test case ,the 1st line contains two integers N( 10 <= N <= 500000 ) and D (1 < D < N) which are the lengths of the array and the distance we define above. There are N integers in the second line , which will be fit in signed 32-bit integers.

Output

For each test case , one line , output the participant’s final score (round to 3 decimal).

Sample Input

10 2 97 98 92 89 87 99 96 96 100 95

Sample Output

96.167

Source

FOJ有奖月赛-2009年11月

Submit  Back  Status  Discuss