Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/dp/tasks/dp_n
import numpy as np

N = int(input())
xs = np.array([0] + [int(s) for s in input().split()])
acc = np.add.accumulate(xs)

dp = np.zeros((N, N + 1), dtype=np.int64)

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

for w in range(2, N + 1):
    for i in range(N - w + 1):
        j = i + w
        subcost = np.min([dp[i][k] + dp[k][j] for k in range(i + 1, j)])
        dp[i][j] = subcost + acc[j] - acc[i]

print(dp[0][N])


Fixed submission:
# https://atcoder.jp/contests/dp/tasks/dp_n

import itertools as it

INF = 1 << 62
N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

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

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

for w in range(2, N + 1):
    for i in range(N - w + 1):
        j = i + w
        subcost = min(dp[i][k] + dp[k][j] for k in range(i + 1, j))
        dp[i][j] = subcost + acc[j] - acc[i]

print(dp[0][N])

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/dp/tasks/dp_n

import itertools as it

INF = 1 << 62
N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

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

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

for w in range(2, N + 1):
    for i in range(N - w + 1):
        j = i + w
        subcost = min(dp[i][k] + dp[k][j] for k in range(i + 1, j))
        dp[i][j] = subcost + acc[j] - acc[i]

print(dp[0][N])


Fixed submission:
# https://atcoder.jp/contests/dp/tasks/dp_n

import itertools as it

INF = 1 << 62
N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

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

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

for w in range(2, N + 1):
    for i in range(N - w + 1):
        j = i + w
        subcost = min(dp[i][k] + dp[k][j] for k in range(i + 1, j))
        dp[i][j] = subcost + acc[j] - acc[i]

print(dp[0][N])

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/dp/tasks/dp_n

import itertools as it

INF = 1000000007
N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

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

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

for w in range(2, N + 1):
    for i in range(N - w + 1):
        j = i + w
        dp[i][j] = min(dp[i][k] + dp[k][j] + acc[j] - acc[i] for k in range(i + 1, j))

print(dp[0][N])


Fixed submission:
# https://atcoder.jp/contests/dp/tasks/dp_n

import itertools as it

INF = 1 << 62
N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

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

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

for w in range(2, N + 1):
    for i in range(N - w + 1):
        j = i + w
        subcost = min(dp[i][k] + dp[k][j] for k in range(i + 1, j))
        dp[i][j] = subcost + acc[j] - acc[i]

print(dp[0][N])

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/dp/tasks/dp_n

import itertools as it

N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

dp = dict()
for i in range(N):
    dp[i, i + 1] = 0

for w in range(2, N + 1):
    for i in range(N - w + 1):
        j = i + w
        dp[i, j] = min(dp[i, k] + dp[k, j] + acc[j] - acc[i] for k in range(i + 1, j))

print(dp[0, N])


Fixed submission:
# https://atcoder.jp/contests/dp/tasks/dp_n

import itertools as it

INF = 1 << 62
N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

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

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

for w in range(2, N + 1):
    for i in range(N - w + 1):
        j = i + w
        subcost = min(dp[i][k] + dp[k][j] for k in range(i + 1, j))
        dp[i][j] = subcost + acc[j] - acc[i]

print(dp[0][N])

Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/dp/tasks/dp_n
import functools
import itertools as it

N = int(input())
xs = [int(s) for s in input().split()]
acc = [0] + list(it.accumulate(xs))

@functools.lru_cache(None)
def f(i, j):
    if (j == i + 1):
        return 0

    return min(f(i, k) + f(k, j) + acc[j] - acc[i] for k in range(i + 1, j))

print(f(0, N))


Fixed submission:
# https://atcoder.jp/contests/dp/tasks/dp_n

import itertools as it

INF = 1 << 62
N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

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

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

for w in range(2, N + 1):
    for i in range(N - w + 1):
        j = i + w
        subcost = min(dp[i][k] + dp[k][j] for k in range(i + 1, j))
        dp[i][j] = subcost + acc[j] - acc[i]

print(dp[0][N])