Buggy python submission (verdict: Time Limit Exceeded):
#N

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

S=[0]*(N+1)
for i in range(N):
    S[i+1]=S[i]+a[i]


#dp[i][j]は[i,j)の範囲で全てをマージする最小コスト
inf=10**15
dp=[[inf]*(N+1) for _ in range(N+1)]

#区間[i,j)を[i,k)+[k,j)に分けて考える
for d in range(1,N+1):#dはj-i
    for i in range(N+1):
        j=i+d
        if j>N:
            break
        if d==1:
            dp[i][j]=0
        else:
            for k in range(i,j):
                dp[i][j]=min(dp[i][j] , dp[i][k]+dp[k][j]+S[j]-S[i])
            
print(dp[0][-1])
            



Fixed submission:
#N

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

S=[0]*(N+1)
for i in range(N):
    S[i+1]=S[i]+a[i]


#dp[i][j]は[i,j)の範囲で全てをマージする最小コスト
inf=10**15
dp=[[inf]*(N+1) for _ in range(N+1)]

#区間[i,j)を[i,k)+[k,j)に分けて考える
for d in range(1,N+1):#dはj-i
    for i in range(N+1):
        j=i+d
        if j>N:
            break
        if d==1:
            dp[i][j]=0
        else:
            for k in range(i,j):
                dp[i][j]=min(dp[i][j] , dp[i][k]+dp[k][j]+S[j]-S[i])
            
print(dp[0][-1])

Buggy python submission (verdict: Time Limit Exceeded):
#N
import copy
from collections import defaultdict
dd = defaultdict(int)

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

def rep(L):
    if len(L)==1:
        return 0
    S='-'.join(map(str, L))
    if dd[S]!=0:
        return dd[S]
    temp=10**15
    for i in range(len(L)-1):
        LL=copy.deepcopy(L)
        LL[i]+=LL[i+1]
        LL.pop(i+1)
        temp=min(temp,rep(LL)+L[i]+L[i+1])
    dd[S]=temp
    return temp
        
rep(a)
S='-'.join(map(str, a))
print(dd[S])





Fixed submission:
#N

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

S=[0]*(N+1)
for i in range(N):
    S[i+1]=S[i]+a[i]


#dp[i][j]は[i,j)の範囲で全てをマージする最小コスト
inf=10**15
dp=[[inf]*(N+1) for _ in range(N+1)]

#区間[i,j)を[i,k)+[k,j)に分けて考える
for d in range(1,N+1):#dはj-i
    for i in range(N+1):
        j=i+d
        if j>N:
            break
        if d==1:
            dp[i][j]=0
        else:
            for k in range(i,j):
                dp[i][j]=min(dp[i][j] , dp[i][k]+dp[k][j]+S[j]-S[i])
            
print(dp[0][-1])

Buggy python submission (verdict: Time Limit Exceeded):
#N
import copy
from collections import defaultdict
dd = defaultdict(int)

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

def rep(L):
    if len(L)==1:
        return 0
    S='-'.join(map(str, L))
    if dd[S]!=0:
        return dd[S]
    temp=10**15
    for i in range(len(L)-1):
        LL=copy.deepcopy(L)
        LL[i]+=LL[i+1]
        LL.pop(i+1)
        temp=min(temp,rep(LL)+L[i]+L[i+1])
    dd[S]=temp
    return temp
        
rep(a)
S='-'.join(map(str, a))
print(dd[S])






Fixed submission:
#N

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

S=[0]*(N+1)
for i in range(N):
    S[i+1]=S[i]+a[i]


#dp[i][j]は[i,j)の範囲で全てをマージする最小コスト
inf=10**15
dp=[[inf]*(N+1) for _ in range(N+1)]

#区間[i,j)を[i,k)+[k,j)に分けて考える
for d in range(1,N+1):#dはj-i
    for i in range(N+1):
        j=i+d
        if j>N:
            break
        if d==1:
            dp[i][j]=0
        else:
            for k in range(i,j):
                dp[i][j]=min(dp[i][j] , dp[i][k]+dp[k][j]+S[j]-S[i])
            
print(dp[0][-1])