Fail to become GM.

Hints are omitted.

$$$O(nmh^2)$$$ is too simple,just use dynamic programming. $$$dp(i,j,k)$$$ means the probability to reach the goal in the first $$$i$$$ turns,$$$\min(h_i)=j$$$,$$$\sum (h_i-j)=k$$$,and make simple transitions.

As we see,the $$$k$$$ cound be big. And if $$$k\leq n$$$,we get $$$O(nmh)$$$,which is fast enough.

And the $$$k$$$ can only be big in the beginning,and we can enumerate the time when $$$h_i$$$ are equal.

And set another dp,which is used frequently. $$$g(i,j)$$$ means the probability to have $$$j$$$ times when the Sword doesn't shine.It can be done in $$$O(nmh)$$$.

So the work are done.

https://mirror.codeforces.com/contest/2115/submission/322464169