""" https://yukicoder.me/problems/no/1590 分からなければさっさと見ちゃおうかな 寄与を考えるよね x人目がy番目の商品を買う確率 がわかればおk x,yのペアに関して求めたい ===================== 答えを見た 出来そうなdpから結果を導出する Borderごとに dp[Border][a][b] = a日目でBorder以下がb個残っている確率 とすると、 a日目の人の購入額の期待値は 1/2 * ( dp[B0][a][0] * B0 + dp[B1][a][0] * (B1-B0) + ... ) ただし、その日の商品 A[a] < B? p[i][j] = """ from sys import stdin N = int(stdin.readline()) A = list(map(int,stdin.readline().split())) R = list(map(int,stdin.readline().split())) s = set(A) s.add(0) B = list(s) B.sort() #print (B) dp = {} for Border in B: ndp = [[0] * (N+1) for i in range(N+1)] ndp[0][0] = 1 for a in range(N): na = A[a] for b in range(N+1): if na <= Border: #追加して、取る場合 ndp[a+1][b] += ndp[a][b] / 2 #追加して、取らない場合 if b != N: ndp[a+1][b+1] += ndp[a][b] / 2 else: #追加はしない、取る場合 ndp[a+1][max(0,b-1)] += ndp[a][b]/2 #追加はしない、取らない場合 ndp[a+1][b] += ndp[a][b] / 2 dp[Border] = ndp #print (dp) ans = 0 for a in range(1,N+1): na = A[a-1] nr = R[a-1] nsum = 0 for j in range(len(B)-1): p = 0 #人aが、B[j]より大きい奴を取る確率 if na <= B[j]: p = 0 else: p = dp[B[j]][a-1][0] / 2 #print (a,B[j],p) nsum += (B[j+1]-B[j]) * p ans += nsum * nr #print (nsum * nr) print (ans)