Buggy python submission (verdict: Time Limit Exceeded):
import heapq
import math
import random
import sys
import numpy as np


sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    arr = sorted(enumerate(map(int, input().split())),
                 key=lambda x: x[1], reverse=True)
    dp = np.zeros((n+1, n+1), dtype=np.int)

    for i in range(n):
        for j in range(n-i):
            idx, a = arr[i+j]
            dp[i+1, j] = max(dp[i+1, j], dp[i, j] + a*(idx-i))
            dp[i, j+1] = max(dp[i, j+1], dp[i, j] + a*(n-1-j-idx))

    print(max(dp[i, n-i] for i in range(n+1)))


Fixed submission:
import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)
import numpy as np


sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    arr = sorted(enumerate(map(int, input().split()), 1),
                 key=lambda x: x[1], reverse=True)
    dp = np.zeros(n+1, dtype=np.int)

    for k, (i, a) in enumerate(arr, 1):
        ndp = dp.copy()
        
        add_left = np.abs(np.arange(1, k+1) - i) * a
        ndp[1:k+1] = np.maximum(ndp[1:k+1], dp[:k] + add_left)
        
        add_right = np.abs(np.arange(n-k+1, n+1) - i) * a
        ndp[:k] = np.maximum(ndp[:k], dp[:k] + add_right)

        dp = ndp

    print(dp.max())

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)
from operator import itemgetter

sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    arr = sorted(enumerate(map(int, input().split())),
                 key=itemgetter(1), reverse=True)
    dp = [[0] * (n+1) for _ in range(n+1)]

    for i in range(n):
        for j in range(n-i):
            idx, a = arr[i+j]
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + a*(idx-i))
            dp[i][j+1] = max(dp[i][j+1], dp[i][j] + a*(n-1-j-idx))

    print(max(dp[i][n-i] for i in range(n+1)))


Fixed submission:
import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)
import numpy as np


sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    arr = sorted(enumerate(map(int, input().split()), 1),
                 key=lambda x: x[1], reverse=True)
    dp = np.zeros(n+1, dtype=np.int)

    for k, (i, a) in enumerate(arr, 1):
        ndp = dp.copy()
        
        add_left = np.abs(np.arange(1, k+1) - i) * a
        ndp[1:k+1] = np.maximum(ndp[1:k+1], dp[:k] + add_left)
        
        add_right = np.abs(np.arange(n-k+1, n+1) - i) * a
        ndp[:k] = np.maximum(ndp[:k], dp[:k] + add_right)

        dp = ndp

    print(dp.max())

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)

sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    arr = sorted(enumerate(map(int, input().split())),
                 key=lambda x: x[1], reverse=True)
    dp = [[0] * (n+1) for _ in range(n+1)]

    for i in range(n):
        for j in range(n-i):
            idx, a = arr[i+j]
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + a*(idx-i))
            dp[i][j+1] = max(dp[i][j+1], dp[i][j] + a*(n-1-j-idx))

    print(max(dp[i][n-i] for i in range(n+1)))


Fixed submission:
import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)
import numpy as np


sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    arr = sorted(enumerate(map(int, input().split()), 1),
                 key=lambda x: x[1], reverse=True)
    dp = np.zeros(n+1, dtype=np.int)

    for k, (i, a) in enumerate(arr, 1):
        ndp = dp.copy()
        
        add_left = np.abs(np.arange(1, k+1) - i) * a
        ndp[1:k+1] = np.maximum(ndp[1:k+1], dp[:k] + add_left)
        
        add_right = np.abs(np.arange(n-k+1, n+1) - i) * a
        ndp[:k] = np.maximum(ndp[:k], dp[:k] + add_right)

        dp = ndp

    print(dp.max())

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)

sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    arr = [(num, i) for i, num in enumerate(int(c) for c in input().split())]
    arr.sort(reverse=True)
    dp = [[0] * (n+1) for _ in range(n+1)]    

    for i in range(n):
        for j in range(n-i):
            a, idx = arr[i+j]
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + a*(idx-i))
            dp[i][j+1] = max(dp[i][j+1], dp[i][j] + a*(n-1-j-idx))

    print(max(dp[i][n-i] for i in range(n+1)))

Fixed submission:
import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)
import numpy as np


sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    arr = sorted(enumerate(map(int, input().split()), 1),
                 key=lambda x: x[1], reverse=True)
    dp = np.zeros(n+1, dtype=np.int)

    for k, (i, a) in enumerate(arr, 1):
        ndp = dp.copy()
        
        add_left = np.abs(np.arange(1, k+1) - i) * a
        ndp[1:k+1] = np.maximum(ndp[1:k+1], dp[:k] + add_left)
        
        add_right = np.abs(np.arange(n-k+1, n+1) - i) * a
        ndp[:k] = np.maximum(ndp[:k], dp[:k] + add_right)

        dp = ndp

    print(dp.max())

Buggy python submission (verdict: Time Limit Exceeded):

if __name__ == "__main__":
    n = int(input())
    arr = [(num, i) for i, num in enumerate(int(c) for c in input().split())]
    arr.sort(reverse=True)
    dp = [[0] * (n+1) for _ in range(n+1)]    

    for i in range(n):
        for j in range(n-i):
            a, idx = arr[i+j]
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + a*(idx-i))
            dp[i][j+1] = max(dp[i][j+1], dp[i][j] + a*(n-1-j-idx))

    print(max(dp[i][n-i] for i in range(n+1)))

Fixed submission:
import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)
import numpy as np


sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    arr = sorted(enumerate(map(int, input().split()), 1),
                 key=lambda x: x[1], reverse=True)
    dp = np.zeros(n+1, dtype=np.int)

    for k, (i, a) in enumerate(arr, 1):
        ndp = dp.copy()
        
        add_left = np.abs(np.arange(1, k+1) - i) * a
        ndp[1:k+1] = np.maximum(ndp[1:k+1], dp[:k] + add_left)
        
        add_right = np.abs(np.arange(n-k+1, n+1) - i) * a
        ndp[:k] = np.maximum(ndp[:k], dp[:k] + add_right)

        dp = ndp

    print(dp.max())

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)

sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
# input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    nums = [int(c) for c in input().split()]
    arr = [(num, i) for i, num in enumerate(nums)]
    arr.sort(key=lambda x: -x[0])
    dp = [[0] * (n+1) for _ in range(n+1)]    

    for i in range(n):
        for j in range(n-i):
            a, idx = arr[i+j]
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + a*(idx-i))
            dp[i][j+1] = max(dp[i][j+1], dp[i][j] + a*(n-1-j-idx))

    print(max(dp[i][n-i] for i in range(n+1)))

Fixed submission:
import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)
import numpy as np


sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    arr = sorted(enumerate(map(int, input().split()), 1),
                 key=lambda x: x[1], reverse=True)
    dp = np.zeros(n+1, dtype=np.int)

    for k, (i, a) in enumerate(arr, 1):
        ndp = dp.copy()
        
        add_left = np.abs(np.arange(1, k+1) - i) * a
        ndp[1:k+1] = np.maximum(ndp[1:k+1], dp[:k] + add_left)
        
        add_right = np.abs(np.arange(n-k+1, n+1) - i) * a
        ndp[:k] = np.maximum(ndp[:k], dp[:k] + add_right)

        dp = ndp

    print(dp.max())

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)

sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
# input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    nums = [int(c) for c in input().split()]
    arr = [(num, i) for i, num in enumerate(nums)]
    arr.sort(key=lambda x: -x[0])
    dp = [[0] * (n+1) for _ in range(n+1)]    

    for i in range(n):
        a, idx = arr[i]
        for j in range(i+1):
            dp[j+1][i-j] = max(dp[j+1][i-j], dp[j][i-j] + a*(idx - j))
            dp[j][i-j+1] = max(dp[j][i-j+1], dp[j][i-j] + a*(n-1-(i-j)-idx))

    print(max(dp[i][n-i] for i in range(n+1)))

Fixed submission:
import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)
import numpy as np


sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    arr = sorted(enumerate(map(int, input().split()), 1),
                 key=lambda x: x[1], reverse=True)
    dp = np.zeros(n+1, dtype=np.int)

    for k, (i, a) in enumerate(arr, 1):
        ndp = dp.copy()
        
        add_left = np.abs(np.arange(1, k+1) - i) * a
        ndp[1:k+1] = np.maximum(ndp[1:k+1], dp[:k] + add_left)
        
        add_right = np.abs(np.arange(n-k+1, n+1) - i) * a
        ndp[:k] = np.maximum(ndp[:k], dp[:k] + add_right)

        dp = ndp

    print(dp.max())