Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict

sys.setrecursionlimit(4000)


def main():
  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = defaultdict(int)

  def cal(ln, rn):
    if ln + rn > n:
      return

    p, a = arr[ln + rn - 1]
    val_l = dp[ln - 1, rn] + a * abs(p - (ln - 1)) if ln > 0 else 0
    val_r = dp[ln, rn - 1] + a * abs(p - (n - rn)) if rn > 0 else 0

    dp[ln, rn] = max(val_l, val_r)

    cal(ln + 1, rn)
    cal(ln, rn + 1)

  cal(1, 0)
  cal(0, 1)

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


main()


Fixed submission:

def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()

Buggy python submission (verdict: Time Limit Exceeded):

n = int(input())
arr = map(int, input().split())
arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

dp = [[0] * (n + 1) for _ in range(n + 1)]
for i, (p, a) in enumerate(arr):
  for l in range(i + 1):
    dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
    dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

print(max(dp[n]))


Fixed submission:

def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

n = int(input())
arr = map(int, input().split())
arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

dp = defaultdict(int)
for i, (p, a) in enumerate(arr):
  for l in range(i + 1):
    dp[i + 1, l] = max(dp[i + 1, l], dp[i, l] + a * abs(p - (n - (i - l) - 1)))
    dp[i + 1, l + 1] = max(dp[i + 1, l + 1], dp[i, l] + a * abs(p - l))

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


Fixed submission:

def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict

sys.setrecursionlimit(4000)

n = int(input())
arr = map(int, input().split())
arr = sorted(enumerate(arr), key=lambda tpl: -tpl[1])

dp = defaultdict(int)

def cal(ln, rn):
  if ln < 0 or rn < 0 or ln == rn == 0:
    return 0

  if dp[ln, rn] == 0:
    p, a = arr[ln + rn - 1]
    val_l = cal(ln - 1, rn) + a * abs(p - (ln - 1)) if ln > 0 else 0
    val_r = cal(ln, rn - 1) + a * abs(p - (n - rn)) if rn > 0 else 0

    dp[ln, rn] = max(val_l, val_r)

  return dp[ln, rn]


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


Fixed submission:

def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(4000)

n = int(input())
arr = map(int, input().split())
arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

dp = {}
for ln in range(n + 1):
  for rn in range(n + 1 - ln):
    if ln + rn > n or dp.get((ln, rn)):
      continue

    if ln == rn == 0:
      dp[0, 0] = 0
    else:
      p, a = arr[ln + rn - 1]
      val_l = dp[ln - 1, rn] + a * abs(p - (ln - 1)) if ln > 0 else 0
      val_r = dp[ln, rn - 1] + a * abs(p - (n - rn)) if rn > 0 else 0

      dp[ln, rn] = max(val_l, val_r)

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


Fixed submission:

def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict

sys.setrecursionlimit(4000)

n = int(input())
arr = map(int, input().split())
arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

dp = defaultdict(int)

for ln in range(n + 1):
  for rn in range(n + 1 - ln):
    if ln + rn > n or dp[ln, rn]:
      continue

    p, a = arr[ln + rn - 1]
    val_l = dp[ln - 1, rn] + a * abs(p - (ln - 1)) if ln > 0 else 0
    val_r = dp[ln, rn - 1] + a * abs(p - (n - rn)) if rn > 0 else 0

    dp[ln, rn] = max(val_l, val_r)

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


Fixed submission:

def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict

sys.setrecursionlimit(4000)

n = int(input())
arr = map(int, input().split())
arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

dp = defaultdict(int)

def cal(ln, rn):
  if ln + rn > n:
    return

  p, a = arr[ln + rn - 1]
  val_l = dp[ln - 1, rn] + a * abs(p - (ln - 1)) if ln > 0 else 0
  val_r = dp[ln, rn - 1] + a * abs(p - (n - rn)) if rn > 0 else 0

  dp[ln, rn] = max(val_l, val_r)

  cal(ln + 1, rn)
  cal(ln, rn + 1)

cal(1, 0)
cal(0, 1)

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


Fixed submission:

def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()

Buggy python submission (verdict: Runtime Error):
import sys
from collections import defaultdict

sys.setrecursionlimit(4000)

n = int(input())
arr = map(int, input().split())
arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

dp = {}
def cal(ln, rn):
  if ln + rn > n:
    return

  if ln > 0 or rn > 0:
    idx = ln + rn - 1
    p, a = arr[idx]
    val_l = dp[ln - 1, rn] + a * abs(p - (ln - 1)) if ln > 0 else 0
    val_r = dp[ln, rn - 1] + a * abs(p - (n - rn)) if rn > 0 else 0

    dp[ln, rn] = max(val_l, val_r)
  else:
    dp[ln, rn] = 0

  cal(ln + 1, rn)
  cal(ln, rn + 1)

cal(0, 0)

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


Fixed submission:

def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict

sys.setrecursionlimit(4000)

n = int(input())
arr = map(int, input().split())
arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

dp = defaultdict(int)

def cal(ln, rn):
  if ln + rn > n:
    return

  if ln > 0 or rn > 0:
    idx = ln + rn - 1
    p, a = arr[idx]
    val_l = dp[ln - 1, rn] + a * abs(p - (ln - 1)) if ln > 0 else 0
    val_r = dp[ln, rn - 1] + a * abs(p - (n - rn)) if rn > 0 else 0

    dp[ln, rn] = max(val_l, val_r)

  cal(ln + 1, rn)
  cal(ln, rn + 1)

cal(0, 0)

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


Fixed submission:

def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

n = int(input())
arr = map(int, input().split())
arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

dp = defaultdict(int)

def cal(ln, rn):
  if ln + rn > n:
    return

  if ln > 0 or rn > 0:
    idx = ln + rn - 1
    p, a = arr[idx]
    val_l = dp[ln - 1, rn] + a * abs(p - (ln - 1)) if ln > 0 else 0
    val_r = dp[ln, rn - 1] + a * abs(p - (n - rn)) if rn > 0 else 0

    dp[ln, rn] = max(val_l, val_r)

  cal(ln + 1, rn)
  cal(ln, rn + 1)

cal(0, 0)

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


Fixed submission:

def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()

Buggy python submission (verdict: Runtime Error):

n = int(input())
arr = tuple(map(int, input().split()))

def cal(i, dst):
  if i == -1:
    return 0

  result = None
  for j in dst:
    next_dst = [v for v in dst if v != j]
    val = arr[i] * abs(i - j) + cal(i - 1, next_dst)
    result = max(result, val) if result else val

  return result

print(cal(n - 1, [i for i in range(n)]))


Fixed submission:

def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()

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

n = int(input())
arr = tuple(map(int, input().split()))


def cal(i, dst):
  if i == -1:
    return 0

  result = None
  for j in range(n):
    if dst[j]:
      continue
    dst[j] = i
    val = arr[i] * abs(i - j) + cal(i - 1, dst)
    dst[j] = None
    result = max(result, val) if result else val

  return result

print(cal(n - 1, [None for _ in range(n)]))


Fixed submission:

def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()

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

n = int(input())
arr = tuple(map(int, input().split()))


def cal(i, dst):
  if i == -1:
    return 0

  results = []
  for j in range(n):
    if dst[j]:
      continue
    dst[j] = i
    val = arr[i] * abs(i - j)
    results.append(val + cal(i - 1, dst))
    dst[j] = None

  return max(results)

print(cal(n - 1, [None for _ in range(n)]))


Fixed submission:

def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()

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

n = int(input())
arr = tuple(map(int, input().split()))


def cal(i, dst):
  if i == -1:
    return 0

  results = []
  for j in range(n):
    if dst[j]:
      continue
    next_dst = copy.deepcopy(dst)
    next_dst[j] = i
    val = arr[i] * abs(i - j)
    results.append(val + cal(i - 1, next_dst))

  return max(results)

print(cal(n - 1, [None for _ in range(n)]))


Fixed submission:

def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import itertools

n = int(input())
arr = tuple(map(int, input().split()))

results = []
for dst in itertools.permutations(range(n)):
  results.append(sum(
    [a * abs(i - dst[i]) for i, a in enumerate(arr)]
  ))

print(max(results))


Fixed submission:

def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()