KUPC 2011

問題 H - あばれうなぎ

time limit 1 sec / memory limit 64 MB

問題文

きつねのしえるはうなぎを食べるのが好きである．

2T+1 枚の鉄板が連続して並んでおり，順番に -T, -T+1, ..., T の番号が付いている．しえるはこれらの鉄板に熱を加え，生きたうなぎを焼こうとしている．うなぎを焼く手順は以下のようなものである．

  • まず，時刻 t=-1 のときに各鉄板にどれだけのエネルギーを加えるかを決め，実際にエネルギーを加える．各鉄板に加えるエネルギーの総和は E 以下でなければならない．すなわち，i 番の鉄板に加えるエネルギーを E(i) として，E(i) ≥ 0,\ E(-T)+...+E(T) ≤ E でなければならない．なお，エネルギーは整数でなくてもよい．
  • エネルギーを加えたあと，鉄板の熱さは E(i) / C(i) になる．ここで，C(i) は i 番の鉄板の比熱である．
  • t = -0.5 のときにうなぎを 0 番の鉄板に載せる．
  • t = 0, 1, 2,..., T のときに，うなぎは今自分がいる鉄板の熱さだけ加熱される．
  • t = 0.5, 1.5, 2.5,...,T-0.5 のとき，うなぎは自分の今いる鉄板にとどまるか，両隣の鉄板に移動することができる．
  • t = T+0.5 のときにうなぎを鉄板の上から回収する．

ところで生きたうなぎというのはとても活きがよくさらに頭も良いので，もしかすると自分にかかる熱さの総和が最小になるように動いたりするんではないかとしえるは不安になった．そうなると鉄板に適当に熱を加えただけではうなぎを十分に加熱できない恐れさえある．

そこであなたには，うなぎが常に最適に動くとして，うなぎに与えることのできる熱さの和の最大値を求めて欲しい．

入力形式

入力は以下の形式で与えられる．


T\ E\\
C(-T)\ C(-T+1)\ ...\ C(T)
T はうなぎを熱する時間，E は鉄板に与えることの出来るエネルギーの総和，C(i) は i 番の鉄板の比熱である．

出力形式

1 行目にうなぎに与えられる熱さの和の最大値を出力せよ．小数点以下何桁でも出力して構わないが，相対誤差あるいは絶対誤差が 10-6 未満になっていなければならない．

制約

  • 1 ≤ T ≤ 105
  • 1 ≤ E ≤ 105
  • 1 ≤ C(i) ≤ 105
  • 入力に含まれる値はすべて整数である．

入出力例

入力例 1

1 100
1 1 1

出力例 1

100.0

この場合は 0 番の鉄板にエネルギーを全て加えるのが最適である．

入力例 2

2 100
1 2 100 2 1

出力例 2

2.8301886792453

入力例 3

5 100000
99999 99999 99999 1 1000 1000 1000 1 99999 99999 99999

出力例 3

199.4680851063830

謝辞

この問題は Writer の二人がインド料理 RAJU 百万遍店とマクドナルド百万遍店において夏の暑さに辟易する中で作られた．
Writer: 楠本充，吉田悠一
Tester: 平澤恭治
この問題に解答する