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

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def cost(l, r):
        if l + 2 == r:
            return aa[l] + aa[l + 1]
        if l + 1 == r:
            return 0
        if dp[l][r] != -1:
            return dp[l][r]
        res = 10 ** 10
        for m in range(l + 1, r):
            res = min(res, cost(l, m) + cost(m, r))
        res += cumsum_aa[r] - cumsum_aa[l]
        dp[l][r] = res
        return res

    n = int(input())
    aa = list(map(int, input().split()))
    dp = [[-1] * (n + 1) for _ in range(n + 1)]
    cumsum_aa = [0]
    for i, a in enumerate(aa):
        cumsum_aa.append(cumsum_aa[i] + a)
    print(cost(0, n))

main()


Fixed submission:
def f(n, a):
    inf = float("inf")
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        s = a[i]
        dpi = dp[i]
        for j in range(i + 1, n):
            mn = inf
            s += a[j]
            for d in range(i, j):
                k = dpi[d] + dp[d + 1][j]
                if k < mn:
                    mn = k
            dpi[j] = mn + s
    return dp[0][-1]


n = int(input())
a = tuple(map(int, input().split()))
print(f(n, a))

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

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    ans = 0
    while len(aa) > 1:
        mn = 10**10
        mi = -1
        for i in range(len(aa) - 1):
            now = aa[i] + aa[i + 1]
            if now < mn:
                mn = now
                mi = i
        aa = aa[:mi] + [mn] + aa[mi + 2:]
        ans+=mn
    print(ans)

main()


Fixed submission:
def f(n, a):
    inf = float("inf")
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        s = a[i]
        dpi = dp[i]
        for j in range(i + 1, n):
            mn = inf
            s += a[j]
            for d in range(i, j):
                k = dpi[d] + dp[d + 1][j]
                if k < mn:
                    mn = k
            dpi[j] = mn + s
    return dp[0][-1]


n = int(input())
a = tuple(map(int, input().split()))
print(f(n, a))

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

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    ans = 0
    while len(aa) > 1:
        mn = 10**10
        mi = -1
        for i in range(len(aa) - 1):
            now = aa[i] + aa[i + 1]
            if now < mn:
                mn = now
                mi = i
        aa = aa[:mi] + [mn] + aa[mi + 2:]
        ans+=mn
    print(ans)

main()


Fixed submission:
def f(n, a):
    inf = float("inf")
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        s = a[i]
        dpi = dp[i]
        for j in range(i + 1, n):
            mn = inf
            s += a[j]
            for d in range(i, j):
                k = dpi[d] + dp[d + 1][j]
                if k < mn:
                    mn = k
            dpi[j] = mn + s
    return dp[0][-1]


n = int(input())
a = tuple(map(int, input().split()))
print(f(n, a))

Buggy python submission (verdict: Time Limit Exceeded):
def f(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        s = a[i]
        dpi=dp[i]
        for j in range(i + 1, n):
            k = []
            s += a[j]
            for d in range(i, j):
                k += [dpi[d] + dp[d + 1][j]]
            dp[i][j] = min(k) + s
    return dp[0][-1]


n = int(input())
a = tuple(map(int, input().split()))
print(f(n, a))


Fixed submission:
def f(n, a):
    inf = float("inf")
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        s = a[i]
        dpi = dp[i]
        for j in range(i + 1, n):
            mn = inf
            s += a[j]
            for d in range(i, j):
                k = dpi[d] + dp[d + 1][j]
                if k < mn:
                    mn = k
            dpi[j] = mn + s
    return dp[0][-1]


n = int(input())
a = tuple(map(int, input().split()))
print(f(n, a))

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

dp = [[0] * n for _ in range(n)]
for i in range(n - 2, -1, -1):
    s = a[i]
    for j in range(i + 1, n):
        k = []
        s += a[j]
        for d in range(i, j):
            k += [dp[i][d] + dp[d + 1][j]]
        dp[i][j] = min(k) + s
print(dp[0][-1])


Fixed submission:
def f(n, a):
    inf = float("inf")
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        s = a[i]
        dpi = dp[i]
        for j in range(i + 1, n):
            mn = inf
            s += a[j]
            for d in range(i, j):
                k = dpi[d] + dp[d + 1][j]
                if k < mn:
                    mn = k
            dpi[j] = mn + s
    return dp[0][-1]


n = int(input())
a = tuple(map(int, input().split()))
print(f(n, a))

Buggy python submission (verdict: Time Limit Exceeded):
def cost(a):
    la = len(a)
    if la == 1:
        return 0
    if la == 2:
        return a[0] + a[1]
    if a in memo:
        return memo[a]
    re = []
    for i in range(1, la):
        re += [cost(a[:i]) + cost(a[i:]) + sum(a)]
    re = min(re)
    memo[a] = re
    return re


memo = {}
n = int(input())
a = tuple(map(int, input().split()))
print(cost(a))


Fixed submission:
def f(n, a):
    inf = float("inf")
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        s = a[i]
        dpi = dp[i]
        for j in range(i + 1, n):
            mn = inf
            s += a[j]
            for d in range(i, j):
                k = dpi[d] + dp[d + 1][j]
                if k < mn:
                    mn = k
            dpi[j] = mn + s
    return dp[0][-1]


n = int(input())
a = tuple(map(int, input().split()))
print(f(n, a))