Buggy python submission (verdict: Time Limit Exceeded):
# 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]))


Fixed submission:
# dp[i][j]：i枚で表がj枚になる確率
# 1 - sum(:dp[N][(N+1)//2])を求めればいいため，dp[N][(N+1)//2:]は求める必要が無い
# jが大きい順に更新すればdp[i][j]のjを保持する必要はない

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

dp = [0]*(N+1) # dp[N][j]：N枚で表がj枚になる確率

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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
# 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)]))

Fixed submission:
# dp[i][j]：i枚で表がj枚になる確率
# 1 - sum(:dp[N][(N+1)//2])を求めればいいため，dp[N][(N+1)//2:]は求める必要が無い
# jが大きい順に更新すればdp[i][j]のjを保持する必要はない

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

dp = [0]*(N+1) # dp[N][j]：N枚で表がj枚になる確率

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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
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:]))

Fixed submission:
# dp[i][j]：i枚で表がj枚になる確率
# 1 - sum(:dp[N][(N+1)//2])を求めればいいため，dp[N][(N+1)//2:]は求める必要が無い
# jが大きい順に更新すればdp[i][j]のjを保持する必要はない

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

dp = [0]*(N+1) # dp[N][j]：N枚で表がj枚になる確率

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

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

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