Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
INF = float('inf')
A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
A = sorted(A, key=lambda x: x[1], reverse = True)
dp = [[-INF] * (N+1) for _ in range(N+1)]
dp[0][0] = 0

for s in range(1, N+1):
    for l in range(s+1):
        r = s - l
        dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))

ans = 0
for m in range(N):
    if dp[m][N-m] > ans:
        ans = dp[m][N-m]

print(ans)

Fixed submission:
def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)

  dp = [[-INF] * (N+1) for _ in range(N+1)]
  dp[0][0] = 0

  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)

main()

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [(a, i+1) for i, a in enumerate(map(int, input().split()))]
A.sort(reverse=True)
INF = float('inf')
dp = [[-INF] * (N+1) for _ in range(N+1)]
dp[0][0] = 0

for s in range(1, N+1):
    for l in range(s+1):
        r = s - l
        dp[l][r] = max(dp[l-1][r] + A[s-1][0] * abs(A[s-1][1]-l), dp[l][r-1] + A[s-1][0] * abs(N-r+1-A[s-1][1]))

ans = 0
for m in range(N):
    if dp[m][N-m] > ans:
        ans = dp[m][N-m]

print(ans)

Fixed submission:
def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)

  dp = [[-INF] * (N+1) for _ in range(N+1)]
  dp[0][0] = 0

  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)

main()

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**6)
N = int(input())
A = list(map(int, input().split()))
acts = [(x, i) for i, x in enumerate(A)]
acts.sort()
dp = [[-1]*N for _ in range(N)]
 
def rec(l, r):
    if r < l:
        return 0
    if dp[l][r] >= 0:
        return dp[l][r]
    k = r - l
    act, init_pos = acts[k]
    gain_l = act * abs(l - init_pos)
    gain_r = act * abs(r - init_pos)
    res = dp[l][r] = max(gain_l + rec(l+1, r), gain_r + rec(l, r-1))
    return res
 
print(solve(0, N-1))

Fixed submission:
def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)

  dp = [[-INF] * (N+1) for _ in range(N+1)]
  dp[0][0] = 0

  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)

main()

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = [(A, i) for i, A in enumerate(map(int, input().split()))]

a.sort()
dp = [[-1]*n for _ in range(n)]

def recursive(l, r):
    if l > r:
        return 0
    if dp[l][r] >= 0:
        return dp[l][r]
    k = r - l
    energy, pos = a[k]
    from_l = energy * abs(l - pos)
    from_r = energy * abs(r - pos)
    ans = dp[l][r] = max(from_l + recursive(l+1, r), from_r + recursive(l, r-1))
    return ans

print(recursive(0, n-1))

Fixed submission:
def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)

  dp = [[-INF] * (N+1) for _ in range(N+1)]
  dp[0][0] = 0

  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)

main()

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = [(A, i) for i, A in enumerate(map(int, input().split()))]

a.sort()
dp = [[-1]*n for _ in range(n)]

def recursive(l, r):
    if l > r:
        return 0
    if dp[l][r] >= 0:
        return dp[l][r]
    k = r - l
    energy, pos = a[k]
    from_l = energy * abs(l - pos)
    from_r = energy * abs(r - pos)
    dp[l][r] = max(from_l + recursive(l+1, r), from_r + recursive(l, r-1))
    return dp[l][r]

print(recursive(0, n-1))

Fixed submission:
def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)

  dp = [[-INF] * (N+1) for _ in range(N+1)]
  dp[0][0] = 0

  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)

main()

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [(A, i) for i, A in enumerate(map(int, input().split()))]

a.sort(reverse=True)
INF = float('inf')
#print(a)

dp = [[-INF]*(n+1) for _ in range(n+1)]
dp[0][0] = 0

for num, (A, pos) in enumerate(a):
    #print("="*5, num, "="*5)
    for i in range(num+1):
        j = num - i
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + A*abs(pos-i))  # 左からi番目の時
        dp[i][j+1] = max(dp[i][j+1], dp[i][j] + A*abs((n-1-j)-pos))  # 右からj番目の時

        # print("="*3, i, "="*3)
        # for k in range(len(dp)):
        #     print(dp[k])
    

ans = 0
for i in range(n+1):
    j = n-i
    ans = max(ans, dp[i][j])
    # print(f"i = {i}")
    # print(f"j = {j}")
    # print(max(ans, dp[i][j]))

print(ans)

Fixed submission:
def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)

  dp = [[-INF] * (N+1) for _ in range(N+1)]
  dp[0][0] = 0

  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)

main()

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [(A, i) for i, A in enumerate(map(int, input().split()))]
a.sort(reverse=True)

dp = [[-1]*(n+1) for _ in range(n+1)]
dp[0][0] = 0

for num, (A, pos) in enumerate(a):
    for i in range(num+1):
        j = num - i
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + A*abs(pos-i))  # 左からi番目の時
        dp[i][j+1] = max(dp[i][j+1], dp[i][j] + A*abs((n-1-j)-pos))  # 右からj番目の時


ans = 0
for i in range(n+1):
    j = n-i
    ans = max(ans, dp[i][j])

print(ans)

Fixed submission:
def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)

  dp = [[-INF] * (N+1) for _ in range(N+1)]
  dp[0][0] = 0

  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)

main()