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: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
memo = {}
p = [0]
for num in a:
    p += [p[-1] + num]

dp = [[0 for _ in range(n)] for _ in range(n)]
for l in range(2,n+1):
    for i in range(n-l+1):
        dp[i][i+l-1] = min([dp[i][k] + dp[k+1][i+l-1] for k in range(i,i+l-1)]) + p[i+l] - p[i]
print(dp[0][n-1])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
memo = {}
p = [0]
for num in a:
    p += [p[-1] + num]

def dp(i,j):
    if i >= j:
        return 0
    if (i,j) not in memo:
        ans = float("inf")
        for k in range(i,j):
            temp = dp(i,k) + dp(k+1,j) + p[j+1] - p[i]
            ans = min(ans,temp)
        memo[i,j] = ans
    return memo[i,j]
print(dp(0,n-1))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

#from collections import defaultdict
#from heapq import heappush, heappop
from itertools import accumulate
from functools import lru_cache
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = sys.maxsize  # float("inf")


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, XS):
    accum = list(accumulate(XS)) + [0]
    @lru_cache(maxsize=None)
    def sub(L, R):
        # debug(": L,R", L, R)
        if L == R:
            return 0
        ret = INF
        for x in range(L, R):
            v = sub(L, x) + sub(x + 1, R)
            if v < ret:
                ret = v
            # debug("loop: ", XS[L:x+1], XS[x+1: R+1],  v)
        # debug(": ret, ", ret, accum[R] - accum[L - 1])
        return ret + accum[R] - accum[L - 1]
    return sub(0, N - 1)


def main():
    # parse input
    N = int(input())
    XS = list(map(int, input().split()))
    print(solve(N, XS))


# tests
T0 = """
2
10 20
"""


def test_T0():
    """
    >>> as_input(T0)
    >>> main()
    30
    """


T01 = """
3
10 20 30
"""


def test_T01():
    """
    >>> as_input(T01)
    >>> main()
    90
    """


T1 = """
4
10 20 30 40
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    190
    """


T2 = """
5
10 10 10 10 10
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    120
    """


T3 = """
3
1000000000 1000000000 1000000000
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    5000000000
    """


T4 = """
6
7 6 8 6 1 1
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    68
    """
# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N = INT()
a = [0]+LIST()
a_acc = list(accumulate(a))
dp = [[None]*(N+1) for _ in range(N+1)]

def rec(l, r):
    if dp[l][r]: return dp[l][r] 
    if l == r:
        return 0
    mi = INF
    for i in range(l, r):
        mi = min(mi, rec(l, i)+rec(i+1, r))
    dp[l][r] = mi + (a_acc[r]-a_acc[l-1])
    return dp[l][r]

print(rec(1, N))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N = INT()
a = [0]+LIST()
a_acc = list(accumulate(a))

@lru_cache(maxsize=None)
def rec(l, r):
    if l == r:
        return 0
    mi = INF
    for i in range(l, r):
        mi = min(mi, rec(l, i)+rec(i+1, r))
    return mi + (a_acc[r]-a_acc[l-1])

print(rec(1, N))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
suma = [0, a[0]]
for i in range(1, N):
    suma.append(suma[-1] + a[i])
inf = float("inf")
dp = [[-1 for i in range(N+1)] for j in range(N+1)]
# dp[i][j]は区間[i, j)での最小のコスト

# メモ化再帰
def rec(l, r):
    if r - l == 0:
        dp[l][r] = 0
        return 0
    elif r - l == 1:
        dp[l][r] = a[l]
        return a[l]

    # r - l >= 2である
    # iを媒介にdpを貪欲に探索する。
    res = inf
    for pos in range(l+1, r):
        tmp = 0
        if pos - l > 1:
            tmp += rec(l, pos) + suma[pos] - suma[l]
        else:
            tmp += rec(l, pos)
        if r - pos > 1:
            tmp += rec(pos, r) + suma[r] - suma[pos]
        else:
            tmp += rec(pos, r)
        res = min(res, tmp)
    dp[l][r] = res
    return res

print(rec(0, N))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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 += s[right] - (s[left-1] if left > 0 else 0)
    dp[left][right] = ret
    return ret

inf = 10**15
N = int(input())
A = list(map(int, input().split()))
s = list(accumulate(A))
dp = [[0]*(N) for _ in range(N)]
print(solve(0, N-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
sys.setrecursionlimit(10**6)
n=int(input())
a=list(map(int,input().split()))
s=[0]+list(itertools.accumulate(a))

dp=[[10**10]*(n+1) for _ in range(n)]
for l in range(n):
    dp[l][l+1]=0
def c(i,j):
    if dp[i][j]!=10**10:
        return dp[i][j]
    else:
        S=s[j]-s[i]
        for k in range(1,j-i):
            dp[i][j]=min(c(i,i+k)+c(i+k,j)+S,dp[i][j])
        return dp[i][j]

print(c(0,n))

Submission status: Time Limit Exceeded

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 W in range(2, N+1):
        for L in range(N-W+1):
            R = L+W-1
            dp[L][R] = min([dp[L][k-1] + dp[k][R] for k in range(L+1, R+1)]) + accAs[R+1] - accAs[L]

    ans = dp[0][-1]
    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

INF = float('inf')

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

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

dp = [[0] * (N) for _ in range(N)]
for num in range(2, N+1):
    for i in range(N-num+1):
        cost = INF
        for j in range(1, num):
            cost = min(cost, dp[i][i+j-1] + dp[i+j][i+num-1])
        dp[i][i+num-1] = accAs[i+num] - accAs[i] + cost

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**9)
N = int(input())
A = list(map(int, input().split()))
cost = [[sum(A[i:j]) for j in range(N+1)] for i in range(N+1)]
INF = float('inf')

# iからjまでの最小コストの再帰関数
@lru_cache(maxsize=10**9)
def rec(i,j):
    if j - i == 1:
        return 0
    ret = INF
    for m in range(i+1,j):
        ret = min(ret, rec(i,m) + rec(m,j)+ cost[i][j])
    return ret

print(rec(0,N))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
N = int(input())
A = list(map(int, input().split()))
cost = [[sum(A[i:j]) for j in range(N+1)] for i in range(N+1)]
INF = float('inf')

# iからjまでの最小コストの再帰関数
def rec(i,j):
    if j - i == 1:
        return 0
    ret = INF
    for m in range(i+1,j):
        ret = min(ret, rec(i,m) + rec(m,j)+ cost[i][j])
    return ret

print(rec(0,N))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
N = int(input())
A = list(map(int, input().split()))
INF = float('inf')

# iからjまでの最小コストの再帰関数
def rec(i,j):
    if j - i == 1:
        return 0
    ret = INF
    for m in range(i+1,j):
        ret = min(ret, rec(i,m) + rec(m,j)+ sum(A[i:j]))
    return ret

print(rec(0,N))

Submission status: Time Limit Exceeded

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


      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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")
def findans(start,end,li):
  #print("HI")
  if(start>=end):
    return 0
  if(dp[start][end]!=-1):
    return dp[start][end]
  ans = INF
  for k in range(start,end+1):

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

Submission status: Time Limit Exceeded

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] + range_sum(arr, L, R))

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: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000000)
n=int(input())
a=list(map(int,input().split()))
b=[0]
for i in a:b.append(i+b[-1])
dp=[n*[10**15]for _ in range(n)]
def dfs(l,r):
  if dp[l][r]!=10**15:return dp[l][r]
  if l==r:return 0
  dp[l][r]=b[r+1]-b[l]+min(dfs(l,i)+dfs(i+1,r)for i in range(l,r))
  return dp[l][r]
print(dfs(0,n-1))

Submission status: Time Limit Exceeded

Solution code:
# from random import randint 
# mod=10**9+7

def slime(n,arr):
	dp=[[float('inf')]*n for _ in range(n)]

	for i in range(n):
		dp[i][i]=arr[i]
		if i+1<n:
			dp[i][i+1]=arr[i]+arr[i+1]

	prefix=[0]
	for i in arr:
		prefix.append(prefix[-1]+i)


	for gap in range(1,n):
		for i in range(n):
			if i+gap <n:

				for k in range(i+1,i+gap-1):
					dp[i][i+gap]=min(dp[i][i+gap],dp[i][k-1]+dp[k+1][i+gap]+arr[k]+prefix[i+gap+1]-prefix[i]+min( prefix[k-1+1]-prefix[i] ,prefix[i+gap+1]-prefix[k+1]))

				dp[i][i+gap]=min(dp[i][i+gap],(arr[i]+prefix[i+gap+1]-prefix[i+1])+min(dp[i][i+gap-1],dp[i+1][i+gap]))
				# dp[i][i+gap]=min(dp[i][i+gap],(arr[i+gap]+prefix[i+gap]-prefix[i])+dp[i][i+gap-1])
	# print(prefix)
	# print(dp)
	return dp[0][n-1]
# with open ('input.txt') as f :
n=int(input())
arr=list(map(int,input().split()))
res=slime(n,arr)

# res=ways(100,10**5,[randint(0,10**5) for _ in range(100)])
print(res)

Submission status: Time Limit Exceeded

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))

    return dp(0, N-1)


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

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import lru_cache


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


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


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()

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

    return dp(0, N-1)


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

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline
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: Time Limit Exceeded

Solution code:
N=int(input())
ans={}
for i in range(N):
 ans[(i,i)] = 0
size=[0]*(N+1)
a = list(map(int,input().split()))
for i in range(N):
 size[i+1]=size[i]+a[i]
for j in range(1,N):
 for i in range(N-j):
  ans[(i,i+j)]=float('inf')
  for k in range(j):
   ans[(i,i+j)]=min(ans[(i,i+k)]+ans[(i+k+1,i+j)],ans[(i,i+j)])
  ans[(i,i+j)]+=(size[i+j+1]-size[i])
print(ans[0,N-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def cost(l,r):
 if (l,r) in memo:
  return memo[(l,r)]
 else:
  ans=float('inf')
  for j in range(l,r):
    if (l,j) in memo:
     a=memo[(l,j)]
    else:
     a=cost(l,j)
    if (j+1) in memo:
     b=memo[(j+1,r)]
    else:
     b=cost(j+1,r)
    ans=min(ans,a+b)
  memo[(l,r)]=ans+size[r+1]-size[l]
  return(ans+size[r+1]-size[l])
memo={}
N=int(input())
size=[0]*(N+1)
a = list(map(int,input().split()))
for i in range(N):
 memo[(i,i)] = 0
 size[i+1]=size[i]+a[i]
print(cost(0,N-1))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
from functools import lru_cache
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(N: int, a: "List[int]"):

    acc = [0]+list(accumulate(a))

    @lru_cache(maxsize=None)
    def rec(l, r):
        if l == r:
            return 0

        wa = acc[r+1]-acc[l]
        ans = INF
        for k in range(l, r):
            ans = min(rec(l, k) + rec(k+1, r), ans)
        return ans + wa

    print(rec(0, N-1))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(N: int, a: "List[int]"):

    acc = [0]+list(accumulate(a))

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

    def rec(l, r):
        if dp[l][r] > 0:
            return dp[l][r]
        if l == r:
            return 0

        wa = acc[r+1]-acc[l]
        ans = INF
        for k in range(l, r):
            ans = min(rec(l, k) + rec(k+1, r), ans)
        dp[l][r] = ans + wa
        return dp[l][r]

    print(rec(0, N-1))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
import sys

input = sys.stdin.buffer.readline

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: Time Limit Exceeded

Solution code:
from itertools import accumulate

N, *A = map(int, open(0).read().split())

S = [0] + list(accumulate(A))

memo = [[-1] * N for _ in range(N)]
def dp(L, R):
    if L == R:
        return 0
    if memo[L][R] >= 0:
        return memo[L][R]

    memo[L][R] = min(dp(L, c) + dp(c + 1, R) + S[R + 1] - S[L] for c in range(L, R))
    return memo[L][R]

print(dp(0, N - 1))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

N, *A = map(int, open(0).read().split())

S = [0] + list(accumulate(A))

memo = {}
def dp(L, R):
    if L == R:
        return 0
    if (L, R) in memo:
        return memo[(L, R)]

    memo[(L, R)] = min(dp(L, c) + dp(c + 1, R) + S[R + 1] - S[L] for c in range(L, R))
    return memo[(L, R)]

print(dp(0, N - 1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
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]

    @lru_cache(None)
    def dfs(l, r):
        # base case
        if r - l == 1:
            return 0
        # recursion
        return min(dfs(l, m) + dfs(m, r) + S[r] - S[l] for m in range(l + 1, r))

    print(dfs(0, n))
resolve()

Submission status: Time Limit Exceeded

Solution code:


def rec(a, s, e, dp, ss):
    if dp[s][e] > 0:
        return dp[s][e]

    if e - s == 1:
        dp[s][e] = 0
        return 0
    
    cur_min = float('inf')
    for i in range(s + 1, e):
        lc = rec(a, s, i, dp, ss)
        rc = rec(a, i, e, dp, ss)
        test = lc + rc + ss[s][e]
        if test < cur_min:
            cur_min = test
    dp[s][e] = cur_min
    return cur_min


def submit():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    ss = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

    for i in range(n + 1):
        for j in range(i, n + 1):
            ss[i][j] = sum(a[i:j])
    
    print(rec(a, 0, n, dp, ss))


submit()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    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] + x
        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):
                if D > DP[k]+dp[k+1][j]:
                    D = DP[k]+dp[k+1][j]
            DP[j] = D + tmp
    print(dp[0][N-1])


main()

Submission status: Time Limit Exceeded

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] + x
        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):
                if D > DP[k]+dp[k+1][j]:
                    D = DP[k]+dp[k+1][j]
            DP[j] = D + tmp
    print(dp[0][N-1])
main()

Submission status: Time Limit Exceeded

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] + x
        dp[i][i] = 0
    for i in range(N-1, -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):
                if D > DP[k]+dp[k+1][j] + tmp:
                    D = DP[k]+dp[k+1][j] + tmp
            DP[j] = D
    print(dp[0][N-1])
main()

Submission status: Time Limit Exceeded

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

    dp = [[10**13]*N for i in range(N)]
    s = [0] * (N+1)
    for i, x in enumerate(a):
        s[i+1] = s[i] + x
        dp[i][i] = 0
    for i in range(N-1, -1, -1):
        for j in range(i+1, N):
            tmp = s[j+1] - s[i]
            D = dp[i]
            for k in range(i, j):
                if D[j] > D[k]+dp[k+1][j] + tmp:
                    D[j] = D[k]+dp[k+1][j] + tmp

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

Submission status: Time Limit Exceeded

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

    dp = [[10**13]*N for i in range(N)]
    s = [0] * (N+1)
    for i in range(N):
        s[i+1] = s[i] + a[i]
        dp[i][i] = 0
    for i in range(N-1, -1, -1):
        for j in range(i+1, N):
            tmp = s[j+1] - s[i]
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j] + tmp)

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


main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
INF = 1 << 62


def solve(N: int, a: "List[int]"):
    dp = [[INF] * N for _ in range(N + 1)]
    cumsize = [0] * (N + 1)
    for i in range(1, N + 1):
        cumsize[i] = cumsize[i - 1] + a[i - 1]

    def mincost(length, head):
        if head + length > N:
            return INF
        if dp[length][head] < INF:
            return dp[length][head]
        base_cost = cumsize[head + length] - cumsize[head]
        if length == 1:
            dp[length][head] = 0
            return 0
        cost = INF
        split_point = head
        for j in range(1, length):
            if split_point + j >= N:
                continue
            c = mincost(j, head) + mincost(length - j, head + j)
            if cost > c:
                cost = c
        cost += base_cost
        dp[length][head] = cost
        return cost

    return mincost(N, 0)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, a))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
A = tuple(map(int, input().split()))
S = [0] + list(itertools.accumulate(A))

dp = [[0] * (N + 1) for _ in range(N + 1)]
for length in range(2, N + 1):
    for l in range(N - length + 1):
        r = length + l
        dp[l][r] = min(dp[l][m] + dp[m][r] for m in range(l + 1, r)) + S[r] - S[l]
print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
# 大きさがsum(a)のスライムが1匹いる
# dp[l][r]=min(区間[l,r]を分解するための最小コスト)
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
INF=10**15
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=[[-1]*n for i in range(n)]
for i in range(n):
    dp[i][i]=0
def memo(i,j):
    if dp[i][j]>=0:
        return dp[i][j]
    ans=INF
    for k in range(i,j):
        ans=min(ans,memo(i,k)+memo(k+1,j))
    dp[i][j]=ans+b[j+1]-b[i]
    return dp[i][j]
print(memo(0,n-1))

Submission status: Time Limit Exceeded

Solution code:
# 大きさがsum(a)のスライムが1匹いる
# dp[l][r]=min(区間[l,r]を分解するための最小コスト)
n=int(input())
a=list(map(int,input().split()))
INF=10**15
dp=[[0]*n for i in range(n)]
for i in range(n):
    dp[i][i]=a[i]
for i in range(n-1):
    for j in range(i+1,n):
        dp[i][j]=dp[i][j-1]+a[j]

for i in range(n-1):
    for j in range(i+1,n):
        ans=INF
        # print(j-i-1,j)
        for k in range(j-i-1,j):
            ans=min(ans,dp[j-i-1][k]+dp[k+1][j])
        if i<n-2:
            dp[j-i-1][j]+=ans
        else:
            print(ans)