/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
整数 N,M,S，及び長さ N の整数列 A=(A_1,A_2,\cdots,A_N) が与えられます．
次の条件をすべて満たす長さ N の非負実数列 x=(x_1,x_2,\cdots,x_N) を作ることを考えます．
- 0 \leq x_1 \leq x_2 \leq \cdots \leq x_N \leq M
- \sum_{1 \leq i \leq N} x_i=S
ここで，x のスコアを \sum_{1 \leq i \leq N} A_i \times x_i と定義します． x のスコアとしてありうる最大の値を求めてください．
制約
- 1 \leq N \leq 5000
- 1 \leq M \leq 10^6
- 1 \leq S \leq \min(N \times M,10^6)
- 1 \leq A_i \leq 10^6
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N M S A_1 A_2 \cdots A_N
出力
答えを出力せよ． 絶対誤差または相対誤差が 10^{-6} 以内であれば，正解と判定される．
入力例 1
3 2 3 1 2 3
出力例 1
8.00000000000000000000
x=(0,1,2) とするのが最適です．
入力例 2
3 3 2 5 1 1
出力例 2
4.66666666666666666667
x=(2/3,2/3,2/3) とするのが最適です．
入力例 3
10 234567 1000000 353239 53676 45485 617014 886590 423581 172670 928532 312338 981241
出力例 3
676780145098.25000000000000000000
Score : 600 points
Problem Statement
Given are integers N, M, S, and a sequence of N integers A=(A_1,A_2,\cdots,A_N).
Consider making a sequence of N non-negative real numbers x=(x_1,x_2,\cdots,x_N) satisfying all of the following conditions:
- 0 \leq x_1 \leq x_2 \leq \cdots \leq x_N \leq M,
- \sum_{1 \leq i \leq N} x_i=S.
Now, let us define the score of x as \sum_{1 \leq i \leq N} A_i \times x_i. Find the maximum possible score of x.
Constraints
- 1 \leq N \leq 5000
- 1 \leq M \leq 10^6
- 1 \leq S \leq \min(N \times M,10^6)
- 1 \leq A_i \leq 10^6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M S A_1 A_2 \cdots A_N
Constraints
Print the answer. Your output will be considered correct if its absolute or relative error is at most 10^{-6}.
Sample Input 1
3 2 3 1 2 3
Sample Output 1
8.00000000000000000000
The optimal choice is x=(0,1,2).
Sample Input 2
3 3 2 5 1 1
Sample Output 2
4.66666666666666666667
The optimal choice is x=(2/3,2/3,2/3).
Sample Input 3
10 234567 1000000 353239 53676 45485 617014 886590 423581 172670 928532 312338 981241
Sample Output 3
676780145098.25000000000000000000