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: Time Limit Exceeded

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

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

answer = 10 ** 18

def dfs(arr, can_select_first,to_right,to_left, erased = 0):
    global answer
    # ある元を選ばないなら、状況が変わるまで禁止
    i = can_select_first
    if erased == N - 2:
        x = arr[i]
        j = to_left[i]
        if j is not None:
            x += arr[j]
        else:
            x += arr[to_right[i]]
        if answer > x:
            answer = x
        return
    while True:
        R = to_right[i]
        L = to_left[i]
        if L is None:
            i = R
            continue
        if R is None:
            break
        # i番目を選ぶ
        add = arr[i]
        arr[L] += add
        arr[R] += add
        arr[i] = None
        trL = to_right[L]
        tlR = to_left[R]
        to_right[L] = R
        to_left[R] = L
        can = R if to_left[L] is None else to_left[L]
        dfs(arr, can, to_right, to_left, erased + 1)
        # 戻す
        arr[L] -= add
        arr[R] -= add
        arr[i] = add
        to_right[L] = trL
        to_left[R] = tlR
        i = R

dfs(A, 1, list(range(1,N)) + [None], [None] + list(range(N-1)))

print(answer)

Submission status: Time Limit Exceeded

Solution code:

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

def eat(list_i:list):
    global rtn
    lll = len(list_i)
    if (lll == 2):
        www = list_i[0] + list_i[1]
        if ((rtn == -1) or (rtn > www)):
            rtn = www
    else:
        if ((rtn == -1) or (sum(list_i) < rtn)):
            for iii in range(1 , lll - 1):
                list_n = list_i.copy()

                vvv = list_n.pop(iii)
                list_n[iii - 1] += vvv
                list_n[iii] += vvv

                #print(list_n)

                eat(list_n)

eat(a)
print(rtn)

Submission status: Time Limit Exceeded

Solution code:
import copy

result = []

def Add_and_Remove(lis):
    if (len(lis) == 2):
        result.append(lis[0] +lis[1])

    for i in range(len(lis)-2):
        li_tmp = copy.copy(lis)
        #print(li_tmp)
        li_tmp[i] += li_tmp[i+1]
        li_tmp[i+2] += li_tmp[i+1]
        li_tmp.pop( i + 1 )
        #print(li_tmp)
        Add_and_Remove(li_tmp)
        

if __name__ == '__main__':
    a=int(input())
    li = list(map(int,input().split()))

    Add_and_Remove(li)
    print(min(result))

Submission status: Time Limit Exceeded

Solution code:

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

def eat(list_i:list):
    global rtn
    lll = len(list_i)
    if (lll == 2):
        www = list_i[0] + list_i[1]
        if ((rtn == -1) or (rtn > www)):
            rtn = www
    else:
        for iii in range(1,lll-1):
                list_n = list_i.copy()

                vvv = list_n.pop(iii)
                list_n[iii - 1] += vvv
                list_n[iii] += vvv

                #print(list_n)

                eat(list_n)

eat(a)
print(rtn)

Submission status: Time Limit Exceeded

Solution code:
import copy

n = int(input())
a_list = list(map(int, input().split()))
result_list = []

def calc(hoge):
    if len(hoge) == 2:
        result_list.append(hoge[0] + hoge[1])
        return 0
    for i in range(len(hoge)-2):
        hoge2 = copy.deepcopy(hoge)
        hoge3 = hoge2.pop(i+1)
        hoge2[i] = hoge2[i] + hoge3
        hoge2[i+1] = hoge2[i+1] + hoge3
        calc(hoge2)

calc(a_list)
print(min(result_list))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[int(i) for i in input().split()]


def rec():
    global opps
    global sum
    if len(l)==2:
        if sum<opps:
            opps=sum
    else:
        for i in range(1,len(l)-1):
            if sum+l[i]<opps:
                acc=l[i]
                l[i-1]+=l[i]
                sum+=l[i]
                l[i+1]+=l[i]
                del l[i]
                #print(l,sum)
                rec()
                l.insert(i,acc)
                l[i-1]-=l[i]
                sum-=l[i]
                l[i+1]-=l[i]
                #print(l,sum)
opps=pow(10,18)
sum=0
for a in l:
    sum+=a

rec()
print(opps)

Submission status: Time Limit Exceeded

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

minV = 1000000000 * 18

def modify(array, idx):
    if len(array) == 2:
        return array

    new = list(array)
    new[idx-1] += new[idx]
    new[idx+1] += new[idx]
    del new[idx]

    return new

def solve(array):
    global minV
    if len(array) == 2:
        return array[0] + array[1]
    else:
        for i in range(1, len(array)-1):
            new = modify(array, i)
            temp = solve(new)
            if temp < minV:
                minV = temp

        return minV

#        array = modify(array, 1...len(array)-1)


print(solve(a))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5)
N = int(input())
A = list(map(int, input().split()))

# if N == 2:
#     print (A[0] + A[1])
#     exit()
# if N == 3:
#     print (A[0] + 2 * A[1] + A[2])
#     exit()

def dfs(lst):
    if len(lst) == 2:
        return lst[0] + lst[1]
    for i in range(1, len(lst)-1):
        tmp_lst = lst[:i-1] + [lst[i-1] + lst[i], lst[i] + lst[i + 1]] + lst[i+2:]
        if i == 1:
            tmp = dfs(tmp_lst)
        else:
            tmp = min(tmp, dfs(tmp_lst))
    return tmp

print (dfs(A))

Submission status: Accepted

Solution code:

"""

https://atcoder.jp/contests/agc035/tasks/agc035_d

毎回1枚カードが減り、寄与が2倍になる
両端のカードは消せない → 寄与は1倍のまま

端から2枚目のカードしか選ばなくていいみたいなの無いかな？
端から2枚目を選ぶと、1つは端の寄与になり、もう一つは動の寄与になる
つまり、動の寄与の総和は変化しない
そうでないのを選ぶと、動の寄与に2倍かかる

→ 2**18 になっていい感じのオーダーにはなる

検証：
5枚で真ん中を最初に選ぶべきなのを作れるか？
0,X,Y,Z,0
0,X+Y,Y+Z,0
0,X+2Y+Z,Y+Z
X+2Y+Z,X+3Y+2Z
→2X+3Y+3Z or 3X+3Y+2Z (真ん中を選んだ場合)

0,X,Y,Z,0
X,X+Y,Z,0 → X,X+Y+Z,Z → 2X+Y+Z,X+Y+2Z → 3X+2Y+3Z
2X+Y,X+Y+Z,0 → 3X+2Y+Z,X+Y+Z → 4X+3Y+2Z

すなわち、真ん中を選んだ方がいい場合もある…
最後まで残した数は2倍だけの寄与で済む
最後まで残す数を決め打ちする？
最後の数で左右を分ける
→さらにその区間で最後に残すやつは3倍の寄与で済む

1 4 3 5 2 5 3 4 1
→こんな感じ

あとは分割統治で、
ある点で区切った場合の左右の最小を足して上に返せばよい
計算量は？
長さ1の場合1
2の場合 1+1 = 2
3の場合 2+1+1+2 = 6
4の場合 6+

dp[0] = 0
dp[1] = 1
dp[n] = 2*(dp[n-1]+dp[n-2]…+dp[0])
dp[16] = 9565938 なので十分可能

"""

from sys import stdin

def want(l,r,lb,rb):
    if l > r:
        return 0
    elif l == r:
        return A[l] * (lb+rb)
    
    nmin = float("inf")
    for i in range(l,r+1):
        nmin = min(nmin , A[i]*(lb+rb) + want(l,i-1,lb,lb+rb) + want(i+1,r,lb+rb,rb) )
    return nmin
    

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

print (A[0] + A[-1] + want(1,N-2,1,1) )

Submission status: Accepted

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

memo={}
def dp(i,j,L,R):
    if (i,j,L,R) in memo:
        return memo[(i,j,L,R)]
    if i==j:
        memo[(i,j,L,R)]=0
        memo[(i,j,L,R)]=(L+R)*A[i]
        return (L+R)*A[i]
    elif i>j:
        return 0

    ans=10**18
    for k in range(i,j+1):
        test=dp(i,k-1,L,L+R)+dp(k+1,j,L+R,R)+A[k]*(L+R)
        ans=min(ans,test)

    memo[(i,j,L,R)]=0
    memo[(i,j,L,R)]=ans
    return ans

res=dp(1,N-2,1,1)
print(res+A[0]+A[-1])

Submission status: Accepted

Solution code:
from functools import lru_cache
 
N = int(input())
A = list(map(int, input().split()))
 
@lru_cache(None)
def f(l, r, xl, xr):
  if l+1 == r:
    return xl * A[l] + xr * A[r]
  tmp = float("inf")
  for m in range(l+1, r):
    v = f(l, m, xl, xl+xr) + f(m, r, xl+xr, xr) - (xl+xr) * A[m]
    tmp = min(tmp, v)
  return tmp
 
print(f(0, N-1, 1, 1))

Submission status: Accepted

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**11
    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: Accepted

Solution code:
# ikatakosさんの提出を見てlru_cacheなるものを知った。
# まだまだ知らないことがたくさんありますね。

from functools import lru_cache

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

@lru_cache(maxsize=None)
def rec(l, r, xl, xr) :
    if l + 1 == r :
        return 0
    
    return min(rec(l, m, xl, xl+xr)+rec(m, r, xl+xr, xr)+A[m]*(xl+xr) for m in range(l+1, r))
    
print(A[0] + rec(0, N-1, 1, 1) + A[N-1])

Submission status: Accepted

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

@lru_cache(maxsize=None)
def dfs(l, r, wl, wr):
    if r <= l + 1:
        return 0
    v = min(dfs(l, m, wl, wl+wr) + dfs(m, r, wl+wr, wr) + A[m] * (wl+wr) for m in range(l+1, r))
    return v

print(dfs(0, N-1, 1, 1) + A[0] + A[N-1])

Submission status: Accepted

Solution code:
from functools import lru_cache


def solve(n, aaa):
    @lru_cache(maxsize=None)
    def search_min(li, ri, lc, rc):
        w = ri - li
        if w == 1:
            return 0
        lrc = lc + rc
        if w == 2:
            return aaa[li + 1] * lrc
        if w == 3:
            a1, a2 = aaa[li + 1], aaa[li + 2]
            return (a1 + a2) * lrc + min(a1 * lc, a2 * rc)
        ret = min(aaa[i] * lrc + search_min(li, i, lc, lrc) + search_min(i, ri, lrc, rc) for i in range(li + 1, ri))
        return ret

    return search_min(0, n - 1, 1, 1) + aaa[0] + aaa[-1]


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

Submission status: Accepted

Solution code:
from functools import lru_cache


def solve(n, aaa):
    @lru_cache(maxsize=None)
    def search_min(li, ri, lc, rc):
        w = ri - li
        base = aaa[li] * lc
        if w == 1:
            return base
        lrc = lc + rc
        if w == 2:
            return base + aaa[li + 1] * lrc
        if w == 3:
            a1, a2 = aaa[li + 1], aaa[li + 2]
            return base + (a1 + a2) * lrc + min(a1 * lc, a2 * rc)
        ret = min(search_min(li, i, lc, lrc) + search_min(i, ri, lrc, rc) for i in range(li + 1, ri))
        return ret

    return search_min(0, n - 1, 1, 1) + aaa[-1]


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

Submission status: Accepted

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=None)
def f(x, y, l, r):
    if r - l + 1 <= 2:
        return 0
    return min(a[i] * (x + y) + f(x, x + y, l, i) + f(x + y, y, i, r) for i in range(l + 1 , r))

print(a[0] + a[-1] + f(1, 1, 0, n - 1))

Submission status: Runtime Error

Solution code:
/****************************************************************
*	Author: huhao
*	Email: 826538400@qq.com
*	Create time: 2020-02-02 09:45:14
****************************************************************/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define fr(i,a,b) for(int i=(a),end_##i=(b);i<=end_##i;i++)
#define fd(i,a,b) for(int i=(a),end_##i=(b);i>=end_##i;i--)
int read()
{
	int r=0,t=1,c=getchar();
	while(c<'0'||c>'9')
	{
		t=c=='-'?-1:1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		r=(r<<3)+(r<<1)+(c^48);
		c=getchar();
	}
	return r*t;
}
#define i64 long long
#include<map>
#define mp(a,b,c,d) std::make_pair(std::make_pair(a,b),std::make_pair(c,d))
const int N=20,M=666;
const i64 inf=1ll<<60;
i64 f[N][N][M][M];
i64 n,a[N];
std::map<std::pair<std::pair<int,int>,std::pair<i64,i64> >,i64> F;
i64 solve(int l,int r,i64 cl,i64 cr)
{
	if(l==r-1) return 0;
	if(cl<M&&cr<M){ if(f[l][r][cl][cr]!=-1) return f[l][r][cl][cr]; }
	else{ if(F.count(mp(l,r,cl,cr))) return F[mp(l,r,cl,cr)]; }
	i64 ans=inf;
	fr(i,l+1,r-1) ans=std::min(ans,solve(l,i,cl,cl+cr)+solve(i,r,cl+cr,cr)+(cl+cr)*a[i]);
	if(cl<M&&cr<M) return f[l][r][cl][cr]=ans;
	else return F[mp(l,r,cl,cr)]=ans;
}
int main()
{
	n=read();
	fr(i,1,n) fr(j,i,n) fr(k,0,M-1) fr(l,0,M-1) f[i][j][k][l]=-1;
	fr(i,1,n) a[i]=read();
	printf("%lld\n",solve(1,n,1,1)+a[1]+a[n]);
	return 0;
}

Submission status: Runtime Error

Solution code:
#include <stdio.h>
#include <iostream>
using namespace std;

int N;
int A[18];

long long rec(int l, int r, long long xl, long long xr) {
    if (r - l == 1) {
        return 0;
    }
    
    long long ret = (long long) 1e18;
    for (int i = l + 1; i < r; i++) {
        long long tmp = A[i] * (xl+xr) + rec(l, i, xl, xl+xr) + rec(i, r, xl+xr, xr);
        ret = min(ret, tmp);
    }
    return ret;
}

int main() {    
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    
    cout << rec(0, N - 1, 1, 1) + A[0] + A[N - 1];
    
}

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())

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

def kansu(a = [1, 1], X=[]):
    min_number = 10**9
    for i in range(len(a)-1):
        aa = a[:i+1] + [(a[i]+a[i+1])] + a[i+1:]
        if len(aa) == N:
            X.append((A*np.array(aa)).sum())
        else:
            kansu(aa, X)
    return (min(X))

print(kansu())

Submission status: Runtime Error

Solution code:
import queue

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

_queue = queue.Queue()

_queue.put(a_list)


ans=100000000000000000000000000000000000000000000

while not _queue.empty():

  a_list = _queue.get()
  changeable_list=a_list[1:-1]
  target=min(changeable_list)

  inde=[i for i, x in enumerate(changeable_list) if x == target]
  
  for i in inde:
    ind=i+1
  
    #print(a_list[:ind-1])

    bef=[a_list[ind-1]+a_list[ind]]
    #print(bef)
    #print("ind",ind)
    aft=[a_list[ind+1]+a_list[ind]]
    #print(aft)

    #print(a_list[ind+2:])

    new_a_list=a_list[:ind-1]+bef+aft+a_list[ind+2:]
    
    if len(new_a_list)==2:
      koho=sum(new_a_list)
      ans=min(ans,koho)
    else:
      _queue.put(new_a_list)   
      #print(new_a_list)

    
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
sys.setrecursionlimit(200000)
# local only
# if not __debug__:
#     fin = open('in_1.txt', 'r')
#     sys.stdin = fin
# local only
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

def sub(A):
    if len(A) == 2:
        return sum(A)
    if len(A) == 3:
        return [1]
    if len(A) == 4:
        if calculate(A, [2, 1]) < calculate(A, [1, 1]):
            return [2, 1]
        else:
            return [1, 1]
    # if len(A) == 4:
    #     return min(A[0] + 2 * A[1] + 3 * A[2] + A[3], A[0] + 3 * A[1] + 2 * A[2] + A[3])
    if len(A) > 4:
        x = A.index(min(A[2:len(A) - 2]))
        if A[1] < A[-2]:
            y = 1
        else:
            y = len(A) - 2
    X = deepcopy(A)
    Y = deepcopy(A)
    tx = X.pop(x)
    ty = Y.pop(y)
    ax = calculate(A, [x] + sub(X))
    ay = calculate(A, [y] + sub(Y))
    if ax < ay:
        return [x] + sub(X)
    else:
        return [y] + sub(Y)

def calculate(A, ans):
    # debug(A, ans)
    A = deepcopy(A)
    for i in ans:
        x = A.pop(i)
        A[i - 1] += x
        A[i] += x
    # debug(A)
    return sum(A)

def main():
    N = ii()
    A = lmi()
    print(calculate(A, sub(A)))





if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import copy

result = []

def Add_and_Remove(lis):
    if (len(lis) == 2):
        result.append(lis[0] +lis[1])
    else :
        minmum = 999
        mat = []
        for i in range(1,len(lis)-1):
            if lis[i] <= minmum :
                minmum = lis[i] 
                mat.append([minmum,i])

        mat.sort()

        li_tmp = copy.copy(lis)
        #print(li_tmp)
        #print("最小値",minmum,label)
        label = []
        label.append(mat[0][1])

        for j in range(1,len(mat)):
            if mat[j][0] == mat[0][0]:
                label.append(mat[j][1])
            else :
                break

        for j in range(len(label)):
            li_tmp[label[j] - 1] += li_tmp[label[j]]
            li_tmp[label[j] + 1] += li_tmp[label[j]]
            li_tmp.pop(label[j])
            #print(li_tmp)
            Add_and_Remove(li_tmp)
        
        

if __name__ == '__main__':
    a=int(input())
    li = list(map(int,input().split()))

    Add_and_Remove(li)
    print(min(result))

Submission status: Runtime Error

Solution code:
from collections import deque

n = int(input())
a = deque([int(i) for i in input().split()])

while len(a) != 2:
	a_left = a.popleft()
	a_right = a.pop()
	m = min(a)
	min_index = [i for i,x in enumerate(a) if x == min(a)]
	a.append(a_right)
	a.appendleft(a_left)
	tmp = 0
	tmp_index = 0
	for i in min_index:
		if tmp < a[i] + a[i+2]:
			tmp = a[i] + a[i+2]
			tmp_index = i
	b = a.copy()
	a= deque([])
	for i in range(len(b)):
		if i == tmp_index:
			a.append(b[i]+m)
		elif i == tmp_index+2:
			a.append(b[i]+m)
		elif i != tmp_index +1:
			a.append(b[i])

a1 = a.popleft()
a2 = a.popleft()
print(a1+a2)

Submission status: Runtime Error

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)]))
    p = a[k]
    a[k - 1] += p
    a[k + 1] += p
    del a[k]
print(sum(a))

Submission status: Runtime Error

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
  m = min(sub)
  total = 2*10**9
  sub = [0] + sub + [0]
  for i in range(1, len(sub)-1):
    if sub[i] == m:
      t = sub[i-1] + sub[i+1]
      if total > t:
        total = t
        idx = i
  a[idx-1] += a[idx]
  a[idx+1] += a[idx]
  del a[idx]
print(a[0]+a[-1])

Submission status: Runtime Error

Solution code:
import sys

def eat(A, i):
    Ai = A[i]
    A[i-1] += Ai
    A[i+1] += Ai
    A.pop(i)

    if len(A) == 2:
        return sum(A)
    
    output = []
    for x in range(1, len(A)-1):
        _A = A[:]
        output.append(eat(_A, x))

    return min(output)

def main():

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

    _min = min(A[1:-1])
    mi = A[1:-1].index(_min)+1
    ret = eat(A, mi)
    print(ret)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import itertools

def proc(a, b, c):
    return a+b, b+c

def macho(p, i):
    a = p.copy()
    a1, a3 = proc(a.pop(i),a.pop(i),a.pop(i))
    a.insert(i, a3)
    a.insert(i, a1)
    #print(a, len(a))
    if len(a) is 2:
        #print("sum: ", a, sum(a))
        return sum(a)
    else:
        for iter in range(0, len(a)-2):
            return macho(a, iter)

n = int(input())
a = list(map(int, input().split()))
result = []    
for i in range(0, n-2):
    result.append(macho(a, i))
print(min(result))

Submission status: Runtime Error

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

while len(A) > 2:
#  print(A)
  lenA = len(A)
  presums = 10**10
  for i in range(lenA-2):
#    sums = A[i] + A[i+1]*2 + A[i+2]
    sums = A[i+1]
    if presums > sums:
      presums = sums
      prei = i
  A[prei] += A[prei+1]
  A[prei+2] += A[prei+1]
  A.pop(prei+1)
#print(A)
print(sum(A))

Submission status: Runtime Error

Solution code:
import copy
n = int(input())
line = list(map(int,input().split()))

def q(line):
  idx = idx_s(line)
  line[idx - 1] += line[idx]
  line[idx + 1] += line[idx]
  line.remove(line[idx])
  return line

def q_(line):
  idx = idx_s_(line)
  line[idx - 1] += line[idx]
  line[idx + 1] += line[idx]
  line.remove(line[idx])
  return line

def idx_s_(line):
  # 最も小さい数を探す
  c = 10000000
  for i in range(len(line)-2):
    a = line[i] +line[i+1]
    b = line[i+2] +line[i+1]
    if c > a + b:
      c = a + b
      idx = i + 1
    
  return idx

def idx_s(line):
  # 最も小さい数を探す
    
  line2 = copy.copy(line)
  line2.pop()
  line2.pop(0)
  idx = line2.index(min(line2))
  idx += 1
  return idx

if n > 6:
  for i in range(int(n - 5)):
    line = q(line)
if n > 2:
  for i in range(n  - 2):
    line = q_(line)  
  
print(line[0] + line[1])

Submission status: Runtime Error

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

for i in range(n-2):
    mina = 10 ** 9 + 1
    if len(a) > 4:
        for j in range(n-4-i):
            if a[j+2] < mina:
                mina = a[j+2]
                p = j+2

    if min(a[1], a[len(a)-2], 2 * mina) == a[1]:
        a[0] += a[1]
        a[2] += a[1]
        del a[1]
    elif min(a[1], a[len(a)-2], 2 * mina) == a[len(a)-2]:
        a[len(a)-3] += a[len(a)-2]
        a[len(a)-1] += a[len(a)-2]
        del a[len(a)-2]
    else:
        a[p-1] += a[p]
        a[p+1] += a[p]
        del a[p]


print(sum(a))

Submission status: Runtime Error

Solution code:
from collections import deque

N = int(input())
ai = [int(x) for x in input().split()]
queue = deque([ai])
log = []
while queue:
  ai = queue.popleft()
  ind = [i for i, v in enumerate(ai[1:-1]) if v <= min(ai[1:-1])+1]
  #ind = list(range(1,len(ai)-1))
  for index in ind:
    pi = ai[:]
    pi[index-1] += pi[index]
    pi[index+1] += pi[index]
    si = pi[0:index]
    si.extend(pi[index+1:])
    if len(si)==2:
      log.append(sum(si))
    else:
      queue.append(si)
#print(min([sum(i) for i in log]))
print(min(log))

Submission status: Runtime Error

Solution code:
import copy
n = int(input())
line = list(map(int,input().split()))

def q(line):
  idx = idx_s(line)
  line[idx - 1] += line[idx]
  line[idx + 1] += line[idx]
  line.remove(line[idx])
  return line

def q_(line):
  idx = idx_s_(line)
  line[idx - 1] += line[idx]
  line[idx + 1] += line[idx]
  line.remove(line[idx])
  return line

def idx_s_(line):
  # 最も小さい数を探す
  c = 10000000
  for i in range(len(line)-2):
    a = line[i] +line[i+1]
    b = line[i+2] +line[i+1]
    if c > a + b:
      c = a + b
      idx = i + 1
    
  return idx

def idx_s(line):
  # 最も小さい数を探す
    
  line2 = copy.copy(line)
  line2.pop()
  line2.pop(0)
  idx = line2.index(min(line2))
  idx += 1
  return idx


for i in range(int(n - 5)):
  line = q(line)

line = q_(line)  
line = q_(line)  
line = q_(line)  
  
print(line[0] + line[1])

Submission status: Runtime Error

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

for i in range(N - 2):
  cen_a = a[1:N - 1]
  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: Runtime Error

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.pop(y)
  a[y-1] += x
  a[y+1] += x
print(sum(a))

Submission status: Runtime Error

Solution code:
from collections import deque

N = int(input())
ai = [int(x) for x in input().split()]
queue = deque([ai])
log = []
while queue:
  ai = queue.popleft()

  ind = list(range(1,len(ai)-1))
  for index in ind:
    pi = ai[:]
    pi[index-1] += pi[index]
    pi[index+1] += pi[index]
    si = pi[0:index]
    si.extend(pi[index+1:])
    if len(si)==2:
      log.append(si)
    else:
      queue.append(si)
print(min([sum(i) for i in log]))

Submission status: Runtime Error

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

def q(line):
  idx = idx_s(line)
  line[idx - 1] += line[idx]
  line[idx + 1] += line[idx]
  line.remove(line[idx])
  return line

def idx_s(line):
  c = 10000000
  for i in range(len(line)-2):
    a = line[i] +line[i+1]
    b = line[i+2] +line[i+1]
    if c > a + b:
      c = a + b
      idx = i + 1
    
  return idx


for i in range(int(n - 2)):
  line = q(line)

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

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int, input().split()))
INF=10**9+1
B=A[:]
B[0]=INF
B[-1]=INF

for i in range(N-2):
    min_value=min(B)
    min_index=B.index(min_value)
    A[min_index-1]+=min_value
    A[min_index+1]+=min_value
    B[min_index-1]+=min_value
    B[min_index+1]+=min_value
    A.pop(min_index)
    B.pop(min_index)
    
print(A[0]+A[1])

Submission status: Runtime Error

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

while len(A) != 2:
  min_sum = 10**10
  for i in range(1, len(A)-1):
    if sum(A[i-1:i+2]) + A[i] < min_sum:
      A_index = i
      min_sum = sum(A[i-1:i+2]) + A[i]
  A[A_index-1] += A[A_index]
  A[A_index+1] += A[A_index]
  del A[A_index]
  
print(sum(A))

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int, input().rstrip().split(' ')))
while len(a)>2:
  print(c)
  print(a)
  ix,v=sorted(enumerate(a[1:-1]),key=lambda x:x[1])[0]
  del a[ix+1]
  a[ix]+=v
  a[ix+1]+=v
print(sum(a))

Submission status: Runtime Error

Solution code:
import numpy as np

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

for n in range(N-4):
    i_ = np.argmin([A[1]]+[m*2 for m in A[2:-2]]+[A[-1]])
    i = i_ + 1
    A[i-1] = A[i-1] + A[i]
    A[i+1] = A[i+1] + A[i]
    A.pop(i)

for _ in range(2):
  i_ = np.argmin(A[1:-1])
  i = i_ + 1
  A[i-1] = A[i-1] + A[i]
  A[i+1] = A[i+1] + A[i]
  A.pop(i)

print(sum(A))

Submission status: Runtime Error

Solution code:
n=int(input())
l=[int(i) for i in raw_input().split()]


def rec():
    global opps
    global sum
    if len(l)==2:
        if sum<opps:
            opps=sum
    else:
        for i in range(1,len(l)-1):
            if sum+l[i]<opps:
                acc=l[i]
                l[i-1]+=l[i]
                sum+=l[i]
                l[i+1]+=l[i]
                del l[i]
                #print(l,sum)
                rec()
                l.insert(i,acc)
                l[i-1]-=l[i]
                sum-=l[i]
                l[i+1]-=l[i]
                #print(l,sum)
opps=pow(10,18)
sum=0
for a in l:
    sum+=a

rec()
print(opps)