ZOJ Problem Set - 3694
There are N (1 ≤ N ≤ 100000) soldiers stand in a line. Each soldier has a ability assessment value Vi (-10^8 ≤ Vi ≤ 10^8).
July want to select some soldiers into M (1 ≤ M ≤ 10) teams, each team consist of some soldiers standing consecutively. And its size should be between [L,R](inclusively and 1 ≤ L ≤ R ≤ N). Notice that each selected soldier can belong exactly one team.
Now your task is to maximize the average ability value of selected soldiers.
The input will consist of about 100 testcases.
The first line of one testcase is four integer N, indicating the amount of soldiers, M, indicating the required amount of teams, and [L,R] ,the size limit of each team.
following is N integers, the ability value of each soldier.
Each testcase should output exactly 1 lines, each line a float legal answer with two decimal places reserved. Output "-1"(without quotation) if there is no legal arrangement.
6 2 2 3 3 1 3 1 1 3 1 2 1 1 1
No matter you answer is 1.009 or 1.002, you should output 1.00 both to make the answer legitimate.
Author: CHEN, Cong
Contest: ZOJ Monthly, March 2013