Problem:


Score : 100 points

Problem Statement

Let N be a positive odd number.

There are N coins, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N), when Coin i is tossed, it comes up heads with probability p_i and tails with probability 1 - p_i.

Taro has tossed all the N coins.
Find the probability of having more heads than tails.

Constraints

N is an odd number.

1 \leq N \leq 2999

p_i is a real number and has two decimal places.

0 < p_i < 1

Input

Input is given from Standard Input in the following format:

N
p_1 p_2 \ldots p_N

Output

Print the probability of having more heads than tails.
The output is considered correct when the absolute error is not greater than 10^{-9}.

Sample Input 1

3
0.30 0.60 0.80

Sample Output 1

0.612

The probability of each case where we have more heads than tails is as follows:

The probability of having (Coin 1, Coin 2, Coin 3) = (Head, Head, Head) is 0.3 × 0.6 × 0.8 = 0.144;

The probability of having (Coin 1, Coin 2, Coin 3) = (Tail, Head, Head) is 0.7 × 0.6 × 0.8 = 0.336;

The probability of having (Coin 1, Coin 2, Coin 3) = (Head, Tail, Head) is 0.3 × 0.4 × 0.8 = 0.096;

The probability of having (Coin 1, Coin 2, Coin 3) = (Head, Head, Tail) is 0.3 × 0.6 × 0.2 = 0.036.

Thus, the probability of having more heads than tails is 0.144 + 0.336 + 0.096 + 0.036 = 0.612.

Sample Input 2

1
0.50

Sample Output 2

0.5

Outputs such as 0.500, 0.500000001 and 0.499999999 are also considered correct.

Sample Input 3

5
0.42 0.01 0.42 0.99 0.42

Sample Output 3

0.3821815872



Sample input:
3
0.30 0.60 0.80


Sample output:
0.612

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
P=[0]+list(map(float,input().split()))

DP=[[0]*(N+1) for _ in range(N+1)]
DP[0][0]=1

for i in range(N):
    for j in range(i+1):
        DP[i+1][j+1]+=DP[i][j]*P[i+1]
        DP[i+1][j]+=DP[i][j]*(1-P[i+1])

#for row in range(N+1):
    #string=''
    #for column in range(N+1):
        #string+=str(DP[row][column])+' '
    #print(string)

ans=0
half=(N+1)//2
for k in range(half,N+1):
    ans+=DP[N][k]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
N = int(input())
p = list(map(float,input().split()))
#DP = np.array([[0 for i in range(N+1)] for j in range(N+1)])
DP = [[0 for i in range(N+1)] for j in range(N+1)]
sum = 0
DP[0][0] = 1
for i in range(1,N+1):
    for j in range(i+1):
        if j == 0:
            DP[i][0] = DP[i-1][0] * (1 - p[i-1])
        elif i == 1 and j == 1:
            DP[i][j] = p[0]
        else:
            DP[i][j] = DP[i-1][j] * (1 - p[i-1]) + DP[i-1][j-1] * p[i-1]

for i in range(int(N/2)+1, N+1):
    sum += DP[N][i]
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
p = list(map(float, input().split()))

#dp[i][j]は最初のi枚まで投げてj枚表になる確率
#初期化
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
#初期条件 0枚投げたとき0枚表→1
dp[0][0] = 1

for i in range(N):
    for j in range(N):
        dp[i+1][j] += dp[i][j] * (1 - p[i])
        dp[i+1][j+1] += dp[i][j] * p[i]

#i == N で j >= (N+1)/2 のものを足し合わせる
ans = 0
for j in range((N+1)//2, N+1):
    ans += dp[N][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = 3005
dp = [[0]*N for _ in range(N)] 
n = int(input())
p = list(map(float,input().split()))
dp[1][1] = p[0]
dp[1][0] = 1 - p[0]
for i in range(2,n+1):
    pr = p[i-1]
    dp[i][0] = dp[i-1][0] * (1-pr)
    j = i
    while (j > 0) :
        dp[i][j] = dp[i-1][j] * (1-pr) + dp[i-1][j-1] * pr
        j -= 1
ans = 0
m = (n+1)//2
for i in range(m,n+1):
    ans += dp[n][i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
p = list(map(float, input().split()))
dp = [[0 for i in range(N+1)] for j in range(N+1)]
dp[0][0] = 1
for i in range(N):
  x = p[i]
  dp[0][i+1] = dp[0][i] * (1-x)
  for j in range(1, i+2):
    dp[j][i+1] = dp[j-1][i] * x + dp[j][i] * (1-x)
S = 0
for i in range(N//2+1, N+1):
  S += dp[i][N]
print(S)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
p = list(map(float, input().split()))
dp = [[0 for i in range(N+1)] for j in range(N+1)]
dp[0][0] = 1
for i in range(N):
  dp[0][i+1] = dp[0][i] * (1-p[i])
  for j in range(1, i+2):
    dp[j][i+1] = dp[j-1][i] * p[i] + dp[j][i] * (1-p[i])
S = 0
for i in range(N//2+1, N+1):
  S += dp[i][N]
print(S)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, p: "List[float]"):
    dp = []
    for _ in range(0, N + 1):
        L = [0.0] * (N + 1)
        dp.append(L)
    
    dp[1][0] = 1 - p[0]
    dp[1][1] = p[0]

    for i in range(2, N + 1):
        for j in range(0, i + 1):
            if j == 0:
                dp[i][j] = dp[i - 1][j] * (1 - p[i - 1])
            else:
                dp[i][j] = dp[i - 1][j - 1] * p[i - 1] + dp[i - 1][j] * (1 - p[i - 1])

    res = 0
    for j in range(0, N + 1):
        if j < N / 2:
            continue
        res += dp[N][j]
    print(res)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [float(next(tokens)) for _ in range(N)]  # type: "List[float]"
    solve(N, p)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
p = list(map(float, input().split()))
#dp[i][j]:i番のコインを投げた時、表のコインの枚数がj枚になる確率
#配るdp
dp = [[0.0 for i in range(N+1)] for j in range(N+1)]
dp[0][0] = 1.0
for i in range(N):
    for j in range(i+1):
        dp[i+1][j+1] += dp[i][j] * p[i]
        dp[i+1][j] += dp[i][j] * (1.0-p[i])
ans = 0.0
thr = int(N/2+1)

for j in range(thr, N+1):
    ans += dp[N][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
from decimal import Decimal as d
l=list(map(d,input().split()))
k=[0]*(n+1)
k[0]=1
for p in l:
    for j in range(n,-1,-1):
        k[j]*=(1-p)
        if j!=0:k[j]+=k[j-1]*p

print(sum(k[n//2+1:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n = int(input()) #odd
p = list(map(float,input().split()))

#dp[i][j] = i枚まで投げた時の表がj枚出た時の確率。

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


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

ans = 0

for i in range(n//2+1,n+1):
    ans += dp[n][i] 

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(float, input().split()))
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
    for j in range(n+1):
        dp[i][j] += dp[i-1][j-1]*p[i-1]
        dp[i][j] += dp[i-1][j]*(1-p[i-1])
print(sum(dp[-1][-(-n//2):]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
*P, = map(float, input().split())
DP = [0 for j in range(n+1)]
DP[0] = 1
for i in range(n):
    DP_ = []
    DP_.append(DP[0]*(1-P[i]))
    for j in range(1, n+1):
        DP_.append(DP[j]*(1-P[i])+DP[j-1]*P[i])
    DP = DP_
print(sum(DP[(n+1)//2:]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
*P, = map(float, input().split())
# DP[i][j]=i枚中j枚が表の確率
DP = [[0 for j in range(n+1)] for i in range(n+1)]
DP[0][0] = 1
for i in range(1, n+1):
    for j in range(n+1):
        DP[i][j] = DP[i-1][j]*(1-P[i-1])+DP[i-1][j-1]*P[i-1]
print(sum(DP[n][(n+1)//2:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5+10)
input = sys.stdin.readline
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h,w): return [[i for j in range(w)] for k in range(h)]
MOD = 1000000007
INF = float("inf")

N = I()
p = [float(x) for x in input().split()]

dp = FILL(0,N+1,N+1)
dp[0][0] = 1
dp[0][1] = 0
for i in range(N):
    for f in range(i+2):
        if f == 0:
            dp[i+1][f] = dp[i][f]*(1-p[i])
        else:
            dp[i+1][f] = dp[i][f]*(1-p[i]) + dp[i][f-1]*p[i]
ans = 0
for i in range(N+1):
    if i>N/2:
        ans += dp[N][i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = list(map(float, input().split()))

dp = [[0.0] * (N+1) for _ in range(N+1)]

dp[0][0] = 1

for i in range(N):
    for j in range(i+1):
        dp[i+1][j] += dp[i][j] * (1-P[i])
        dp[i+1][j+1] += dp[i][j] * P[i]

ans = 0.0
for i in range(N//2+1, N+1):
    ans += dp[N][i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5+10)
input = sys.stdin.readline
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h,w): return [[i for j in range(w)] for k in range(h)]
MOD = 1000000007
INF = float("inf")

N = I()
p = [float(x) for x in input().split()]

dp = FILL(0,N+1,N+1)
dp[0][0] = 1
dp[0][1] = 0
for i in range(N):
    for f in range(N+1):
        if f == 0:
            dp[i+1][f] = dp[i][f]*(1-p[i])
        else:
            dp[i+1][f] = dp[i][f]*(1-p[i]) + dp[i][f-1]*p[i]
ans = 0
for i in range(N+1):
    if i>N/2:
        ans += dp[N][i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = list(map(float, input().split()))

dp = [[0.0] * (N+1) for _ in range(N+1)]

dp[0][0] = 1

for i in range(1, N+1):
    for j in range(i+1):
        dp[i][j] = dp[i-1][j] * (1-P[i-1])
        if j > 0:
            dp[i][j] += dp[i-1][j-1] * P[i-1]

ans = 0.0
for i in range(N//2+1, N+1):
    ans += dp[N][i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(float,input().split(" ")))
mat=[]

for i in range(n):
	temp=[0]*(i+1+1)
	if(i==0):
		temp[0]=1-p[0]
		temp[1]=p[0]
	else:
		prev=mat[-1]

		for j in range(len(prev)):
			temp[j]+=prev[j]*(1-p[i])
			temp[j+1]+=prev[j]*p[i]


	mat.append(temp)
ans=0
temp=mat[-1]
for i in range((n//2)+1,len(temp)):
	ans+=temp[i]
# print(temp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(float,input().split()))
dp=[[0]*(n//2+2) for i in range(n)] #dp[i][j]=i番目までに裏がj枚出る確率
dp[0][0]=p[0]
dp[0][1]=1-p[0]
for i in range(1,n):
    dp[i][0]=dp[i-1][0]*p[i]
    for j in range(1,n//2+1):
        dp[i][j]=dp[i-1][j]*p[i]+dp[i-1][j-1]*(1-p[i])
ans=0
for i in range(n//2+1):
    ans+=dp[-1][i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(float,input().split()))
dp=[[0]*(n+1) for i in range(n)] #dp[i][j]=i番目までに裏がj枚出る確率
dp[0][0]=p[0]
dp[0][1]=1-p[0]
for i in range(1,n):
    dp[i][0]=dp[i-1][0]*p[i]
    for j in range(1,n+1):
        dp[i][j]=dp[i-1][j]*p[i]+dp[i-1][j-1]*(1-p[i])
ans=0
for i in range(n//2+1):
    ans+=dp[-1][i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(float,input().split()))

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(n):
        dp[i+1][j+1] += dp[i][j]*p[i]
        dp[i+1][j] += dp[i][j]*(1-p[i])
res = 0
for j in range((n+1)//2,n+1):
    res += dp[n][j]
print(res)

Submission status: Time Limit Exceeded

Solution code:

n = int(input())

A = [float(x) for x in input().split()]

B = [0] * (n + 1)

B[0] = 1

for x in A:
    for i in range(n, 0, -1):
        B[i] = (B[i - 1] * x + B[i] * (1 - x))
    B[0] *= (1 - x)

print("%.10f" % sum(B[n // 2 + 1:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(float, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

N = ii()
P = li()

dp = dp2(0, N+1, N)
dp[0][0] = 1 - P[0]
dp[0][1] = P[0]

for i in range(1, N):
    for j in range(i+1):
        dp[i][j] += dp[i-1][j] * (1-P[i])
        dp[i][j+1] += dp[i-1][j] * P[i]

print(sum(dp[N-1][(N//2+1):]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(float,input().split()))
dp = [[0 for _ in range(n+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
    dp[i][0] = dp[i-1][0]*(1-l[i-1])
for i in range(1,n+1):
    for j in range(1,n+1):
        dp[i][j] = dp[i-1][j]*(1-l[i-1]) + dp[i-1][j-1]*l[i-1]
ans = 0
for i in range(n//2+1,n+1):
    ans+=dp[n][i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(float,input().split()))
#dp[i][j] i tells u i coins from 0, j tells u j heads 
#dp[n+1][n+1]
dp=[[0 for i in range(0,n+1)]for j in range(n+1)]

dp[0][0]=1.0
# for i in range(1,n+1):
#     dp[0][i]=0.0
for i in range(1,n+1):
    for j in range(0,n+1):
        if(j==0):
            dp[i][j]=(1.0-p[i-1])*dp[i-1][j]
        else:
            dp[i][j]=p[i-1]*dp[i-1][j-1]+(1.0-p[i-1])*dp[i-1][j]

k=(n//2)+1
ans=0.0
for i in range(k,n+1):
    ans+=dp[n][i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = [float(x) for x in input().split()]

dp = [[0]*(n+1) for _ in range(n)]  #dp[i][j] Prob of j heads in i tries
dp[0][1] = p[0]
dp[0][0] = 1-p[0]

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

sum = 0
for i in range(n + 1):
    if i > n - i:
        sum += dp[n-1][i]
print(sum)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

P=list(map(float,input().split()))

dp=[[0 for i in range(N+1)] for j in range(N+1)]
dp[0][0]=1

for i in range(N):
    for j in range(N-i):
        dp[i+1][j]+=dp[i][j]*P[i+j]
        dp[i][j+1]+=dp[i][j]*(1-P[i+j])        

ans=0
start=(N+1)//2
j=0
for i in range(start,N+1)[::-1]:
    ans+=dp[i][j]
    j+=1
print(ans)
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(float,input().split()))
dp = [[0]*(n+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
    for j in range(n+1):
        dp[i][j] = dp[i-1][j]*(1-l[i-1])+dp[i-1][j-1]*l[i-1]
print(sum(dp[-1][n//2+1:]))

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(float,input().split()))

n = ii()
p =li()

dp = [[0]*(n+2) for i in range(n)]
# dp[0] = 1
dp[0][1] = 1-p[0]
dp[0][2] = p[0]
# print(dp)
for i in range(1,n):
    for j in range(1,i+3):
            dp[i][j] = dp[i-1][j-1] * p[i] + dp[i-1][j] * (1-p[i])
    # print(dp)
    # print(sum(dp))
print(sum(dp[n-1][((n+1)//2)+1:]))

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(float,input().split()))

n = ii()
p =li()

dp = [0]*(n+2)
# dp[0] = 1
dp[1] = 1-p[0]
dp[2] = p[0]
# print(dp)
for i in range(1,n):
    for j in range(1,i+3)[::-1]:
            dp[j] = dp[j-1] * p[i] + dp[j] * (1-p[i])
    # print(dp)
    # print(sum(dp))
print(sum(dp[((n+1)//2)+1:]))

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(float,input().split()))

n = ii()
p =li()

dp = [0]*(n+1)
dp[0] = 1-p[0]
dp[1] = p[0]

for i in range(1,n):
    for j in range(i+2)[::-1]:
        if j==0:
            dp[0] = dp[0] * (1-p[i])
        else:
            dp[j] = dp[j-1] * p[i] + dp[j] * (1-p[i])
print(sum(dp[(n+1)//2:]))

Submission status: Time Limit Exceeded

Solution code:
from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]

n = val()
l = li4()
mihe = n//2 + 1


sumarray = [0 for i in range(n)] + [1]

dp = [0]*(n + 1)

for i in range(n-1,-1,-1):
    dp = [0] *(n + 1)
    for j in range(n-1,i - 1,-1):
        dp[j] += ( l[i] / (1 - l[i]) ) * sumarray[j + 1]

    
    for j in range(n):sumarray[j] += dp[j]
    # print(dp)


# for i in dp:print(*i)
# print(*sumarray)

curr = 1
for i in l:curr *= (1 - i)
ans = 0
for i in sumarray[:-mihe]:
    ans += i * curr
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[float(i) for i in input().split()]
dp=[0 for i in range(n+1)]
dp[0]=1
for k in range(1,n+1):
    p=a[k-1]
    for i in range(k,-1,-1):
        if i==0:
            dp[i]=dp[i]*(1-p)
        else:
            dp[i]=dp[i-1]*p+dp[i]*(1-p)
s=0
for i in range(n+1):
    if i>n-i:
        s+=dp[i]
print(s)

Submission status: Time Limit Exceeded

Solution code:
from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]

n = val()
l = li4()
mihe = n//2 + 1


dp = [[0 for i in range(n)] for j in range(n + 1)]
sumarray = [1 for i in range(n + 1)]



for i in range(n-1,-1,-1):
    for j in range(n-1,i - 1,-1):
        dp[i][j] = ( l[i] / (1 - l[i]) ) * sumarray[j + 1]

    for j in range(n):
        if sumarray[j] != 1:
            sumarray[j] += dp[i][j]
        else:
            sumarray[j] = dp[i][j]



# for i in dp:print(*i)
# print(*sumarray)

curr = 1
for i in l:curr *= (1 - i)
ans = 0
for i in sumarray[:-mihe]:
    ans += i * curr
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]

n = val()
l = li4()
mihe = n//2 + 1


dp = [[0 for i in range(n)] for j in range(n + 1)]
sumarray = [1 for i in range(n + 1)]



for i in range(n-1,-1,-1):
    for j in range(n-1,i - 1,-1):
        dp[i][j] = round(( l[i] / (1 - l[i]) ) * sumarray[j + 1],10)

    for j in range(n):
        if sumarray[j] != 1:
            sumarray[j] = round(sumarray[j] + dp[i][j],10)
        else:
            sumarray[j] = round(dp[i][j],10)



# for i in dp:print(*i)
# print(*sumarray)

curr = 1
for i in l:curr = round(curr * (1 - i),10)

print(sum(round(j * curr,10) for j in sumarray[:- mihe]))

Submission status: Time Limit Exceeded

Solution code:
from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [Decimal(i) for i in input().rstrip('\n').split(' ')]

n = val()
l = li4()
mihe = n//2 + 1


dp = [[Decimal(0) for i in range(n)] for j in range(n + 1)]
sumarray = [Decimal(1) for i in range(n + 1)]



for i in range(n-1,-1,-1):
    for j in range(n-1,i - 1,-1):
        dp[i][j] = ( l[i] / (1 - l[i]) ) * sumarray[j + 1]

    for j in range(n):
        if sumarray[j] != 1:
            sumarray[j] += dp[i][j]
        else:
            sumarray[j] = dp[i][j]



# for i in dp:print(*i)
# print(*sumarray)

curr = 1
for i in l:curr *= (1 - i)

print(sum(j * curr for j in sumarray[:- mihe]))

Submission status: Time Limit Exceeded

Solution code:
from decimal import *
getcontext().prec = 20
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [Decimal(i) for i in input().rstrip('\n').split(' ')]

n = val()
l = li4()
mihe = n//2 + 1


dp = [[Decimal(0) for i in range(n)] for j in range(n + 1)]
sumarray = [Decimal(1) for i in range(n + 1)]



for i in range(n-1,-1,-1):
    for j in range(n-1,i - 1,-1):
        dp[i][j] = ( l[i] / (1 - l[i]) ) * sumarray[j + 1]

    for j in range(n):
        if sumarray[j] != 1:
            sumarray[j] += dp[i][j]
        else:
            sumarray[j] = dp[i][j]



# for i in dp:print(*i)
# print(*sumarray)

curr = 1
for i in l:curr *= (1 - i)

print(sum(j * curr for j in sumarray[:- mihe]))

Submission status: Time Limit Exceeded

Solution code:
from decimal import *
getcontext().prec = 100
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [Decimal(i) for i in input().rstrip('\n').split(' ')]

n = val()
l = li4()
mihe = n//2 + 1


dp = [[Decimal(0) for i in range(n)] for j in range(n + 1)]
sumarray = [Decimal(1.0000000000000000000000000000000000000000000000000000000000000000000000000) for i in range(n + 1)]



for i in range(n-1,-1,-1):
    for j in range(n-1,i - 1,-1):
        dp[i][j] = ( l[i] / (1 - l[i]) ) * sumarray[j + 1]

    for j in range(n):
        if sumarray[j] != 1:
            sumarray[j] += dp[i][j]
        else:
            sumarray[j] = dp[i][j]



# for i in dp:print(*i)
# print(*sumarray)

curr = 1
for i in l:curr *= (1 - i)

print(sum(j * curr for j in sumarray[:- mihe]))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
p = list(map(float, input().split()))
dp = [0] * (len(p) + 1)
dp[0] = 1
answer = 0
for curr_toss in range(1, len(p) + 1):
    for hd_tn in range(curr_toss, 0, -1):
        dp[hd_tn] = p[curr_toss - 1] * dp[hd_tn - 1] + (1 - p[curr_toss - 1]) * dp[hd_tn]
    dp[hd_tn - 1] = (1 - p[curr_toss - 1]) * dp[hd_tn - 1]

print(sum(dp[N//2+1:]))

Submission status: Time Limit Exceeded

Solution code:
# cook your dish here
N = int(input())
p = list(map(float, input().split()))
dp = [0]*(len(p)+1)
dp[0] = 1
answer = 0
for curr_toss in range(1, len(p)+1):
    for hd_tn in range(curr_toss, 0,-1):
        dp[hd_tn] = p[curr_toss-1]*dp[hd_tn-1] + (1-p[curr_toss-1])*dp[hd_tn]
    dp[hd_tn-1] = (1-p[curr_toss-1])*dp[hd_tn-1]
   
for heads in range(1, len(p)+1):
    tails = len(p)-heads
    if heads > tails:
        answer += dp[heads]
print(answer)

Submission status: Time Limit Exceeded

Solution code:
# cook your dish here
N = int(input())
p = list(map(float, input().split()))
#p = [0.42, 0.01, 0.42, 0.99, 0.42]
dp = [0]*(len(p)+1)
dp[0] = 1
answer = 0
for curr_toss in range(1, len(p)+1):
    for hd_tn in range(curr_toss, 0,-1):
        #print(curr_toss, hd_tn)
        dp[hd_tn] = p[curr_toss-1]*dp[hd_tn-1] + (1-p[curr_toss-1])*dp[hd_tn]
    dp[hd_tn-1] = (1-p[curr_toss-1])*dp[hd_tn-1]
    #print(dp)
    
for heads in range(1, len(p)+1):
    tails = len(p)-heads
    if heads > tails:
        answer += dp[heads]
print(answer)

Submission status: Time Limit Exceeded

Solution code:
# cook your dish here
N = int(input())
p = list(map(float, input().split()))
#p = [0.42, 0.01, 0.42, 0.99, 0.42]
dp = [0] * (len(p)+1)
dp[0] = 1
#[070 , 0.30]
answer = 0
for toss in range(1, N+1):
    new_dp = [0] * (len(p)+1)
    new_dp[0] = (1-p[toss-1])* dp[0]
    for i in range(1, toss+1):
	    #print(toss, i, p[i-1],  dp[i-1],1-p[i-1], dp[i] )
	    new_dp[i] = p[toss-1] * dp[i-1] + (1-p[toss-1])*dp[i]
    #print(new_dp)
    dp = new_dp

for heads in range(1, len(new_dp)):
    tails = len(new_dp)-1-heads
    if heads > tails:
        answer +=dp[heads]
        
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
P=list(map(float,input().split()))
dp=[[0]*(N+1) for i in range(N+1)]
dp[0][0]=1
for i in range(1,N+1):
  for j in range(N+1):
    dp[i][j]=dp[i-1][j-1]*P[i-1]+dp[i-1][j]*(1-P[i-1])
ans=0

for i in range(N//2+1,N+1):
  ans+=dp[-1][i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(float, input().split()))

dp = [[0]*3100 for _ in range(3100)]

N = int(input())
P = input_nums()

dp[0][0] = 1.0

for i in range(N):
    for j in range(i+1):
        dp[i+1][j+1] += dp[i][j] * P[i]
        dp[i+1][j] += dp[i][j] * (1-P[i])

res = 0.0
a = ((N+1)//2)
for j in range(a, N+1):
    res += dp[N][j]
print(res)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil

n = int(input())
parr = list(map(float,input().split()))

dp = [[0 for i in range(n+1)] for j in range(n+1)]
dp[0][0] = 1

for i in range(1,n+1):
    for j in range(0,n+1):
        if j == 0:
            dp[i][j] = dp[i-1][j] * (1-parr[i-1])
        else:
            dp[i][j] = dp[i-1][j-1] * parr[i-1] + dp[i-1][j] * (1-parr[i-1])
print(sum(dp[-1][ceil(n/2):]))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
p=list(map(float, input().split()))
dp=[[0]*(N+1) for _ in range(N+1)]
dp[0][0]=1
for i in range(N):
    for j in range(N):
        dp[i+1][j+1]+=dp[i][j]*p[i]
        dp[i+1][j]+=dp[i][j]*(1-p[i])
print(sum(dp[N][N//2+1:]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(float, input().split()))
dp = [[0] * (n+1) for i in range(n+1)]
dp[0][0] = 1.0
for i in range(n):
    for j in range(0, i+1):
        dp[i + 1][j + 1] += dp[i][j] * p[i]
        dp[i+1][j] += dp[i][j]*(1-p[i])

ans = 0
for i in range((n + 1) // 2):
    ans += dp[n][i]

print(1-ans)

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  p=LF()
  p=[0]+p

  dp=[[0]*(n+1) for _ in range(n+1)]
  dp[0][0]=1

  # dp[i][j]=i個目までに表がj回出る確率
  for i in range(1,n+1):
    for j in range(n+1):
      if j>0:
        dp[i][j]=dp[i-1][j]*(1-p[i])+dp[i-1][j-1]*p[i]
      else:
        dp[i][j]=dp[i-1][j]*(1-p[i])

  ans=0
  for j in range(n//2+1,n+1):
    ans+=dp[n][j]
  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
# dp[i][j]：i枚で表がj枚になる確率
# 1 - sum(:dp[N][(N+1)//2])を求めればいいため，dp[N][(N+1)//2:]は求める必要が無い

N = int(input())
P = list(map(float, input().split()))
overhalf_N = (N+1)//2

dp = [[0]*(N+1) for _ in range(N+1)] # dp[i][j]：i枚で表がj枚になる確率
dp[0][0] = 1
for i in range(N):
  for j in range(min(i+1, overhalf_N)):
    dp[i+1][j+1] += dp[i][j] * P[i]
    dp[i+1][j] += dp[i][j] * (1-P[i])

print(1-sum(dp[N][:overhalf_N]))

Submission status: Time Limit Exceeded

Solution code:
# dp[i][j]：i枚で表がj枚になる確率
# sum(dp[N][(N+1)//2:])を求めればいいため，dp[N][:(N+1)//2]は求める必要が無い
import sys
sys.setrecursionlimit(10 ** 9)

def rec(i,j):
  if dp[i][j] != -1:
    return dp[i][j]
  else:
    dp[i][j] = rec(i-1,j-1) * P[i-1] + rec(i-1,j) * (1-P[i-1]) if j > 0 else rec(i-1,j) * (1-P[i-1])
    return dp[i][j]

N = int(input())
P = list(map(float, input().split()))

#dp = [[0]*(N+1)] + [[-1]*(N+1) for _ in range(N)]
dp = [[-1]*(N+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
  dp[i][i+1] = 0

print(sum([rec(N, i) for i in range((N+1)//2, N+1)]))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = list(map(float, input().split()))

dp = [[0]*(N+1) for _ in range(N+1)] # dp[i][j]：i枚で表がj枚になる確率
dp[0][0] = 1
for i in range(N):
  for j in range(i+1):
    #dp[i][j] = dp[i-1][j-1] * P[i-1] + dp[i-1][j] * (1-P[i-1])
    dp[i+1][j+1] += dp[i][j] * P[i]
    dp[i+1][j] += dp[i][j] * (1-P[i])

print(sum(dp[N][(N+1)//2:]))