Buggy python submission (verdict: Time Limit Exceeded):
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])


Fixed submission:
# 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])

Buggy python submission (verdict: Time Limit Exceeded):
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])


Fixed submission:
# 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])

Buggy python submission (verdict: Time Limit Exceeded):
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])


Fixed submission:
# 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])

Buggy python submission (verdict: Runtime Error):
#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];
    
}

Fixed submission:
# 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])

Buggy python submission (verdict: Time Limit Exceeded):
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])

Fixed submission:
# 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])

Buggy python submission (verdict: Time Limit Exceeded):
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])

Fixed submission:
# 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])