Problem:


Score : 1000 points

Problem Statement

There is a stack of N cards, each of which has a non-negative integer written on it. The integer written on the i-th card from the top is A_i.

Snuke will repeat the following operation until two cards remain:

Choose three consecutive cards from the stack.

Eat the middle card of the three.

For each of the other two cards, replace the integer written on it by the sum of that integer and the integer written on the card eaten.

Return the two cards to the original position in the stack, without swapping them.

Find the minimum possible sum of the integers written on the last two cards remaining.

Constraints

2 \leq N \leq 18

0 \leq A_i \leq 10^9 (1\leq i\leq N)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the minimum possible sum of the integers written on the last two cards remaining.

Sample Input 1

4
3 1 4 2

Sample Output 1

16

We can minimize the sum of the integers written on the last two cards remaining by doing as follows:

Initially, the integers written on the cards are 3, 1, 4, and 2 from top to bottom.

Choose the first, second, and third card from the top. Eat the second card with 1 written on it, add 1 to each of the other two cards, and return them to the original position in the stack. The integers written on the cards are now 4, 5, and 2 from top to bottom.

Choose the first, second, and third card from the top. Eat the second card with 5 written on it, add 5 to each of the other two cards, and return them to the original position in the stack. The integers written on the cards are now 9 and 7 from top to bottom.

The sum of the integers written on the last two cards remaining is 16.

Sample Input 2

6
5 2 4 1 6 9

Sample Output 2

51

Sample Input 3

10
3 1 4 1 5 9 2 6 5 3

Sample Output 3

115



Sample input:
4
3 1 4 2


Sample output:
16

Submission status: Wrong Answer

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

while len(a) >= 3:
  m = min(a[1:-1])
  id = a[1:-1].index(m)
  a[id] += m
  a[id+2] += m
  a.remove(m)

print(a[0] + a[1])

Submission status: Wrong Answer

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

def tami(visited,x,cnt,List):
  global ans
  #print(a)
  #print("visited=",visited)
  #print("List=",List)
  #print("-----------")
  if cnt == N-2:
    ans = min(ans,List[0]+List[-1])
    return
  else:
    for j in range(1,N-1): # 次の探索 j
      if j in visited:
        continue
      else:
        if x < j:
          for v in range(x+1,j): # x→j 間に未探索 → ダメ
            if v not in visited:
              break
          else:
            for k in range(j-1,-1,-1): # listの更新
              if k not in visited:
                left = k
                break
            for k in range(j+1,N):
              if k not in visited:
                right = k
                break
            l = List[:left] + [List[left]+List[j]] + List[left+1:right] + [List[right]+List[j]] + List[right+1:]
            tami(visited+[j],j,cnt+1,l)
        else:
          for k in range(j-1,-1,-1): # listの更新
            if k not in visited:
              left = k
              break
          for k in range(j+1,N):
            if k not in visited:
              right = k
              break        
          l = List[:left] + [List[left]+List[j]] + List[left+1:right] + [List[right]+List[j]] + List[right+1:]
          tami(visited+[j],j,cnt+1,l)

N = I()
a = IL()

ans = MAX_INT
for i in range(1,N-1):
  l = a[:i-1] + [a[i-1]+a[i]] + [a[i]] + [a[i+1]+a[i]] + a[i+2:]
  #print(l)
  tami([i],i,1,l)

print(ans)

Submission status: Wrong Answer

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

def kukan(l,r,el=1,er=1):
    em=el+er
    if l+1==r:
        return 0
    if l+2==r:
        return a[l+1]*em
    t=(l,r,el,er)
    if t in memo:
        return memo[t]
    re=10**9
    for m in range(l+1,r):
        tmp=kukan(l,m,el,em)+kukan(m,r,em,er)+a[m]*em
        if tmp<re:
            re=tmp
    memo[t]=re
    return re

n=int(input())
a=list(map(int,input().split()))
memo={}
print(a[0]+kukan(0,n-1)+a[-1])

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
from operator import itemgetter
from random import randint
from time import time


@lru_cache(maxsize=None)
def contract(aaa):
    if len(aaa) == 2:
        return sum(aaa)
    ans = 10 ** 18
    for i in range(1, len(aaa) - 1):
        ret = list(aaa[:i])
        ret.extend(aaa[i + 1:])
        ret[i - 1] += aaa[i]
        ret[i] += aaa[i]
        res = contract(tuple(ret))
        ans = min(ans, res)
    return ans


def greedy(aaa, order):
    ans = 10 ** 18
    contracted = set()
    for i, v in order:
        j = i
        for c in contracted:
            if c < i:
                j -= 1
        aj = aaa[j]
        aaa = aaa[:j] + aaa[j + 1:]
        aaa[j - 1] += aj
        aaa[j] += aj
        contracted.add(i)
        if len(aaa) <= 9:
            ans = min(ans, contract(tuple(aaa)))
            break
    return ans


def solve(aaa):
    if len(aaa) <= 12:
        return contract(tuple(aaa))
    order = sorted(enumerate(aaa[1:-1], start=1), key=itemgetter(1))
    ans = greedy(aaa, order)
    lim = time() + 1.9
    while time() < lim:
        i = randint(1, n - 4)
        order[i], order[i + 1] = order[i + 1], order[i]
        res = greedy(aaa, order)
        if res < ans:
            ans = res
        elif res == ans:
            if randint(0, 1) == 1:
                order[i], order[i + 1] = order[i + 1], order[i]
        else:
            order[i], order[i + 1] = order[i + 1], order[i]
    return ans


n = int(input())
aaa = list(map(int, input().split()))
ans = solve(aaa)
# ans = contract(tuple(aaa))
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
from operator import itemgetter
from random import randint
from time import time


@lru_cache(maxsize=None)
def contract(aaa):
    if len(aaa) == 2:
        return sum(aaa)
    ans = 10 ** 18
    for i in range(1, len(aaa) - 1):
        ret = list(aaa[:i])
        ret.extend(aaa[i + 1:])
        ret[i - 1] += aaa[i]
        ret[i] += aaa[i]
        res = contract(tuple(ret))
        ans = min(ans, res)
    return ans


def greedy(aaa, order):
    ans = 10 ** 18
    contracted = set()
    for i, v in order:
        j = i
        for c in contracted:
            if c < i:
                j -= 1
        aj = aaa[j]
        aaa = aaa[:j] + aaa[j + 1:]
        aaa[j - 1] += aj
        aaa[j] += aj
        contracted.add(i)
        if len(aaa) <= 10:
            ans = min(ans, contract(tuple(aaa)))
            break
    return ans


def solve(aaa):
    if len(aaa) <= 12:
        return contract(tuple(aaa))
    order = sorted(enumerate(aaa[1:-1], start=1), key=itemgetter(1))
    ans = greedy(aaa, order)
    lim = time() + 1.6
    while time() < lim:
        i = randint(1, n - 4)
        order[i], order[i + 1] = order[i + 1], order[i]
        res = greedy(aaa, order)
        if res < ans:
            ans = res
        elif res == ans:
            if randint(0, 1) == 1:
                order[i], order[i + 1] = order[i + 1], order[i]
        else:
            order[i], order[i + 1] = order[i + 1], order[i]
    return ans


n = int(input())
aaa = list(map(int, input().split()))
ans = solve(aaa)
# ans = contract(tuple(aaa))
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
from operator import itemgetter


@lru_cache(maxsize=None)
def contract(aaa):
    if len(aaa) == 2:
        return sum(aaa)
    ans = 10 ** 18
    for i in range(1, len(aaa) - 1):
        ret = list(aaa[:i])
        ret.extend(aaa[i + 1:])
        ret[i - 1] += aaa[i]
        ret[i] += aaa[i]
        res = contract(tuple(ret))
        ans = min(ans, res)
    return ans


def greedy(aaa):
    if len(aaa) <= 14:
        return contract(tuple(aaa))

    ans = 10 ** 18
    contracted = set()
    order = sorted(enumerate(aaa[1:-1], start=1), key=itemgetter(1))
    for i, v in order:
        j = i
        for c in contracted:
            if c < i:
                j -= 1
        aj = aaa[j]
        aaa = aaa[:j] + aaa[j + 1:]
        aaa[j - 1] += aj
        aaa[j] += aj
        contracted.add(i)
        if len(aaa) <= 13:
            ans = min(ans, contract(tuple(aaa)))
    return ans


n = int(input())
aaa = list(map(int, input().split()))
ans = greedy(aaa)
# ans = contract(tuple(aaa))
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
from operator import itemgetter


@lru_cache(maxsize=None)
def contract(aaa):
    if len(aaa) == 2:
        return sum(aaa)
    ans = 10 ** 18
    for i in range(1, len(aaa) - 1):
        ret = list(aaa[:i])
        ret.extend(aaa[i + 1:])
        ret[i - 1] += aaa[i]
        ret[i] += aaa[i]
        res = contract(tuple(ret))
        ans = min(ans, res)
    return ans


def greedy(aaa):
    if len(aaa) <= 10:
        return contract(tuple(aaa))

    ans = 10 ** 18
    contracted = set()
    order = sorted(enumerate(aaa[1:-1], start=1), key=itemgetter(1))
    for i, v in order:
        j = i
        for c in contracted:
            if c < i:
                j -= 1
        aj = aaa[j]
        aaa = aaa[:j] + aaa[j + 1:]
        aaa[j - 1] += aj
        aaa[j] += aj
        contracted.add(i)
        if len(aaa) <= 10:
            ans = min(ans, contract(tuple(aaa)))
    return ans


n = int(input())
aaa = list(map(int, input().split()))
ans = greedy(aaa)
print(ans)

Submission status: Wrong Answer

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

def nasu(X, re):
  L = len(X)
  if L == 3:
    return X[0] + X[1] * 2 + X[2]
  if L == 4:
    a = X[0] + X[1] * 3 + X[2] * 2 + X[3]
    b = X[0] + X[1] * 2 + X[2] * 3 + X[3]
    return min(a, b)
  ans = 10 ** 20
  for i in range(max(1, re), L - 1):
    t = X[:i - 1] + [X[i - 1] + X[i], X[i] + X[i + 1]] + X[i + 2:]
    ans = min(ans, nasu(t, i - 1))

  return ans

print(nasu(A, 1))

Submission status: Wrong Answer

Solution code:
size = int(input())
nums = list(map(int, input().split()))

# size = 10
# nums = list(map(int, "3 1 4 1 5 9 2 6 5 3".split()))

fnums = nums[1:size - 1]
rnums = list(reversed(fnums))

tmp = nums[1: size - 1]
tmp.sort()
tmps = len(tmp)

idxs = []
for num in tmp:
  fix = fnums.index(num)
  lix = rnums.index(num)
  if fix <= lix:
    # print("fix")
    # print("{} {}".format(tmps, fix))
    idxs.append(fix)
    fnums[fix] = -1
    rnums[tmps - fix - 1] = -1

  else:
    # aaaa
    # print("lix")
    idxs.append(tmps - lix - 1)
    fnums[tmps - lix - 1] = -1
    rnums[lix] = -1

  # print(fnums)
  # print(rnums)

first = 0
# print(idxs)
for i in range(0, len(idxs)):
  idx = idxs[i]
  # print("{} {}".format(idx, nums))
  n = nums.pop(idx + 1)
  nums[idx] += n
  nums[idx + 1] += n
  for j in range(0, len(idxs)):
    idxs[j] -= 1 if idxs[j] > idx else 0

print(sum(nums))

# 5 2 4 1 6 9
# 5 2 5 7 9
# 7 7 7 9
# 14 14 9
# 28 23
# 51

Submission status: Wrong Answer

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

a_max = max(a)
a.remove(a_max)
a_max2 = max(a)
a.remove(a_max2)
s = sum(a)
print(a)
print(a_max+a_max2+s*3)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A=list(map(int, input().split()))
A=np.array(A)

for i in range(N-2):
    nn=len(A)
    B=np.copy(A[1:nn-1])
    min_index=B.argmin()+1
    A_min = A[min_index]

    A[min_index-1] += A_min
    A[min_index+1] += A_min
    A=np.delete(A,min_index)

ans=sum(A)
print(ans)

Submission status: Wrong Answer

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

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

B = A[1:-1]
N_B = N-2
B_acc = [0]+list(accumulate(B))
# 現時点の総和
dp = [float('inf')]*(1 << N_B)
dp[0] = 0

for mask in range(1 << N_B):
    for new_card in range(N_B):  # 次に食べるカード
        if mask >> new_card & 1:
            continue
        new_state = mask | 1 << new_card
        # calc add
        if new_card == 0:
            left = 0
        else:
            # leftは含む
            left = new_card
            while left > 0:
                if new_state >> (left-1) & 1:
                    left -= 1
                else:
                    break
        if new_card == N_B-1:
            # rightは含む
            right = N_B-1
        else:
            right = new_card
            while right < N_B-1:
                if new_state >> (right+1) & 1:
                    right += 1
                else:
                    break
        # 累積和でとる
        add = B_acc[right+1]-B_acc[left]

        dp[new_state] = min(dp[new_state], dp[mask] + add)

print(dp[-1]+sum(A))

Submission status: Wrong Answer

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

def calc(X):
    # print("X =", X)
    if len(X) == 2:
        return sum(X)
    mi = min(X[1:-1])
    T = [i for i in range(1, len(X)-1) if X[i] == mi]
    # print("len =", len(T))
    mii = random.randrange(len(T))
    # print("T =", T)
    # print("mii =", mii)
    k = T[mii]
    if 1:
        k = random.randrange(len(X)-2) + 1
    Y = [X[i] + (X[k] if i == k-1 or i == k+1 else 0) for i in range(len(X)) if i != k]
    return calc(Y)

ans = 10**30
while time.time()-sTime < 1.7:
    ans = min(ans, calc(A))

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
for i in range(n - 2):
    k = a.index(min(a[1:len(a) - 1]))
    p = a[k]
    a[k - 1] += p
    a[k + 1] += p
    del a[k]
print(sum(a))

Submission status: Wrong Answer

Solution code:

def Solve():
    mn2=0
    mnidx2=0
    N=int(input())
    AL=[int(x) for x in input().split()]
    while True:
        if len(AL)==2:
            return sum(AL)

        mn=10**9
        mnidx=-1
        for i,a in enumerate(AL):
            if i==0 or i==len(AL)-1:
                continue
            if a<mn:
                mn=a
                mnidx=i
                
        AL=AL[:mnidx]+AL[mnidx+1:]
        AL[mnidx-1]+=mn
        AL[mnidx]+=mn  

print(Solve())

Submission status: Wrong Answer

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

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

B = A[1:-1]
N_B = N-2
B_acc = [0]+list(accumulate(B))
# 現時点の総和
dp = [float('inf')]*(1 << N_B)
dp[0] = 0

for mask in range(1 << N_B):
    for new_card in range(N_B):  # 次に食べるカード
        if mask >> new_card & 1:
            continue
        new_state = mask | 1 << new_card
        # calc add
        if new_card == 0:
            left = 0
        else:
            # leftは含む
            left = new_card
            while left > 0:
                if mask >> (left-1) & 1:
                    left -= 1
                else:
                    break
        if new_card == N_B-1:
            # rightは含む
            right = N_B-1
        else:
            right = new_card
            while right < N_B-1:
                if mask >> (right+1) & 1:
                    right += 1
                else:
                    break
        # 累積和でとる
        add = B_acc[right+1]-B_acc[left]

        dp[new_state] = min(dp[new_state], dp[mask] + add)

print(dp[-1]+sum(A))

Submission status: Wrong Answer

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

def calc(X):
    # print("X =", X)
    if len(X) == 2:
        return sum(X)
    mi = min(X[1:-1])
    T = [i for i in range(1, len(X)-1) if X[i] == mi]
    # print("len =", len(T))
    mii = random.randrange(len(T))
    # print("T =", T)
    # print("mii =", mii)
    k = T[mii]
    if random.randrange(10) == 0:
        k = random.randrange(len(X)-2) + 1
    Y = [X[i] + (X[k] if i == k-1 or i == k+1 else 0) for i in range(len(X)) if i != k]
    return calc(Y)

ans = 10**30
while time.time()-sTime < 1.7:
    ans = min(ans, calc(A))

print(ans)

Submission status: Wrong Answer

Solution code:

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

for j in range(N-2):
    min_tmp = A[1]
    count = 1
    for i in range(N-j-2, N-j-1):
        if A[i] < min_tmp:
            min_tmp = A[i]
            count = i
    A[count-1] += A[count]
    A[count+1] += A[count]
    A.pop(count)

print(A[0]+A[1])

Submission status: Wrong Answer

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

def calc(X):
    # print("X =", X)
    if len(X) == 2:
        return sum(X)
    mi = min(X[1:-1])
    T = [i for i in range(1, len(X)-1) if X[i] == mi]
    # print("len =", len(T))
    mii = random.randrange(len(T))
    # print("T =", T)
    # print("mii =", mii)
    k = T[mii]
    if random.randrange(100) == 0:
        k = random.randrange(len(X)-2) + 1
    Y = [X[i] + (X[k] if i == k-1 or i == k+1 else 0) for i in range(len(X)) if i != k]
    return calc(Y)

ans = 10**30
while time.time()-sTime < 1.7:
    ans = min(ans, calc(A))

print(ans)

Submission status: Wrong Answer

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

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

B = A[1:-1]
N_B = N-2
B_acc = [0]+list(accumulate(B))
# 現時点の総和
dp = [float('inf')]*(1 << N_B)
dp[0] = 0

for mask in range(1 << N_B):
    for new_card in range(N_B):  # 次に食べるカード
        if mask >> new_card & 1:
            continue
        new_state = mask | 1 << new_card
        # calc add
        if new_card == 0:
            left = 0
        else:
            # leftは含む
            left = new_card
            while left > 0:
                if mask >> (left-1) & 1:
                    left -= 1
                else:
                    break
        if new_card == N_B-1:
            # rightは含む
            right = N_B-1
        else:
            right = new_card
            while new_card < N_B-1:
                if mask >> (right+1) & 1:
                    right += 1
                else:
                    break
        # 累積和でとる
        add = B_acc[right+1]-B_acc[left]

        dp[new_state] = min(dp[new_state], dp[mask] + add)

print(dp[-1]+sum(A))

Submission status: Wrong Answer

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

def nasu(X, l, r):
  L = len(X)
  if L == 3:
    return X[0] + X[1] * 2 + X[2]
  if L == 4:
    a = X[0] + X[1] * 3 + X[2] * 2 + X[3]
    b = X[0] + X[1] * 2 + X[2] * 3 + X[3]
    return min(a, b)
  ans = 10 ** 20
  if l == -1:
    for i in range(1, L - 1):
      t = X[:i - 1] + [X[i - 1] + X[i], X[i] + X[i + 1]] + X[i + 2:]
      a = i - 1
      b = i
      ans = min(ans, nasu(t, a, b))
      if i >= 2:
        if X[i] < X[i - 1]:
          k = t[:i - 2] + [t[i - 2] + t[i - 1], t[i - 1] + t[i]] + t[i + 1:]
          ans = min(ans, nasu(k, -1, -1))
      if i < L - 2:
        if X[i] < X[i + 1]:
          k = t[:i - 1] + [t[i - 1] + t[i], t[i] + t[i + 1]] + t[i + 2:]
          ans = min(ans, nasu(k, -1, -1))
  else:
    for i in range(1, L - 1):
      if l <= i <= r:
        continue
      t = X[:i - 1] + [X[i - 1] + X[i], X[i] + X[i + 1]] + X[i + 2:]
      a = i - 1
      b = i + 1
      ans = min(ans, nasu(t, a, b))
      if i >= 2:
        if X[i] < X[i - 1]:
          k = t[:i - 2] + [t[i - 2] + t[i - 1], t[i - 1] + t[i]] + t[i + 1:]
          ans = min(ans, nasu(k, -1, -1))
      if i < L - 2:
        if X[i] < X[i + 1]:
          k = t[:i - 1] + [t[i - 1] + t[i], t[i] + t[i + 1]] + t[i + 2:]
          ans = min(ans, nasu(k, -1, -1))
  return ans

print(nasu(A, -1, -1))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = A[1:N-1]
B.sort
C = 0
for i in range(N-2):
  X = B.index(min(B))
  C += min(B)*(N-1-i)
  if X == 0:
    A[0]=A[0]+min(B)*(N-1-i)
    B[X]=B[X]+min(B)*(N-1-i)
  elif X == N-1-i:
    A[N-1]=A[N-1]+min(B)*(N-1-i)
    B[X-2]=B[X-2]+min(B)*(N-1-i)
  else:
    B[X-2]=B[X-2]+min(B)*(N-1-i)
    B[X]=B[X]+min(B)*(N-1-i)
  del B[X-1]
print(A[0]+A[N-1])

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

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

NN = N

# N = 2になるまで繰り返す
if N >= 5:
    for n in range(N-5):
        m = np.min(A[1:NN-1])
        sum3i = np.max(A)*3+1
        p = np.argmin(A[1:NN-1])
        p += 1
        dd = min([NN-p+1, p])

        for i in range(1,NN-1):
            if A[i] == m:
                sum3 = A[i-1] + A[i+1]
                if sum3 < sum3i:
                    sum3i = sum3
                    p = i
                elif sum3 == sum3i:
                    d = min([NN-i-1, i])
                    if d < dd:
                        dd = d
                        p = i

        #print(A[1:NN-1])
        #p = np.argmin(A[1:NN-1])
        #p = int(p+1)
        A[p-1] += A[p]
        A[p+1] += A[p]
        A = np.delete(A,p)
        NN -= 1

    B = np.zeros(5)

    B[0] = A[0] + 3*A[1] + 2*A[2] + 3*A[3] + A[4]
    B[1] = A[0] + 4*A[1] + 3*A[2] + 2*A[3] + A[4]
    B[2] = A[0] + 2*A[1] + 5*A[2] + 3*A[3] + A[4]
    B[3] = A[0] + 3*A[1] + 5*A[2] + 2*A[3] + A[4]
    B[4] = A[0] + 2*A[1] + 3*A[2] + 4*A[3] + A[4]
        
    print(int(np.min(B)))

else:
    for n in range(N-2):
        m = np.min(A[1:NN-1])
        sum3i = np.max(A)*3+1
        p = np.argmin(A[1:NN-1])
        p += 1
        dd = min([NN-p+1, p])

        for i in range(1,NN-1):
            if A[i] == m:
                sum3 = A[i-1] + A[i+1]
                if sum3 < sum3i:
                    sum3i = sum3
                    p = i
                elif sum3 == sum3i:
                    d = min([NN-i-1, i])
                    if d < dd:
                        dd = d
                        p = i

        #print(A[1:NN-1])
        #p = np.argmin(A[1:NN-1])
        #p = int(p+1)
        A[p-1] += A[p]
        A[p+1] += A[p]
        A = np.delete(A,p)
        NN -= 1

    print(np.sum(A))

Submission status: Wrong Answer

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

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

B = A[1:-1]
N_B = N-2
# 現時点の総和
dp = [float('inf')]*(1 << N_B)
dp[0] = 0

for mask in range(1 << N_B):
    for new_card in range(N_B):  # 次に食べるカード
        if mask >> new_card & 1:
            continue
        new_state = mask | 1 << new_card
        # calc add
        if new_card == 0:
            left = 0
        else:
            # leftは含む
            left = new_card
            while left > 0:
                if mask >> (left-1) & 1:
                    left -= 1
                else:
                    break
        if new_card == N_B-1:
            # rightは含む
            right = N_B-1
        else:
            right = new_card
            while new_card < N_B-1:
                if mask >> (right+1) & 1:
                    right += 1
                else:
                    break
        # 累積和でとる
        add = 0
        for i in range(left, right+1):
            add += B[i]

        dp[new_state] = min(dp[new_state], dp[mask] + add)

print(dp[-1]+sum(A))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 100000000000
for i in range(2**(N-2)):
    a = A[:]
    binary = format(i, "016b")
    binary = binary[(18-N):]
    for j in range(len(binary)):
        if binary[j] == "0":
            a[0] += a[1]
            a[2] += a[1]
            a.pop(1)
        else:
            a[-1] += a[-2]
            a[-3] += a[-2]
            a.pop(-2)
    ans = min(ans, sum(a))

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
if n==2:print(sum(l));exit()
else: pass

list=[[1,1]]

for j in range(n-2):
    newlist=[]
    for L in list:
        for i in range(j+1):
            if L[:i+1]+[sum(L[i:i+2])]+L[i+1:] in newlist:pass
            else: newlist.append(L[:i+1]+[sum(L[i:i+2])]+L[i+1:])
    list=newlist

print(list)

mi=[]

for m in list:
    mi.append(sum([l[i]*m[i] for i in range(n)]))

print(min(mi))

Submission status: Wrong Answer

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

print ("a= {}".format(a))
if N == 2:
    print(a[0]+a[1])
    sys.exit()

for i in range(N-2):
    addval = min(a[1:-1])
    addidx = a.index(addval)
    a.remove(addval)
    a[addidx-1]+=addval
    a[addidx]+=addval
print(a[0]+a[1])

Submission status: Wrong Answer

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

while len(A) > 2:
    ans = [(i, a+c+b+b) for i, (a, b, c) in enumerate(zip(A[:-2], A[1:-1], A[2:]))]
    m = ans[0][1]
    i = ans[0][0]
    for a in ans[1:]:
        if a[1] < m:
            m = a[1]
            i = a[0]
    A = A[:i] + [A[i]+A[i+1], A[i+2]+A[i+1]] + A[i+3:]
print(A[0] + A[1])

Submission status: Wrong Answer

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

ans = sum(a)
for i in range(n-2):
    m = len(a)
    mina = min(a[1:m-1])
    mind = a.index(mina)
    a[mind-1] += mina
    a[mind+1] += mina
    del a[mind]
print(sum(a))

Submission status: Wrong Answer

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

for x in range(0,N-2):
    B=A[1:-1]
    Y=len(B)//2
    for y in range(0,len(B)):
        if min(B)==B[y]:
            if (len(B)//2-y)**2>(len(B)//2-Y)**2:
                Y=y
    print(A)
    print(B)
    print(Y)
    A=A[0:Y+1]+A[Y+2:N]
    A[Y]=A[Y]+B[Y]
    A[Y+1]=A[Y+1]+B[Y]
print(A[0]+A[1])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
for _ in range(n-2):
  sub = a[1:-1]
  for i in range(1, len(sub)-1):
    sub[i] *= 2
  idx = sub.index(min(sub))+1
  a[idx-1] += a[idx]
  a[idx+1] += a[idx]
  del a[idx]
print(a[0]+a[-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
while len(a_list) > 2:

    a_list2 = a_list[1:-1]
    index_num = a_list2.index(min(a_list2)) + 1

    a_list[index_num - 1] = a_list[index_num - 1] + min(a_list2)
    a_list[index_num + 1] = a_list[index_num + 1] + min(a_list2)
    del a_list[index_num]
print(sum(a_list))

Submission status: Wrong Answer

Solution code:
import sys

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

if N == 2:
  print(a[0] + a[1])
  sys.exit()


for i in range(N - 2):
  cen_a = a[1:N - 1 - i]
  sor_a = sorted(cen_a)
  eat = sor_a[0]
  pos = cen_a.index(eat)

  a[pos] = a[pos] + eat
  a[pos + 2] = a[pos + 2] + eat

  del a[pos + 1]
  
print(a[0] + a[1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N=int(input())
A=list(map(int,input().split()))

def eat(listA):
    i=min(listA[1:len(listA)-1])
    j=listA[1:len(listA)-1].index(i)+1
    if len(A)>=5 and listA[1]<i*2:
        i=listA[1]
        j=1
    elif len(A)>=5 and listA[-3]<i*2:
        i=listA[-3]
        j=-3
    listA[j-1]=listA[j-1]+i
    listA[j+1]=listA[j+1]+i
    del listA[j]
    return listA

while len(A)>=3:
    eat(A)

print(sum(A))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
AtCoder A
"""

import sys, math, random
import numpy as np

# N = int(input())
# A = list(map(int,input().split())) # N row 1 column
# A = [int(input()) for _ in range(N)] # 1 row N column
# S = str(input()) # str(input()) == input() -> 'abc'
# S = list(input()) # abc -> ['a','b','c']
# S.replace('ABC','X') # "testABCABC" -> "testXX"

inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


# def main():
#     N=I()
#     A= list(map(int,input().split()))
#     A=np.asarray(A)
#     while len(A)>2:
#         print(A)
#         i=np.argmin(A[1:len(A)-1])
#         i=i+1
#         print(i)
#         A[i-1]+=A[i]
#         A[i+1]+=A[i]
#         A=np.delete(A,i)
#     print(A[0]+A[1])
    # print(A,B)


def main():
    N=I()
    a= list(map(int,input().split()))
    A=np.asarray(a)
    B=np.asarray(a)
    while len(A)>2:
        # print(A)
        b=np.argmin(B[1:len(B)-1])
        a=np.argmin(A[1:len(A)-1])
        if B[b+1]<A[a+1]:
            i=b+1
        else:
            i=a+1
        # i=i+1
        # print(i)
        A[i-1]+=A[i]
        A[i+1]+=A[i]
        A=np.delete(A,i)
        B=np.delete(B,i)

    print(A[0]+A[1])
    # print(A,B)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools

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

all_ai = list(itertools.permutations(ais, len(ais)))
all_result = []

for each_ai in all_ai:
  ai = list(each_ai)
  while len(ai) > 2:
    ai[0] += ai[1]
    ai[2] += ai[1]
    ai.pop(1)
  all_result.append(ai[0]+ai[1])
print(min(all_result))

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
while len(a_list) > 2:

    a_list2 = a_list[1:-1]
    index_num = a_list2.index(min(a_list2)) + 1

    a_list[index_num - 1] = a_list[index_num - 1] + min(a_list2)
    a_list[index_num + 1] = a_list[index_num + 1] + min(a_list2)
    del a_list[index_num]
#print(a_list)
print(sum(a_list))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
for i in range(n-2):
  x = min(a[1:-1])
  y = a[1:-1].index(x)+1
  a[y-1] += x
  a[y+1] += x
  a.pop(y)
print(sum(a))

Submission status: Wrong Answer

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

for j in range(N-2):
    min_tmp = A[1]
    count = 1
    for i in range(1, N-j-1):
        if A[i] < min_tmp:
            min_tmp = A[i]
            count = i
    A[count-1] += A[count]
    A[count+1] += A[count]
    A.pop(count)

print(A[0]+A[1])