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:
from itertools import accumulate
INF=1001001001001
n=int(input())
a=list(map(int,input().split()))
dp=[[INF for i in range(n+1)] for j in range(n+1)]
wa=[0]+list(accumulate(a))
for i in range(n):
  dp[i][i+1]=0
for gap in range(2,n+1):
  for l in range(n-gap+1):
    r=l+gap
    for k in range(l+1,r):
      dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]+wa[r]-wa[l])
print(dp[0][n])

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
INF=1001001001001
n=int(input())
a=list(map(int,input().split()))
dp=[[INF for i in range(n+1)] for j in range(n+1)]
wa=list(accumulate(a))
for i in range(n):
  dp[i][i+1]=0
for gap in range(2,n+1):
  for l in range(n-gap+1):
    r=l+gap
    for k in range(l+1,r):
      dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]+wa[r-1]-wa[l]+a[l])
print(dp[0][n])

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
INF=1001001001
n=int(input())
a=list(map(int,input().split()))
dp=[[INF for i in range(n+1)] for j in range(n+1)]
wa=list(accumulate(a))
for i in range(n):
  dp[i][i+1]=0
for gap in range(2,n+1):
  for l in range(n):
    r=l+gap
    if r>=n+1:
      break
    for k in range(l+1,r):
      dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]+wa[r-1]-wa[l]+a[l])
print(dp[0][n])

Submission status: Wrong Answer

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
    ind = 0
    # print(l)
    for i in range(1, n):
        curr = l[i] + l[i - 1]
        if curr < ans:
            ans = curr
            ind = i - 1
    
    return ans + dp(l[:ind] + [ans] + l[ind + 2:])

print(dp(l))

Submission status: Wrong Answer

Solution code:
import heapq
n = int(input())
arr = list(map(int, input().strip().split()))

heapq.heapify(arr)

ans = 0
while len(arr) > 1:
    sumi = heapq.heappop(arr) + heapq.heappop(arr)
    heapq.heappush(arr, sumi)
    ans += sumi

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ar = [int(x) for x in input().split()]
INT_MAX = 1000000000
dp = [[INT_MAX for i in range(n + 5)] for j in range(n + 5)]
for i in range(n):
    dp[i][i] = 0
prefix = [0, ar[0]]
for i in range(1, n):
    prefix.append(prefix[i] + ar[i])
for i in range(n - 1, -1, -1):
    for j in range(i + 1, n):
        for k in range(0, j - i):
            dp[i][j] = min(dp[i][j], (dp[i][i + k] + dp[i + k + 1][j]) + prefix[j + 1] - prefix[i])
print(dp[0][n - 1])

Submission status: Wrong Answer

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

def get_index(arr):
    init_arr = []
    for i in range(len(arr)-1):
        init_arr.append([arr[i]+arr[i+1], i])
    return min(init_arr, key=lambda x: x[0])[1]

n = int(input())

arr = [int(i) for i in input().split(' ')]

ans = 0
for _ in range(1, n):
    index = get_index(arr)

    ans += arr[index] + arr[index+1]
    a, b = arr[index], arr[index+1]
    arr.insert(index, a+b)
    del arr[index+1]; del arr[index+1]

print(ans)

Submission status: Wrong Answer

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

costs = []
lr = []

res = 0

for i in range(N-1):
  costs.append(A[i] + A[i+1])
  lr.append({"l": A[i], "r": A[i+1]})

ccosts = []
for i in range(N-1):
  mc = min(costs)
  res += mc
  index = costs.index(mc)
  
  if index+1 < len(costs) and costs[index+1] == mc:
    cindex = index+1
    ccosts = deepcopy(costs)
    clr = deepcopy(lr)
    ccosts.pop(cindex)
    if cindex < len(ccosts):
      ccosts[cindex] += clr[cindex]["l"]
      clr[cindex+1]["l"] += clr[cindex]["l"]
    if 0 < cindex:
      ccosts[cindex-1] += clr[cindex]["r"]
      clr[cindex-1]["r"] += clr[cindex]["r"]

  costs.pop(index)
  if index < len(costs):
    costs[index] += lr[index]["l"]
    lr[index+1]["l"] += lr[index]["l"]
  if 0 < index:
    costs[index-1] += lr[index]["r"]
    lr[index-1]["r"] += lr[index]["r"]
  lr.pop(index)
  if 0 < len(costs) and 0 < len(ccosts) and min(ccosts) < min(costs):
    costs = ccosts
    lr = clr

print(res)

Submission status: Wrong Answer

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

costs = []
lr = []

res = 0

for i in range(N-1):
  costs.append(A[i] + A[i+1])
  lr.append({"l": A[i], "r": A[i+1]})

for i in range(N-1):
  res += min(costs)
  index = costs.index(min(costs))
  costs.pop(index)
  if index < len(costs):
    costs[index] += lr[index]["l"]
    lr[index+1]["l"] += lr[index]["l"]
  if 0 < index:
    costs[index-1] += lr[index]["r"]
    lr[index-1]["r"] += lr[index]["r"]
  lr.pop(index)

print(res)

Submission status: Wrong Answer

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

dp = []

res = 0

for i in range(N-1):
  res += A[0] + A[1]
  A[1] += A[0]
  A.pop(0)
  A = sorted(A)

print(res)

Submission status: Wrong Answer

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

from bisect import insort
n = inp()
x = ip()
x.sort()
ans = 0
for i in range(n-1):
    t = x.pop(0) + x.pop(0)
    ans += t
    insort(x,t)
print(ans)

Submission status: Wrong Answer

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

from queue import PriorityQueue
n = inp()
x = ip()
pq = PriorityQueue()
[pq.put(i) for i in x]
ans = 0
for i in range(n-1):
    a = pq.get()
    b = pq.get()
    ans += a+b
    pq.put(a+b)
print(ans)

Submission status: Wrong Answer

Solution code:
INF = 10**12


def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    dp = [[INF]*(N+1) for _ in range(N)]
    cost = [[INF]*(N+1) for _ in range(N)]

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

    for w in range(2, N+1):
        for le in range(N-w+1):
            ri = le + w
            for i in range(le+1, ri):
                if dp[le][ri] >= dp[le][i] + dp[i][ri]:
                    dp[le][ri] = dp[le][i] + dp[i][ri]
                    cost[le][ri] = min(cost[le][ri],
                                       cost[le][i] + cost[i][ri] + dp[le][ri])

    print(cost[0][N])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)

ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return np.fromstring(readline(), sep=' ', dtype=np.int64)

'''
DPじゃなくて貪欲に小さい方からくっつけるのじゃだめ？←隣り合うという制約が入れられない

sum a_i から をaiに分解するイメージ
dp[i,j] ... コストの最小. A[i:j]を合体させたとき

更新式
dp[i,j] = min(dp[i,i+1] + dp[i+1,j],
              dp[i,i+2] + dp[i+2,j],...
              ) + sum(A[i,j])

dp[i,i+1]=0かな？
'''


N = a_int()
A = ints()
A_accum = zeros(N + 1)
A_accum[1:] = np.cumsum(A)
dp = full((N + 1, N + 1), -1)
dp[np.arange(N), np.arange(N) + 1] = 0

from numba import njit


@njit('(i8,i8,i8[:,:],i8[:])', cache=True)
def dfs(i, j, dp, A_accum):
    if dp[i, j] != -1:
        return dp[i, j]
    mi = 10**12
    for k in range(i + 1, j):
        mi = min(mi, dfs(i, k, dp, A_accum) + dfs(k, j, dp, A_accum))
    dp[i, j] = mi + A_accum[j] - A_accum[i]
    return dp[i, j]


print(dfs(0, N, dp, A_accum))

Submission status: Wrong Answer

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count


n=int(inp())
ar=lis()
inf=10**12
dp=[[inf for i in range(n+5)] for _ in range(n+5)]
for i in range(n):
    dp[i][i]=0
prefix=[0,ar[0]]
for i in range(1,n):
    prefix.append(prefix[i]+ar[i])
for i  in range(n-1,-1,-1):
    for j in range(i+1,n):
        for k in range(0,j-i):
            dp[i][j]=min(dp[i][j],(dp[i][i+k]+dp[i+k+1][j])+prefix[j+1]-prefix[i])

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

Submission status: Wrong Answer

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count


n=int(inp())
ar=lis()
inf=10**10
dp=[[inf for i in range(n+5)] for _ in range(n+5)]
for i in range(n):
    dp[i][i]=0
prefix=[0,ar[0]]
for i in range(1,n):
    prefix.append(prefix[i]+ar[i])
for i  in range(n-1,-1,-1):
    for j in range(i+1,n):
        for k in range(0,j-i):
            dp[i][j]=min(dp[i][j],(dp[i][i+k]+dp[i+k+1][j])+prefix[j+1]-prefix[i])

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

Submission status: Wrong Answer

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count


n=int(inp())
ar=lis()
import heapq as hp
hp.heapify(ar)
c=0
while(len(ar)>1):
    m1=hp.heappop(ar)
    m2=hp.heappop(ar)
    c+=(m1+m2)
    hp.heappush(ar,m1+m2)
print(c)

Submission status: Wrong Answer

Solution code:
'''
sum a_i から
DPじゃなくて貪欲に小さい方からくっつけるのじゃだめ？
'''
from heapq import heapify, heappop, heappush, heappushpop


class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)


import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


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


N = a_int()
A = ints()

pq = PriorityQueue(A)
ans = 0
while len(pq) > 1:
    a = pq.pop()
    b = pq.pop()
    s = a + b
    ans += s
    pq.push(s)
print(ans)

Submission status: Wrong Answer

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

ans=0
for _ in range(N-1):
  MIN=10**20
  argmin=-1
  for i in range(1,len(a)):
    if a[i-1]+a[i]<MIN:
      MIN=a[i-1]+a[i]
      argmin=i

  a[argmin] = MIN
  del a[argmin-1]
  ans += MIN
  
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from numba import njit
N=int(input())
a=np.array([int(i) for i in input().split()],dtype=np.int64)
s=[0]

dp=np.array([[-1 for i in range(N)] for _ in range(N)],dtype=np.int64)

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

s=np.array(s,dtype=np.int64)
for i in range(N):
    dp[i][i]=0

@njit('i8(i8,i8,i8[:,:],i8[:])', cache=True)
def calc(i,j,dp,s):
    if dp[i][j]!=-1:
        return dp[i][j]
    m=10**12
    for k in range(i,j):
        m=min(m,calc(i,k,dp,s)+calc(k+1,j,dp,s)+s[j+1]-s[i])
    dp[i][j]=m
    return dp[i][j]

print(calc(0,N-1,dp,s))

Submission status: Wrong Answer

Solution code:
import numpy as np
from numba import njit
N=int(input())
a=np.array([int(i) for i in input().split()],dtype=np.int64)
s=[0]

dp=np.array([[-1 for i in range(N)] for _ in range(N)],dtype=np.int64)

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

s=np.array(s,dtype=np.int64)
for i in range(N):
    dp[i][i]=0

@njit('i8(i8,i8,i8[:,:],i8[:])', cache=True)
def calc(i,j,dp,s):
    if dp[i][j]!=-1:
        return dp[i][j]
    m=10**11
    for k in range(i,j):
        m=min(m,calc(i,k,dp,s)+calc(k+1,j,dp,s)+s[j+1]-s[i])
    dp[i][j]=m
    return dp[i][j]

print(calc(0,N-1,dp,s))

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()

cost = 0

while N!=1:
  rin = [A[i]+A[i+1] for i in range(N-1)]
  m = min(rin)
  cost += m
  p = rin.index(m)
  A = A[:p]+[m]+A[p+2:]
  N -= 1
  
print(cost)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()

cnt = 1
for i in range(n-1):
    if s[i]!=s[i+1]:
        cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1<<30)
def f(i,j,d):
  if i>=j:
    return 0
  if z[i][j]==-1:
    q=1<<64
    for k in xrange(i+1,j):
      q=min(q,s[j+1]-s[i]+f(i,k,d)+f(k+1,j,d))
    z[i][j]=q
  return z[i][j]
n=input()
a=map(int,raw_input().split())
s=[0]
for i in a:
  s.append(s[-1]+i)
z=[[-1]*n for i in xrange(n)]
print f(0,n-1,{})