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:
# -*- 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)
        i=np.argmin(B[1:len(B)-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:
# coding: utf-8

n = int(input())

Ax = list(map(int, input().split()))

while len(Ax) > 2:
    inner = Ax[1: len(Ax)-1]
    target = min(inner)
    i = inner.index(target) + 1
    Ax[i-1] += Ax[i]
    Ax[i+1] += Ax[i]
    Ax.pop(i)

print(sum(Ax))

Submission status: Wrong Answer

Solution code:
N = int(input())

nums = list(map(int, input().split()))

while len(nums) != 2:
    min_num = min(nums[1:len(nums)-1])
    #print(len(nums), nums)
    #print("minimum", min_num)
    
    del_index = []
    
    for j in range(1, len(nums)-1):
        if nums[j] == min_num:
            nums[j-1] += min_num
            nums[j+1] += min_num
            del_index.append(j)
            
    for k in range(len(del_index)):
        del nums[del_index[len(del_index)-k-1]]

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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


while(len(a)>2):
  min_idx = np.argmin(a[1:-1])+1
  #print(a[min_idx])

  a1 = a[:min_idx]
  a2 = a[(min_idx+1):]
  a1[-1]+=a[min_idx]
  a2[0]+=a[min_idx]
  a = a1 + a2
  #print(a)
  
print(sum(a))

Submission status: Wrong Answer

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]
    elif sum(array) > minV:
        return minV
    else:
        for i in range(1, len(array)-1):
            new = modify(array, i)
            temp = solve(new)
            if temp < minV:
                minV = temp

        return minV

print(solve(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()))
# 現時点の総和
dp = [float('inf')]*(1 << N)
dp[0] = sum(A)

for mask in range(1 << N):
    if mask & 1 == 1 or mask & 1 << N == 1:  # 端っこのカードは食べない
        continue
    for new_card in range(1, N-1):  # 次に食べるカード
        if mask >> new_card & 1:
            continue
        new_state = mask | 1 << new_card
        # calc add
        add = 0
        left = new_card-1
        while left > 0:
            # 累積和かなんかで早くなりそう
            if mask >> left & 1:
                add += A[left]
                left -= 1
            else:
                break
        right = new_card+1
        while right < N-1:
            if mask >> right & 1:
                add += A[right]
                right += 1
            else:
                break

        dp[new_state] = min(dp[new_state], dp[mask] + add +
                            A[new_card])  # addは今回食べるカードの値


print(dp[(1 << N-1)-2])

Submission status: Wrong Answer

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

# n=6
# # A=[3,1,4,1,5,9,2,6,5,3]
# A=[5,2,4,1,6,9]
while n!=2:
    if A.count(min(A))==1:
        #最小値が一番上か下の場合
        if A.index(min(A))==0 or A.index(min(A))==n-1:
           B=sorted(A)
           #2番目に小さい数も一番上か一番下の場合
           if B[1]==A[0] or B[1]==A[n-1]:
              # B=heapq.nsmallest(3,A)
              l=A.index(B[2])
              A[l-1]=A[l-1]+B[2]
              A[l+1]=A[l+1]+B[2]
              del A[l]
              n=n-1
           #2番目に小さい数がデッキの中
           else:
              l=A.index(B[1])
              A[l - 1] = A[l - 1] + B[1]
              A[l + 1] = A[l + 1] + B[1]
              del A[l]
              n = n - 1
        #最小値がデッキの中
        else:
            l = A.index(min(A))
            A[l - 1] = A[l - 1] + min(A)
            A[l + 1] = A[l + 1] + min(A)
            del A[l]
            n = n - 1
    elif A.count(min(A))==2:
        C=sorted(A)
        if C[0]==A[0] and C[1]==A[n-1]:
           l=A.index(C[2])
           A[l - 1] = A[l - 1] + C[2]
           A[l + 1] = A[l + 1] + C[2]
           del A[l]
           n = n - 1
        elif C[0]==A[0]:
            for i in range(1,n):
                if C[0]==A[i]:
                    l=i
                    A[l - 1] = A[l - 1] + C[0]
                    A[l + 1] = A[l + 1] + C[0]
                    del A[l]
                    n = n - 1
                    break
        elif C[0]==A[n-1]:
            for i in range(0,n-1):
                if C[0]==A[i]:
                    l=i
                    A[l - 1] = A[l - 1] + C[0]
                    A[l + 1] = A[l + 1] + C[0]
                    del A[l]
                    n = n - 1
                    break
        else:
            for i in range(0,n):
                if C[0]==A[i]:
                    l=i
                    A[l - 1] = A[l - 1] + C[0]
                    A[l + 1] = A[l + 1] + C[0]
                    del A[l]
                    n = n - 1
                    break
    else:
        C = sorted(A)
        for i in range(1, n-1):
            if C[0] == A[i]:
                l = i
                A[l - 1] = A[l - 1] + C[0]
                A[l + 1] = A[l + 1] + C[0]
                del A[l]
                n = n - 1
                break
print(A[0]+A[1])

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

N = int(input().strip())
As = list(map(int, input().strip().split(' ')))

for i in range(N - 2):
    target = sorted(As[1:-1])[0]
    index = As[1:-1].index(target)
    index += 1
    if target <= As[0] and target <= As[-1]:
        As[index - 1] += target
        As[index + 1] += target
        As.pop(index)
    else:
        if As[1] < As[-2]:
            As[0] += As[1]
            As[2] += As[1]
            As.pop(1)
        else:
            As[-3] += As[-2]
            As[-1] += As[-2]
            As.pop(-2)
print(sum(As))

Submission status: Wrong Answer

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

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

    while len(a) > 2:
        min_ = min(a[0]+a[1], a[1]+a[2])
        ind = 1
        sub = a[1]
        for i in range(1,len(a)-1):
            tmp = min(a[i-1] + a[i], a[i] + a[i+1])
            if tmp < min_:
                min_ = tmp
                ind = i
            elif tmp == min_:
                if a[i] < sub:
                    ind = i
                    sub = a[i]
        tmp = a.pop(ind)
        a[ind-1] += tmp
        a[ind] += tmp
    print(sum(a))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# sorry

n = int(input())
orig = [int(x) for x in input().split()]
n = len(orig)

A = orig[:]

while n > 2:
    i = min(range(1,n-1), key=lambda i: A[i])
    a,b,c = A[i-1:i+2]
    A[i-1:i+2] = [a+b, b+c]
    n -= 1

greed = sum(A)

mem = {}

import time,sys
start = time.clock()

best = greed
def f(state, sm):
    global best
    if len(state) == 2:
        if time.clock() - start > 1.75:
            print(best)
            sys.exit()
        if sm < best:
            best = sm
            #print(best)
        return sm
    if sm >= best:
        return sm

    key = tuple(state)
    if key not in mem:
        res = 1000000000000
        I = sorted(range(1,len(state)-1), key=lambda i: state[i])
        for i in I:
            a,b,c = state[i-1:i+2]
            res = min(f(state[:i-1] + [a+b,c+b] + state[i+2:], sm+b), res)
        mem[key] = res
    return mem[key]

f(orig, sum(orig))
print(len(mem))
print(best)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
S = [i for i in map(int, input().split())]

S = np.array(S)
N = len(S)
lim_S = S[1:N-1]
pos = np.argsort(lim_S)
value_pool = S[0] + S[-1]
for i in pos:
    val = lim_S[i]
    absolute_pos = np.where(S == val)[0][0]
    value_pool += val*(len(S)-1)
    S = np.delete(S,absolute_pos)
print(value_pool)

Submission status: Wrong Answer

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

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

    while len(a) > 2:
        min_ = min(a[0]+a[1], a[1]+a[2])
        ind = 1
        sub = a[1]
        for i in range(1,len(a)-1):
            tmp = min(a[i-1] + a[i], a[i] + a[i+1])
            if tmp < min_:
                min_ = tmp
                ind = i
            elif tmp == min_:
                if a[i] < sub:
                    ind = i
        tmp = a.pop(ind)
        a[ind-1] += tmp
        a[ind] += tmp
    print(sum(a))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().rstrip().split(' ')))
while len(a)>2:
  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: Wrong Answer

Solution code:
n = int(input())
l = [int(i) for i in input().split()]
#print(l)
for i in range(n-2):
    s = l[1]
    for j in range(1,n-i-1):
        if s>l[j]:
            s=l[j]
    for k in range(1,n-i-1):
        if l[k]==s:
            l[k-1]+=s
            l[k+1]+=s
            l.remove(s)
            break
    #print(l)
print(l[0]+l[1])

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

N = int(input().strip())
As = list(map(int, input().strip().split(' ')))

for i in range(N - 2):
    target = sorted(As[1:-1])[0]
    index = As.index(target)
    if target < As[0] and target < As[-1]:
        As[index - 1] += target
        As[index + 1] += target
        As.pop(index)
    else:
        if As[1] < As[-2]:
            As[0] += As[1]
            As[2] += As[1]
            As.pop(1)
        else:
            As[-3] += As[-2]
            As[-1] += As[-2]
            As.pop(-2)
print(sum(As))

Submission status: Wrong Answer

Solution code:
n = int(input())
l = [int(i) for i in input().split()]
print(l)
for i in range(n-2):
    s = l[1]
    for j in range(1,n-i-1):
        if s>l[j]:
            s=l[j]
    for k in range(1,n-i-1):
        if l[k]==s:
            l[k-1]+=s
            l[k+1]+=s
            l.remove(s)
            break
    #print(l)
print(l[0]+l[1])

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)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=sorted(map(int,input().split()))
r=a.pop()
for n,i in zip(a,range(n-1,0,-1)):
	r+=n*i
print(r)

Submission status: Wrong Answer

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

for _ in range(n-2):
    i = a[1:-1].index(min(a[1:-1]))+1
    a[i-1] += a[i]
    a[i+1] += a[i]
    del a[i]

print(sum(a))

Submission status: Wrong Answer

Solution code:
# D - Add and Remove
N = int(input())
A = list(map(int, input().split()))

for i in range(len(A)-2):
    if len(A) < 3:
        break
    third = A.pop(2)
    second = A.pop(1)
    first = A.pop(0)
    first += second
    third += second
    A.insert(0, third)
    A.insert(0, first)
    print(A)
print(A.pop() + A.pop())

Submission status: Wrong Answer

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


if N % 2 == 0:
    for i in range(N-1):
        for j in range(1, N-1-i):
            if A[j] == min(A[1:len(A)-1]):
                A[j-1] = A[j-1] + A[j]
                A[j+1] = A[j+1] + A[j]
                A.pop(j)
                break
  
else:
    for i in range(N-2):
        for j in range(1, N-1-i):
            if A[j] == min(A[1:len(A)-1]):
                A[j-1] = A[j-1] + A[j]
                A[j+1] = A[j+1] + A[j]
                A.pop(j)
                break       
        
print(A[0]+A[1])

Submission status: Wrong Answer

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


if N % 2 == 0:
    for i in range(N-1):
        for j in range(1, N-1-i):
            print(j, A)
            if A[j] == min(A[1:len(A)-1]):
                A[j-1] = A[j-1] + A[j]
                A[j+1] = A[j+1] + A[j]
                A.pop(j)
                break
  
else:
    for i in range(N-2):
        for j in range(1, N-1-i):
            print(j, A)
            if A[j] == min(A[1:len(A)-1]):
                A[j-1] = A[j-1] + A[j]
                A[j+1] = A[j+1] + A[j]
                A.pop(j)
                break       
        
print(A[0], A[1])

Submission status: Wrong Answer

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

while len(cards) >= 3:
    new_cards = cards.copy()
    
    new_cards.pop(0)
    new_cards.pop(len(new_cards)-1)

    a = new_cards.index(min(new_cards))
    remove = cards.pop(a+1)
    cards[a] = cards[a] + remove
    cards[a+1] = cards[a+1] + remove

print(sum(cards))

Submission status: Wrong Answer

Solution code:

# D - Add and Remove

N = int(input())
input_line = input().split(' ')

A = [int(i) for i in input_line]


while len(A)>2:

    selection_mid = A.index(min(A))
    if selection_mid == 0:
        selection_mid += 1
    elif selection_mid == (len(A)-1):
        selection_mid -= 1

    A[selection_mid-1] += A[selection_mid]
    A[selection_mid+1] += A[selection_mid]
    A.pop(selection_mid)


print(sum(A))

Submission status: Wrong Answer

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


def taberu(A):
#    print(A)
    if len(A)==2:
        print(A[0]+A[1])
    else:
        B=A[1:-1]
        target=B.index(min(B))+1
#        print(target)
        A[target-1] += A[target]
        A[target+1] += A[target]
        B=A[:target]
        C=A[target+1:]
        B.extend(C)
        taberu(B)


taberu(A)

Submission status: Wrong Answer

Solution code:
def prob_a():
    n = int(input())
    a_list = [int(a) for a in input().split()]
    ans = a_list[0] + a_list[-1]
    a_list = a_list[1:-1]
    if n >= 3:
        for i in range(n - 3):
            if min(a_list[0]/2, a_list[-1]/2) <= min(a_list):
                if a_list[0] <= a_list[-1]:
                    x = a_list[0]
                    a_list = a_list[1:]
                    a_list[0] += x
                    ans += x
                else:
                    x = a_list[-1]
                    a_list = a_list[:-1]
                    a_list[-1] += x
                    ans += x
            else:
                x = min(a_list)
                ind = a_list.index(x)
                a_list[ind - 1] += x
                a_list[ind + 1] += x
                a_list.pop(ind)
            # print(a_list)
        ans += a_list[0] * 2
    else:
        pass
    print(str(ans))




prob_a()

Submission status: Wrong Answer

Solution code:
import numpy as np
n=int(input())
A=[int(n) for n in input().split()]
while len(A)>2:
  num=A[1:len(A)-1].index(min(A[1:len(A)-1]))+1
  A[num+1] = A[num] + A[num+1]
  A[num-1] = A[num] + A[num-1]
  del A[num]
print(A[0]+A[1])

Submission status: Wrong Answer

Solution code:
n = int(input())
num = [int(_) for _ in input().split()]

while len(num) > 2:
    second = 0
    smallest = 100000000000
    if len(num) > 3:
        for i in range(1, len(num)-1):
            if num[i] < smallest:
                smallest = num[i]
                second = i
    else:
        second = 1
    
    sec = num[second]
    num[second - 1] += sec
    num[second + 1] += sec
    del num[second]

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

Submission status: Wrong Answer

Solution code:
n=int(input())
p=input().rstrip().split(' ')
S=0;
if len(p)==2:
    print(int(p[0]) + int(p[1]))
elif len(p)==3:
    print((int(p[1])*2) + int(p[0]) + int(p[2]))
else:
    l=[]
    for i in range(0,len(p)):
        l.append(int(p[i]))
    S=list(l)
    while(len(l)>=3):
        t=min(l)
        C=l.index(t)
        if C==0:
            l[C]=l[C]+l[C+1];
            l[C+2]=l[C+2] + l[C+1]
            del(l[C+1])
        elif C==len(l)-1:
            l[C-2]=l[C-2]+l[C-1];
            l[C]=l[C]+l[C-1];
            del(l[C-1])
        else:
            l[C-1]=l[C-1]+l[C];
            l[C+1]=l[C+1]+l[C]
            del(l[C])
    A=l[0]+l[1];
    S.reverse();
    l=S;
    while(len(l)>=3):
        t=min(l)
        C=l.index(t)
        if C==0:
            l[C]=l[C]+l[C+1];
            l[C+2]=l[C+2] + l[C+1]
            del(l[C+1])
        elif C==len(l)-1:
            l[C-2]=l[C-2]+l[C-1];
            l[C]=l[C]+l[C-1];
            del(l[C-1])
        else:
            l[C-1]=l[C-1]+l[C];
            l[C+1]=l[C+1]+l[C]
            del(l[C])
    B=l[0]+l[1]
    print(min(A,B))

Submission status: Wrong Answer

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

while len(ai) > 2:
  ai[0] += ai[1]
  ai[2] += ai[1]
  ai.pop(1)

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

Submission status: Time Limit Exceeded

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

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

DP = [[{} for _ in range(N)] for _ in range(N)]
DP[0][N-1][(1, 1)] = float("inf")

def initialize(l, r, xl, xr):
  for m in range(l+1, r):
    DP[l][m][(xl, xl+xr)] = float("inf")
    DP[m][r][(xl+xr, xr)] = float("inf")
    initialize(l, m, xl, xl+xr)
    initialize(m, r, xl+xr, xr)
  return

initialize(0, N-1, 1, 1)

for i in range(N-1):
  for xl, xr in DP[i][i+1].keys():
    DP[i][i+1][(xl, xr)] = xl * A[i] + xr * A[i+1]
    
for d in range(2, N):
  for i in range(N-d):
    l = i
    r = i+d
    for xl, xr in DP[l][r].keys():
      tmp = float("inf")
      for m in range(l+1, r):
        v = DP[l][m][(xl, xl+xr)] + DP[m][r][(xl+xr, xr)] - (xl+xr) * A[m]
        if v < tmp:
          tmp = v
      DP[l][r][(xl, xr)] = tmp
print(DP[0][N-1][(1,1)])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

dp = defaultdict(int)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

dp = defaultdict(int)

def rec(l, r, xl, xr) :
    if l + 1 == r :
        return 0
    
    if dp[(l, r, xl, xr)] > 0 :
        return dp[(l, r, xl, xr)]
    
    ret = float('inf')
    for m in range(l + 1, r) :
        ret = min(ret, rec(l, m, xl, xl+xr) + rec(m, r, xl+xr, xr) + A[m] * (xl+xr))
   
    dp[(l, r, xl, xr)] = ret
    return ret
    
print(A[0] + rec(0, N-1, 1, 1) + A[N-1])

Submission status: Time Limit Exceeded

Solution code:
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
        
    ret = float('inf')
    for m in range(l + 1, r) :
        ret = min(ret, rec(l, m, xl, xl+xr) + rec(m, r, xl+xr, xr) + A[m] * (xl+xr))
    return ret
    
print(A[0] + rec(0, N-1, 1, 1) + A[N-1])

Submission status: Time Limit Exceeded

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

def rec(l, r, xl, xr) :
    if l + 1 == r :
        return 0
        
    ret = float('inf')
    for m in range(l + 1, r) :
        ret = min(ret, rec(l, m, xl, xl+xr) + rec(m, r, xl+xr, xr) + A[m] * (xl+xr))
    return ret
    
print(A[0] + rec(0, N-1, 1, 1) + A[N-1])

Submission status: Time Limit Exceeded

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

memo = dict()
def dfs(l, r, wl, wr):
    if r <= l + 1:
        return 0
    if memo.get((l, r, wl, wr)):
        return memo[(l, r, wl, wr)]
    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))
    memo[(l, r, wl, wr)] = v
    return v

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

Solution code:
def contract(n, aaa):
    d = n
    aaa_can = [(sum(aaa), aaa)]
    while d > 2:
        next_totals = []
        for i in range(len(aaa_can)):
            total, aaa = aaa_can[i]
            for j in range(1, d - 1):
                next_totals.append((total + aaa[j], i, j))
        next_totals.sort()
        next_can = []
        checked = set()
        for total, i, j in next_totals:
            aaa = aaa_can[i][1]
            aj = aaa[j]
            bbb = aaa[:j] + aaa[j + 1:]
            bbb[j - 1] += aj
            bbb[j] += aj
            ccc = tuple(bbb)
            if ccc in checked:
                continue
            checked.add(ccc)
            next_can.append((total, bbb))
            if len(next_can) >= 20000:
                break
        aaa_can = next_can
        d -= 1
    return aaa_can[0][0]


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

Submission status: Time Limit Exceeded

Solution code:
def contract(aaa_can, d):
    if d == 2:
        return aaa_can[0][0]

    next_totals = []
    for i, (total, aaa) in enumerate(aaa_can):
        for j, a in enumerate(aaa[1:-1], start=1):
            next_totals.append((total + a, i, j))
    next_totals.sort()
    next_can = []
    checked = set()
    for total, i, j in next_totals:
        aaa = aaa_can[i][1]
        aj = aaa[j]
        bbb = aaa[:j] + aaa[j + 1:]
        bbb[j - 1] += aj
        bbb[j] += aj
        ccc = tuple(bbb)
        if ccc in checked:
            continue
        checked.add(ccc)
        next_can.append((total, bbb))
        if len(next_can) >= 20000:
            break
    return contract(next_can, d - 1)


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

Submission status: Time Limit Exceeded

Solution code:
def solve(l, r, lx, rx):
  if l+1 == r:
    return 0
  res = float('inf')
  for k in range(l+1, r):
    res = min(res, solve(l, k, lx, lx+rx) + solve(k, r, lx+rx, rx) + alist[k]*(lx+rx))
  return res

n = int(input())
alist = list(map(int, input().split()))
print(solve(0, n-1, 1, 1) + alist[0] + alist[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(pow(10, 6))
# input = sys.stdin.readline

def solve(l, r, lx, rx):
  if l+1 == r:
    return 0
  res = float('inf')
  for k in range(l+1, r):
    res = min(res, solve(l, k, lx, lx+rx) + solve(k, r, lx+rx, rx) + alist[k]*(lx+rx))
  return res

n = int(input())
alist = list(map(int, input().split()))
print(solve(0, n-1, 1, 1) + alist[0] + alist[-1])

Submission status: Time Limit Exceeded

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

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

list=[[1,1]]

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

mi=[]

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

print(min(mi))

Submission status: Time Limit Exceeded

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):
            newlist.append(L[:i+1]+[sum(L[i:i+2])]+L[i+1:])
    list=newlist

mi=[]

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

print(min(mi))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from sys import stdin
def test(h,n):
    if n==3:
        y=len(h)
        k=float('inf')
        for i in xrange (y):
            g=h.popleft()
            k=min(k,g[0]+g[2]+2*g[1])
        return k
    else:
        y=len(h)
        for i in xrange (y):
            g=h.popleft()
            for j in xrange (1,n-1):
                p=list(g)
                p[j-1]+=p[j]
                p[j+1]+=p[j]
                del p[j]
                h.append(p)
        return test(h,n-1)
n=int(stdin.readline())
l=map(int,stdin.readline().split())
if n==2:
    print sum(l)
else:
    ans=test(deque([l]),n)
    print ans