Problem:


Score : 100 points

Problem Statement

There are N slimes lining up in a row.
Initially, the i-th slime from the left has a size of a_i.

Taro is trying to combine all the slimes into a larger slime.
He will perform the following operation repeatedly until there is only one slime:

Choose two adjacent slimes, and combine them into a new slime. The new slime has a size of x + y, where x and y are the sizes of the slimes before combining them. Here, a cost of x + y is incurred. The positional relationship of the slimes does not change while combining slimes.

Find the minimum possible total cost incurred.

Constraints

All values in input are integers.

2 \leq N \leq 400

1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \ldots a_N

Output

Print the minimum possible total cost incurred.

Sample Input 1

4
10 20 30 40

Sample Output 1

190

Taro should do as follows (slimes being combined are shown in bold):

(10, 20, 30, 40) → (30, 30, 40)

(30, 30, 40) → (60, 40)

(60, 40) → (100)

Sample Input 2

5
10 10 10 10 10

Sample Output 2

120

Taro should do, for example, as follows:

(10, 10, 10, 10, 10) → (20, 10, 10, 10)

(20, 10, 10, 10) → (20, 20, 10)

(20, 20, 10) → (20, 30)

(20, 30) → (50)

Sample Input 3

3
1000000000 1000000000 1000000000

Sample Output 3

5000000000

The answer may not fit into a 32-bit integer type.

Sample Input 4

6
7 6 8 6 1 1

Sample Output 4

68

Taro should do, for example, as follows:

(7, 6, 8, 6, 1, 1) → (7, 6, 8, 6, 2)

(7, 6, 8, 6, 2) → (7, 6, 8, 8)

(7, 6, 8, 8) → (13, 8, 8)

(13, 8, 8) → (13, 16)

(13, 16) → (29)



Sample input:
4
10 20 30 40


Sample output:
190

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=1):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def parent(self,x):
        return self.dfs(0,func=lambda pr,prv,nx,dist:pr,root_v=-1)
 
    def topological_sort(self,x):  # return topological sort of the tree
        tps=[]
        q=deque([x])
        v=[None]*self.size
        v[x]=0
        while q:
            c=q.popleft()
            tps.append(c)
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=0
        return tps
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        #self.st=SegTree(self.size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
    def __str__(self):
        return  str(self.edges)
 
    def show(self):
        if all([all([d==1 for nd,d in edge]) for edge in self.edges]):
            print( [[nd for nd,d in edge] for edge in self.edges] )
        else:
            print(self)
 
class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    # return boundary index of r such that func({table[i]} =< x , i in [pos,r]
    def right_bound(self,pos,x):
        k=(self.size-pos).bit_length()
        for j in range(k)[::-1]:
            nx=pos+(1<<j)
            if nx<n and self.query(pos,nx+1)<=x:
                pos+=(1<<j)
        return pos
    
    # return boundary index of l such that func({table[i]} =< x , i in [l,pos]
    def left_bound(self,pos,x):
        k=pos.bit_length()
        for j in range(k)[::-1]:
            nx=pos-(1<<j)
            if 0<=nx and self.query(nx,pos+1)<=x:
                pos-=(1<<j)
        return pos
 
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)
 
show_flg=False
show_flg=True
ans=0

n=I()
a=LI()
ac=accum(a)

dp=[[inf]*-~n for i in rep(n)]
for i in rep(n):
    dp[i][i+1]=0

for l in rep(2,n+1):
    for b in rep(n-l+1):
        for m in rep(1,l):
            dp[b][b+l]=min(dp[b][b+l],dp[b][b+m]+dp[b+m][b+l]+ac[b+l]-ac[b])

print(dp[0][n])

Submission status: Accepted

Solution code:
from itertools import accumulate

def solve():
    INF = 10**15

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

    accAs = list(accumulate([0]+As))

    dp = [[INF]*(N) for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0

    for L in reversed(range(N)):
        dpL = dp[L]
        for R in range(L+1, N):
            dpL[R] = min([dpL[k-1] + dp[k][R] for k in range(L+1, R+1)]) + accAs[R+1] - accAs[L]

    print(dp[0][-1])


solve()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
dp=[[9999999999999999999999999999999999999 for i in range(n)] for j in range(n)]
pre=[0]*n
pre[0]=a[0]
dp[0][0]=0
for i in range(1,n):
    pre[i]=a[i]+pre[i-1]
    dp[i-1][i]=a[i-1]+a[i]
    dp[i][i]=0
for i in range(3,n+1):
    for j in range(n-i+1):
        k=j+i-1
        for l in range(j,k):
            t1,t2=0,0
            if l>=j:
                t1=dp[j][l]
            if l+1<=k:
                t2=dp[l+1][k]
            # print(pre[l],pre[j],a[j],a[l],pre[l]-(pre[j]-a[j])-a[l],t1,t2)
            # if count==2:
            #     print(t1,t2)
            # print(t1,t2,pre[k]-pre[j]+a[j])
            dp[j][k]=min(dp[j][k],t1+t2+pre[k]-pre[j]+a[j])
# print(dp)
print(dp[0][n-1])

Submission status: Accepted

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

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

# [i:j) のスライムを合体させるのに必要な最小のコスト
dp = [[10**(18)]*(N+1) for _ in range(N)]
for i in range(N):
    dp[i][i+1] = 0
for l in range(2, N+1):
    for i in range(N-l+1):
        j = i+l
        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][N])

Submission status: Accepted

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

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

# [i:j) のスライムを合体させるのに必要な最小のコスト
dp = [[10**(18)]*(N+1) for _ in range(N+1)]
for i in range(N):
    dp[i][i+1] = 0
for l in range(2, N+1):
    for i in range(N-l+1):
        j = i+l
        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][N])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")

def findsum(li):

    for i in range(1,len(li)+1):
        tot[i]=tot[i-1]+li[i-1]
    #print(tot)

def findans(start,end,li):
  global tot
  #print("HI")
  if(start>=end):
    return 0
  if(dp[start][end]!=-1):
    return dp[start][end]
  ans = INF
  for k in range(start,end):


      ans=min(findans(start,k,li)+findans(k+1,end,li),ans)
  dp[start][end]=ans+(tot[end+1]-tot[start])
  return dp[start][end]
n=int(input())
li=[int(k) for k in input().split()]
tot=[0]*(len(li)+1)
findsum(li)
dp=[[-1 for i in range(n)]for k in range(n)]
print(findans(0,n-1,li))

Submission status: Accepted

Solution code:
def main():
    INF = 10 ** 15
    N = int(input())
    A = list(map(int, input().split(' ')))
    cumsum = [0 for _ in range(N)]
    cumsum[0] = A[0]
    for i in range(1, N):
        cumsum[i] = A[i] + cumsum[i - 1]
    dp = [[0 for _ in range(N)] for _ in range(N)]

    def solve(left, right):
        if left == right:
            return 0
        ret = dp[left][right]
        if ret > 0:
            return ret
        ret = INF
        for mid in range(left, right):
            ret = min([
                ret,
                solve(left, mid) + solve(mid + 1, right)
            ])
        ret += cumsum[right] - (cumsum[left - 1] if left > 0 else 0)
        dp[left][right] = ret
        return ret

    print(solve(0, N - 1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# dp[i][j] - minimum cost from i to j

INF = 1e18+5

n = int(input())

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

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

def range_sum(arr, L, R):
    s = 0
    for i in range(L, R+1):
        s += arr[i]
    return s

for L in reversed(range(n)):
    for R in range(L, n):
        if L == R:
            dp[L][R] = 0
        else:
            dp[L][R] = INF
            s = range_sum(arr, L, R)
            # try every possible middle
            for mid in range(L, R):
                dp[L][R] = min(dp[L][R], dp[L][mid] + dp[mid+1][R] + s)

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

"""

int main() {
    const int INF = 1e9+7;
    
    int n;
    
    scanf("%d", &n);
    
    vector<int> arr(n);
    
    vector<vector<ll>> dp(n, vector<ll>(n, -1));
    
    vector<vector<int>> mids(n, vector<int>(n));
    
    vector<ll> pref_sums(n+1);
    
    ll pref_sum = 0;
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        dp[i][i] = 0;
    }
    
    for (int i = 0; i <= n; i++) {
        pref_sum += arr[i];
        pref_sums[i] = pref_sum;
    }
    
    for (int length = 1; length < n; length++) {
        for (int left = 0; left+length < n; left++) {
            int right = left + length;
            //cout << left << " " << right << endl;
            for (int mid = left; mid < right; mid++) {
                ll left_cost = dp[left][mid];
                ll right_cost = dp[mid+1][right];
                ll range_sum = pref_sums[right] - (left-1 < 0 ? 0 : pref_sums[left-1]);
                ll my_cost = left_cost + right_cost + range_sum;
                //cout << total << endl;
                /*
                if (total < dp[left][right]) {
                    // update chosen mid & min value
                    dp[left][right] = my_cost;//total;
                    //mids[left][right] = mid;
                }
                */
                if (dp[left][right] == -1) {
                    dp[left][right] = my_cost;
                }
                else {
                    dp[left][right] = min(dp[left][right], my_cost);                
                }
            }
        }
    }
    /*
    vector<pair<int, int>> v; // (start, end)
    
    v.push_back({0, n-1});
    
    ll ans = 0; //-dp[0][n-1]; // the last one 
    
    while (!v.empty()) {
        pair<int, int> cur = v.back();
        v.pop_back();
        if (cur.second - cur.first + 1 >= 2) { // interval at least two
            ans += dp[cur.first][cur.second];
            int mid = mids[cur.first][cur.second];
            cout << "L: " << cur.first << " R: " << cur.second << " Total: " << dp[cur.first][cur.second] << " mid: " << mid << endl;
            v.push_back({cur.first, mid});
            v.push_back({mid+1, cur.second});    
        }
    }
    */
    
    
	/*
	for (int i = 0; i < n; i++) {
	    for (int j = 0; j < n; j++) {
	        for (int mid = i; mid <= j; mid++) {
	            ll cur = dp[i][mid];
	            if (mid+1 <= j) {
	                cur += dp[mid+1][j];
	            }
	            dp[i][j] = min(dp[i][j], cur);
	        }
	    }
	}
	*/
	
	//printf("%lld", ans);
	
	printf("%lld", dp[0][n-1]);
	
	return 0;
}
"""

Submission status: Accepted

Solution code:
import math
from functools import lru_cache, reduce


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def prefix_sum(arr, a):
    arr.append(arr[-1]+a)
    return arr


def solve():
    """
    OPT[i][j] = min(OPT[i][k]+OPT[k+1][j])+sum(A[i:j+1])    i <= k < j
    OPT[i][j] = 0 if i == j
    """
    N = read_int()
    A = read_ints()
    prefix = reduce(prefix_sum, A, [0])

    @lru_cache(None)
    def dp(i, j):
        if i == j:
            return 0
        return min(dp(i, k)+dp(k+1, j)+(prefix[j+1]-prefix[i]) for k in range(i, j))

    OPT = [[0]*N for _ in range(N)]
    for j in range(N):
        for i in range(j-1, -1, -1):
            OPT[i][j] = min(OPT[i][k]+OPT[k+1][j] for k in range(i, j))+(prefix[j+1]-prefix[i])

    return OPT[0][N-1]


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
#dp[i][j] denotes answer for subarray from i to j
n=int(input())
l=input().split()
li=[int(i) for i in l]
dp=[[0 for i in range(n)]for i in range(n)]
pref=[0 for i in range(n)]
sumi=0
for i in range(n):
    sumi+=li[i]
    pref[i]=sumi
for i in range(n):
    dp[i][i]=0
for gap in range(1,n):
    for i in range(n-gap):
        left=i
        right=i+gap
        mina=[]
        if(left==0):
            curr=pref[right]
        else:
            curr=pref[right]-pref[left-1]
        for j in range(left,right):
            mina.append(dp[left][j]+dp[j+1][right]+curr)
        dp[left][right]=min(mina)
print(dp[0][n-1])

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from itertools import chain

dp = []
dp2 = []
aac = []

def fdp(l, r):
    global dp, dp2
    if dp2[l][r]:
        return dp[l][r]
    else:
        dp2[l][r] = 1
        if l == r:
            return 0
        result_tmp = float('inf')
        for kugiri in range(l, r):
            result_tmp = min(result_tmp, fdp(l, kugiri) + fdp(kugiri+1, r))
        result = result_tmp + (aac[r+1] - aac[l])
        dp[l][r] = result
        return result
def main():
    global dp, dp2, aac
    n = int(input())
    a = tuple(map(int, input().split()))
    aac = list(accumulate(a))
    aac = tuple(chain([0], aac))
    dp = [[0] * n for _ in range(n)]
    dp2 = [[0] * n for _ in range(n)]
    fdp(0, n - 1)
    print(dp[0][-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def sumi(i,j):
    s=0
    for k in range(i,j+1):
        s+=l[k]
    return s

n = int(input())
l = list(map(int, input().split()))
dp = []
for i in range(n):
    dp.append([sys.maxsize]*n)
for i in range(n-1,-1,-1):
    for j in range(i,n):
        if i==j:
            dp[i][j]=0
        else:
            s=sumi(i,j)
            for k in range(i,j):
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s)
print(dp[0][n-1])

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A=list(map(int,input().split()))
    cum_A=[0]*(n+1) #Aの[0,i)の和
    for i in range(1,n+1):
        cum_A[i]=cum_A[i-1]+A[i-1]
    dp=[[0]*(n+1) for _ in range(n+1)]  #[i,j)をまとめるために必要なコストの最小値
    for length in range(2,n+1):
        for i in range(n-length+1):
            j=i+length #右側
            res=10**20
            for k in range(i+1,j):#区間[i,k)と[k,j)に分ける
                res=min(res,dp[i][k]+dp[k][j])
            dp[i][j]=res+cum_A[j]-cum_A[i]
    print(dp[0][n])


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A=list(map(int,input().split()))
    cum_A=[0]*(n+1) #Aの[0,i)の和
    for i in range(1,n+1):
        cum_A[i]=cum_A[i-1]+A[i-1]
    dp=[[0]*n for _ in range(n)]  #[i,j]をまとめるために必要なコストの最小値
    for length in range(2,n+1):
        for i in range(n-length+1):
            j=i+length-1 #右側
            res=10**20
            for k in range(i+1,j+1):#区間[i,k)と[k,j]に分ける
                res=min(res,dp[i][k-1]+dp[k][j])
            dp[i][j]=res+cum_A[j+1]-cum_A[i]
    print(dp[0][n-1])


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
# 単位元とseg_funcを設定する
from fractions import gcd
class seg():
    def __init__(self,init_val):
        self.n=len(init_val)
        self.ide_ele=0 #単位元
        self.num=2**(self.n-1).bit_length() #n以上の最小の2のべき乗
        self.seg=[self.ide_ele]*2*self.num
        for i in range(self.n):
            self.seg[i+self.num-1]=init_val[i]
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.seg_func(self.seg[2*i+1],self.seg[2*i+2])
    def seg_func(self,a,b):
        return a+b #0
        #return a*b #1
        #return gcd(a,b) #0
        #return max(a,b) #-1か-10**10 (十分小さいもの)
        #return min(a,b) #10**10 (十分大きいもの)
    def update(self,k,x):
        k+=self.num-1
        self.seg[k]=x
        while k:
            k=(k-1)//2
            self.seg[k]=self.seg_func(self.seg[k*2+1],self.seg[k*2+2])
    def query(self,p,q): #O(logN)
        if q<=p:return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        self.res=self.ide_ele
        while q-p>1:
            if p&1==0:
                self.res=self.seg_func(self.res,self.seg[p])
            if q&1==1:
                self.res=self.seg_func(self.res,self.seg[q])
                q-=1
            p=p//2
            q=(q-1)//2
        if p==q:self.res=self.seg_func(self.res,self.seg[p])
        else:self.res=self.seg_func(self.seg_func(self.res,self.seg[p]),self.seg[q])
        return self.res

def main():
    n=int(input())
    A=list(map(int,input().split()))
    seg_A=seg(A)
    dp=[[0]*n for _ in range(n)]  #[i,j]をまとめるために必要なコストの最小値
    for length in range(2,n+1):
        for i in range(n-length+1):
            j=i+length-1 #右側
            res=10**20
            for k in range(i+1,j+1):#区間[i,k)と[k,j]に分ける
                res=min(res,dp[i][k-1]+dp[k][j])
            dp[i][j]=res+seg_A.query(i,j+1)
    print(dp[0][n-1])


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
# 単位元とseg_funcを設定する
from fractions import gcd
class seg():
    def __init__(self,init_val):
        self.n=len(init_val)
        self.ide_ele=0 #単位元
        self.num=2**(self.n-1).bit_length() #n以上の最小の2のべき乗
        self.seg=[self.ide_ele]*2*self.num
        for i in range(self.n):
            self.seg[i+self.num-1]=init_val[i]
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.seg_func(self.seg[2*i+1],self.seg[2*i+2])
    def seg_func(self,a,b):
        return a+b #0
        #return a*b #1
        #return gcd(a,b) #0
        #return max(a,b) #-1か-10**10 (十分小さいもの)
        #return min(a,b) #10**10 (十分大きいもの)
    def update(self,k,x):
        k+=self.num-1
        self.seg[k]=x
        while k:
            k=(k-1)//2
            self.seg[k]=self.seg_func(self.seg[k*2+1],self.seg[k*2+2])
    def query(self,p,q): #O(logN)
        if q<=p:return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        self.res=self.ide_ele
        while q-p>1:
            if p&1==0:
                self.res=self.seg_func(self.res,self.seg[p])
            if q&1==1:
                self.res=self.seg_func(self.res,self.seg[q])
                q-=1
            p=p//2
            q=(q-1)//2
        if p==q:self.res=self.seg_func(self.res,self.seg[p])
        else:self.res=self.seg_func(self.seg_func(self.res,self.seg[p]),self.seg[q])
        return self.res

def main():
    n=int(input())
    A=list(map(int,input().split()))
    seg_A=seg(A)
    sum_a=sum(A)
    dp=[[0]*n for _ in range(n)]  #[i,j]をまとめるために必要なコストの最小値
    for length in range(2,n+1):
        for i in range(n-length+1):
            j=i+length-1 #右側
            res=10**20
            for k in range(i+1,j+1):#区間[i,k)と[k,j]に分ける
                res=min(res,dp[i][k-1]+dp[k][j])
            dp[i][j]=res+seg_A.query(i,j+1)
    print(dp[0][n-1])


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate

n = int(input())
a = [0] + list(accumulate(map(int, input().split())))

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

for i in range(n)[::-1]:
    for j in range(i + 1, n + 1):
        if j - i == 1:
            continue
        dp[i][j] = min([dp[i][k] + dp[k][j] for k in range(i + 1, j)])
        dp[i][j] += a[j] - a[i]

print(dp[0][n])

Submission status: Accepted

Solution code:
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
infi = 10 ** 20
SA = list(accumulate([0] + A))

dp = [[infi] * (n + 1) for _ in range(n + 1)]
# dp[i]左からi個決めた時の最小値とする。
if n >= 3:
    for i in range(n):
        dp[i][i] = 0
        dp[i][i + 1] = 0
        if i <= n - 2:
            dp[i][i + 2] = A[i] + A[i + 1]
    for d in range(n + 1):
        for i in range(n):
            j = i + d
            if j > n:
                continue
            if d >= 2:
                for m in range(i + 1, j + 1):
                    dp[i][j] = min(dp[i][j], dp[i][m] + dp[m][j] + SA[j] - SA[i])
    print(dp[0][n])
else:
    print(sum(A))

Submission status: Accepted

Solution code:
INF = 10 ** 18
n = int(input())
a = list(map(int, input().split()))
b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = b[i] + a[i]
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(2, n + 1):
    for j in range(n - i + 1):
        t = INF
        for k in range(j + 1, j + i):
            t = min(t, dp[j][k] + dp[k][j + i])
        dp[j][j + i] = b[j + i] - b[j] + t
print(dp[0][n])

Submission status: Accepted

Solution code:
import sys
INF = 10**14
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
a = LI()
sn = [[0 for _ in range(N)] for _ in range(N)]
dp = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    x = 0
    for j in range(i,N):
        x += a[j]
        sn[i][j] = x
for i in range(N):
    dp[i][i] = 0

for j in range(1,N):
    for i in range(j-1,-1,-1):
        for k in range(0,j-i):
            dp[i][j] = min(dp[i][j],dp[i+k+1][j]+ dp[i][i+k] + sn[i][j])
print(dp[0][-1])

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
INF = 10**18
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
a = LI()
sn = [[0 for _ in range(N)] for _ in range(N)]
dp = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    x = 0
    for j in range(i,N):
        x += a[j]
        sn[i][j] = x
for i in range(N):
    dp[i][i] = 0
    if i < N-1:
        dp[i][i+1] = sn[i][i+1]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    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 = [[None] * (n + 1) for _ in range(n + 1)]
    for l in range(n):
        dp[l][l + 1] = 0

    for width in range(2, n + 1):
        for l in range(n - width + 1):
            r = l + width
            res = INF
            for m in range(l + 1, r):
                res = min(res, dp[l][m] + dp[m][r] + S[r] - S[l])
            dp[l][r] = res

    print(dp[0][n])
resolve()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
a=[0]*(N+1)
for i in range(N):
    a[i+1]=a[i]+A[i]
d=[[0]*(N+1) for i in range(N+1)]
for w in range(2,N+1):
    for l in range(N+1-w):
        d[l][l+w]=min([d[l][m]+d[m][l+w] for m in range(l+1,l+w)])+a[l+w]-a[l]
print(d[0][N])

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1<<30)
def f(i,j,d):
  if i>=j:
    return 0
  if z[i][j]==-1:
    q=1<<64
    for k in xrange(i,j):
      q=min(q,s[j+1]-s[i]+f(i,k,d)+f(k+1,j,d))
    z[i][j]=q
  return z[i][j]
n=input()
a=map(int,raw_input().split())
s=[0]
for i in a:
  s.append(s[-1]+i)
z=[[-1]*n for i in xrange(n)]
print f(0,n-1,{})

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
dp = [[0 for _ in range(n)] for _ in range(n)]
size = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
  size[i][i] = a[i]
for i in range(n-1):
  for j in range(1,n-i):
    size[i][i+j] = size[i][i+j-1]+a[i+j]
for i in range(1,n):
  for j in range(0,n-i):
    mn = float("inf")
    for k in range(i):
      if mn > dp[j][j+k] + dp[j+k+1][j+i]:
        mn = dp[j][j+k] + dp[j+k+1][j+i]
    dp[j][j+i] = mn+ size[j][j+i]
print(dp[0][n-1])

Submission status: Accepted

Solution code:
n = int(input())
ns = list(map(int, input().split()))
dp = [[0] * n for i in range(n)]
cur = [0]
cnt = 0
for i in ns:
    cnt += i
    cur.append(cnt)

for i in range(n-1, -1, -1):
    for j in range(i + 1, n):
        dp[i][j] = min(dp[i][k] + dp[k + 1][j] for k in range(i, j)) + cur[j+1] - cur[i]
print(dp[0][-1])

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    inf = 10 ** 13
    dp = [[0]*N for i in range(N)]
    s = [0]*(N+1)
    for i, x in enumerate(a):
        s[i+1] = s[i]+a[i]
        dp[i][i] = 0
    for i in range(N-2, -1, -1):
        DP = dp[i]
        si = s[i]
        for j in range(i+1, N):
            tmp = s[j+1] - si
            D = inf
            for k in range(i, j):
                cost = DP[k]+dp[k+1][j]
                if D > cost:
                    D = cost
            DP[j] = D + tmp
    print(dp[0][N-1])
main()