Particle Accelerator II

import sys
input = sys.stdin.readline
n = int(input())
x = list(map(int, input().split()))

e = [[1000000000000000] * (n + 1) for _ in range(n + 1)]
w = [[0] * (n + 1) for _ in range(n + 1)]

for s in range(1, n + 1):
    w[s][s] = x[s - 1]
    e[s][s] = 0

for length in range(1, n + 1):
    for s in range(1, n + 1 - length):
        f = s + length
        for k in range(s + 1, f + 1):
            a = w[s][k - 1] * w[k][f] + e[s][k - 1] + e[k][f]
            if a < e[s][f]:
                e[s][f] = a
                w[s][f] = w[s][k - 1] + w[k][f]

print(e[1][n])

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: TIME LIMIT EXCEEDED

Test 12

Verdict: RUNTIME ERROR

Test 13

Verdict: RUNTIME ERROR