Buggy python submission (verdict: Runtime Error):
N = int(input())

def solve(a, i, prev):
  r = N - len(prev) - i + 1
  p = -i*a
  for j, s in enumerate(prev):
    yield max(p+abs(j-i)*a, s+abs(j+r)*a)
    p = s
  yield s+abs(len(prev)-i)*a

pd = [0]
A = map(int, input().split())
for a,i in sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True):
  pd = [*solve(a,i, pd)]

print(max(prev))


Fixed submission:
from collections import *
from itertools import *

N = int(input())

A = map(int, input().split())
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

prev = {0:0}
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = defaultdict(int)
  curr_max = 0
  for l, p in prev.items():
    r = k-l
    if p + SB - min(l,r)*SA < prev_max:
      continue
    curr[l] = max(curr[l], p+abs(N-i-r)*a)
    curr[l+1] = p+abs(i-l-1)*a
    curr_max = max(curr_max, curr[l], curr[l+1])
  SA -= a
  SB -= b
  prev = curr
  prev_max = curr_max

print(curr_max)

Buggy python submission (verdict: Runtime Error):
N = int(input())

def solve(a, i, prev):
  r = N - len(prev) - i + 1
  p = -i*a
  for j, s in enumerate(prev):
    yield max(p+abs(j-i)*a, s+abs(j+r)*a)
    p = s
  yield s+abs(len(prev)-i)*a

pd = [0]
A = map(int, input().split())
for a,i in sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True):
  pd = [*solve(a,i, prev)]

print(max(prev))


Fixed submission:
from collections import *
from itertools import *

N = int(input())

A = map(int, input().split())
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

prev = {0:0}
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = defaultdict(int)
  curr_max = 0
  for l, p in prev.items():
    r = k-l
    if p + SB - min(l,r)*SA < prev_max:
      continue
    curr[l] = max(curr[l], p+abs(N-i-r)*a)
    curr[l+1] = p+abs(i-l-1)*a
    curr_max = max(curr_max, curr[l], curr[l+1])
  SA -= a
  SB -= b
  prev = curr
  prev_max = curr_max

print(curr_max)

Buggy python submission (verdict: Runtime Error):
from operator import itemgetter as get
N = int(input())

A = map(int, input().split())
SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

def solve(a, i, prev, th):
  pl, pr, ps = 0, -1, 0
  for l, r, s in prev:
    if s < th:
      continue
    if pr == r-1:
      yield l, r-1, max(s+abs(r-i)*a, ps+abs(i-pl)*a)
    else:
      if pl:
        yield pl+1, pr, ps+abs(i-pl)*a
      yield l, r-1, s+abs(r-i)*a
    pl, pr, ps = l, r, s
  yield pl+1, pr, ps+abs(i-pl)*a

prev = [(1, N, 0)]
pm = 0
for j, (a,b,i) in enumerate(ABI):
  M = 0
  prev = [(M:=max(M,s)) and (l, r, s) for l, r, s in solve(a,i, prev, pm-SB)]
  pm = M
  SB -= b

print(pm)


Fixed submission:
from collections import *
from itertools import *

N = int(input())

A = map(int, input().split())
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

prev = {0:0}
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = defaultdict(int)
  curr_max = 0
  for l, p in prev.items():
    r = k-l
    if p + SB - min(l,r)*SA < prev_max:
      continue
    curr[l] = max(curr[l], p+abs(N-i-r)*a)
    curr[l+1] = p+abs(i-l-1)*a
    curr_max = max(curr_max, curr[l], curr[l+1])
  SA -= a
  SB -= b
  prev = curr
  prev_max = curr_max

print(curr_max)

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

N = int(input())

A = map(int, input().split())
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

prev = {0:0}
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = defaultdict(int)
  for l, p in prev.items():
    r = k-l
    if p + SB - (k-1)*SA < prev_max:
      continue
    curr[l] = max(curr[l], p+abs(N-i-r)*a)
    curr[l+1] = p+abs(i-l-1)*a
  SA -= a
  SB -= b
  prev = curr
  prev_max = max(prev.values())

print(prev_max)


Fixed submission:
from collections import *
from itertools import *

N = int(input())

A = map(int, input().split())
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

prev = {0:0}
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = defaultdict(int)
  curr_max = 0
  for l, p in prev.items():
    r = k-l
    if p + SB - min(l,r)*SA < prev_max:
      continue
    curr[l] = max(curr[l], p+abs(N-i-r)*a)
    curr[l+1] = p+abs(i-l-1)*a
    curr_max = max(curr_max, curr[l], curr[l+1])
  SA -= a
  SB -= b
  prev = curr
  prev_max = curr_max

print(curr_max)

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

N = int(input())

A = map(int, input().split())
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a)|1 and (SA:=SA+a)|1 and (SB:=SB+b)|1 and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

prev = {(0,0):0}
prev_max = 0
for a, b, i in ABI:
  curr = defaultdict(int)
  curr_max = 0
  for (l,r), p in prev.items():
    if p + SB - min(l,r)*SA < prev_max:
      continue
    curr[l,r+1] = max(curr[l,r+1], p+abs(N-i-r)*a)
    curr[l+1,r] = max(curr[l+1,r], p+abs(i-l-1)*a)
    curr_max = max(curr_max, curr[l,r+1], curr[l+1,r])
  SA -= a
  SB -= b
  prev = curr
  prev_max = curr_max

print(curr_max)


Fixed submission:
from collections import *
from itertools import *

N = int(input())

A = map(int, input().split())
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

prev = {0:0}
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = defaultdict(int)
  curr_max = 0
  for l, p in prev.items():
    r = k-l
    if p + SB - min(l,r)*SA < prev_max:
      continue
    curr[l] = max(curr[l], p+abs(N-i-r)*a)
    curr[l+1] = p+abs(i-l-1)*a
    curr_max = max(curr_max, curr[l], curr[l+1])
  SA -= a
  SB -= b
  prev = curr
  prev_max = curr_max

print(curr_max)

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

N = int(input())

A = map(int, input().split())

ABI = sorted(((a, max(N-i, i-1)*a, i) for i, a in enumerate(A, 1)), reverse=True)
SA, SB = map(sum, islice(zip(*ABI), 0, 2))

prev = {(0,0):0}
prev_max = 0
for a, b, i in ABI:
  curr = defaultdict(int)
  curr_max = 0
  for (l,r), p in prev.items():
    if p + SB - min(l,r)*SA < prev_max:
      continue
    curr[l,r+1] = max(curr[l,r+1], p+abs(N-i-r)*a)
    curr[l+1,r] = max(curr[l+1,r], p+abs(i-l-1)*a)
    curr_max = max(curr_max, curr[l,r+1], curr[l+1,r])
  SA -= a
  SB -= b
  prev = curr
  prev_max = curr_max

print(curr_max)


Fixed submission:
from collections import *
from itertools import *

N = int(input())

A = map(int, input().split())
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

prev = {0:0}
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = defaultdict(int)
  curr_max = 0
  for l, p in prev.items():
    r = k-l
    if p + SB - min(l,r)*SA < prev_max:
      continue
    curr[l] = max(curr[l], p+abs(N-i-r)*a)
    curr[l+1] = p+abs(i-l-1)*a
    curr_max = max(curr_max, curr[l], curr[l+1])
  SA -= a
  SB -= b
  prev = curr
  prev_max = curr_max

print(curr_max)