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

cum = [[0]*(N) for i in range(N)]
for i in range(N):
  c = 0
  for j in range(i, N):
    c += A[j]
    cum[i][j] = c

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

def get_min_cost(i, j):
  global dp
  if dp[i][j] > 0:
    return dp[i][j]
  else:
    min_cost = 0
    for k in range(i, j):
      if min_cost == 0:
        min_cost = get_min_cost(i, k) + get_min_cost(k+1, j) + cum[i][j]
      else:
        cost = get_min_cost(i, k) + get_min_cost(k+1, j) + cum[i][j]
        min_cost = min(min_cost, cost)
    
    dp[i][j] = min_cost
    return dp[i][j]

print(get_min_cost(0, N-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)

N = int(raw_input())
COSTS = list(map(int, raw_input().split()))
min_cost_cache = {}
last = 0
SUMS = [None]*N
for i, cost in enumerate(COSTS):
    last += cost
    SUMS[i] = last
def get_min_cost_of_mixing_slime(i, j):

    if (i, j) in min_cost_cache:
        return min_cost_cache[i, j]

    if i==j:
        return 0

    s = SUMS[j] - (SUMS[i-1] if i != 0 else 0)
    min_cost = min(
        (get_min_cost_of_mixing_slime(i, x) + get_min_cost_of_mixing_slime(x+1, j) + s) for x in range(i, j))
    min_cost_cache[i, j] = min_cost
    return min_cost

print get_min_cost_of_mixing_slime(0, N-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = list(map(int, input().split()))
o = [0]*(N**2)
INF = 10**19
from itertools import accumulate
aa = [0] + list(accumulate(As))

for i in range(1, N+1):
    for j in range(N-i+1):
        span = (i-1)*N+j
        # 長さi, 開始位置jの合成コスト+構成要素の和
        if i == 1:
            o[span] = As[j]
            continue
        C = INF
        for k in range(1, i):
            # 長さ,開始位置=(k,j)と(i-k,j+k)
            span1, span2 = (k-1)*N+j, (i-k-1)*N+j+k
            C = min(C, o[span1]+o[span2])
        o[span] = C + aa[(j+i-1)+1] - aa[(j-1)+1]
print(o[span]-aa[-1])

Submission status: Time Limit Exceeded

Solution code:
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista

def potworny_Jan_Kanty():
    N = wczytaj_liste()[0]
    potwory = wczytaj_liste()
    wynik = {}
    for dlugosc_przedzialu in range(1,len(potwory)+1):
        for poczatek in range(len(potwory)-dlugosc_przedzialu+1): 
            koniec = dlugosc_przedzialu + poczatek
            if dlugosc_przedzialu == 1:
                wynik[poczatek,koniec] = 0
            else:
                odp = 10**18
                for i in range(1, dlugosc_przedzialu):
                    kandydat = wynik[poczatek+i,koniec]+wynik[poczatek, poczatek+i]
                    if kandydat < odp: 
                        odp = kandydat
                wynik[poczatek, koniec] = odp+sum(potwory[poczatek:koniec])
    print(wynik[0, N])
    
potworny_Jan_Kanty()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate as ac
n=int(input())
dp=[[0for i in range(n)]for j in range(n)]
acc=[0]+list(ac(list(map(int,input().split()))))
def f(x,y):
    if dp[x][y]:
        return dp[x][y]
    else:
        if x==y:return 0
        else:
            dp[x][y]=min(f(x,i)+f(i+1,y)for i in range(x,y))+acc[y+1]-acc[x]
            return dp[x][y]
print(f(0,n-1))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
import functools
INF = float("inf")


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

    dp = [[0]*N for _ in range(N)]
    acc = [0]+list(accumulate(a))

    @functools.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:
def f():
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=[int(j) for j in input().split()]
    #import numpy as np
    #dp=np.zeros((n,n,2),dtype=np.int64)
    dp=[[[0,0]for j in range(n)] for i in range(n)]

    for i in range(1,1+n):
        for j in range(n-i+1):
            #j~j+i-1
            if i==1:
                dp[j][j][1]=a[j]
                continue
            tmp=10**18
            for k in range(i-1):
                #j~j+k,j+k+1~j+i-1
                if sum(dp[j][j+k])+sum(dp[j+k+1][j+i-1])<tmp:
                    tmp=sum(dp[j][j+k])+sum(dp[j+k+1][j+i-1])
                    dp[j][j+i-1][0]=tmp
                    dp[j][j+i-1][1]=dp[j][j+k][1]+dp[j+k+1][j+i-1][1]
    print(dp[0][n-1][0])

f()

Submission status: Time Limit Exceeded

Solution code:
def f():
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=[int(j) for j in input().split()]
    import numpy as np
    #dp=np.zeros((n,n,2),dtype=np.int64)
    dp=[[[0,0]for j in range(n)] for i in range(n)]

    for i in range(1,1+n):
        for j in range(n-i+1):
            #j~j+i-1
            if i==1:
                dp[j][j][1]=a[j]
                continue
            tmp=10**18
            for k in range(i-1):
                #j~j+k,j+k+1~j+i-1
                if sum(dp[j][j+k])+sum(dp[j+k+1][j+i-1])<tmp:
                    tmp=sum(dp[j][j+k])+sum(dp[j+k+1][j+i-1])
                    dp[j][j+i-1][0]=tmp
                    dp[j][j+i-1][1]=dp[j][j+k][1]+dp[j+k+1][j+i-1][1]
    print(dp[0][n-1][0])

f()

Submission status: Time Limit Exceeded

Solution code:
def f():
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=[int(j) for j in input().split()]
    import numpy as np
    dp=np.zeros((n,n,2),dtype=np.int64)

    for i in range(1,1+n):
        for j in range(n-i+1):
            #j~j+i-1
            if i==1:
                dp[j][j][1]=a[j]
                continue
            tmp=10**18
            for k in range(i-1):
                #j~j+k,j+k+1~j+i-1
                if dp[j][j+k].sum()+dp[j+k+1][j+i-1].sum()<tmp:
                    tmp=dp[j][j+k].sum()+dp[j+k+1][j+i-1].sum()
                    dp[j][j+i-1][0]=tmp
                    dp[j][j+i-1][1]=dp[j][j+k][1]+dp[j+k+1][j+i-1][1]
    print(dp[0][n-1][0])

f()

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
N = int(input())
a = list(map(int, input().split()))
S = [0]*(N+1)#i~j-1の和はS[j]-S[i]
for i in range(1, N+1):
    S[i] = S[i-1]+a[i-1]
memo = [[-1]*(N+1) for _ in range(N)]
def dp(i, j):
    if memo[i][j]>=0:
        return memo[i][j]
    if j-i == 1:
        memo[i][j] = 0
        return 0
    memo[i][j] = min(dp(i, k)+dp(k, j)+S[j]-S[i]for k in range(i+1, j))
    return memo[i][j]
print(dp(0, N))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    dp = [[0] * (len(A) - i) for i in range(len(A))]

    for i in range(1, len(A)):
        s = sum(A[:i])
        for j in range(len(A) - i):
            s += A[i + j]
            dp[i][j] = min(dp[k][j] + dp[i - k - 1][j + k + 1] for k in range(i)) + s
            s -= A[j]
    print(dp[-1][0])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    l = [[10**9+1] * (N+1) for _ in range(N+1)]
    s = [[0] * (N+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(N+1):
            s[i][j] = sum(a[k] for k in range(i, j))
    for i in range(N):
        l[i][i+1] = 0
    for j in range(2, N+1):
        for i in range(N):
            m = i + j
            if m > N:
                continue
            l[i][m] = min(l[i][k] + l[k][m] for k in range(i+1, m)) + s[i][m]
    return l[0][-1]

print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    l = [[10**9+1] * (N+1) for _ in range(N+1)]
    for i in range(N):
        l[i][i+1] = 0
    for j in range(2, N+1):
        for i in range(N):
            m = i + j
            if m > N:
                continue
            l[i][m] = min(l[i][k] + l[k][m] for k in range(i+1, m)) + sum(a[k] for k in range(i, m))
    return l[0][-1]

print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    ans = 0
    while len(aa) > 1:
        mn = 10**10
        mi = -1
        for i in range(len(aa) - 1):
            now = aa[i] + aa[i + 1]
            if now < mn:
                mn = now
                mi = i
        aa = aa[:mi] + [mn] + aa[mi + 2:]
        ans+=mn
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
def solve(n, a):
    from itertools import accumulate

    inf = (400 ** 2) * (10 ** 9) + 10

    # [l,r)
    def dfs(l, r):
        if memo[l][r] != -1:
            return memo[l][r]
        if r - l == 1:
            return 0
        res = inf
        for c in range(l + 1, r):
            # [l, c), [c, r)
            res = min(res, dfs(l, c) + dfs(c, r))
        res += acc[r] - acc[l]
        memo[l][r] = res
        return res

    acc = (0,) + tuple(accumulate(a))
    memo = [[-1] * (n + 1) for _ in range(n + 1)]

    return dfs(0, n)


if __name__ == '__main__':
    n = int(input())
    a = tuple(map(int, input().split()))
    print(solve(n, a))

Submission status: Time Limit Exceeded

Solution code:
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 + csum(i,j)

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

Submission status: Time Limit Exceeded

Solution code:
n,*a=list(map(int,open(0).read().split()))
dp = [[-1] * (n+1) for _ in range(n+1)]
b = [0] * (n+1)
for i in range(n): b[i+1] = b[i] + a[i]
def rec(l, r):
    if l == r:
        return 0
    if dp[l][r] != -1:
        return dp[l][r]
    ret = 1000000000000
    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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

# 累積和
acc = [0] + list(accumulate(A))

dp = list2d(N+1, N+1, INF)
for i in range(N):
    dp[i][i+1] = 0
for d in range(2, N+1):
    for l in range(N+1-d):
        r = l + d
        for m in range(l+1, r):
            dp[l][r] = min(dp[l][r], dp[l][m]+dp[m][r])
        # この先切った分の最小値に、今回のlとrを合体させる分を足す
        dp[l][r] += acc[r] - acc[l]
print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
slime = list(map(int, input().split()))
cumSlime = [0] * (N + 1)
for i in range(1, N + 1):
    cumSlime[i] = cumSlime[i - 1] + slime[i - 1]

def calc(qLeft, qRight):
    st = deque([(False, qLeft, qRight)])
    memo = dict()

    while st:
        canCalc, left, right = st.pop()

        if left + 1 == right:
            memo[(left, right)] = slime[left]
            continue

        if (left, right) in memo:
            continue

        if canCalc:
            ret = float('inf')
            for mid in range(left + 1, right):
                ret = min(ret, memo[(left, mid)] + memo[(mid, right)])
            ret += cumSlime[right] - cumSlime[left]
            memo[(left, right)] = ret
        else:
            st.append((True, left, right))
            for mid in range(left + 1, right):
                if not (left, mid) in memo:
                    st.append((False, left, mid))
                if not (mid, right) in memo:
                    st.append((False, mid, right))

    return memo[(qLeft, qRight)]

ans = calc(0, N) - sum(slime)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
slime = list(map(int, input().split()))
cumSlime = [0] * (N + 1)
for i in range(1, N + 1):
    cumSlime[i] = cumSlime[i - 1] + slime[i - 1]

def calc(qLeft, qRight):
    st = deque([(False, qLeft, qRight)])
    memo = dict()

    while st:
        canCalc, left, right = st.pop()

        if canCalc:
            if left + 1 == right:
                memo[(left, right)] = slime[left]
                continue
            ret = float('inf')
            for mid in range(left + 1, right):
                ret = min(ret, memo[(left, mid)] + memo[(mid, right)])
            ret += cumSlime[right] - cumSlime[left]
            memo[(left, right)] = ret
        else:
            st.append((True, left, right))
            if left + 1 == right:
                continue
            for mid in range(left + 1, right):
                if not (left, mid) in memo:
                    st.append((False, left, mid))
                if not (mid, right) in memo:
                    st.append((False, mid, right))

    return memo[(qLeft, qRight)]

ans = calc(0, N) - sum(slime)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = [int(x) for x in input().split()]

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

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

for j in range(1, N):
    for i in range(N-1):
        if i + j >= N:
            break
        minimum = float('inf')
        for k in range(j):
            #print('i:',i,' j:',j,' k:',k,' i+k:',i+k,' j-k:',j-k)
            temp = dp[i][k] + dp[i+k+1][j-k-1]
            if minimum > temp:
                minimum = temp
        dp[i][j] = minimum + (cumsum[i+j] - cumsum[i-1] if i > 0 else cumsum[i+j])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

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

flag = [[0]*(N+1) for i in range(N+1)]

cA = [0]*(N+1)
for i in range(1,N+1) :
    cA[i] = cA[i-1] + A[i-1]

def f(left, right) :
    if flag[left][right] :
        return dp[left][right]
    elif left == right :
        return 0
    else :
        res = float("inf")
        for i in range(left, right) :
            res = min(res, f(left, i) + f(i+1, right))
        res += cA[right+1] - cA[left]
        dp[left][right] = res
        return res

ans = f(0,N-1)

print(ans)

#print(cA)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    n,k = LI()
    a = LI()
    dp = [0 for i in range(k+1)]
    f = [0 for i in range(k+1)]
    for i in range(k+1):
        if not f[i]:
            for j in a:
                if i-j >= 0:
                    dp[i] = 1-dp[i-j]
                    if dp[i] == 0:
                        break
            else:
                dp[i] = 1
    print(["First","Second"][dp[k]])
#B
def B():
    n = I()
    a = LI()
    ma = n*(n+1)//2
    su = sum(a)
    s = [1 for i in range(n+1)]
    for i in range(1,n):
        s[i+1] = s[i]+n-i+1
    d = [None for i in range(ma+1)]
    d[0] = 0
    k = 1
    for i in range(1,n+1):
        for j in range(n+1-i):
            d[k+j] = i
        k += n+1-i
    k = n%2
    dp = [su if (d[i]+k)%2 else -su for i in range(ma+1)]
    dp[0] = 0
    if k:
        for i in range(n):
            dp[i+1] = a[n-1-i]
    else:
        for i in range(n):
            dp[i+1] = -a[n-1-i]
    for i in range(1,ma):
        r = n-1-(i-s[d[i]])
        l = r+1-d[i]
        j = i+(n-d[i])
        j2 = j+1
        if (d[i]+k)%2:
            if r < n-1:
                if a[r+1]+dp[i] > dp[j]:
                    dp[j] = a[r+1]+dp[i]
            if l > 0:
                if a[l-1]+dp[i] > dp[j2]:
                    dp[j2] = a[l-1]+dp[i]
        else:
            if r < n-1:
                if -a[r+1]+dp[i] < dp[j]:
                    dp[j] = -a[r+1]+dp[i]
            if l > 0:
                if -a[l-1]+dp[i] < dp[j2]:
                    dp[j2] = -a[l-1]+dp[i]
    print(dp[ma])
    return

#C
def C():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%mod

    n,k = LI()
    a = LI()
    """
    fact = [1]
    for i in range(n+k):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*(n+k+1)
    inv[n+k] = pow(fact[n+k],mod-2,mod)
    for i in range(n+k)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    f = [comb(i+n-1,n-1) for i in range(k+1)]
    for i in a:
        for j in range(k-i)[::-1]:
            f[j+i+1] -= f[j]
            f[j+i+1] %= mod
    print(f[k])
    """
    dp = [[0]*(k+1) for i in range(n+1)]
    for i in range(k+1):
        dp[0][i] = 1
    for i in range(n):
        ni = i+1
        ai = a[i]
        for j in range(k+1):
            if j >= ai+1:
                dp[ni][j] = (dp[i][j]-dp[i][j-ai-1])%mod
            else:
                dp[ni][j] = dp[i][j]
        if i < n-1:
            for j in range(k):
                dp[ni][j+1] += dp[ni][j]
                dp[ni][j+1] %= mod
    print(dp[n][k]%mod)
    return

#D
def D():
    def dp(l,r):
        if mem[(l,r)] != None:
            return mem[(l,r)]
        mem[(l,r)] = float("inf")
        for i in range(l+1,r):
            res = dp(l,i)+dp(i,r)+a[r]-a[l]
            if res < mem[(l,r)]:
                mem[(l,r)] = res
        return mem[(l,r)]
    n = I()
    a = LI()
    mem = defaultdict(lambda : None)
    for i in range(n):
        mem[(i,i+1)] = 0
    a.insert(0,0)
    for i in range(n):
        a[i+1] += a[i]
    print(dp(0,n))
    return

#E
def E():
    n = I()
    a = LIR(n)
    b = [1<<i for i in range(n+1)]
    dp = [0 for i in range(b[n])]
    dp[0] = 1
    for i in range(n):
        for k in range(b[n])[::-1]:
            for j in range(n):
                if a[i][j] and not b[j]&k:
                    dp[b[j]|k] += dp[k]
                    dp[b[j]|k] %= mod
    print(dp[-1])
#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

prefix = [0]*n
prefix[0] = a[0]

for i in range(1, n):
    prefix[i] = prefix[i-1]+a[i]

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


def solve(s, e):
    if (s>=e):
        return 0

    if (dp[s][e]!=-1):
        return dp[s][e]

    ans = 1e18
    for i in range(s, e):
        innerans = solve(s, i)+solve(i+1, e)
        p = prefix[i]-(prefix[s-1] if s-1>=0 else 0)
        q = prefix[e]-prefix[i]
        innerans += p+q
        ans = min(ans, innerans)
    
    dp[s][e]=ans
    return ans


print(solve(0, n-1))

Submission status: Time Limit Exceeded

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

def A(i, j):
    if i == j:
        return 0
    elif j == i + 1:
        return sum(a[i:i+2])
    else:
        S = sum(a[i:j+1])
        return min([A(i, k) + A(k+1, j) for k in range(i, j)]) + S

print(A(0, N-1))

Submission status: Time Limit Exceeded

Solution code:
from numpy import*
n,a=open(0)
n=int(n)
a=cumsum(int64([0]+a.split()))
dp=zeros((n,n+1),'i8')
for k in range(1,n):
  l=arange(n-k)
  r=arange(k+1,n+1)
  m=array([arange(i+1,j)for i,j in zip(l,r)]).T
  dp[l,r]=amin(dp[l,m]+dp[m,r],0)+a[r]-a[l]
print(dp[0,n])

Submission status: Time Limit Exceeded

Solution code:
from numpy import*
n,a=open(0)
n=int(n)
a=cumsum(int64([0]+a.split()))
dp=zeros((n,n+1),'i8')
for k in range(1,n):
  l=arange(n-k)
  r=arange(k+1,n+1)
  dp[l,r]=amin([dp[l,m]+dp[m,r]for m in array([arange(i+1,j)for i,j in zip(l,r)]).T],0)+a[r]-a[l]
print(dp[0,n])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def main():
  def s(l,r):
    k=l*n+r
    if d[k]:return d[k]
    if r-l<2:return 0
    d[k]=t=min(s(l,i)+s(i,r)for i in range(l+1,r))+a[r-1]-a[l-1]
    return t
  n,*a=map(int,open(0).read().split())
  d=[None]*(n*n+1)
  for i in range(n-1):a[i+1]+=a[i]
  a+=[0]
  print(s(0,n))
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def main():
  def s(l,r):
    if(l,r)in d:return d[(l,r)]
    if r-l<2:return 0
    d[(l,r)]=min(s(l,i)+s(i,r)for i in range(l+1,r))+a[r-1]-a[l-1]
    return d[(l,r)]
  d={}
  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))
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import*
sys.setrecursionlimit(10**7)
@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: Time Limit Exceeded

Solution code:
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(a,0))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

"""
最後の2つを決める：[0,x) [x,N)
小問題2つに分割できる。
全ての連続区間を計算すればよい
"""

from functools import lru_cache
import itertools

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

A_cum = tuple(itertools.accumulate(A))

@lru_cache(None)
def min_cost(L,R):
    # 区間[L,R)
    if R - L == 1:
        return 0
    x = min(min_cost(L,i) + min_cost(i,R) for i in range(L+1,R))
    x += A_cum[R-1] - (A_cum[L-1] if L > 0 else 0)
    return x

answer = min_cost(0,N)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(map(int,input().split()))
dp = [[0 for _ in range(n)] for _ in range(n)]
psum = [0 for _ in range(n+1)]
sm = 0
for i in range(n):
    sm +=s[i]
    psum[i+1]=sm
def findMin(left,right):
    dp[left][right]=dp[left][left]+dp[left+1][right]+psum[right+1]-psum[left]
    for i in range(left+1,right):
        dp[left][right] = min(dp[left][right],dp[left][i]+dp[i+1][right]+psum[right+1]-psum[left])
for length in range(2,n+1):
    for l in range(n-length+1):
        r = l+length-1
        findMin(l,r)

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

Submission status: Time Limit Exceeded

Solution code:
# @author 

import sys

class NSlimes:
    def solve(self):
        n = int(input())
        a = [None] + [int(_) for _ in input().split()]

        dp = [[float('inf')] * (n + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            dp[i][i] = 0
        for i in range(n + 1, 0, -1):
            for j in range(1, n + 1):
                for k in range(i, j):
                    dp[i][j] = min(dp[i][k] + dp[k + 1][j] + sum(a[p] for p in range(i, j + 1)), dp[i][j])

        print(dp[1][n])


        # Greedy, not working

        # b = a[:]
        # ans = 0
        # for i in range(n - 1):
        #     idx = -1
        #     mn = float('inf')
        #     for j in range(n - 1 - i):
        #         if b[j] + b[j + 1] < mn:
        #             mn = b[j] + b[j + 1]
        #             idx = j
        #     assert(idx != -1)
        #     b[idx] += b[idx + 1]
        #     ans += b[idx]
        #     del b[idx + 1]
        # assert(len(b) == 1)
        # print(ans)

solver = NSlimes()
input = sys.stdin.readline

solver.solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

# N < 100 , K < 10^5
N = inp()
aa = inpl()

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

raa = [0]*(N+1)
tmp = 0
for i in range(N):
    tmp += aa[i]
    raa[i+1] = tmp

def calc(l,r):
    global dp
    if r-l <= 1:
        return 0
    elif r-l == 2:
        return aa[l]+aa[r-1]
    else:
        if dp[l][r-1] != INF:
            return dp[l][r-1]
        else:
            tmp = INF
            for s in range(l,r-1):
                tmp = min(calc(l,s+1)+calc(s+1,r)+raa[r]-raa[l],tmp)

            dp[l][r-1] = tmp
            return tmp


print(calc(0,N))

Submission status: Time Limit Exceeded

Solution code:
inf = float('inf')

def accmulate(array):
    global cs
    cs = [0]*(len(array)+1)
    for i in range(len(array)):
        cs[i+1] = cs[i] + array[i]

def query(l,r):
    return cs[r+1] - cs[l]

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

accmulate(A)

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

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

for i in range(N-1):
    dp[i][i+2] = A[i] + A[i+1]

for b in range(3,N+1):
    for i in range(N-b+1):
        j = i + b
        for k in range(i+1,j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + query(i,j-1))

ans = dp[0][N]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
arr = map(int,raw_input().split())
dp = [[-1 for i in range(504)] for i in range(504)]
prefix = [0]
for i in range(n):
	prefix.append(prefix[-1] + arr[i])


def solve(i,j):
	if (i>j):
		return (10**15)
	if (i==j):
		dp[i][i] = 0 
		return dp[i][i]
	if (i+1 == j):
		dp[i][j] = arr[i-1] + arr[j-1]
		return dp[i][j]

	if (dp[i][j] != -1):
		return dp[i][j]
	ma = (10**15)
	for k in range(i,j):
		ma = min(ma, solve(i,k) + solve(k+1,j))
	ma += prefix[j] - prefix[i-1]
	dp[i][j] = ma
	return ma

print solve(1,n)

"""
6
1 2 1000 1000 2 1


"""

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
d = [[0]*n for i in range(n)]
pref = [a[0]]
p,k=0,0
for i in range(1,n):
    pref.append(pref[i-1]+a[i])
for size in range(1,n+1):
    for l in range(n):
        r = l + size - 1
        if r == n:
            break
        if size == 1:
            d[l][l]=0
        else:
            d[l][r]=2e18
            calc = 0
            for mid in range(l,r):
                if l == 0:
                    calc = d[l][mid] + d[mid + 1][r] + pref[r]
                else:
                    calc = d[l][mid] + d[mid + 1][r] + (pref[r] - pref[l-1])
                d[l][r] = min(d[l][r],calc)
print(d[0][-1])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = [[0]*n for i in range(n)]
pref = [a[0]]
for i in range(1, n):
    pref.append(pref[i-1]+a[i])
for size in range(1, n+1):
    for l in range(n):
        r = l+size-1
        if r == n:
            break
        if size == 1:
            dp[l][l] = 0
        else:
            dp[l][r]=2e18
            for mid in range(l, r):
                if l == 0:
                    calc = dp[l][mid]+dp[mid+1][r]+pref[r]
                else:
                    calc = dp[l][mid]+dp[mid+1][r]+pref[r]-pref[l-1]
                dp[l][r] = min(dp[l][r], calc)
print(dp[0][-1])

Submission status: Time Limit Exceeded

Solution code:
def pref(lst):
    listik = [lst[0]]
    for i in range(1, len(lst)):
        listik.append(listik[i-1]+lst[i])
    return listik
n = int(input())
a = list(map(int, input().split()))
prefix = pref(a)
dp = [[0]*n for i in range(n)]
for lena in range(1, n+1):
    for l in range(n):
        r = l+lena-1
        if r == n:
            break
        if lena == 1:
            dp[l][l] = 0
        else:
            dp[l][r] = 2e18
            for mid in range(l, r):
                if l == 0:
                    calc = dp[l][mid] + dp[mid + 1][r] + prefix[r]
                else:
                    calc = dp[l][mid] + dp[mid+1][r]+prefix[r]-prefix[l-1]
                dp[l][r] = min(dp[l][r], calc)
print(dp[0][n-1])

Submission status: Time Limit Exceeded

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