[AtCoder][DP][競プロ][Educational DP Contest]I-Coins

#atcoder template
def main():
    import sys
    input = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #表の枚数がn枚である確率をdp[n]とする。
    import numpy as np
    n = int(input())
    p = list(map(float, input().split()))
    dp = np.zeros((n+1), np.float64)
    dp[0] = 1-p[0]
    dp[1] = p[0]

    for i in range(1, n):
        dp[i+1] = p[i]*dp[i]
        dp[1:i+1] = (1-p[i])*dp[1:i+1] + p[i]*dp[0:i]
        dp[0] *=  (1-p[i])

    print(sum(dp[(n+1)//2:]))
    
    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

for i in range(1, n):
        dp[i+1] = p[i]*dp[i]
        dp[1:i+1] = (1-p[i])*dp[1:i+1] + p[i]*dp[0:i]
        dp[0] *=  (1-p[i])