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:
from itertools import accumulate
n = int(input())
alst = list(map(int, input().split()))
acc = [0] + list(accumulate(alst))
dp = [[None] * (n + 1) for _ in range(n + 1)]
for i in range(n):
  dp[i][i] = 0

for length in range(2, n + 1):
  for left in range(n - length + 1):
    right = left + length - 1
    dp[left][right] = min([dp[left][k] + dp[k + 1][right] for k in range(left, right)]) + acc[right + 1] - acc[left]
print(dp[0][n - 1])

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
dp=[[10**23]*N for i in range(N)]
S=[0]*(N+1)
for i in range(1,N+1):
    S[i]=S[i-1]+A[i-1]
for i in range(N):
    dp[i][i]=0
for k in range(1,N):
    for i in range(N-k):
        for l in range(i,i+k):
            dp[i][i+k]=min(dp[i][i+k],dp[i][l]+dp[l+1][i+k]+S[i+k+1]-S[i])
print(dp[0][N-1])

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit
N=int(input())
a=np.array([int(i) for i in input().split()],dtype=np.int64)

s=[0]

dp=np.array([[-1 for i in range(N)] for _ in range(N)],dtype=np.int64)

for i in range(1,N+1):
    s.append(s[i-1]+a[i-1])

s=np.array(s,dtype=np.int64)
for i in range(N):
    dp[i][i]=0

@njit('i8(i8,i8,i8[:,:],i8[:])', cache=True)
def calc(i,j,dp,s):
    if dp[i][j]!=-1:
        return dp[i][j]
    m=float('inf')
    for k in range(i,j):
        m=min(m,calc(i,k,dp,s)+calc(k+1,j,dp,s)+s[j+1]-s[i])
    dp[i][j]=m
    return dp[i][j]

print(calc(0,N-1,dp,s))

Submission status: Runtime Error

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+1):
      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: Runtime Error

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:

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>  
using namespace std; 
using ll  = long long;
const ll INF = 1e18 + 5;
int main() { 
	int n;
	cin >> n;
	vector<ll> arr(n,0);
	for(int i = 0; i < n; ++i){
		cin >> arr[i];
	}
	vector<vector<pair<ll,ll>>> dp(n, vector<pair<ll,ll>> (n,{INF,(ll)-1}));
	
	for(int i = n-1; i >= 0; i--){
		for(int j = i; j < n; ++j){
			if(i == j){
				dp[i][j] = {0,arr[i]};
				continue;
			}
			for(int k = i; k < j; ++k){
				ll temp = dp[i][k].first + dp[i][k].second + dp[k+1][j].first + dp[k+1][j].second;
				if(dp[i][j].first > temp){
					dp[i][j] =  {temp,dp[i][k].second + dp[k+1][j].second};
				}
			}
		}
	}
	cout << dp[0][n-1].first<<endl;
	
}

Submission status: Runtime Error

Solution code:
from functool import lru_cache
N = int(input())
A = list(map(int, input().split()))
INF = 1.0e+100

@lru_cache(maxsize=None)
def f(l, r):
  if r - l == 1:
    return (A[l], 0)
  ret = (INF, INF)
  for i in range(l+1, r):
    (lr, lc) = f(l, i)
    (rr, rc) = f(i, r)
    if lr+rr+lc+rc < ret[1]:
      ret = (lr+rr, lr+rr+lc+rc)
  return ret

print(f(0, N)[1])

Submission status: Runtime Error

Solution code:
N = input()
A = list(map(int, input().split()))
INF = 1.0e+100

def f(l, r):
  if r - l == 1:
    return A[l]
  ret = INF
  for i in range(l+1, r):
    lr = f(l, i)
    rr = f(i, r)
    ret = min(ret, lr+rr)
  return ret

print(f(l,r))

Submission status: Runtime Error

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

li = a.copy()
li2 = li.copy()
ans = 0
while(len(li)>1):
    mm = 10**10
    li2 = li.copy()
    for i in range(len(li2)-3):
        if li2[i]+li2[i+1] < mm:
            plc = i
            mm = li2[i]+li2[i+1]
    li = []
    for i in range(len(li2)):
        if i==plc:
            li.append(li2[i]+li2[i+1])
            ans += li2[i]+li2[i+1]
        elif i==plc+1:
            continue
        else:
            li.append(li2[i])
    #print(li)
print(ans)

Submission status: Runtime Error

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

li = a.copy()
li2 = li.copy()
ans = 0
while(len(li)>1):
    mm = 10**10
    li2 = li.copy()
    for i in range(len(li2)-2):
        if li2[i]+li2[i+1] < mm:
            plc = i
            mm = li2[i]+li2[i+1]
    li = []
    for i in range(len(li2)):
        if i==plc:
            li.append(li2[i]+li2[i+1])
            ans += li2[i]+li2[i+1]
        elif i==plc+1:
            continue
        else:
            li.append(li2[i])
    #print(li)
print(ans)

Submission status: Runtime Error

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

li = a.copy()
li2 = li.copy()
ans = 0
while(len(li)>1):
    mm = 10**10
    li2 = li.copy()
    for i in range(len(li2)-1):
        if li2[i]+li2[i+1] < mm:
            plc = i
            mm = li2[i]+li2[i+1]
    li = []
    for i in range(len(li2)):
        if i==plc:
            li.append(li2[i]+li2[i+1])
            ans += li2[i]+li2[i+1]
        elif i==plc+1:
            continue
        else:
            li.append(li2[i])
    #print(li)
print(ans)

Submission status: Runtime Error

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

li = a.copy()
li2 = li.copy()
ans = 0
while(len(li)!=1):
    mm = 10**10
    li2 = li.copy()
    for i in range(len(li2)-1):
        if li2[i]+li2[i+1] < mm:
            plc = i
            mm = li2[i]+li2[i+1]
    li = []
    for i in range(len(li2)):
        if i==plc:
            li.append(li2[i]+li2[i+1])
            ans += li2[i]+li2[i+1]
        elif i==plc+1:
            continue
        else:
            li.append(li2[i])
    #print(li)
print(ans)

Submission status: Runtime Error

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

li = a.copy()
li2 = li.copy()
ans = 0
while(len(li2)!=2):
    mm = 10**10
    li2 = li.copy()
    for i in range(len(li2)-1):
        if li2[i]+li2[i+1] < mm:
            plc = i
            mm = li2[i]+li2[i+1]
    li = []
    for i in range(len(li2)):
        if i==plc:
            li.append(li2[i]+li2[i+1])
            ans += li2[i]+li2[i+1]
        elif i==plc+1:
            continue
        else:
            li.append(li2[i])
    #print(li)
print(ans)

Submission status: Runtime Error

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

li = a.copy()
ans = 0
while(len(li)!=1):
    mm = 10**10
    li2 = li.copy()
    for i in range(len(li2)-1):
        if li2[i]+li2[i+1] < mm:
            plc = i
            mm = li2[i]+li2[i+1]
    li = []
    for i in range(len(li2)):
        if i==plc:
            li.append(li2[i]+li2[i+1])
            ans += li2[i]+li2[i+1]
        elif i==plc+1:
            continue
        else:
            li.append(li2[i])
    #print(li)
print(ans)

Submission status: Runtime Error

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

li = a.copy()
ans = 0
while(len(li)!=1):
    mm = 10**10
    for i in range(len(li)-1):
        if li[i]+li[i+1] < mm:
            plc = i
            mm = li[i]+li[i+1]
    li2 = li.copy()
    li = []
    for i in range(len(li2)):
        if i==plc:
            li.append(li2[i]+li2[i+1])
            ans += li2[i]+li2[i+1]
        elif i==plc+1:
            continue
        else:
            li.append(li2[i])
    #print(li)
print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
dp=[0]*(k+1)
for i in range(a[0]+1):
    dp[i]=1
for i in range(1,n):
    u=a[i]
    h=dp[:]
    for j in range(u+1,k+1):
        h[j]=(dp[j]-dp[j-u-1])%mod
    for j in range(1,k+1):
        h[j]=(h[j]+h[j-1])%mod
    dp=h
print(dp[k])

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
cnt = 0
while len(A)>1:
    cmin = 10**10
    for i in range(len(A)-2+1):
        if A[i]+A[i+1]<cmin:
            ind = i
            cmin = A[i]+A[i+1]
    cnt += cmin
    A[ind] += A[ind+1]
    A.pop(ind+1)
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

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

CSUM = [0 for _ in range(N)]
CSUM[0] = A[0]
for i in range(1,N):
  CSUM[i] = CSUM[i-1] + A[i]
#print(CSUM)
def csum(i,j):
  if i == 0:
    return CSUM[j]
  else:
    return CSUM[j]-CSUM[i-1]

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

for k in range(1,N):
  for i in range(N-k):
    j = i+k
    tmp = 10**10
    for l in range(i,j):
      tmp = min(tmp,dp[i][l]+dp[l+1][j])
    dp[i][j] = tmp + sum(S[i:j+1])

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

Submission status: Runtime Error

Solution code:
n,*a=list(map(int,open(0).read().split()))
b = [0] * (n+1)
for i in range(n): b[i+1] = b[i] + a[i]

dp = [[-1] * (n+1) for _ in range(n+1)]
def rec(l, r):
    if l == r: return 0
    if ~dp[l][r]:return dp[l][r]

    ret = 1e12
    for i in range(l, r):
        ret = min(ret, rec(l, i) + rec(i+1, r) + b[r+1] - b[l])
    dp[l][r] = ret
    return ret
print(rec(0, n-1))

Submission status: Runtime Error

Solution code:
n,*a=list(map(int,open(0).read().split()))
b = [0] * -~n
for i in range(n): b[i+1] = b[i] + a[i]

dp = [[-1] * -~n for _ in range(-~n)]
def rec(l, r):
    if l == r: return 0
    if ~dp[l][r]:return dp[l][r]

    ret = 1e12
    for i in range(l, r):
        ret = min(ret, rec(l, i) + rec(i+1, r) + b[r+1] - b[l])
    dp[l][r] = ret
    return ret
print(rec(0, n-1))

Submission status: Runtime Error

Solution code:
n = int(input())
a = [*map(int, input().split())]
ans = 0

while len(a) > 1:
	t = []
	for i in range(len(a) - 1):
		t.append(a[i] + a[i + 1])
	
	i = t.index(min(t))
	ans += t[i]

	a = a[:i] + [t[i]] + a[i + 2:]

print(ans)

Submission status: Runtime Error

Solution code:

# dp[0]=l[0]
# dp[1]=l[0]+l[1]
# mp = l[0]+l[1]
def fun(arr):
    # global ans1
    l = [int(j) for j in arr.split()]
    if len(l)==1:
        return 0
    if len(l)==0:
        return 0
    min_pair = 1
    
    ans = l[0]+l[1]
    # l = []
    for i in range(1,len(l)):
        if l[i]+l[i-1]<ans:
            min_pair = i
            ans = l[i]+l[i-1]
    mx = 10**11
    for i in range(1,len(l)):
        if l[i]+l[i-1]==ans:
            s = ""
            for j in range(i-1):
                s = s+str(l[j])+" "
            s = s+str(l[i]+l[i-1])+" "
            for j in range(i+1,len(l)):
                s = s+str(l[j])+" "
            
            x = fun(s)
            # print(s, "dekh",x)
            mx = min(l[i]+l[i-1]+x, mx)
            i1 = i
    # print(mx)
    ans1.append(mx)
    return mx
        
n = int(input())
l = [int(j) for j in input().split()]
s=""
for i in l:
    s = s+str(i)+" "
# ans1=[]
print(fun(s))
# print("f", sum(ans1))

Submission status: Runtime Error

Solution code:
from math import inf

n = int(input().strip())
l = list(map(int,input().strip().split()))
pref_sum = []
for i in range(len(l)):
	try:
		pref_sum.append(pref_sum[i-1]+l[i])
	except:
		pref_sum.append(l[i])

sol = [[None for _ in range(len(l))] for __ in range(len(l))]

def solve(i,j):
	global sol
	global pref_sum
	if sol[i][j] is not None:
		return sol[i][j]
	elif i == j:
		return 0
	data = 	inf
	for k in range(i,j):
		if i>0:
			data = min(data,solve(i,k)+solve(k+1,j)+pref_sum[j]-pref_sum[i-1])
		else:
			data = min(data,solve(i,k)+solve(k+1,j)+pref_sum[j])
	sol[i][j]=data
	return sol[i][j]

print(solve(0,len(l)-1))

Submission status: Runtime Error

Solution code:
from functools import*
@lru_cache(None)
def s(l,r):
  if r-l<2:return 0
  return min(s(l,i)+s(i,r)for i in range(l+1,r))+a[r-1]-a[l-1]
n,*a=map(int,open(0).read().split())
for i in range(n-1):a[i+1]+=a[i]
a+=[0]
print(s(0,n))

Submission status: Runtime Error

Solution code:
from functools import*
@lru_cache(None)
def s(a,d):
  n=len(a)
  if n==1:return a[0]*d
  return min(s(a[:i],d+1)+s(a[i:],d+1)for i in range(1,n))
n,*a=map(int,open(0).read().split())
print(s(tuple(a),0))

Submission status: Runtime Error

Solution code:
import fileinput


def solve_slimes(slimes):
    slime_union_table = [0] * len(slimes) * len(slimes)
    slime_cost_table = [0] * len(slimes) * len(slimes)

    for i in range(len(slimes)):
        slime_union_table[i] = slimes[i]

    for gap in range(1, len(slimes)):
        for li in range(len(slimes) - gap):
            split_size = slime_union_table[li] + slime_union_table[li + 1 + (gap - 1) * len(slimes)]
            slime_union_table[li + gap * len(slimes)] = split_size

            for split in range(0, gap):
                split_cost = slime_cost_table[li + split * len(slimes)] + slime_cost_table[li + split + 1 + (gap - split - 1) * len(slimes)] + split_size

                if slime_cost_table[li + gap * len(slimes)] == 0:
                    slime_cost_table[li + gap * len(slimes)] = split_cost

                else:
                    slime_cost_table[li + gap * len(slimes)] = min(
                        split_cost,
                        slime_cost_table[li + gap * len(slimes)]
                    )
    return slime_cost_table[len(slimes) * (len(slimes) - 1)]


inp = fileinput.FileInput()

inp.readline()
slimes = [int(v) for v in inp.readline().split()]

print(solve_slimes(slimes)

Submission status: Runtime Error

Solution code:
# 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))

Submission status: Runtime Error

Solution code:
N = int(input())
# A = list(map(int, input()))
A = tuple(map(int, input().split()))

from collections import defaultdict, deque
dp = defaultdict(lambda : -1)

q = deque([])
q.append( (A, 0) )

inf = float("inf")

ans = inf
while q:
    t,cost = q.popleft()
    if len(t) == 0:
        ans = min(ans, cost)
        continue
    
    tpl = t
    for i in range(len(tpl)-1):
        q.append (   ( tpl[0:i] + ( tpl[i]+tpl[i+1], )  + tpl[i+2: ],   tpl[i] + tpl[i+1] ) ) 


print(ans - sum(A))
exit(0)[

def dfs(tpl):
    if dp[tpl] != -1:
        return dp[tpl]
    if len(tpl) == 0:
        return 0
    if len(tpl) == 1:
        dp[tpl] = tpl[0]
        return tpl[0]

    lst_candidates = []
    now_cost = []
    for i in range(len(tpl)-1):
        # print("i: ", i )
        lst_candidates.append (   tpl[0:i] + ( tpl[i]+tpl[i+1], )  + tpl[i+2: ]   )
        now_cost.append ( tpl[i] + tpl[i+1] ) 

    total_cost = []
    for i in range(len(now_cost)):
        total_cost.append ( now_cost [i] + dfs(lst_candidates[i]))

    # print("totla_cost: ", total_cost)
    # print("lst_candidates: ", lst_candidates)
    res = min(total_cost)
    dp[tpl] = res

    return res

# print(dfs(A) - sum(A))