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


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

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


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

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


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

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


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