Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2 ** 2000)
n = int(input())
a = list(map(int, input().split()))
a = [(i, v) for i, v in enumerate(a)]
a.sort(key=lambda x: x[1], reverse=True)

dp = [[-1] * (m + 1) for m in range(n + 1)]
# m: 何人選んだか, l: 左を選んだ人数
def f(m, l):
    if m == n: return 0
    if dp[m][l] != -1: return dp[m][l]
    r = n - m + l - 1
    i, v = a[m]
    if i >= l: dp[m + 1][l + 1] = f(m + 1, l + 1)
    if i <= r: dp[m + 1][l] = f(m + 1, l)
    return max(dp[m + 1][l + 1] + v * (i - l), dp[m + 1][l] + v * (r - i))
print(f(0, 0))

Fixed submission:
import sys
sys.setrecursionlimit(2000 * 2)
n = int(input())
a = list(map(int, input().split()))
a = [(i, v) for i, v in enumerate(a)]
a.sort(key=lambda x: x[1], reverse=True)

dp = [[-1] * (m + 1) for m in range(n + 1)]
# m: 何人選んだか, l: 左を選んだ人数
def f(m, l):
    if m == n: return 0
    if dp[m][l] != -1: return dp[m][l]
    r = n - m + l - 1
    i, v = a[m]
    if i >= l: dp[m + 1][l + 1] = f(m + 1, l + 1)
    if i <= r: dp[m + 1][l] = f(m + 1, l)
    return max(dp[m + 1][l + 1] + v * (i - l), dp[m + 1][l] + v * (r - i))
print(f(0, 0))

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
a = [(i, v) for i, v in enumerate(a)]
a.sort(key=lambda x: x[1], reverse=True)

dp = [[-1] * (m + 1) for m in range(n + 1)]
# m: 何人選んだか, l: 左を選んだ人数
def f(m, l):
    if m == n: return 0
    if dp[m][l] != -1: return dp[m][l]
    r = n - m + l - 1
    i, v = a[m]
    if i >= l: dp[m + 1][l + 1] = f(m + 1, l + 1)
    if i <= r: dp[m + 1][l] = f(m + 1, l)
    return max(dp[m + 1][l + 1] + v * (i - l), dp[m + 1][l] + v * (r - i))
print(f(0, 0))

Fixed submission:
import sys
sys.setrecursionlimit(2000 * 2)
n = int(input())
a = list(map(int, input().split()))
a = [(i, v) for i, v in enumerate(a)]
a.sort(key=lambda x: x[1], reverse=True)

dp = [[-1] * (m + 1) for m in range(n + 1)]
# m: 何人選んだか, l: 左を選んだ人数
def f(m, l):
    if m == n: return 0
    if dp[m][l] != -1: return dp[m][l]
    r = n - m + l - 1
    i, v = a[m]
    if i >= l: dp[m + 1][l + 1] = f(m + 1, l + 1)
    if i <= r: dp[m + 1][l] = f(m + 1, l)
    return max(dp[m + 1][l + 1] + v * (i - l), dp[m + 1][l] + v * (r - i))
print(f(0, 0))

Buggy python submission (verdict: Runtime Error):
import itertools

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

def make_key(select):
    key = ''
    for i in select:
        key += str(i)
    return key

dp = {}
def f(select):
    try:
        key = make_key(select)
        return dp[key]
    except KeyError:
        if len(select) == 1:
            return 0
        if len(select) == 2:
            i, j = select
            return abs(i - j) * (a[i] + a[j])
        happy = 0
        for i, j in itertools.combinations(select, 2):
            tmp = abs(i - j) * (a[i] + a[j]) + f(select - {i, j})
            happy = max(tmp, happy)
        key = make_key(select)
        dp[key] = happy
        return happy

select = set([i for i in range(n)])
print(f(select))

Fixed submission:
import sys
sys.setrecursionlimit(2000 * 2)
n = int(input())
a = list(map(int, input().split()))
a = [(i, v) for i, v in enumerate(a)]
a.sort(key=lambda x: x[1], reverse=True)

dp = [[-1] * (m + 1) for m in range(n + 1)]
# m: 何人選んだか, l: 左を選んだ人数
def f(m, l):
    if m == n: return 0
    if dp[m][l] != -1: return dp[m][l]
    r = n - m + l - 1
    i, v = a[m]
    if i >= l: dp[m + 1][l + 1] = f(m + 1, l + 1)
    if i <= r: dp[m + 1][l] = f(m + 1, l)
    return max(dp[m + 1][l + 1] + v * (i - l), dp[m + 1][l] + v * (r - i))
print(f(0, 0))