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:

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

Submission status: Wrong Answer

Solution code:

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
ans=0
temp=a[0]
for i in range(1,n):
    temp+=a[i]
    ans+=temp
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

dp = [[0]*(N+1) for i in range(N+1)]
data = [[0]*(N+1) for i in range(N+1)] # data[i][j] = sum(a[i:j])
for i in range(N):
  data[i][i+1] = a[i]
for i in range(N+1):
  for j in range(N+1):
    if i+j <= N:
      data[j][i+j] = sum(a[j:i+j])
    else:
      break

for i in range(2,N+1):
  for j in range(N+1):
    if i+j <= N:
      tmp = MAX_INT
      for k in range(1,i):
        tmp = min(tmp,dp[j][k+j] + dp[k+j][i+j])
      dp[j][i+j] = tmp + data[j][i+j]
    else:
      break

#print(data)
#print(dp)
print(dp[0][N])

Submission status: Wrong Answer

Solution code:
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

dp = [[0]*(N+1) for i in range(N+1)]
data = [[0]*(N+1) for i in range(N+1)] # data[i][j] = sum(a[i:j])
for i in range(N):
  data[i][i+1] = a[i]
for i in range(N+1):
  for j in range(N):
    if i+j <= N:
      data[j][i+j] = sum(a[j:i+j])
    else:
      break

for i in range(2,N+1):
  for j in range(N+1):
    if i+j <= N:
      tmp = MAX_INT
      for k in range(1,i):
        tmp = min(tmp,dp[j][k+j] + dp[k+j][i+j])
      dp[j][i+j] = tmp + data[j][i+j]
    else:
      break

print(dp[0][N])

Submission status: Wrong Answer

Solution code:
# @author 

import sys

class NSlimes:
    def solve(self):
        n = int(input())
        a = [int(_) for _ in input().split()]
        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: Wrong Answer

Solution code:
# @author 

import sys

class NSlimes:
    def solve(self):
        n = int(input())
        a = [int(_) for _ in input().split()]
        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
            b[idx] += b[idx + 1]
            ans += b[idx]
            del b[idx + 1]
        print(ans)

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

solver.solve()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().strip().split(" ")))
dp=[[10**10]*len(A)  for i in range(0,len(A)+1)]
##dp[length][start_position]
pre=[]
temp=0
for i in range(len(A)):
    temp+=A[i]
    pre+=[temp]
length=1
for i in range(len(A)):
    dp[length][i]=0

for L in range(2,len(A)+1):
    for start in range(0,len(A)-L+1):
        for j in range(start+1,start+L):
            if start>0:
                dp[L][start]=min(dp[j-start][start]+dp[L-j+start][j]+pre[start+L-1]-pre[start-1],dp[L][start])
            else:
                dp[L][start]=min(dp[j-start][start]+dp[L-j+start][j]+pre[start+L-1],dp[L][start])
print(dp[len(A)][0])

Submission status: Wrong Answer

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

Solution code:
import copy
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
a = list(map(int, input().split()))
Inf = 10 ** 18
ans = 0

for i in range(N - 1):
	tmp = Inf
	for j in range(len(a) - 1):
		if a[j] + a[j + 1] < tmp:
			tmp = a[j] + a[j + 1]
			ind = j
	
	ans += tmp
	tmp_lis = []
	
	for j in range(ind):
		tmp_lis.append(a[j])
		
	tmp_lis.append(tmp)
	
	for j in range(ind + 2, len(a)):
		tmp_lis.append(a[j])
	
	a = copy.copy(tmp_lis)
	
print(ans)

Submission status: Wrong Answer

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

total_cost = 0

while len(A) > 1:
    min_i = 0
    min_cost = 1<<50
    for i in range(len(A)-1):
        cost = A[i] + A[i+1]
        if cost < min_cost:
            min_i = i
            min_cost = cost
    total_cost += min_cost
    A[min_i] = min_cost
    del A[min_i+1]

print(total_cost)

Submission status: Wrong Answer

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


res = 0
while len(a) > 1:
    index = -1
    sum_size = float('inf')
    n = len(a)
    for i in range(n-1):
        if sum_size > a[i] + a[i+1]:
            sum_size = a[i] + a[i+1]
            index = i

    a[index] = a[index] + a[index+1]
    res += a[index]
    a.pop(index+1)
    # print(res)


print(res)

Submission status: Wrong Answer

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

answer = 0

for _ in range(n - 1):
    nxt = [v1 + v2 for v1, v2 in zip(a[1:], a[:-1])]
    i, cost = min(enumerate(nxt), key=lambda x: x[1])
    answer += cost
    del a[i]
    a[i] = cost

print(answer)

Submission status: Wrong Answer

Solution code:
def calcdp(i,j):
    global dp, A, BIG_INT
    
    if dp[i][j] != -1:
        return dp[i][j]
    
    if i + 1== j:
        dp[i][j] = 0
        return dp[i][j]
    
    elif i + 2== j:
        dp[i][j] = A[i] + A[i + 1]
        return dp[i][j]
    
    else:
        m = BIG_INT
        for k in range(i + 1, j):
            m = min(calcdp(i, k) + calcdp(k, j), m)
        m += sum(A[i:j])
        dp[i][j] = m
        return dp[i][j]

    
BIG_INT = 10**12
N = int(input())
A = [int(x) for x in input().split()]
dp = [[-1] * (N + 1) for _ in range(N)] 

print(calcdp(0, N))

Submission status: Wrong Answer

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

ans = 0
for i in range(n - 1):
    aa = [x + y for x, y in zip(a[1:], a[:-1])]
    aa_min = min(aa)
    ans += aa_min
    rep = aa.index(aa_min)
    a[rep] = aa_min
    del a[rep + 1]
print(ans)

Submission status: Wrong Answer

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

#dp[l][r] = [l, r)区間のスライムを
dp = [[float("inf")]*(n+1) for i in range(n+1)]
for i in range(n):
    dp[i][i] = 0

#cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和
cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]

#メモ化再帰でdp[0][n]求める
def dfs(l, r):
    if dp[l][r] != float("inf"):
        return dp[l][r]
    else:
        res = float("inf")
        if (r - l) == 1:
            dp[l][r] = 0
            return dp[l][r]
        for k in range(l, r):
            if k == l or k == r:
                continue
            #dp[l][k] + dp[k][r] + 合体に必要なコスト
            res = min(res, dfs(l, k) + dfs(k, r) + (cost[r] - cost[l]))
            print(l,k,r,dfs(l, k) + dfs(k, r))
        dp[l][r] = res
    return dp[l][r]

print(dp[0][n])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
c = 0
for k in range(n - 2):
    mn = a[0] + a[1]
    mni = 0
    for i in range(1, n - k - 1):
        s = a[i] + a[i + 1]
        if s < mn:
            mn = s
            mni = i
    a = a[:mni] + [mn] + a[mni + 2:]
    c += mn
print(sum(a) + c)

Submission status: Wrong Answer

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

ans = 0
for i in range(n-1):
    ind = -1
    min_cost = 10**12
    for j in range(n-1-i):
        if min_cost > a[j]+a[j+1]:
            ind = j
            min_cost = a[j]+a[j+1]
    ans += min_cost
    new_a = []
    for j in range(n-i):
        if j == ind:
            new_a.append(min_cost)
        elif j == ind+1:
            continue
        else:
            new_a.append(a[j])
    a = new_a

print(ans)

Submission status: Wrong Answer

Solution code:
import array as ar

def getInt(): return int(input())
def getIntList(): return [int(x) for x in input().split()]
def zeros(n): return [0]*n

class Debug():
    def __init__(self):
        self.debug = True
 
    def off(self):
        self.debug = False
 
    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                print(cmt, ':  ', end='')
            print(x)
        return x

def prob_N():  # WA 10
    d = Debug()
    d.off()
    N = getInt()
    A = getIntList()
    d.dmp((N), 'N')
    d.dmp((A), 'A')
    dp = ar.array('q', [0]*(N-1))
    for i in range(N-1):
        dp[i] = A[i]+A[i+1]
    d.dmp(dp, 'dp')
    cost = 0
    for i in range(N-2):
        mn = min(dp)
        cost += mn
        idx = dp.index(mn)
        if idx > 0:
            dp[idx-1] += A[idx+1]
        A[idx+1] += A[idx]
        if idx < len(dp)-1:
            dp[idx+1] += A[idx]
        dp.pop(idx)
        A.pop(idx)
    return cost+dp[0]


ans = prob_N()
if ans is None:
    pass
elif type(ans) == tuple and ans[0] == 1:  # 1,ans
    for elm in ans[1]:
        print(elm)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import array as ar

def getInt(): return int(input())
def getIntList(): return [int(x) for x in input().split()]
def zeros(n): return [0]*n
def zeros2(n, m): return [zeros(m) for i in range(n)] # obsoleted zeros((n, m))で代替
def getIntLines(n): return [int(input()) for i in range(n)]
def getIntMat(n, m):  # n行に渡って、1行にm個の整数
    mat = zeros((n, m))
    for i in range(n):
        mat[i] = getIntList()
    return mat

class Debug():
    def __init__(self):
        self.debug = True
 
    def off(self):
        self.debug = False
 
    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                print(cmt, ':  ', end='')
            print(x)
        return x

def prob_N():  # Grid 1    AC 10  TLE 6
    d = Debug()
    d.off()
    N = getInt()
    A = getIntList()
    d.dmp((N), 'N')
    d.dmp((A), 'A')
    dp = ar.array('q', [0]*(N-1))
    for i in range(N-1):
        dp[i] = A[i]+A[i+1]
    d.dmp(dp, 'dp')
    cost = 0
    for i in range(N-2):
        mn = min(dp)
        cost += mn
        idx = dp.index(mn)
        #d.dmp((idx,A,dp),'idx,A,dp')
        if idx > 0:
            dp[idx-1] += A[idx+1]
        A[idx+1] += A[idx]
        if idx < len(dp)-1:
            dp[idx+1] += A[idx]
        else:
            dp[idx] += A[idx]
        dp.pop(idx)
        A.pop(idx)
        #d.dmp((mn,idx),'mn,idx')
        #d.dmp((A,dp,cost), 'A,dp,cost')
    return cost+dp[0]


ans = prob_N()
if ans is None:
    pass
elif type(ans) == tuple and ans[0] == 1:  # 1,ans
    for elm in ans[1]:
        print(elm)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
dp=[-1]*n
for i in range(n):
	dp[i]=-(i+1)
ct=n-1
ans=0
while(ct):
	mini=999999999999999999999
	ind=-1
	for i  in range(n-1):
		if (dp[i] != dp[i+1]) and arr[i]+arr[i+1]<mini:
			mini=arr[i]+arr[i+1]
			ind=i
	arr[ind]=mini
	arr[ind+1]=mini
	j=ind
	while(j>=1 and dp[j]==dp[j-1]):
		dp[j]=ct
		arr[j]=mini
		j-=1
		if j==0:
			dp[0]=ct
			arr[0]=mini
	if j==ind:
		dp[j]=ct
	j=ind+1
	while(j<n-1 and dp[j]==dp[j+1]):
		arr[j]=mini
		dp[j]=ct
		j+=1
		if j==n-1:
			dp[j]=ct
			arr[j]=mini
	if j==ind+1:
		dp[j]=ct
	# for j in range(ind+2,n):
	# 	if dp[j]<0:
	# 		break
	# 	arr[j]=mini
	# 	dp[j]=ct
	# for j in range(ind-1,-1,-1):
	# 	if dp[j]<0:
	# 		break 
	# 	arr[j]=mini
	# 	dp[j]=ct
	ans+=mini
	ct-=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = tuple(map(int,input().split()))
b = [a[0]]+[0]*(n-1)
for i in range(1,n):
    b[i] = b[i-1]+a[i]

dp = [0]*n
for i in range(1,n):
    mi = float("inf")
    #s:a[i-j+1]+...s[i]
    s = 0
    #cost:a[i-j+1]~a[i]を端から順につなげたときのコスト
    cost = -a[i]
    for j in range(1,i+1):
        cost += s + a[i-j+1]
        s += a[i-j+1]
        mi = min(mi,b[i-j]+dp[i-j]+s+cost)
    dp[i] = mi

print(dp[-1])

Submission status: Wrong Answer

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

INF = float('inf')
dp = [[INF] * (n+1) for _ in range(n+1)]

acum = [0] * (n+1)
for i, ai in enumerate(a):
    acum[i+1] += acum[i] + ai

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

for l in range(2, n+1):
    for i in range(n-l+1):
        j = i + l
        dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + acum[j] - acum[i]

print(dp[0][n])

Submission status: Wrong Answer

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

right = [i+1 for i in range(n)]

ans = 0

while right[0] != n:
    i = 0
    min_num = float('inf')
    min_i = 0
    while right[i] != n:
        if a[i] + a[right[i]] < min_num:
            min_num = a[i] + a[right[i]]
            min_i = i
        i = right[i]
    a[min_i] += a[right[min_i]]
    ans += a[min_i]
    right[min_i] = right[right[min_i]]

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

heapq.heapify(a)

cost = 0
while len(a) > 1:
    x = heapq.heappop(a)
    y = heapq.heappop(a)
    cost += x + y
    heapq.heappush(a, x + y)

print(cost)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    while len(A) > 1:
        minimum = float("inf")
        idx = 0
        for i in range(len(A)-1):
            if minimum > A[i] + A[i+1]:
                minimum = A[i] + A[i+1]
                idx = i
        ans += minimum
        A = A[:idx] + [minimum] + A[idx+2:]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

ans = 0
while len(A) > 1:
    A = sorted(A)[::-1]
    t = A.pop() + A.pop()
    ans += t
    A.append(t)
    
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=0
for loop in range(n-1):
    mini =1234567890123
    idx = -1
    for i in range(len(a)-1):
        if a[i]+a[i+1] < mini:
            mini = a[i]+a[i+1]
            idx=i
    
    ans += mini
    a[idx] += a[idx+1]
    del a[idx+1]
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import sys
# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dp = [[float(0)]*N for _ in range(N)]
a_acc = [0]+list(accumulate(A))


def dfs(l, r):
    """
    List[l:r]
    """
    if dp[l][r-1] != float('inf'):
        return dp[l][r-1]
    if r-l == 1:
        dp[l][r-1] = 0
        return 0
    if r-l == 2:
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    else:
        dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                         for v in range(l+1, r))+a_acc[r]-a_acc[l]
        return dp[l][r-1]


def bfs():
    for d in range(2, N+1):
        for l in range(0, N-d+1):
            r = l + d
            #print("l,r->", l, r)
            tmp = float('inf')
            for m in range(l+1, r):
                tmp = min(tmp, dp[l][m-1]+dp[m][r-1])
            #print("tmp->", tmp)
            #print("acc->", a_acc[r]-a_acc[l])
            dp[l][r-1] = tmp+a_acc[r]-a_acc[l]


# print(a_acc)
bfs()
# print(dp)
print(dp[0][-1])

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import accumulate
input = stdin.readline

INF = 10**12

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

cost = [[INF]*N for _ in range(N)]
for i in range(N):
    cost[i][i] = 0
prefix = [0]+ list(accumulate(a))

for i in range(1,N):
    for j in range(0,N-i):
        temp = INF
        for k in range(i):
            temp = min(temp,cost[j][j+k] + cost[j+k+1][j+i])
        cost[j][j+i] = temp + prefix[j+i+1] - prefix[j]


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

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline

INF = 10**12

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

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

for i in range(1,N):
    for j in range(0,N-i):
        d = INF
        c = INF
        for k in range(i):
            temp = cost[j][j+k] + cost[j+k+1][j+i] + dp[j][j+k]+dp[j+k+1][j+i]
            if c > temp:
                c = temp
                d = dp[j][j+k]+dp[j+k+1][j+i]
        cost[j][j+i] = c
        dp[j][j+i] = d


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

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
inf = float("inf")

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

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

for j in range(3,N+1):
    for i in range(1,N - j + 3 -1):

        # dp[i][j+i-1] =  min(dp[i+1][i+j-1]*2 + A[i -1], dp[i][i+j-2]*2 + A[i+j-2])
        dp[i][j+i-1] =  min(dp[i+1][i+j-1]*2 + dp[i+1][i+j-1] , dp[i][i+j-2]*2  + A[i+j-2])
        # dp[i][j+i-1] =  min(dp[i+1][i+j-1] + dp[i][i+j-2] , dp[i][i+j-2] + A[i+j-2])
        # if dp[i+1][i+j-1]+A[i-1] < dp[i][i+j-2]+A[i+j-2]:
        #     dp_or[i][j+i-1] = -1 # down
        # else:
        #     dp_or[i][j+i-1] = -2
            
cost_map = []
for i in dp[1:]:
    cost_map.append(i[1:])

orient_map = []
for i in dp_or[1:]:
    i = i[1:]
    print(" ".join( list(map( lambda x: "{:5d}".format(x), i ))))
    orient_map.append( i ) 

ans = 0
pos = [0,N-1]

while orient_map[pos[0]][pos[1]] != 0:
    if orient_map[pos[0]][pos[1]]  == -2:
        ans += cost_map[pos[0]][pos[1]]
        pos[1] -= 1
    else:
        ans += cost_map[pos[0]][pos[1]]
        pos[0] += 1
ans += cost_map[pos[0]][pos[1]]
print(ans)
        




for i in dp:
    print(i)

print(dp[1][N])

Submission status: Wrong Answer

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

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
aN = LIST()

ans = 0
while len(aN) > 1:
    mn = INF
    idx = 0
    for i in range(1, len(aN)):
        sm = aN[i-1] + aN[i]
        if mn > sm:
            mn = sm
            idx = i
    ans += mn
    aN[idx-1] = mn
    aN.pop(idx)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
cost = 0
while len(a) > 1:
    min_pair = 400000000001
    pair_index = 0
    for i in range(len(a) - 1):
        if min_pair > a[i] + a[i + 1]:
            min_pair = a[i] + a[i + 1]
            pair_index = i
    cost +=min_pair
    del(a[pair_index])
    a[pair_index] = min_pair
    #print(a)

print(cost)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
cost = 0
while len(a) > 1:
    min_pair = 400000000000
    pair_index = 0
    for i in range(len(a) - 1):
        if min_pair > a[i] + a[i + 1]:
            min_pair = a[i] + a[i + 1]
            pair_index = i
    cost +=min_pair
    del(a[pair_index])
    a[pair_index] = min_pair
    #print(a)

print(cost)

Submission status: Wrong Answer

Solution code:
n = input()

a = [int(x) for x in raw_input().split()]

sum = 0

s = 0

while len(a) > 0:
  if len(a) == 1:
    break
  sum = 0
  sum = sum + min(a)
  a.remove(min(a))
  sum = sum + min(a)
  a.remove(min(a))
  a.append(sum)
  s = s + sum
  
print s

Submission status: Wrong Answer

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

def MIN(A,score):

    ANS=float("inf")
    for i in range(1,len(A)):
        if A[i]+A[i-1]<ANS:
            ANS=A[i]+A[i-1]
            ANSind=i

    score+=ANS
    A=A[:ANSind-1]+[ANS]+A[ANSind+1:]

    return A,score


score=0
for i in range(N-1):
    A,score=MIN(A,score)
    #print(score,A)

print(score)

Submission status: Wrong Answer

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

value=2000000000 #合体に必要なコスト
index=0 #合体するスライムの若い方の添字
ans=0 #総コスト

#jが1からN-1まで変わる(N-1回合体を施行)
for j in range(1,N):
  #iが0からN-j-1まで変わる
  for i in range(N-j):
    if value >= (a[i]+a[i+1]):
      value = (a[i]+a[i+1])
      index = i
  a[index] = a[index]+a[index+1]
  ans += a[index]
  del a[index+1]
  value=2000000000 
  index=0
  
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = []
INF = 2000000000
sum = 0
for i in range(N - 1):
    b.append([a[i] + a[i + 1], a[i], a[i + 1]])
for i in range(N - 1):
    mm = INF
    mj = 0
    if len(b) == 1:
        sum += b[0][0]
        break
    for j in range(len(b)):
        if mm > b[j][0]:
            mm = b[j][0]
            mj = j
    sum += mm
    if mj == 0:
        b[mj + 1][1] += b[mj][1]
        b[mj + 1][0] += b[mj][1]
        del (b[mj])
    elif mj == len(b) - 1:
        b[mj - 1][2] += b[mj][2]
        b[mj - 1][0] += b[mj][2]
        del (b[mj])
    else:
        b[mj + 1][1] += b[mj][1]
        b[mj + 1][0] += b[mj][1]
        b[mj - 1][2] += b[mj][2]
        b[mj - 1][0] += b[mj][2]
        del(b[mj])
print(sum)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = []
INF = 2000000000
sum = 0
for i in range(N - 1):
    b.append([a[i] + a[i + 1], a[i], a[i + 1]])
for i in range(N - 2):
    mm = INF
    mj = 0
    for j in range(len(b)):
        if mm > b[j][0]:
            mm = b[j][0]
            mj = j
    sum += mm
    if mj == 0:
        b[mj + 1][1] += b[mj][1]
        b[mj + 1][0] += b[mj][1]
        del (b[mj])
    elif mj == len(b) - 1:
        b[mj - 1][2] += b[mj][2]
        b[mj - 1][0] += b[mj][2]
        del (b[mj])
    else:
        b[mj + 1][1] += b[mj][1]
        b[mj + 1][0] += b[mj][1]
        b[mj - 1][2] += b[mj][2]
        b[mj - 1][0] += b[mj][2]
        del(b[mj])
sum += b[0][0]
print(sum)

Submission status: Wrong Answer

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

ans = 0
while len(A) > 1:
    min_c = float('inf')
    min_i = -1
    for i in range(len(A)-1):
        c = A[i] + A[i+1]
        if c < min_c:
            min_c = c
            min_i = i
    ans += min_c
    A = A[:min_i] + [min_c] + A[min_i+2:]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
mem = {}
def getAns(pre, L, H):
    if L == H:
        return 0
    if L > H:
        return 0
    
    if (L, H) in mem:
        return mem[(L, H)]
    
    mini = float('inf')
    for i in range(L, H):
        mini = min(mini, getAns(pre, L, i) + getAns(pre, i+1, H) + pre[i+1]-pre[L] + pre[H+1]-pre[i+1])
    mem[(L, H)] = mini
    return mini




n = int(input())
arr = list(map(int, input().strip().split()))

pre = [0 for i in range(n+1)]
for i in range(1, n+1):
    pre[i] = pre[i-1] + arr[i-1]

print(getAns(pre, 0, n-1))
# print(pre)

Submission status: Time Limit Exceeded

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

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
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')]




n = val()
l = li()


@lru_cache(None)
def dp(l):
    l = list(l)
    
    ans = float('inf')
    n = len(l)

    if n == 1:return 0
    for i in range(1, n):
        curr = l[i] + l[i - 1]
        ans = min(ans, curr + dp(tuple(l[:i-1] + [curr] + l[i + 1:])))
    return ans

print(dp(tuple(l)))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
flag=[[0 for j in range(n)] for i in range(n)]
dp=[[0 for j in range(n)] for i in range(n)]
ru=[0]
for i in range(n):
    ru.append(ru[-1]+a[i])
def f(l,r):
    if flag[l][r]==1:
        return dp[l][r]
    flag[l][r]=1
    if l==r:
        return 0
    fans=10**20
    for m in range(l,r):
        fans=min(fans,f(l,m)+f(m+1,r))
    dp[l][r]=fans+ru[r+1]-ru[l]
    return dp[l][r]

ans=f(0,n-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from itertools import accumulate
n = int(input())
A = [0] + list(map(int, input().split()))
B = tuple(accumulate(A))
dp = [[-1]*(n+1) for _ in range(n+1)]
def f(i, j):
  if i == j:
    return 0
  if dp[i][j] != -1:
    return dp[i][j]
  if j-i == 1:
    dp[i][j] = A[i]+A[j]
    return dp[i][j]
  res = float("inf")
  for m in range(i, j):
    res = min(res, f(i,m)+f(m+1,j)+(B[j]-B[i-1]))
  dp[i][j] = res
  return res
ans = f(1, n)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

N = int(input())
slimes = list(map(int, input().split()))
csum_slimes = [0]
for i in range(N):
    csum_slimes.append(csum_slimes[-1]+slimes[i])

dpt = np.full((N, N), -1, dtype='int64')

def get_min_cost(l, r):
    if dpt[l][r] != -1:
        return dpt[l][r]
    if l == r:
        return 0
    min_cost = 10**18
    for m in range(l, r):
        min_cost = min(min_cost, get_min_cost(l,m)+get_min_cost(m+1,r)+csum_slimes[r+1]-csum_slimes[l])
    dpt[l][r] = min_cost
    return min_cost
    

print(get_min_cost(0, N-1))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

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

dpt = np.full((N, N), -1, dtype='int64')

def get_min_cost(l, r):
    if dpt[l][r] != -1:
        return dpt[l][r]
    if l == r:
        return 0
    min_cost = 10**18
    for m in range(l, r):
        min_cost = min(min_cost, get_min_cost(l,m)+get_min_cost(m+1,r)+sum(slimes[l:r+1]))
    dpt[l][r] = min_cost
    return min_cost
    

print(get_min_cost(0, N-1))