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

N = int(input())
ans_list = []

for i in range(N):
    A = int(input())
    if A in ans_list:
        ans_list.remove(A)
    else:
        ans_list.append(A)

print(len(ans_list))

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

N = int(input())

# 集合　listよりも 検索などが高速
# 重複なしの順序も無し
ans_set = set()

for i in range(N):
    A = int(input())
    if A in ans_set:
        ans_set.remove(A)
    else:
        ans_set.add(A)

print(len(ans_set))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
ans_list = []

for i in range(N):
    A = int(input())
    if A in ans_list:
        ans_list.remove(A)
    else:
        ans_list.append(A)

print(len(ans_list))

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

N = int(input())

# 集合　listよりも 検索などが高速
# 重複なしの順序も無し
ans_set = set()

for i in range(N):
    A = int(input())
    if A in ans_set:
        ans_set.remove(A)
    else:
        ans_set.add(A)

print(len(ans_set))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
ans_list = []

for i in range(N):
    A = int(input())
    if A in ans_list:
        ans_list.pop(ans_list.index(A))
    else:
        ans_list.append(A)

print(len(ans_list))

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

N = int(input())

# 集合　listよりも 検索などが高速
# 重複なしの順序も無し
ans_set = set()

for i in range(N):
    A = int(input())
    if A in ans_set:
        ans_set.remove(A)
    else:
        ans_set.add(A)

print(len(ans_set))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A_list = []

for i in range(N):
    A_list.append(int(input()))

ans_list = []
for i in range(N):
    if A_list[i] in ans_list:
        ans_list.pop(ans_list.index(A_list[i]))
    else:
        ans_list.append(A_list[i])

print(len(ans_list))

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

N = int(input())

# 集合　listよりも 検索などが高速
# 重複なしの順序も無し
ans_set = set()

for i in range(N):
    A = int(input())
    if A in ans_set:
        ans_set.remove(A)
    else:
        ans_set.add(A)

print(len(ans_set))
Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0
throwgh_point_list = [-1 for i in range(N)]

def dfs(i, current, throwgh_point_list, ans_point_list):   
    # 頂点をN個通ったら終了処理
    if i >= N:
        # すでにカウント済の経路である場合
        if throwgh_point_list in ans_point_list:
            return

        # すでにカウント済ではないかつ全ての点に到達している場合
        # 順不同で比較
        if set(throwgh_point_list) == set(list(range(N))):
            global ans_count
            ans_count += 1
            ans_point_list.append(copy.copy(throwgh_point_list))
        return

    for j in range(len(Graph_list[current])):
        # 現在地を書き込む
        throwgh_point_list[i] = current

        # 次の点に移動する        
        dfs(i + 1, Graph_list[current][j], throwgh_point_list, ans_point_list)

dfs(0, 0, throwgh_point_list, [])
print(ans_count)

Fixed submission:
# https://atcoder.jp/contests/abc054/tasks/abc054_a

A, B = map(int, input().split())
Alice = 'Alice'
Bob = 'Bob'
Draw = 'Draw'

if A == B:
    print(Draw)
elif A == 1 and B != 1:
    print(Alice)
elif A != 1 and B == 1:
    print(Bob)
elif A > B:
    print(Alice)
elif A < B:
    print(Bob)
Buggy python submission (verdict: Time Limit Exceeded):
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

def main():
    n = int(input())
    ans = 1
    for i in map(int, input().split()):
        ans *= i
    if ans > 1e18:
        print(-1)
    else:
        print(ans)
main()

Fixed submission:
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 1
    for i in a:
        ans *= i
        if (ans > 1e18):
            print(-1)
            exit()
    print(ans)
main()
Buggy python submission (verdict: Time Limit Exceeded):
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)



def main():
    K = int(input()) + 1
    ans = 0
    for i in range(1, K):
        for j in range(1, K):
            for k in range(1, K):
                gcd = 1
                mx = min(i, j, k)
                for l in range(2, K):
                    if i % l == 0 and j % l == 0 and k % l == 0:
                        gcd = l
                    if l == mx:
                        break
                ans += gcd
    print(ans)

main()

Fixed submission:
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)


def main():
    K = int(input()) + 1
    ans = 0
    for i in range(1, K):
        ans += i
        for j in range(i + 1, K):
            def GCD(x, y):
                return GCD(y, x%y) if y else x
            ans += GCD(i, j) * 6
            for k in range(j + 1, K):
                gcd = 1
                mx = min(i, j, k)
                for l in range(2, K):
                    if i % l == 0 and j % l == 0 and k % l == 0:
                        gcd = l
                    if l == mx:
                        break
                ans += gcd * 6
    print(ans)

main()
Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
    A, B = map(int, input().split())
    a[i] = A
    b[i] = B

ans = [-1] * (h + 1)
ans[0] = 0

for i in range(h):
    if (ans[i] >= 0):
        for j in range(n):
            next = min(h, i + a[j])
            if ans[next] < 0:
                ans[next] = ans[i] + b[j]
            else:
                ans[next] = min(ans[next], ans[i] + b[j])

print(ans[h])

Fixed submission:
h, n = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
    A, B = map(int, input().split())
    a[i] = A
    b[i] = B

ans = [-1] * (h + 1)
ans[0] = 0

for i in range(h):
    if (ans[i] >= 0):
        for j in range(n):
            next = min(h, i + a[j])
            if ans[next] < 0:
                ans[next] = ans[i] + b[j]
            else:
                ans[next] = min(ans[next], ans[i] + b[j])

print(ans[h])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

ans = 0
divisor = 10
if N % 2 == 0:
    while N >= divisor:
        ans += N // divisor
    divisor *= 5
print(ans)

Fixed submission:
N = int(input())

ans = 0
divisor = 10
if N % 2 == 0:
    while N >= divisor:
        ans += N // divisor
        divisor *= 5
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 1000000007

N = int(input())
A = list(map(int, input().split()))

digits = [0] * 60
for i in A:
    for j in range(60):
        if i>>j&1 == 1:
            digits[j] += 1

ans = 0
for i in range(60):
    ans += digits[i] * (N - digits[i]) * (1<<i)
    ans %= MOD

print(ans)

Fixed submission:
MOD = 1000000007

N = int(input())
A = list(map(int, input().split()))

digits = [0] * 60
for i in A:
    for j in range(60):
        if i>>j&1 == 1:
            digits[j] += 1

ans = 0
for i in range(60):
    ans += digits[i] * (N - digits[i]) * (1<<i)
    ans %= MOD

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 1000000007

N = int(input())
A = list(map(int, input().split()))

digits = [0] * 60
for i in A:
    for j in range(60):
        if i>>j&1 == 1:
            digits[j] += 1

ans = 0
for i in range(60):
    ans += (digits[i] * (N - digits[i]) % MOD) * ((1<<i) % MOD)
    ans %= MOD

print(ans)

Fixed submission:
MOD = 1000000007

N = int(input())
A = list(map(int, input().split()))

digits = [0] * 60
for i in A:
    for j in range(60):
        if i>>j&1 == 1:
            digits[j] += 1

ans = 0
for i in range(60):
    ans += digits[i] * (N - digits[i]) * (1<<i)
    ans %= MOD

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = list(map(int, list(input())))
ans = 0
for i in range(1000):
    c = 0
    for j in s:
        if i % 10 == j:
            if c == 2:
                ans += 1
                break
            c += 1
            i //= 10
print(ans)

Fixed submission:
n = int(input())
s = list(map(int, list(input())))

ans = 0

def dfs(depth, id):
    global ans
    for i in range(10):
        for j in range(id, n):
            if i == s[j]:
                if depth < 2:
                    dfs(depth + 1, j + 1)
                else:
                    ans += 1
                break

dfs(0, 0)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = list(map(int, input()))

ans = 0
for i in range(1000):
    A = i // 100
    B = i // 10 % 10
    C = i % 10
    a = False
    b = False
    for j in S:
        if a:
            if b:
                if j == C:
                    ans += 1
                    break
            elif j == B:
                b = True
        elif j == A:
            a = True

print(ans)

Fixed submission:
n = int(input())
s = list(map(int, list(input())))

ans = 0

def dfs(depth, id):
    global ans
    for i in range(10):
        for j in range(id, n):
            if i == s[j]:
                if depth < 2:
                    dfs(depth + 1, j + 1)
                else:
                    ans += 1
                break

dfs(0, 0)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = sorted([int(x) for x in input().split()],reverse=True)
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        if L[j] < L[i] / 2:
            break
        for k in range(j+1, N):
            if L[i] < L[j] + L[k]:
                ans += 1
            else:
                break
print(ans)

Fixed submission:
import bisect

N = int(input())
L = sorted([int(x) for x in input().split()])
ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        ab = L[i] + L[j]
        r = bisect.bisect_left(L,ab)
        l = j + 1
        ans += r - l

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

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

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

ans = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        now = min(dp[i][j], j-i)
        ans = max(ans, now)

print(ans)

Fixed submission:
N = int(input())
S = input()

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

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

ans = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        now = min(dp[i][j], j-i)
        ans = max(ans, now)

print(ans)

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

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        if S[i] == S[j]:
            if i != 0:
                if S[i-1] == S[j-1]:
                    continue
            equal = 1
            for k in range(1, min(j-i, N-j)):
                if S[i+k] == S[j+k]:
                    equal += 1
                else:
                    break
            ans = max(ans, equal)

print(ans)


Fixed submission:
N = int(input())
S = input()

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

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

ans = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        now = min(dp[i][j], j-i)
        ans = max(ans, now)

print(ans)

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

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        if S[i] == S[j]:
            equal = 1
            for k in range(1, min(j-i, N-j)):
                if S[i+k] == S[j+k]:
                    equal += 1
                else:
                    break
            ans = max(ans, equal)

print(ans)

Fixed submission:
N = int(input())
S = input()

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

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

ans = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        now = min(dp[i][j], j-i)
        ans = max(ans, now)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = [int(x) - 1 for x in input().split()]

idx = [0] * N
for i in range(N):
    idx[P[i]] = i

ans = 0
for i in range(N - 2, -1, -1):
    find = False
    l1 = idx[i] + 1
    l2 = 0
    for j in range(idx[i] - 1, -1, -1):
        if i < P[j]:
            if not find:
                l1 = idx[i] - j
                l2 = j + 1
                find = True
            else:
                l2 = idx[i] - l1 - j
                break
    
    find = False
    r1 = N - idx[i]
    r2 = 0
    for j in range(idx[i] + 1, N):
        if i < P[j]:
            if not find:
                r1 = j - idx[i]
                r2 = N - j
                find = True
            else:
                r2 = j - r1 - idx[i]
                break
    ans += (i + 1) * (l1 * r2 + l2 * r1)

print(ans)

Fixed submission:
N = int(input())
P = [int(x) for x in input().split()]

PIdx = sorted([(i + 1, v) for i, v in enumerate(P)], key = lambda x: x[1])

L = [0]
for i in range(N + 1):
    L.append(i)

R = [i + 1 for i in range(N + 1)]
R.append(N + 1)

ans = 0
for i, v in PIdx:
    l1 = L[i]
    l2 = L[l1]
    r1 = R[i]
    r2 = R[r1]

    ans += v * ((i - l1) * (r2 - r1) + (l1 - l2) * (r1 - i))

    L[r1] = l1
    R[l1] = r1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = [int(x) - 1 for x in input().split()]

idx = [0] * N
for i in range(N):
    idx[P[i]] = i

ans = 0
for i in range(N - 2, -1, -1):
    find = False
    l1 = idx[i] + 1
    l2 = 0
    for j in range(idx[i] - 1, -1, -1):
        if i < P[j]:
            if not find:
                l1 = idx[i] - j
                l2 = j + 1
                find = True
            else:
                l2 = idx[i] - l1 - j
                break
    
    find = False
    r1 = N - idx[i]
    r2 = 0
    for j in range(idx[i] + 1, N):
        if i < P[j]:
            if not find:
                r1 = j - idx[i]
                r2 = N - j
                find = True
            else:
                r2 = j - r1 - idx[i]
                break
    ans += (i + 1) * (l1 * r2 + l2 * r1)

print(ans)

Fixed submission:
N = int(input())
P = [int(x) for x in input().split()]

PIdx = sorted([(i + 1, v) for i, v in enumerate(P)], key = lambda x: x[1])

L = [0]
for i in range(N + 1):
    L.append(i)

R = [i + 1 for i in range(N + 1)]
R.append(N + 1)

ans = 0
for i, v in PIdx:
    l1 = L[i]
    l2 = L[l1]
    r1 = R[i]
    r2 = R[r1]

    ans += v * ((i - l1) * (r2 - r1) + (l1 - l2) * (r1 - i))

    L[r1] = l1
    R[l1] = r1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N = int(input())
S = sorted([int(x) for x in input().split()])

Slimes = [S.pop(-1)]

flag = True
for i in range(1, N + 1):
    newSlimes = []
    for j in Slimes:
        idx = bisect.bisect_left(S, j)
        if idx == 0:
            flag = False
            break
        newSlimes.append(S.pop(idx-1))
    if not flag:
        break
    Slimes.extend(newSlimes)

print('Yes' if flag else 'No')

Fixed submission:
N = int(input())
N2 = 1 << N

S = sorted([int(x) for x in input().split()])

s = []
s.append(S[-1])
S[-1] = -1

flag = True
for i in range(N):
    p = sorted([x for x in s])

    Si = N2 - 1
    while len(p) > 0 and Si >= 0:
        if S[Si] == -1:
            Si -= 1
            continue

        if S[Si] < p[-1]:
            s.append(S[Si])
            del p[-1]
            S[Si] = -1
        
        Si -= 1
    
    if len(p) > 0:
        flag = False

print('Yes' if flag else 'No')

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N = int(input())
S = sorted([int(x) for x in input().split()])

Slimes = [[S.pop(-1)]]

flag = True
for i in range(1, N + 1):
    Slimes.append([])
    for j in range(i):
        for k in Slimes[j]:
            idx = bisect.bisect_left(S, k)
            if idx == 0:
                flag = False
                break
            Slimes[i].append(S.pop(idx-1))
        if not flag:
            break
    if not flag:
        break

print('Yes' if flag else 'No')

Fixed submission:
N = int(input())
N2 = 1 << N

S = sorted([int(x) for x in input().split()])

s = []
s.append(S[-1])
S[-1] = -1

flag = True
for i in range(N):
    p = sorted([x for x in s])

    Si = N2 - 1
    while len(p) > 0 and Si >= 0:
        if S[Si] == -1:
            Si -= 1
            continue

        if S[Si] < p[-1]:
            s.append(S[Si])
            del p[-1]
            S[Si] = -1
        
        Si -= 1
    
    if len(p) > 0:
        flag = False

print('Yes' if flag else 'No')

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N = int(input())
S = sorted([int(x) for x in input().split()])

Slimes = [[S.pop(-1)]]

flag = True
for i in range(1, N + 1):
    Slimes.append([])
    for j in range(i):
        for k in Slimes[j]:
            idx = bisect.bisect_left(S, k)
            if idx == 0:
                flag = False
                break
            Slimes[i].append(S.pop(idx-1))
        if not flag:
            break
    if not flag:
        break

print('Yes' if flag else 'No')

Fixed submission:
N = int(input())
N2 = 1 << N

S = sorted([int(x) for x in input().split()])

s = []
s.append(S[-1])
S[-1] = -1

flag = True
for i in range(N):
    p = sorted([x for x in s])

    Si = N2 - 1
    while len(p) > 0 and Si >= 0:
        if S[Si] == -1:
            Si -= 1
            continue

        if S[Si] < p[-1]:
            s.append(S[Si])
            del p[-1]
            S[Si] = -1
        
        Si -= 1
    
    if len(p) > 0:
        flag = False

print('Yes' if flag else 'No')
Buggy python submission (verdict: Runtime Error):
V = 100005
N = int(input())

lines = [[] for _ in range(V * 2)]
visited = [False] * V * 2

count = []
def dfs(v):
	global count
	if visited[v]:
		return
	visited[v] = True
	count[v // V] += 1
	for u in lines[v]:
		dfs(u)


for i in range(N):
	x, y = [int(x) for x in input().split()]
	y += V
	lines[x].append(y)
	lines[y].append(x)

ans = 0
for i in range(V * 2):
	if visited[i]:
		continue
	count = [0, 0]
	dfs(i)
	ans += count[0] * count[1]

ans -= N
print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(10000000)

V = 100005
N = int(input())

lines = [[] for _ in range(V * 2)]
visited = [False] * V * 2

count = []
def dfs(v):
	global count
	if visited[v]:
		return
	visited[v] = True
	count[v // V] += 1
	for u in lines[v]:
		dfs(u)


for i in range(N):
	x, y = [int(x) for x in input().split()]
	y += V
	lines[x].append(y)
	lines[y].append(x)

ans = 0
for i in range(V * 2):
	if visited[i]:
		continue
	count = [0, 0]
	dfs(i)
	ans += count[0] * count[1]

ans -= N
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
h = [int(x) for x in input().split()]

dp = [float('inf')] * N
dp[0] = 0

Func = min
for i in range(N-1):
    for j in range(i+1, i+K+1):
        if j >= N:
            break
        dp[j] = Func(dp[j], dp[i] + abs(h[i] - h[j]))

print(dp[N-1])

Fixed submission:
N, K = map(int, input().split())
h = [int(x) for x in input().split()]

dp = [float('inf')] * N
dp[0] = 0

for i in range(N-1):
    for j in range(i+1, i+K+1):
        if j >= N:
            break
        dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]))

print(dp[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
h = [int(x) for x in input().split()]

dp = [float('inf')] * N
dp[0] = 0

for i in range(N-1):
    for j in range(i+1, i+K+1):
        if j >= N:
            break
        dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]))

print(dp[N-1])

Fixed submission:
N, K = map(int, input().split())
h = [int(x) for x in input().split()]

dp = [float('inf')] * N
dp[0] = 0

for i in range(N-1):
    for j in range(i+1, i+K+1):
        if j >= N:
            break
        dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]))

print(dp[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10000000)

N, K = list(map(lambda x: int(x), input().split()))
ashiba = [int(s) for s in input().split()]

l = [float('inf')] * N
l[0] = 0

for i in range(N):
	if K > N - i - 1:
		K = N - i - 1
	for j in range(i + 1,i + K + 1):
		cost = abs(ashiba[j] - ashiba[i]) + l[i]
		if l[j] > cost:
			l[j] = cost

print(l[N - 1])

Fixed submission:
N, K = map(int, input().split())
h = [int(x) for x in input().split()]

dp = [float('inf')] * N
dp[0] = 0

for i in range(N-1):
    for j in range(i+1, i+K+1):
        if j >= N:
            break
        dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]))

print(dp[N-1])
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, W = map(int, input().split())

w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

def func(N, W):
    dp = [0] * (W+1)
    for i in range(N):
        for j in range(W, w[i]-1, -1):
            a = dp[j-w[i]] + v[i]
            if dp[j] < a:
                dp[j] = a
    return dp[W]

print(func(N, W))

Fixed submission:
N = int(input())

abc = [list(map(lambda x: int(x), input().split())) for _ in range(N)]

happy = [[0] * 3 for _ in range(N)]
for i in range(3):
	happy[0][i] = abc[0][i]

for i in range(1, N):
	for j in range(3):
		for k in range(3):
			if j != k and happy[i][j] < happy[i - 1][k]:
				happy[i][j] = happy[i - 1][k]
		happy[i][j] += abc[i][j]

print(max(happy[N - 1][0], happy[N - 1][1], happy[N - 1][2]))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = [int(x) for x in input().split()]

p = [0] * 3
for i in a:
    p[3-i] += 1

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

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

print(dp[p[0]][p[1]][p[2]])

Fixed submission:
N = int(input())
a = [int(x) for x in input().split()]

p = [0] * 3
for i in a:
    p[3-i] += 1

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

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

print(dp[p[0]][p[1]][p[2]])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = [int(x) for x in input().split()]

dp = [[[] for _ in range(N)] for _ in range(N)]
for i in range(N):
    dp[i][i] = a[i]

for l in range(1, N):
    for i in range(N-l):
        dp[i][i+l] = max(a[i] - dp[i+1][i+l], a[i+l] - dp[i][i+l-1])

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

Fixed submission:
N = int(input())
a = [int(x) for x in input().split()]

dp = [[[] for _ in range(N)] for _ in range(N)]
for i in range(N):
    dp[i][i] = a[i]

for l in range(1, N):
    for i in range(N-l):
        dp[i][i+l] = max(a[i] - dp[i+1][i+l], a[i+l] - dp[i][i+l-1])

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