Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
import numpy as np

def count_question():
    n, q = list(map(int, input().split()))
    s = input()
    lr = [list(map(int, input().split())) for i in range(q)]

    for i in range(q):
        print(s[lr[i][0]-1:lr[i][1]].count("AC"))

count_question()


Fixed submission:
import sys
input = sys.stdin.readline
import numpy as np
import bisect
left = bisect.bisect_left
right = bisect.bisect_right

def question():
    n, q = list(map(int, input().split()))
    s = input()
    lr = [list(map(int, input().split())) for i in range(q)]
    a = [i for i in range(n-1) if s[i:i+2]=="AC"]

    for i in range(q):
        left_index = left(a, lr[i][0]-1)
        right_index = right(a, lr[i][1]-2)
        print(right_index - left_index)

question()

Buggy python submission (verdict: Time Limit Exceeded):

import sys
input = sys.stdin.readline
import numpy as np

def question():
    n, q = list(map(int, input().split()))
    s = input()
    lr = [list(map(int, input().split())) for i in range(q)]
    a = [1 if (s[i]=="A" and s[i+1] =="C") else 0 for i in range(n-1)]
    a = np.array(a)
    for i in range(q):
        print(np.sum(a[lr[i][0]-1:lr[i][1]-1]))

question()


Fixed submission:
import sys
input = sys.stdin.readline
import numpy as np
import bisect
left = bisect.bisect_left
right = bisect.bisect_right

def question():
    n, q = list(map(int, input().split()))
    s = input()
    lr = [list(map(int, input().split())) for i in range(q)]
    a = [i for i in range(n-1) if s[i:i+2]=="AC"]

    for i in range(q):
        left_index = left(a, lr[i][0]-1)
        right_index = right(a, lr[i][1]-2)
        print(right_index - left_index)

question()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


def question():
    n, q = list(map(int, input().split()))
    s = input()
    lr = [list(map(int, input().split())) for i in range(q)]
    a = [(s[i]=="A" and s[i+1] =="C") for i in range(n-1)]
    for i in range(q):
        print(sum(a[lr[i][0]-1:lr[i][1]-1]))


question()

Fixed submission:
import sys
input = sys.stdin.readline
import numpy as np
import bisect
left = bisect.bisect_left
right = bisect.bisect_right

def question():
    n, q = list(map(int, input().split()))
    s = input()
    lr = [list(map(int, input().split())) for i in range(q)]
    a = [i for i in range(n-1) if s[i:i+2]=="AC"]

    for i in range(q):
        left_index = left(a, lr[i][0]-1)
        right_index = right(a, lr[i][1]-2)
        print(right_index - left_index)

question()
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
 
s = input()
 
x = []
 
for i in range(n):
    x.append(s[i])
 
m = len(set(x))
 
import itertools
 
cnt = 0
for i in range(1, m+1):
    p = list(itertools.combinations(s,i))
    cnt += sum(len(pp) == len(set(pp)) for pp in p)
 
print(cnt)

Fixed submission:

n = int(input())

s = input()

x = []

for i in range(n):
    x.append(s[i])

import collections

clist = collections.Counter(x)

y = list(clist.values())

cnt = 1

for item in y:
    cnt = cnt * (item + 1)

cnt = cnt - 1
cnt = cnt % (10 ** 9 + 7)
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

s = input()

x = []

for i in range(n):
    x.append(s[i])

m = len(set(x))

import itertools

cnt = 0
for i in range(1, m+1):
    p = list(itertools.combinations(s,i))
    cnt += sum(len(pp) == len(set(pp)) for pp in p)

print(cnt)


Fixed submission:

n = int(input())

s = input()

x = []

for i in range(n):
    x.append(s[i])

import collections

clist = collections.Counter(x)

y = list(clist.values())

cnt = 1

for item in y:
    cnt = cnt * (item + 1)

cnt = cnt - 1
cnt = cnt % (10 ** 9 + 7)
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

s = input()

x = []

for i in range(n):
    x.append(s[i])
    
m = len(set(x))

import itertools

cnt = 0
for i in range(1,m+1):
    p = list(itertools.combinations(s,i))

    for pp in p:
        if len(pp) == len(set(pp)):
            cnt = cnt + 1

print(cnt)


Fixed submission:

n = int(input())

s = input()

x = []

for i in range(n):
    x.append(s[i])

import collections

clist = collections.Counter(x)

y = list(clist.values())

cnt = 1

for item in y:
    cnt = cnt * (item + 1)

cnt = cnt - 1
cnt = cnt % (10 ** 9 + 7)
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

s = input()

x = []

for i in range(n):
    x.append(s[i])

import itertools

cnt = 0
for i in range(1,n+1):
    p = list(itertools.combinations(s,i))

    for pp in p:
        if len(pp) == len(set(pp)):
            cnt = cnt + 1

print(cnt)


Fixed submission:

n = int(input())

s = input()

x = []

for i in range(n):
    x.append(s[i])

import collections

clist = collections.Counter(x)

y = list(clist.values())

cnt = 1

for item in y:
    cnt = cnt * (item + 1)

cnt = cnt - 1
cnt = cnt % (10 ** 9 + 7)
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
a, b = map(int, input().split())

x = 0

for i in range(a, b+1):
    x = x ^ i

print(x)

Fixed submission:
a, b = map(int, input().split())

N = b - a + 1

if a%2 == 0:
    if N%4 == 0:
        print(0)
    elif N%4 == 1:
        print(b)
    elif N%4 == 2:
        print(1)
    else:
        print(b + 1)
else:
    if N%4 == 0:
        print(a ^ b ^ 1)
    elif N%4 == 1:
        print(a)
    elif N%4 == 2:
        print(a ^ b)
    else:
        print(a ^ 1)

Buggy python submission (verdict: Time Limit Exceeded):
a, b = map(int, input().split())

x = []

for i in range(a, b+1):
    x.append(format(i, "b"))

l = len(x[b - a])

ans = ""

for i in range(1, l+1):
    sum = 0
    for j in range(b-a+1):
        if len(x[j]) >= i:
            sum = sum + int(x[j][-i])
    if sum % 2 == 0:
        ans = "0" + ans
    else:
        ans = "1" + ans

print(int(ans, 2))

Fixed submission:
a, b = map(int, input().split())

N = b - a + 1

if a%2 == 0:
    if N%4 == 0:
        print(0)
    elif N%4 == 1:
        print(b)
    elif N%4 == 2:
        print(1)
    else:
        print(b + 1)
else:
    if N%4 == 0:
        print(a ^ b ^ 1)
    elif N%4 == 1:
        print(a)
    elif N%4 == 2:
        print(a ^ b)
    else:
        print(a ^ 1)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()

complete = False
ans = 0

while complete == False:
    complete = True
    i = 0
    while i < len(s) - 1:
        if s[i] != s[i+1]:
            s = s[:i] + s[i+2:]
            ans = ans + 2
            complete = False
        i = i + 1

print(ans)

Fixed submission:
s = input()

one = s.count("1")
zero = s.count("0")

print(2 * min(one, zero))
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, a, b, c = map(int, input().split())
    arr = [int(input()) for i in range(n)]

    min_cost = float("inf")
    for i in range(1, 2 ** n):
        bin_i = "{:08b}".format(i)[::-1]
        arr_i = [arr[x] for x in range(n) if bin_i[x] == "1"]
        cost_i = (len(arr_i) - 1) * 10
        sum_i = sum(arr_i)
    
        for j in range(1, 2 ** n):
            bin_j = "{:08b}".format(j)[::-1]
    
            if any([x == "1" and y == "1" for x, y in zip(bin_i, bin_j)]):
                continue
    
            arr_j = [arr[x] for x in range(n) if bin_j[x] == "1"]
            cost_j = (len(arr_j) - 1) * 10
            sum_j = sum(arr_j)
    
            for k in range(1, 2 ** n):
                bin_k = "{:08b}".format(k)[::-1]
    
                if any([x == "1" and y == "1" for x, y in zip(bin_i, bin_k)]):
                    continue
    
                if any([x == "1" and y == "1" for x, y in zip(bin_j, bin_k)]):
                    continue
    
                arr_k = [arr[x] for x in range(n) if bin_k[x] == "1"]
    
                cost_k = (len(arr_k) - 1) * 10
                sum_k = sum(arr_k)
    
                cost = abs(sum_i - a) + abs(sum_j - b) + abs(sum_k - c) + cost_i + cost_j + cost_k
    
                if min_cost > cost:
                    min_cost = cost
    
    print(min_cost)


main()


Fixed submission:
from itertools import product


def main():
    n, *target = map(int, input().split())
    arr = [int(input()) for i in range(n)]

    tests = product("0123", repeat=n)
    test_arr = [[] for _ in range(3)]
    min_cost = float("inf")

    for test in tests:
        cost = 0

        if "1" not in test or "2" not in test or "3" not in test:
            continue

        for i in range(3):
            test_arr[i] = [arr[x] for x in range(n) if test[x] == str(i + 1)]
            cost += (len(test_arr[i]) - 1) * 10
            cost += abs(sum(test_arr[i]) - target[i])

        if min_cost > cost:
            min_cost = cost

    print(min_cost)


main()
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())

a = [list(map(int, input().split())) for i in range(n)]

x = [True] * m

for i in a:
    y = i[0]
    xx = [False] * m
    for j in range(y):
        xx[i[j + 1]] = True
    for j in range(m):
        if xx[j] == False:
            x[j] = False

print(sum(x))


Fixed submission:
n, m = map(int, input().split())

S = set(range(1, m + 1))

for i in range(n):
    K, *a = map(int, input().split())
    S = S & set(a)

print(len(S))

Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
 
S = set(range(1, m+1))
 
for i in range(n):
  K, *a = map(int, input().split())
  S = S & set(A)
 
print(len(S))

Fixed submission:
n, m = map(int, input().split())

S = set(range(1, m + 1))

for i in range(n):
    K, *a = map(int, input().split())
    S = S & set(a)

print(len(S))

Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())

a = [list(map(int, input().split())) for i in range(n)]

x = [True] * m

for i in a:
    y = i[0]
    xx = [False] * m
    for j in range(y):
        x[i[j + 1]] = True
    for j in range(m):
        if xx[j] == False:
            x[j] = False

print(sum(x))


Fixed submission:
n, m = map(int, input().split())

S = set(range(1, m + 1))

for i in range(n):
    K, *a = map(int, input().split())
    S = S & set(a)

print(len(S))

Buggy python submission (verdict: Runtime Error):
n, m = int(input())
a = [list(map(int, input().split())) for i in range(n)]

x = [True] * m

for i in a:
    y = i[0]
    xx = [False] * m
    for j in range(y):
        x[i[j + 1]] = True
    for j in range(m):
        if xx[j] == False:
            x[j] = False

print(sum(x))

Fixed submission:
n, m = map(int, input().split())

S = set(range(1, m + 1))

for i in range(n):
    K, *a = map(int, input().split())
    S = S & set(a)

print(len(S))

Buggy python submission (verdict: Runtime Error):
n, m = int(input())

S = set(range(1, m+1))

for i in range(n):
  K, *a = map(int, input().split())
  S = S & set(A)

print(len(S))

Fixed submission:
n, m = map(int, input().split())

S = set(range(1, m + 1))

for i in range(n):
    K, *a = map(int, input().split())
    S = S & set(a)

print(len(S))

Buggy python submission (verdict: Runtime Error):
n, m = int(input())
a = [list(map(int, input().split())) for i in range(n)]

x = [True] * m

for i in a:
  y = i[0]
  xx = [False] * m
  for j in range(y):
    x[i[j+1]] = True
  for j in range(m):
    if xx[j] = False:
      x[j] = False

print(sum(x))

Fixed submission:
n, m = map(int, input().split())

S = set(range(1, m + 1))

for i in range(n):
    K, *a = map(int, input().split())
    S = S & set(a)

print(len(S))
Buggy python submission (verdict: Runtime Error):

n, _ = map(int,input().split())
a = list(map(int, input().split()))
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
dp = [0] * (n + 1)


def calc(num, new):
    if num == 0:
        return 0
    num_str = str(num)
    new_str = str(new)
    sstr_list = list(str(num)) + list(str(new))
    sstr_list.sort(reverse=True)
    return int("".join(sstr_list))


s = set()
for x in range(2, 8):
    for i in a:
        if x > dic[i]:
            dp[x] = max(dp[x], calc(dp[x - dic[i]], i))
        elif x == dic[i]:
            dp[x] = max(dp[x], i)
    if dp[x]:
        for num in str(dp[x]):
            s.add(int(num))

for x in range(n + 1):
    for i in s:
        if x > dic[i]:
            dp[x] = max(dp[x], calc(dp[x - dic[i]], i))

print(dp[n])


Fixed submission:
n, _ = map(int, input().split())
L = list(map(int, input().split()))
weight = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1] * (n+1)
dp[0] = 0

for i in range(n+1):
    for a in L:
        if i+weight[a] < n+1:
            dp[i+weight[a]] = max(dp[i+weight[a]], dp[i]*10+a)

print(dp[n])

Buggy python submission (verdict: Runtime Error):

n, _ = map(int,input().split())
a = list(map(int, input().split()))
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
dp = [0] * (n + 1)


def calc(num, new):
    if num == 0:
        return 0
    num_str = str(num)
    new_str = str(new)
    sstr_list = list(str(num)) + list(str(new))
    sstr_list.sort(reverse=True)
    return int("".join(sstr_list))


for i in a:
    dp[dic[i]] = max(dp[dic[i]], i)

for x in range(n + 1):
    for i in a:
        if x >= dic[i]:
            dp[x] = max(dp[x], calc(dp[x - dic[i]], i))

print(dp[n])

Fixed submission:
n, _ = map(int, input().split())
L = list(map(int, input().split()))
weight = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1] * (n+1)
dp[0] = 0

for i in range(n+1):
    for a in L:
        if i+weight[a] < n+1:
            dp[i+weight[a]] = max(dp[i+weight[a]], dp[i]*10+a)

print(dp[n])
Buggy python submission (verdict: Runtime Error):
n = int(input())
x = list(map(int, input().split()))

x.sort()

print("Yes" if x[-1] < sum(x[:-1] else "No")

Fixed submission:
import sys

n = int(input())

l = list(map(int, input().split()))

for i in range(n):
    if l[i] >= sum(l) - l[i]:
        print("No")
        sys.exit()

print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
tds = [list(map(int, input().split())) for _ in range(n)]

tds.sort(key=lambda x:x[1])

arr = [0] * (n + 1)

for idx, td in enumerate(tds):
    t, d = td
    arr[t] = [d, n - idx - 1]

tds = [y for x, y in tds[::-1]]

base = 0
res = 0
kind = 0

new_arr = []
for xy in arr:
    if not xy:
        continue
    new_arr.append(xy)

new_arr.sort(reverse=True)

for x, y in new_arr:
    kind += 1
    base += x
    if y < k:
        tds[y] = 0
    else:
        while tds[k - 1] == 0:
            k -= 1
            if k == 0:
                break
        k -= 1
        if k <= 0:
            break
    res = max(res, kind ** 2 + base + sum(tds[:k]))

print(res)


Fixed submission:
n, k = map(int, input().split())
tds = [list(map(int, input().split())) for _ in range(n)]

tds.sort(key=lambda x:x[1])

arr = {}
for idx, td in enumerate(tds):
    t, d = td
    arr[t] = [d, n - idx - 1]

tds = [y for x, y in tds[::-1]]

base = 0
rest = sum(tds[:k])
res = 0
kind = 0
new_arr = sorted(arr.values(), reverse=True)

for x, y in new_arr:
    kind += 1
    base += x
    if y < k:
        rest -= x
        tds[y] = 0
    else:
        while k >= 1 and tds[k - 1] == 0:
            k -= 1
        rest -= tds[k - 1]
        k -= 1
        if k <= 0:
            break
    res = max(res, kind ** 2 + base + rest)

if k >= 0:
    res = max(res, kind ** 2 + base + rest)

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
tds = [list(map(int, input().split())) for _ in range(n)]

tds.sort(key=lambda x:x[1])

arr = [0] * (n + 1)

for idx, td in enumerate(tds):
    t, d = td
    arr[t] = [d, n - idx - 1]

tds = [y for x, y in tds[::-1]]

base = 0
res = 0
kind = 0

new_arr = []
for xy in arr:
    if not xy:
        continue
    new_arr.append(xy)

new_arr.sort(reverse=True)

for x, y in new_arr:
    kind += 1
    base += x
    if y < k:
        tds[y] = 0
    else:
        while tds[k - 1] == 0:
            k -= 1
            if k == 0:
                break
        k -= 1
        if k <= 0:
            break
    res = max(res, kind ** 2 + base + sum(tds[:k]))

print(res)


Fixed submission:
n, k = map(int, input().split())
tds = [list(map(int, input().split())) for _ in range(n)]

tds.sort(key=lambda x:x[1])

arr = {}
for idx, td in enumerate(tds):
    t, d = td
    arr[t] = [d, n - idx - 1]

tds = [y for x, y in tds[::-1]]

base = 0
rest = sum(tds[:k])
res = 0
kind = 0
new_arr = sorted(arr.values(), reverse=True)

for x, y in new_arr:
    kind += 1
    base += x
    if y < k:
        rest -= x
        tds[y] = 0
    else:
        while k >= 1 and tds[k - 1] == 0:
            k -= 1
        rest -= tds[k - 1]
        k -= 1
        if k <= 0:
            break
    res = max(res, kind ** 2 + base + rest)

if k >= 0:
    res = max(res, kind ** 2 + base + rest)

print(res)
Buggy python submission (verdict: Runtime Error):
n = int(input())
h = list(map(int, input().split()))

import numpy as np

d = [0] * n

d[1] = np.abs(h[1] - h[0])

for i in range(n-2):
    d[i+2] = min(d[i]+np.abs(h[i+2]-h[i]), d[i+1]+np.abs(h[i+2]-h[i+1]))



import pandas as pd
df = pd.DataFrame(d)

print(d[n-1])

Fixed submission:
n = int(input())
h = list(map(int, input().split()))

import numpy as np

d = [0] * n

d[1] = np.abs(h[1] - h[0])

for i in range(n-2):
    d[i+2] = min(d[i]+np.abs(h[i+2]-h[i]), d[i+1]+np.abs(h[i+2]-h[i+1]))

print(d[n-1])
Buggy python submission (verdict: Runtime Error):
def knapsack():
    n, max_w = map(int, input().split())
    dp = defaultdict(int)
    dp[0] = 0
    for _ in range(n):
        w, v = map(int, input().split())
        for item in list(dp.keys()):
            dp[item+w] = max(dp[item] + v, dp[item+w])
    max_v = 0
    for w, v in dp.items():
        if w <= max_w:
            max_v = max(v, max_v)
    print(max_v)
    

knapsack()

Fixed submission:
import sys
input = sys.stdin.readline

N, W = [int(i) for i in input().split()]

def ans(N, W):
    d = [0] * (W+1)

    for i in range(N):
        wi, vi = [int(i) for i in input().split()]
        for w in range(W, wi - 1, -1):
            v_ = d[w - wi] + vi
            if v_ > d[w]:
                d[w] = v_
    return d[W]

print(ans(N, W))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N, W = [int(i) for i in input().split()]
wv = [[int(i) for i in input().split()] for j in range(N)]

def ans(N, W, wv):
    d = [[0] * (W+1) for i in range(N+1)]

    for i in range(N):
        for j in range(W+1):
            if wv[i][0] > j:
                d[i+1][j] = d[i][j]
            else:
                d[i + 1][j] = max(d[i][j], d[i][j-wv[i][0]] + wv[i][1])
    return d[N][W]

print(ans(N, W, wv))


Fixed submission:
import sys
input = sys.stdin.readline

N, W = [int(i) for i in input().split()]

def ans(N, W):
    d = [0] * (W+1)

    for i in range(N):
        wi, vi = [int(i) for i in input().split()]
        for w in range(W, wi - 1, -1):
            v_ = d[w - wi] + vi
            if v_ > d[w]:
                d[w] = v_
    return d[W]

print(ans(N, W))
Buggy python submission (verdict: Time Limit Exceeded):
def lcs(a, b):
    n = len(a)
    m = len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n):
        for j in range(m):
            if a[i] == b[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

    lcs_str = ''
    i, j = n, m
    while i >= 1 and j >= 1:
        if a[i - 1] == b[j - 1]:
            lcs_str += a[i - 1] #or b[j - 1]
            i -= 1
            j -= 1
        else:
            if dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1

    return lcs_str[::-1]


s = input()
t = input()
print(lcs(s, t))

Fixed submission:
def lcs(a, b):
    n = len(a)
    m = len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
 
    for i in range(n):
        for j in range(m):
            if a[i] == b[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
 
    lcs_str = ''
    i, j = n, m
    while i >= 1 and j >= 1:
        if a[i - 1] == b[j - 1]:
            lcs_str += a[i - 1] #or b[j - 1]
            i -= 1
            j -= 1
        else:
            if dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1
 
    return lcs_str[::-1]
 
 
s = input()
t = input()
print(lcs(s, t))
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict


def rec(node):
    if dp[node]:
        return dp[node]

    res = 0
    for next_node in edge[node]:
        res = max(res, rec(next_node) + 1)

    dp[node] = res
    return res


n, m = map(int, input().split())
dp = [0] * (n + 1)
edge = defaultdict(list)

for i in range(m):
    x, y = map(int, input().split())
    edge[x].append(y)

ans = 0
for i in range(1, n + 1):
    ans = max(ans, rec(i))

print(ans)


Fixed submission:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)


def rec(node):
    if memo[node]:
        return memo[node]

    res = 0
    for next_node in edge[node]:
        res = max(res, rec(next_node) + 1)

    memo[node] = res
    return res


n, m = map(int, input().split())
memo = [0] * (n + 1)
edge = defaultdict(list)

for i in range(m):
    x, y = map(int, input().split())
    edge[x].append(y)

ans = 0
for i in range(1, n + 1):
    ans = max(ans, rec(i))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

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

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

dp[0][0] = 1.0

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

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


Fixed submission:
import numpy as np

n = int(input())
arr = list(map(float, input().split()))
dp = np.zeros(n + 1, dtype=float)
dp[0] = 1.0

for p in arr:
    tmp = dp * (1 - p)
    tmp[1:] += dp[:-1] * p
    dp = tmp

print(np.sum(dp[n // 2 + 1:]))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = a[i]

for i in range(n - 2, -1, -1):
    for j in range(i + 1, n):
        dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])

print(dp[0][n - 1])


Fixed submission:
def kukan(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        g0 = dp[i]
        g1 = dp[i + 1]
        for j in range(i + 1, n):
            L = a[i] - g1[j]
            R = a[j] - g0[j - 1]
            dp[i][j] = L if L > R else R
    return dp[0][n - 1]


n = int(input())
a = list(map(int, input().split()))
print(kukan(n, a))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
arr = list(map(int, input().split()))

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

for length in range(1, n + 1):
    for i in range(n - length + 1):
        j = i + length

        if ((n - length) % 2 == 0):
            dp[i][j] = max(dp[i+1][j] + arr[i], dp[i][j-1] + arr[j-1])
        else:
            dp[i][j] = min(dp[i+1][j] - arr[i], dp[i][j-1] - arr[j-1])


print(dp[0][n])


Fixed submission:
def kukan(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        g0 = dp[i]
        g1 = dp[i + 1]
        for j in range(i + 1, n):
            L = a[i] - g1[j]
            R = a[j] - g0[j - 1]
            dp[i][j] = L if L > R else R
    return dp[0][n - 1]


n = int(input())
a = list(map(int, input().split()))
print(kukan(n, a))