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:
import sys
readline = sys.stdin.readline

# 区間DP
# dp[l][r] = 区間[l,r]のスライムを合体するときの最小コスト
# dp[l][r] = min(dp[l][m] + dp[m + 1][r]) + sum(l,r)

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

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

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

# 区間の長さが小さい順にループする(1～N)
for i in range(2, N + 1): # 区間の長さ
  for l in range(N - i + 1):
    r = l + i - 1
    # lからrまでの区間で最小となるdp[l][m] + dp[m][r]の組み合わせを探す
    # lからrまでのAの累積和
    cost = A[r + 1] - A[l]
    for m in range(l,r):
      if dp[l][m] + dp[m + 1][r] + cost < dp[l][r]:
        dp[l][r] = dp[l][m] + dp[m + 1][r] + cost
        
print(dp[0][-1])

Submission status: Wrong Answer

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

# 区間DP
# dp[l][r] = 区間[l,r]のスライムを合体するときの最小コスト
# dp[l][r] = min(dp[l][m] + dp[m + 1][r]) + sum(l,r)

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

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

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

# 区間の長さが小さい順にループする(1～N)
for i in range(N): # 区間の長さ
  for l in range(N - i):
    r = l + i
    # lからrまでの区間で最小となるdp[l][m] + dp[m][r]の組み合わせを探す
    # lからrまでのAの累積和
    cums = A[r + 1] - A[l]
    for m in range(l,r):
      if dp[l][m] + dp[m + 1][r] + cums < dp[l][r]:
        dp[l][r] = dp[l][m] + dp[m + 1][r] + cums
        
print(dp[0][-1])

Submission status: Wrong Answer

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

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

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


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


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


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


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


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


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


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


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


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


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


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    120
    """
# add tests above


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


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

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

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


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

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

    main()

Submission status: Wrong Answer

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

N = INT()
a = LIST()

ans = 0
for i in range(N-1):
    mi = INF
    idx = None
    for j in range(len(a)-1):
        if a[j+1]+a[j] < mi:
            mi = a[j+1]+a[j]
            idx = j
    ans += mi
    a.pop(idx)
    a[idx] = mi

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N = ni()

a_array = na()
ans = 0
while(len(a_array) > 1):
    size_min = 10 ** 10
    size_index = 0
    for i in range(len(a_array) - 1):
        size = a_array[i] + a_array[i+1]
        if size < size_min:
            size_min = size
            size_index = i
    ans += size_min
    new_array = []
    for i in range(size_index):
        new_array.append(a_array[i])
    new_array.append(size_min)
    for i in range(size_index+2, len(a_array)):
        new_array.append(a_array[i])

    a_array = new_array
    # print(a_array)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

s=[0]+list(itertools.accumulate(a))

dp=[[10**20]*(n+1) for _ in range(n)]
for l in range(n):
    dp[l][l+1]=0
for d in range(2,n+1): 
    for k in range(1,d):
        for i in range(n-d+1):
            j=i+d
            S=s[j]-s[i]
            dp[i][j]=min(dp[i][i+k]+dp[i+k][j],dp[i][j])+S

print(dp[0][n])

Submission status: Wrong Answer

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


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

print(c(0,n))

Submission status: Wrong Answer

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

s=[0]+list(itertools.accumulate(a))

dp=[[10**10]*(n+1) for _ in range(n)]
for l in range(n):
    dp[l][l+1]=0
for d in range(2,n+1): 
    for k in range(1,d):
        for i in range(n-d+1):
            j=i+d
            S=s[j]-s[i]
            dp[i][j]=min(dp[i][i+k]+dp[i+k][j],dp[i][j])+S

print(dp[0][n])

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
s1=[0]+a
for p in range(n):
    s1[p+1]=s1[p]+s1[p+1]


dp=[[10**10]*(n+1) for _ in range(n)]
for l in range(n):
    dp[l][l+1]=0
for d in range(1,n+1): 
    for k in range(1,d):
        for i in range(n-d+1):
            j=i+d
            S=s1[j]-s1[i]
            dp[i][j]=min(dp[i][i+k]+dp[i+k][j]+S,dp[i][j])

print(dp[0][n])

Submission status: Wrong Answer

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

dp=[[10**10]*(n+1) for _ in range(n)]
for l in range(n):
    dp[l][l+1]=0
for d in range(1,n+1): 
    for k in range(1,d):
        for i in range(n-d+1):
            j=i+d
            S=s[j]-s[i]
            dp[i][j]=min(dp[i][i+k]+dp[i+k][j]+S,dp[i][j])

print(dp[0][n])

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int,input().split()))
ans =0
while(len(arr)>1):
    min_sum = arr[0]+arr[1]
    idx=0
    for i in range(1,n-1):
        if(arr[i]+arr[i+1]<min_sum):
            min_sum=arr[i]+arr[i+1]
            idx = i
    arr[idx]=min_sum
    ans += min_sum
    del arr[idx+1]
    n-=1
print(ans)

Submission status: Wrong Answer

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

dp=[[10**10]*(n+1) for _ in range(n)]
for l in range(n):
    dp[l][l+1]=0
for d in range(2,n+1): 
    for k in range(1,d):
        for i in range(n-d+1):
            j=i+d
            S=s[j]-s[i]
            dp[i][j]=min(dp[i][i+k]+dp[i+k][j]+S,dp[i][j])

print(dp[0][n])

Submission status: Wrong Answer

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

dp=[[10**10]*(n+1) for _ in range(n)]
for l in range(n):
    dp[l][l+1]=0
for d in range(2,n+1):
    for i in range(n-d+1):
        j=i+d
        S=s[j]-s[i]
        for k in range(1,d):
            dp[i][j]=min(dp[i][i+k]+dp[i+k][j]+S,dp[i][j])

print(dp[0][n])

Submission status: Wrong Answer

Solution code:
count=0
def get(hk,v,w):
    # global count
    # if count==2:
    #     print(hk,v,w)
    # count+=1
    if hk==0 or v==0 or w==0:
        return hk+v+w
    return min(2*(hk+v)+w,2*(v+w)+hk)
n=int(input())
a=list(map(int,input().split()))
dp=[[9999999999999999999999999999999999999 for i in range(n)] for j in range(n)]
pre=[0]*n
pre[0]=a[0]
dp[0][0]=0
for i in range(1,n):
    pre[i]=a[i]+pre[i-1]
    dp[i-1][i]=a[i-1]+a[i]
    dp[i][i]=0
for i in range(3,n+1):
    for j in range(n-i+1):
        k=j+i-1
        for l in range(j,k+1):
            t1,t2=0,0
            if l-1>=j:
                t1=dp[j][l-1]
            if l+1<=k:
                t2=dp[l+1][k]
            # print(pre[l],pre[j],a[j],a[l],pre[l]-(pre[j]-a[j])-a[l],t1,t2)
            # if count==2:
            #     print(t1,t2)
            dp[j][k]=min(dp[j][k],get(pre[l]-pre[j]+a[j]-a[l],a[l],pre[k]-pre[l])+t1+t2)
# print(dp)
print(dp[0][n-1])

Submission status: Wrong Answer

Solution code:
count=0
def get(hk,v,w):
    # global count
    # if count==2:
    #     print(hk,v,w)
    # count+=1
    if hk==0 or v==0 or w==0:
        return hk+v+w
    return min(2*(hk+v)+w,2*(v+w)+hk)
n=int(input())
a=list(map(int,input().split()))
dp=[[9999999999999999999999999999999999999 for i in range(n)] for j in range(n)]
pre=[0]*n
pre[0]=a[0]
for i in range(1,n):
    pre[i]=a[i]+pre[i-1]
    dp[i-1][i]=a[i-1]+a[i]
    dp[i-1][i-1]=0
for i in range(3,n+1):
    for j in range(n-i+1):
        k=j+i-1
        for l in range(j,k+1):
            t1,t2=0,0
            if l-1>=j:
                t1=dp[j][l-1]
            if l+1<=k:
                t2=dp[l+1][k]
            # print(pre[l],pre[j],a[j],a[l],pre[l]-(pre[j]-a[j])-a[l],t1,t2)
            # if count==2:
            #     print(t1,t2)
            dp[j][k]=min(dp[j][k],get(pre[l]-pre[j]+a[j]-a[l],a[l],pre[k]-pre[l])+t1+t2)
# print(dp)
print(dp[0][n-1])

Submission status: Wrong Answer

Solution code:
count=0
def get(hk,v,w):
    # global count
    # if count==2:
    #     print(hk,v,w)
    # count+=1
    if hk==0 or v==0 or w==0:
        return hk+v+w
    return min(2*(hk+v)+w,2*(v+w)+hk)
n=int(input())
a=list(map(int,input().split()))
dp=[[9999999999999999999999999999999999999 for i in range(n)] for j in range(n)]
pre=[0]*n
pre[0]=a[0]
for i in range(1,n):
    pre[i]=a[i]+pre[i-1]
    dp[i-1][i]=a[i-1]+a[i]
    dp[i-1][i-1]=0
for i in range(3,n+1):
    for j in range(n-i+1):
        k=j+i-1
        for l in range(j,k+1):
            t1,t2=0,0
            if l-1>=0:
                t1=dp[j][l-1]
            if l+1<n:
                t2=dp[l+1][k]
            # print(pre[l],pre[j],a[j],a[l],pre[l]-(pre[j]-a[j])-a[l],t1,t2)
            # if count==2:
            #     print(t1,t2)
            dp[j][k]=min(dp[j][k],get(pre[l]-pre[j]+a[j]-a[l],a[l],pre[k]-pre[l])+t1+t2)
# print(dp)
print(dp[0][n-1])

Submission status: Wrong Answer

Solution code:
count=0
def get(hk,v,w):
    # global count
    # if count==2:
    #     print(hk,v,w)
    # count+=1
    if hk==0 or v==0 or w==0:
        return hk+v+w
    return min(2*(hk+v)+w,2*(v+w)+hk)
n=int(input())
a=list(map(int,input().split()))
dp=[[99999999999999999999 for i in range(n)] for j in range(n)]
pre=[0]*n
pre[0]=a[0]
for i in range(1,n):
    pre[i]=a[i]+pre[i-1]
    dp[i-1][i]=a[i-1]+a[i]
    dp[i-1][i-1]=0
for i in range(3,n+1):
    for j in range(n-i+1):
        k=j+i-1
        for l in range(j,k+1):
            t1,t2=0,0
            if l-1>=0:
                t1=dp[j][l-1]
            if l+1<n:
                t2=dp[l+1][k]
            # print(pre[l],pre[j],a[j],a[l],pre[l]-(pre[j]-a[j])-a[l],t1,t2)
            # if count==2:
            #     print(t1,t2)
            dp[j][k]=min(dp[j][k],get(pre[l]-pre[j]+a[j]-a[l],a[l],pre[k]-pre[l])+t1+t2)
# print(dp)
print(dp[0][n-1])

Submission status: Wrong Answer

Solution code:
def main():
    INF = 10 ** 12
    N = int(input())
    A = list(map(int, input().split(' ')))
    cumsum = [0 for _ in range(N)]
    cumsum[0] = A[0]
    for i in range(1, N):
        cumsum[i] = A[i] + cumsum[i - 1]
    dp = [[0 for _ in range(N)] for _ in range(N)]

    def solve(left, right):
        if left == right:
            return 0
        ret = dp[left][right]
        if ret > 0:
            return ret
        ret = INF
        for mid in range(left, right):
            ret = min([
                ret,
                solve(left, mid) + solve(mid + 1, right)
            ])
        ret += cumsum[right] - (cumsum[left - 1] if left > 0 else 0)
        dp[left][right] = ret
        return ret

    print(solve(0, N - 1))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def solve(A):
    if len(A) == 2:
        return sum(A)
    costs = [A[i] + A[i + 1] for i in range(len(A) - 1)]
    min_cost = min(costs)
    index = costs.index(min_cost)
    next_A = A[:index] + [min_cost] + A[(index + 2):]
    return min_cost + solve(next_A)


def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    print(solve(A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:


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


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


def solve():
    N = read_int()
    A = read_ints()
    total = 0
    while len(A) != 1:
        min_ix = 0
        min_sum = A[0]+A[1]
        for i in range(1, len(A)-1):
            if A[i]+A[i+1] < min_sum:
                min_ix = i
                min_sum = A[i]+A[i+1]
        total += min_sum
        new_A = []
        for i in range(len(A)):
            if i == min_ix+1:
                continue
            if i == min_ix:
                new_A.append(A[i]+A[i+1])
                continue
            new_A.append(A[i])
        A = new_A
    return total


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

Submission status: Wrong Answer

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

n = int(input())
A = list(map(int, input().split()))
heapq.heapify(A)
ans = 0
while len(A) >= 2:
  s = heapq.heappop(A)
  t = heapq.heappop(A)
  ans += s+t
  heapq.heappush(A, s+t)
print(ans)

Submission status: Wrong Answer

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

dp = []
dp2 = []
aac = []

def fdp(l, r):
    global dp, dp2
    if dp2[l][r]:
        return dp[l][r]
    else:
        dp2[l][r] = 1
        if l == r:
            return 0
        result_tmp = float('inf')
        for kugiri in range(l, r):
            result_tmp = min(result_tmp, fdp(l, kugiri) + fdp(kugiri+1, r))
        result = result_tmp + (aac[r+1] - aac[l])
        dp[l][r] = result
        return result


def main():
    global dp, dp2, aac
    n = int(input())
    a = tuple(map(int, input().split()))
    aac = list(accumulate(a))
    aac = tuple(chain([0], aac))
    dp = [[0] * n for _ in range(n)]
    dp2 = [[0] * n for _ in range(n)]

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq as h

n = int(input())
l = list(map(int, input().split()))
h.heapify(l)
cost=0
while len(l)>1:
    a=h.heappop(l)
    b=h.heappop(l)
    cost+=a+b
    h.heappush(l,a+b)
print(cost)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    P=list(map(float,input().split()))
    dp=[[0]*(n+1) for _ in range(n)]#コインi(0-)までで，j枚が表
    dp[0][0]=1-P[0]
    dp[0][1]=P[0]
    for i in range(1,n):
        for j in range(i+2):
            if j==0:
                dp[i][j]=dp[i-1][j]*(1-P[i])
            else:
                dp[i][j]=dp[i-1][j-1]*P[i]+dp[i-1][j]*(1-P[i])
    print(sum(dp[-1][n//2+1:]))
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
import heapq


def solve():
    n = int(input())
    A = [int(i) for i in stdin.readline().split()]
    heapq.heapify(A)
    c = 0
    while len(A) != 1:
        mone = heapq.heappop(A)
        mtwo = heapq.heappop(A)
        c += mone + mtwo
        heapq.heappush(A, mone + mtwo)
    return c

print(solve())

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
dp=[[0]*n for _ in range(n)]
INF=10**12
for i in range(1,n):
    for j in range(n-i):
        s=0
        x=INF
        for k in range(j,i+j):
            x=min(x,dp[j][k]+dp[k+1][i+j])
            s+=a[k]
        s+=a[i+j]
        dp[j][i+j]=x+s
print(dp[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)]
INF=10**9+1
for i in range(1,n):
    for j in range(n-i):
        s=0
        x=INF
        for k in range(j,i+j):
            x=min(x,dp[j][k]+dp[k+1][i+j])
            s+=a[k]
        s+=a[i+j]
        dp[j][i+j]=x+s
print(dp[0][n-1])

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

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

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

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

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
a=[0]*(N+1)
for i in range(N):
    a[i+1]=a[i]+A[i]
print(a)
d=[[0]*(N+1) for i in range(N+1)]
for w in range(2,N+1):
    for l in range(N+1-w):
        d[l][l+w]=min([d[l][m]+d[m][l+w] for m in range(l+1,l+w)])+a[l+w]-a[l]
print(d[0][N])

Submission status: Wrong Answer

Solution code:
n = int(input())
ns = list(map(int, input().split()))
dp = [[0] * n for i in range(n)]
for i in range(n-1): 
    dp[i][i+1] = ns[i] + ns[i+1]
cur = [0]
cnt = 0
for i in ns:
    cnt += i
    cur.append(cnt)

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

Submission status: Wrong Answer

Solution code:
n = int(input())
ns = list(map(int, input().split()))
ans = 0
index = 0
while n >= 2:
    fusion = float('inf')
    for i in range(n - 1):
        if ns[i] + ns[i + 1] <= fusion:
            index = i
            fusion = ns[i] + ns[i+1]
    ans += fusion
    ns = ns[:index] + [fusion] + ns[index + 2:]
    n -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n = int(input())
ns = list(map(int, input().split()))
heapq.heapify(ns)
ans = 0
while len(ns) >= 2:
    a = heapq.heappop(ns) + heapq.heappop(ns)
    ans += a
    heapq.heappush(ns, a)
print(ans)

Submission status: Wrong Answer

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

N = int(input())
ali = list(map(int,input().split()))
c = 0

for j in range(N-1):
  mina = [0,10**10]
  for i in range(N-j-1):
    a1 = ali[i] + ali[i+1]
    if mina[1] > a1:
      mina = [i,a1]
  a1 = mina[0]
  ali[a1] = mina[1]
  c += mina[1]
  del ali[a1+1]

print(c)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools

#input = sys.stdin.readline
def input():
    return sys.stdin.readline().strip("\n").strip(" ")

_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)
    else:
        print(ans)


def solve():



    N = iip()
    A = iip()
    SA = [0]

    cur = 0
    for i in A:
        cur += i
        SA.append(cur)

    #print(SA)
    size = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(i, N):
            size[i][j] = int(SA[j+1]-SA[i])

    #fprint(size)

    dp = [[10**12 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0

    for d in range(N):
        for l in range(N):
            r = l+d
            if r >= N:
                continue

            if l==r:
                dp[l][r] = 0
            else:
                dp[l][r] = min(dp[l][r],
                               dp[l+1][r] + size[l][l] + size[l+1][r],
                               dp[l][r-1] + size[r][r] + size[l][r-1])

            for k in range(l, r):
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + size[l][k] + size[k+1][r])

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




#####################################################ライブラリ集ここから



def kiriage_warizan(a, b):
    return -(-a//b)

def iip(listed=False):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    if isinstance(l, list):
        l = l[0] # 間違って要素１個のタプルを渡されても受け取る
    assert isinstance(l, int)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def flatten(l):
    return list(itertools.chain.from_iterable(l))


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    if isinstance(s, int):
        print(s)
        return
    keta = max([len(str(i)) for i in itertools.chain.from_iterable(s)])
    print("--------")
    for i in s:
        print([str(j).rjust(keta) for j in i])
    print("--------")


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido = 1): # 関数を二分探索
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r-l > seido:
        #print(x)
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r=x
            else:
                l=x


        elif func(x) > target:
            r = x
        else:
            #print(r, l)
            l = x

    #print(l, r)
    if side == "left" and func(r) == target:
        return r
    elif side != "left" and func(l) == target:
        return l
    elif side == "left":
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                #for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0
while(len(a) > 1):
  minn = a[0]+a[1]
  ind = 0
  for i in range(1,n-1):
    if(a[i]+a[i+1] < minn):
      minn = a[i]+a[i+1]
      ind = i
  a[ind+1] = minn
  ans += minn
  del a[ind]
  n -= 1
print(ans)

Submission status: Wrong Answer

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

n=int(input())
a= list(map(int, input().split()))
a+=a
b=itertools.accumulate(a)
b=[0]+list(b)
INF=10**12
dp=[[INF] *(2*n+1) for i in range(2*n+1)]
# dp[i][j][0]: コスト
# dp[i][j][1]:合成したスライムの合計

for i in range(n):
    for l in range(2*n-i):
        r=l+i
        if r==l:
            dp[l][r]=0
        else:
            # 合成の仕方を確定
            for k in range(l,r):
                dp[l][r]=min(dp[l][k]+dp[k+1][r]+b[r+1]-b[l],dp[l][r])

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

Submission status: Wrong Answer

Solution code:
import heapq

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

heapq.heapify(a)

ans = 0
while len(a) >= 2:
    a1 = heapq.heappop(a)
    a2 = heapq.heappop(a)
    ans += a1 + a2
    heapq.heappush(a, a1 + a2)

print(ans)