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: Wrong Answer

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

if N == 2:
    print(sum(a))
    exit()

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

def a_sum(i,j):
    return a_cum[j] - a_cum[i]

INF = 10**9 * 400

dp = [[INF]*(N+1) for _ in range(N+1)]
for i in range(N):
    dp[i][i+1] = 0
    if i != N-1:
        dp[i][i+2] = a[i] + a[i+1]

for length in range(3, N+1):
    for l in range(N-length+1):
        tmp = INF
        for m in range(l+1, l+length):
            tmp = min(tmp, dp[l][m] + dp[m][l+length] + a_sum(l, l+length))
        dp[l][l+length] = tmp

print(dp[0][N])

Submission status: Wrong Answer

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


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

a_accum = [0]
for i in range(n):
    a_accum.append(a_accum[-1] + a[i])

for k in range(2, n+1):
    for i in range(n-k+1):
        mini = 10**10
        for j in range(i+1, i+k):
            mini = min(dp[i][j] + dp[j][i+k], mini)
        dp[i][i+k] = mini + a_accum[i+k]-a_accum[i]
print(dp[0][n])

Submission status: Wrong Answer

Solution code:
from itertools import accumulate


def dfs(l, r):
    if memo[l][r]:
        return dp[l][r]
    for i in range(l, r):
        dp[l][r] = min(max(0, dp[l][r]), dfs(l, i) + dfs(i + 1, r) + acc_A[r] - acc_A[l - 1])
    memo[l][r] = True
    return dp[l][r]


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

INF = 10 ** 18
dp = [[INF] * (n + 1) for _ in range(n + 1)]
memo = [[False] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    dp[i][i] = 0
    memo[i][i] = True


print(dfs(1, n))
[print(row) for row in memo]

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(100000000)
MOD = 10**9+7
INF = 10 ** 10
from functools  import lru_cache

MAXN = 405
a = [0] * MAXN
dp = [[-1] * MAXN for _ in range(MAXN)]
def dfs(l,r):
    if dp[l][r] != -1:
        return dp[l][r]
    if r - l == 1:
        dp[l][r] = 0
        return 0
    ans = INF
    for i in range(l + 1,r):
        ans = min(ans,dfs(l,i) + dfs(i,r)) 
    if l == 0:
        ans += a[r - 1]
    else:
        ans += a[r - 1] - a[l - 1]
    dp[l][r] = ans
    return ans

def main():
    n = int(input())
    b = list(map(int,input().split()))
    a[:n] = b

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

    ans = dfs(0,n)
    print(ans)
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(100000000)
MOD = 10**9+7
INF = 10 ** 10
from functools  import lru_cache

MAXN = 405
a = [0] * MAXN
dp = [[-1] * MAXN for _ in range(MAXN)]
def dfs(l,r):
    if dp[l][r] != -1:
        return dp[l][r]
    if r - l == 1:
        dp[l][r] = 0
        return 0
    else:
        ans = INF
        for i in range(l + 1,r):
            ans = min(ans,dfs(l,i) + dfs(i,r)) 
        if l == 0:
            ans += a[r - 1]
        else:
            ans += a[r - 1] - a[l - 1]
        dp[l][r] = ans
        return ans

def main():
    n = int(input())
    b = list(map(int,input().split()))
    a[:n] = b

    for i in range(1,n):
        a[i] += a[i - 1]
    
    ans = dfs(0,n)
    print(ans)
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 10**9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]



n = val()
l = li()

ans = curr =ind =0
while len(l) > 1:
    curr = ind = float('inf')
    for j in range(1,len(l)):
        if l[j] + l[j - 1] < curr:
            curr = l[j] + l[j-1]
            ind = j
    l[ind - 1] += l[ind]
    ans += l[ind - 1]
    l.pop(ind)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(100000000)
MOD = 10**9+7
INF = 10 ** 9
from functools  import lru_cache

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

    for i in range(1,n):
        a[i] += a[i - 1]
    
    @lru_cache(maxsize = None)
    def dfs(l,r):
        if r - l == 1:
            return 0
        else:
            ans = INF
            for i in range(l + 1,r):
                ans = min(ans,dfs(l,i) + dfs(i,r)) 
            if l == 0:
                ans += a[r - 1]
            else:
                ans += a[r - 1] - a[l - 1]
            return ans
    
    ans = dfs(0,n)
    print(ans)
if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

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

for i in range(n-1):
  tmp = 10**10
  ind = 0
  for j in range(len(a)-1):
    if tmp > a[j]+a[j+1]:
      tmp = a[j]+a[j+1]
      ind = j
  a[ind] = a[ind] + a[ind +1]
  del a[ind + 1]
  dp[i+1] = dp[i] + tmp

print(dp[n-1])

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
import numpy
B=[0]+list(numpy.cumsum(A))
print(B)
dp=[[0]*(N+1) for i in range(N)]
#k:いくつのスライムを合体しているか
for k in range(2,N+1):
  #i:どこのスライムを起点に合体しているか
  for i in range(N-k+1):
    dp[i][k]=min(dp[i][j]+dp[i+j][k-j] for j in range(1,k))+B[i+k]-B[i]
print(dp[0][N])

Submission status: Wrong Answer

Solution code:
def calc(A,n,dp):
    if n==2:
        return A[0]+A[1]
    s=1000000000
    for i in range(0,n-1):
        B=[]
        B=A[0:i]
        B.append(A[i]+A[i+1])
        B=B+A[i+2:]
        l=str(B)
        if l in dp:
            s=min(s,A[i]+A[i+1]+dp[l])
        else:
            d=calc(B,n-1,dp)
            s=min(s,A[i]+A[i+1]+d)
            dp[l]=d

    return s
n=int(input())
A=list(int(i) for i in input().split())
dp={}
print(calc(A,n,dp))
#for i in range(n):

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())), dtype='int64')
total_cost = 0

while len(a) > 1:
    min_i = 0
    min_cost = 10**10
    for i in range(len(a)-1):
        if a[i] + a[i+1] < min_cost:
            min_i = i
            min_cost = a[i] + a[i+1]

    a = np.delete(a, min_i)
    a = np.delete(a, min_i)
    a = np.insert(a, min_i, min_cost)

    total_cost += min_cost

print(total_cost)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))

INF = 1.0e+100


dp = [[[None, INF] for _ in range(N+1)] for _ in range(N+1)]
for i in range(N):
    dp[i][i+1] = [A[i], 0]

for g in range(2, N+1):
    for l in range(N-g+1):
        r = l + g
        print(l, r)
        for i in range(l+1, r):
            lv, lc = dp[l][i]
            rv, rc = dp[i][r]
            nc = lv + rv + lc + rc
            print(l, i, r, lv, rc, lc, rc)
            if dp[l][r][1] > nc:
                dp[l][r][0] = lv + rv
                dp[l][r][1] = nc

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

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
ans = 0
while len(a) > 1:
    min_cost = float('inf')
    idx = -1
    for i in range(len(a)-1):
        cost = a[i] + a[i+1]
        if min_cost > cost:
            min_cost = cost
            idx = i
    ans += min_cost
    a[idx] += a[idx+1]
    a = a[:idx+1] + a[idx+2:]
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

"""
URL: https://atcoder.jp/contests/dp/tasks/dp_n
N - Slimes / 
実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 
100 点

問題文
N 匹のスライムが横一列に並んでいます。 
最初、左から i 番目のスライムの大きさは ai です。

太郎君は、すべてのスライムを合体させて 1 匹のスライムにしようとしています。 
スライムが 1 匹になるまで、太郎君は次の操作を繰り返し行います。

左右に隣り合う 2 匹のスライムを選び、それらを合体させて新しい 1 匹のスライムにする。 
合体前の 2 匹のスライムの大きさを x および y とすると、
    合体後のスライムの大きさは x+y となる。 
このとき、太郎君は x+y のコストを支払う。 
なお、合体の前後でスライムたちの位置関係は変わらない。
太郎君が支払うコストの総和の最小値を求めてください。
"""
#solve
def solve():
    n = II()
    a = LI()
    dp = [[0] * (n + 1) for i in range(n)]
    acc = [0] + list(itertools.accumulate(a))
    c = [[0] * (n + 1) for i in range(n)]
    def f(l, r):
        tmp = inf
        if c[l][r]: return dp[l][r]
        c[l][r] = 1
        # print(dp, l, r)
        if l + 1 == r: return 0
        
        
        for i in range(l + 1, r):
            tmp = min(tmp, f(l, i) + f(i, r) + acc[r] - acc[l])
        # print(l,r)
        dp[l][r] = tmp
        return tmp
    print(f(0, n))
    # print(dp)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

"""
URL: https://atcoder.jp/contests/dp/tasks/dp_n
N - Slimes / 
実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 
100 点

問題文
N 匹のスライムが横一列に並んでいます。 
最初、左から i 番目のスライムの大きさは ai です。

太郎君は、すべてのスライムを合体させて 1 匹のスライムにしようとしています。 
スライムが 1 匹になるまで、太郎君は次の操作を繰り返し行います。

左右に隣り合う 2 匹のスライムを選び、それらを合体させて新しい 1 匹のスライムにする。 
合体前の 2 匹のスライムの大きさを x および y とすると、
    合体後のスライムの大きさは x+y となる。 
このとき、太郎君は x+y のコストを支払う。 
なお、合体の前後でスライムたちの位置関係は変わらない。
太郎君が支払うコストの総和の最小値を求めてください。
"""
#solve
def solve():
    n = II()
    a = LI()
    dp = [[0] * (n + 1) for i in range(n)]
    acc = [0]+list(itertools.accumulate(a))
    def f(l, r):
        tmp = inf
        # print(dp, l, r)
        if l + 1 == r: return 0
        if dp[l][r]: return dp[l][r]
        for i in range(l + 1, r):
            tmp = min(tmp, f(l, i) + f(i, r) )
        # print(l,r)
        dp[l][r] = tmp + acc[r] - acc[l]
        return tmp + acc[r] - acc[l]
    print(f(0, n))
    # print(dp)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

"""
URL: https://atcoder.jp/contests/dp/tasks/dp_n
N - Slimes / 
実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 
100 点

問題文
N 匹のスライムが横一列に並んでいます。 
最初、左から i 番目のスライムの大きさは ai です。

太郎君は、すべてのスライムを合体させて 1 匹のスライムにしようとしています。 
スライムが 1 匹になるまで、太郎君は次の操作を繰り返し行います。

左右に隣り合う 2 匹のスライムを選び、それらを合体させて新しい 1 匹のスライムにする。 
合体前の 2 匹のスライムの大きさを x および y とすると、
    合体後のスライムの大きさは x+y となる。 
このとき、太郎君は x+y のコストを支払う。 
なお、合体の前後でスライムたちの位置関係は変わらない。
太郎君が支払うコストの総和の最小値を求めてください。
"""
#solve
def solve():
    n = II()
    a = LI()
    dp = [[0] * (n + 1) for i in range(n)]
    acc = [0]+list(itertools.accumulate(a))
    def f(l, r):
        tmp = inf
        # print(dp, l, r)
        if l + 1 == r: return 0
        if dp[l][r]: return dp[l][r]
        for i in range(l + 1, r):
            tmp = min(tmp, f(l, i) + f(i, r) + acc[r] - acc[l])
        # print(l,r)
        dp[l][r] = tmp
        return tmp
    print(f(0, n))
    # print(dp)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

"""
URL: https://atcoder.jp/contests/dp/tasks/dp_n
N - Slimes / 
実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 
100 点

問題文
N 匹のスライムが横一列に並んでいます。 
最初、左から i 番目のスライムの大きさは ai です。

太郎君は、すべてのスライムを合体させて 1 匹のスライムにしようとしています。 
スライムが 1 匹になるまで、太郎君は次の操作を繰り返し行います。

左右に隣り合う 2 匹のスライムを選び、それらを合体させて新しい 1 匹のスライムにする。 
合体前の 2 匹のスライムの大きさを x および y とすると、
    合体後のスライムの大きさは x+y となる。 
このとき、太郎君は x+y のコストを支払う。 
なお、合体の前後でスライムたちの位置関係は変わらない。
太郎君が支払うコストの総和の最小値を求めてください。
"""
#solve
def solve():
    n = II()
    a = LI()
    dp = [[0] * (n + 1) for i in range(n)]
    acc = [0]+list(itertools.accumulate(a))
    for i in range(n):
        dp[i][i+1] = a[i]
    def f(l, r):
        tmp = inf
        if dp[l][r]: return dp[l][r]
        for i in range(l + 1, r):
            tmp = min(tmp, f(l, i) + f(i, r) + acc[r] - acc[l])
        dp[l][r] = tmp
        return tmp
    print(f(0, n)-sum(a))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [0] + list(map(int, input().split()))

INF = 10 ** 12

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

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

for j in range(1, N):
    for i in range(N - j):
        tmp = INF
        for k in range(i, i + j):
            # print (i, i + j, k + 1)
            tmp = min(tmp, dp[i][k] + dp[k + 1][i + j])
        dp[i][i + j] = tmp + A[i + j + 1] - A[i]

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

Submission status: Wrong Answer

Solution code:
#N

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

ans=0

for j in range(N-1):

    S=10**15
    num=0
    for i in range(len(a)-1):
        temp=a[i+1]+a[i]
        if temp<S:
            S=temp
            num=i

    ans+=S
    a[num]=S
    a.pop(num+1)
    
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 0
while len(a) >= 2:
    temp = 10**10
    index = 0
    for i in range(len(a)-1):
        if temp > a[i+1] + a[i]:
            temp = a[i+1] + a[i]
            index = i
    a[index] += a.pop(index+1)
    ans += a[index]
    #print(a)

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import *
n=int(input())
A=map(int,input().split())
A=sorted([(-a,a) for a in A])
ans=0
while len(A)>1:
    p=A.pop()[1]+A.pop()[1]
    ans+=p
    insort(A,(-p,p))
print(ans)

Submission status: Wrong Answer

Solution code:

def asum(l,r):
	global cumsum
	l+=1
	r+=1
	return cumsum[r-1]-cumsum[l-1]
def check(l,r):
	global dp
	if l==r:
		return 0
	if l == r-1:
		return arr[l]+arr[r]
	if dp[l][r] != None:
		return dp[l][r]
	else:
		ans = 10**9
		for i in range(l, r):
			st1 = asum(l,i)
			st2 = asum(i,r+1)
			ans = min(st1 + st2 + check(l,i)+ check(i+1, r), ans)
		
		dp[l][r] = ans
		return ans





ll = int(input())
arr = [int(i) for i in input().split()]
cumsum = [0]

for i in arr:
	cumsum.append(cumsum[-1]+i)
dp = [[None for i in range(ll+1)] for j in range(ll+1)]
print(check(0, ll-1))

Submission status: Wrong Answer

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

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

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

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


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

    n = 10**12
    m = s[r+1]-s[l]
    for i in range(l, r):
        n = min([n, solve(l, i)+solve(i+1, r)+m])
    dp[l][r] = n
    return n


print(solve(0, N-1))

Submission status: Wrong Answer

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

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

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

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


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

    n = 10**10
    m = s[r+1]-s[l]
    for i in range(l, r):
        n = min([n, solve(l, i)+solve(i+1, r)+m])
    dp[l][r] = n
    return n


print(solve(0, N-1))

Submission status: Wrong Answer

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

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

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

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


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

    n = 10**9
    m = s[r+1]-s[l]
    for i in range(l, r):
        n = min([n, solve(l, i)+solve(i+1, r)+m])
    dp[l][r] = n
    return n


print(solve(0, N-1))

Submission status: Wrong Answer

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

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

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

for i in range(1,n):
    for head in range(n-i):
        tail = head + i
        temp = 10**11
        for j in range(i):
            temp = min(temp, (dp[head][head+j] + dp[head+j+1][tail] + sum_a[head][tail]) )
        dp[head][tail] = temp

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

Submission status: Wrong Answer

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**9)*500
    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: Wrong Answer

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])
            ans += li2[i]+li2[i]
        elif i==plc+1:
            continue
        else:
            li.append(li2[i])
    #print(li)
print(ans)

Submission status: Wrong Answer

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

li = a.copy()
li2 = li.copy()
ans = 0
while(len(li)>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])
            ans += li2[i]+li2[i]
        elif i==plc+1:
            continue
        else:
            li.append(li2[i])
    #print(li)
print(ans)

Submission status: Wrong Answer

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])
            ans += li2[i]+li2[i]
        elif i==plc+1:
            continue
        else:
            li.append(li2[i])
    #print(li)
print(ans)

Submission status: Wrong Answer

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)-1):
        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: Wrong Answer

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)-1):
        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: Wrong Answer

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 a[i]+a[i+1] < mm:
            plc = i
            mm = a[i]+a[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[0])

Submission status: Wrong Answer

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

li = a.copy()

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

print(li[0])

Submission status: Wrong Answer

Solution code:
import numpy as np

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

slimes = A
ans = 0
for _ in range(N-1):
  idx = np.argmin(np.array(A[1:] + A[:-1]))
  cost = A[idx+1] + A[idx]
  ans += cost
  A = np.delete(A, idx)
  A[idx] = cost


print(ans)

Submission status: Wrong Answer

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

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

print(o[span]-ma)

Submission status: Wrong Answer

Solution code:
N = int(input())
import sys
sys.setrecursionlimit(pow(10, 8))
As = list(map(int, input().split()))
o = dict()
INF = 10**9
def f(n, xs):
    if tuple(xs) in o:
        return o[tuple(xs)]
    C = INF
    if n == 1:
        return 0, xs[0]
    for i in range(n-1):
        a, b = xs[:i+1], xs[i+1:n]
        c, y = f(i+1, a)
        d, z = f(n-i-1, b)
#        print(xs, i,c,d,y,z)
        C = min(C, c+d+y+z)
    o[tuple(xs)] = (C, sum(xs))
#    print(xs, C)
    return C, sum(xs)


print(f(N, As)[0])
#stack = []
#while stack:
#    x = stack.pop()
#print(d[span])

Submission status: Wrong Answer

Solution code:
N = int(input())
import sys
sys.setrecursionlimit(pow(10, 8))
As = list(map(int, input().split()))
o = dict()
INF = 10**9
def f(n, xs):
    if tuple(xs) in o:
        return o[tuple(xs)]
    C = INF
    if n == 1:
        return 0, xs[0]
    for i in range(n-1):
        a, b = xs[:i+1], xs[i+1:n]
        c, y = f(i+1, a)
        d, z = f(n-i-1, b)
#        print(xs, i,c,d,y,z)
        C = min(C, c+d+y+z)
    o[tuple(xs)] = (C, sum(xs))
#    print(xs, C)
    return C, sum(xs)


print(f(N, As))
#stack = []
#while stack:
#    x = stack.pop()
#print(d[span])

Submission status: Wrong Answer

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 potwory():
    N = wczytaj_liste()[0]
    dlugosci_potworow = wczytaj_liste()
    odp = 0
    while len(dlugosci_potworow)>1:
        min_suma = 10**18
        potwor_1 = 0
        potwor_2 = 1
        for i in range(len(dlugosci_potworow)-1):
            if dlugosci_potworow[i]+dlugosci_potworow[i+1] < min_suma: 
                min_suma = dlugosci_potworow[i]+dlugosci_potworow[i+1]
                potwor_1 = i 
                potwor_2 = i+1
        dlugosci_potworow[potwor_1:potwor_2+1] = [min_suma]
        odp +=min_suma
    print(odp)
        
potwory()

Submission status: Wrong Answer

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 potwory():
    N = wczytaj_liste()[0]
    dlugosci_potworow = wczytaj_liste()
    odp = 0
    min_suma = 10**18
    potwor_1 = 0
    potwor_2 = 1
    while len(dlugosci_potworow)>1:
        min_suma = 10**9
        for i in range(len(dlugosci_potworow)-1):
            if dlugosci_potworow[i]+dlugosci_potworow[i+1] < min_suma: 
                min_suma = dlugosci_potworow[i]+dlugosci_potworow[i+1]
                potwor_1 = i 
                potwor_2 = i+1
        dlugosci_potworow[potwor_1:potwor_2+1] = [min_suma]
        odp +=min_suma
    print(odp)
        
potwory()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import heapq
INF = float("inf")


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

    ans = 0
    for L in range(N-1, 0, -1):
        # 隣り合う和
        B = [a[i]+a[i+1] for i in range(L)]
        m = INF
        mi = -1
        for i, b in enumerate(B):
            if m > b:
                m = b
                mi = i
        ans += m
        a = [aa if i != mi else m for i, aa in enumerate(a) if i != mi+1]
        # print(a, ans)
    print(ans)

    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: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import heapq
INF = float("inf")


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

    tot = 0
    heapq.heapify(a)
    while len(a) > 1:
        A = heapq.heappop(a)
        B = heapq.heappop(a)
        heapq.heappush(a, A+B)
        tot += A+B
    print(tot)
    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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(160000)

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

dp = [[0]*N for _ in range(N)]
flag = [[False]*N for _ in range(N)]
S = [0]*(N+1)

for i in range(N):
    flag[i][i] = True

S[0] = A[0]
for i in range(N):
    S[i+1] = S[i]+A[i]
    
def f(l, r):
    if flag[l][r]:
        return dp[l][r]
    flag[l][r] = True
    res = 10**12
    for m in range(l, r):
        res = min(res, f(l, m)+f(m+1, r))
    dp[l][r] = res+S[r+1]-S[l]
    return dp[l][r]

print(f(0, N-1))