Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline

n = int(input())
A = list(map(int, input().split()))
L = [(a, i+1) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = [[-1]*(n+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n+1):
  for j in range(n+1-i):
    a, idx = L[i+j-1]
    if i:
      dp[i][j] = max(dp[i][j], dp[i-1][j]+a*(idx-i))
    if j:
      dp[i][j] = max(dp[i][j], dp[i][j-1]+a*(n+1-j-idx))
ans = 0
for i in range(n+1):
  ans = max(ans, dp[i][n-i])
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
A = list(map(int, input().split()))
L = [(a, i) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = [[-1]*n for _ in range(n)]
def dfs(l, r):
    i = (n-1-r) + l
    a, idx = L[i]
    if i == n-1:
        res = max(idx-l, r-idx) * a
        return res
    if dp[l][r] != -1:
        return dp[l][r]
    res = max((idx-l)*a + dfs(l+1, r), (r-idx)*a + dfs(l, r-1))
    dp[l][r] = res
    return res
ans = dfs(0, n-1)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

def main():
  n = int(input())
  A = list(map(int, input().split()))
  L = [(a, i) for i, a in enumerate(A)]
  L.sort(reverse=True)
  dp = dict()
  def dfs(i, l, r):
      a, idx = L[i]
      if i == n-1:
          res = max(idx-l, r-idx) * a
          return res
      if (i, l, r) in dp:
          return dp[(i, l, r)]
      res = max((idx-l)*a + dfs(i+1, l+1, r), (r-idx)*a + dfs(i+1, l, r-1))
      dp[(i, l, r)] = res
      return res
  ans = dfs(0, 0, n-1)
  print(ans)
  
if __name__ == "__main__":
  main()

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
A = list(map(int, input().split()))
L = [(a, i) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = [[-1]*n for _ in range(n)]
def dfs(l, r):
    i = (n-1-r) + l
    a, idx = L[i]
    if i == n-1:
        res = max(idx-l, r-idx) * a
        return res
    if dp[l][r] != -1:
        return dp[l][r]
    res = max((idx-l)*a + dfs(l+1, r), (r-idx)*a + dfs(l, r-1))
    dp[l][r] = res
    return res
ans = dfs(0, n-1)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
A = list(map(int, input().split()))
L = [(a, i) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = dict()
def dfs(i, l, r):
    a, idx = L[i]
    if i == n-1:
        res = max(idx-l, r-idx) * a
        return res
    if (i, l, r) in dp:
        return dp[(i, l, r)]
    res = max((idx-l)*a + dfs(i+1, l+1, r), (r-idx)*a + dfs(i+1, l, r-1))
    dp[(i, l, r)] = res
    return res
ans = dfs(0, 0, n-1)
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
A = list(map(int, input().split()))
L = [(a, i) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = [[-1]*n for _ in range(n)]
def dfs(l, r):
    i = (n-1-r) + l
    a, idx = L[i]
    if i == n-1:
        res = max(idx-l, r-idx) * a
        return res
    if dp[l][r] != -1:
        return dp[l][r]
    res = max((idx-l)*a + dfs(l+1, r), (r-idx)*a + dfs(l, r-1))
    dp[l][r] = res
    return res
ans = dfs(0, n-1)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
A = list(map(int, input().split()))
L = [(a, i) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = [[-1]*n for _ in range(n)]
def dfs(l, r):
    i = (n-1-r) + l
    a, idx = L[i]
    if i == n-1:
        res = max(idx-l, r-idx) * a
        return res
    if dp[l][r] != -1:
        return dp[l][r]
    res = max((idx-l)*a + dfs(l+1, r), (r-idx)*a + dfs(l, r-1))
    dp[l][r] = res
    return res
ans = dfs(0, n-1)
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
A = list(map(int, input().split()))
L = [(a, i) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = [[-1]*n for _ in range(n)]
def dfs(l, r):
    i = (n-1-r) + l
    a, idx = L[i]
    if i == n-1:
        res = max(idx-l, r-idx) * a
        return res
    if dp[l][r] != -1:
        return dp[l][r]
    res = max((idx-l)*a + dfs(l+1, r), (r-idx)*a + dfs(l, r-1))
    dp[l][r] = res
    return res
ans = dfs(0, n-1)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
A = list(map(int, input().split()))
L = [(a, i) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = dict()
def dfs(l, r):
    i = (n-1-r) + l
    a, idx = L[i]
    if i == n-1:
        res = max(idx-l, r-idx) * a
        return res
    if (l, r) in dp:
        return dp[(l, r)]
    res = max((idx-l)*a + dfs(l+1, r), (r-idx)*a + dfs(l, r-1))
    dp[(l, r)] = res
    return res
ans = dfs(0, n-1)
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
A = list(map(int, input().split()))
L = [(a, i) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = [[-1]*n for _ in range(n)]
def dfs(l, r):
    i = (n-1-r) + l
    a, idx = L[i]
    if i == n-1:
        res = max(idx-l, r-idx) * a
        return res
    if dp[l][r] != -1:
        return dp[l][r]
    res = max((idx-l)*a + dfs(l+1, r), (r-idx)*a + dfs(l, r-1))
    dp[l][r] = res
    return res
ans = dfs(0, n-1)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
A = list(map(int, input().split()))
L = [(a, i) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = dict()
def dfs(i, l, r):
    a, idx = L[i]
    if i == n-1:
        res = max(idx-l, r-idx) * a
        return res
    if (i, l, r) in dp:
        return dp[(i, l, r)]
    res = max((idx-l)*a + dfs(i+1, l+1, r), (r-idx)*a + dfs(i+1, l, r-1))
    dp[(i, l, r)] = res
    return res
ans = dfs(0, 0, n-1)
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
A = list(map(int, input().split()))
L = [(a, i) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = [[-1]*n for _ in range(n)]
def dfs(l, r):
    i = (n-1-r) + l
    a, idx = L[i]
    if i == n-1:
        res = max(idx-l, r-idx) * a
        return res
    if dp[l][r] != -1:
        return dp[l][r]
    res = max((idx-l)*a + dfs(l+1, r), (r-idx)*a + dfs(l, r-1))
    dp[l][r] = res
    return res
ans = dfs(0, n-1)
print(ans)