Problem:


Score : 500 points

Problem Statement

There are N children standing in a line from left to right. The activeness of the i-th child from the left is A_i.

You can rearrange these children just one time in any order you like.

When a child who originally occupies the x-th position from the left in the line moves to the y-th position from the left, that child earns A_x \times |x-y| happiness points.

Find the maximum total happiness points the children can earn.

Constraints

2 \leq N \leq 2000

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum total happiness points the children can earn.

Sample Input 1

4
1 3 4 2

Sample Output 1

20

If we move the 1-st child from the left to the 3-rd position from the left, the 2-nd child to the 4-th position, the 3-rd child to the 1-st position, and the 4-th child to the 2-nd position, the children earns 1 \times |1-3|+3 \times |2-4|+4 \times |3-1|+2 \times |4-2|=20 happiness points in total.

Sample Input 2

6
5 5 6 1 1 1

Sample Output 2

58

Sample Input 3

6
8 6 9 1 2 1

Sample Output 3

85



Sample input:
4
1 3 4 2


Sample output:
20

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
a = int(input())
# スペース区切りの整数の入力
strs = input().split()

nums = []
only_nums = []
for i in range(a):
    v = int(strs[i])
    nums.append((i, v, True))
    only_nums.append(v)

sorted_nums = sorted(only_nums, reverse=True)
# print(sorted_nums)

# print(nums)

# res[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態の(スコア最大値, 移動済のものを除いたnums)とする
res = []
for i in range(a + 1):
    ls = []
    for j in range(a + 1):
        ls.append((0, []))
    res.append(ls)

for i in range(a + 1):
    # print("i in range(a)")
    # print(i)
    # print(a)
    # print("i in range(a)")
    if i == 0:
        continue
    if i == 1:
        max_num = sorted_nums[0]
        sorted_nums = sorted_nums[1:]
        # x,y = 0,1にした場合
        max_num_idx_min = -1
        nums_clone = nums.copy()
        for x in nums_clone:
            if x[1] == max_num:
                max_num_idx_min = x[0]
                break
        nums_clone[max_num_idx_min] = (nums_clone[max_num_idx_min][0], nums_clone[max_num_idx_min][1], False)
        res[0][1] = (max_num * (a - 1 - max_num_idx_min), nums_clone)

        # x,y = 1,0にした場合
        max_num_idx_max = -1
        nums_clone = nums.copy()
        nums_clone.reverse()
        for x in nums_clone:
            if x[1] == max_num:
                max_num_idx_max = x[0]
                break
        nums_clone.reverse()
        nums_clone[max_num_idx_max] = (nums_clone[max_num_idx_max][0], nums_clone[max_num_idx_max][1], False)
        res[1][0] = (max_num * max_num_idx_max, nums_clone)
        # print(res[1][0][0])
        # print(res[0][1][0])
    # elif i == 2:
    #     # x,y = 2,0にした場合
    #     nums_clone = res[1][0][1].copy()
    #     # for x in res[1][0][1]:
    #     #     nums_clone.remove(x)
    #     max_num = max([x[1] for x in nums_clone])
    #     max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
    #     nums_clone.remove((max(max_num_idxes), max_num))
    #     res[2][0] = (max_num * abs(max(max_num_idxes) - 1) + res[1][0][0], nums_clone)
    #
    #     # x,y = 0,2にした場合
    #     nums_clone = res[0][1][1].copy()
    #     max_num = max([x[1] for x in nums_clone])
    #     max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
    #     nums_clone.remove((min(max_num_idxes), max_num))
    #     res[0][2] = (max_num * abs(a - 1 - min(max_num_idxes) - 1) + res[0][1][0], nums_clone)
    #
    #     # print(res[2][0][0])
    #     # print(res[0][2][0])
    #
    #     # x,y = 1,1にした場合
    #     # from 1,0
    #     nums_clone = res[1][0][1].copy()
    #     max_num = max([x[1] for x in nums_clone])
    #     max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
    #     nums_clone.remove((min(max_num_idxes), max_num))
    #     from_1_0 = (max_num * abs(a - 1 - min(max_num_idxes)) + res[1][0][0], nums_clone)
    #     # from 0,1
    #     nums_clone = res[0][1][1].copy()
    #     max_num = max([x[1] for x in nums_clone])
    #     max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
    #     nums_clone.remove((max(max_num_idxes), max_num))
    #     from_0_1 = (max_num * abs(max(max_num_idxes)) + res[0][1][0], nums_clone)
    #     if from_1_0[0] < from_0_1[0]:
    #         res[1][1] = from_0_1
    #     else:
    #         res[1][1] = from_1_0
    #
    #     # print(res[1][1][0])

    else:
        # # x,y = i,0にした場合
        # nums_clone = res[i-1][0][1].copy()
        # max_num = max([x[1] for x in nums_clone])
        # target_idx = max([x[0] for x in nums_clone if x[1] == max_num])
        # nums_clone.remove((target_idx, max_num))
        # res[i][0] = (max_num * abs(target_idx - (i - 1)) + res[i-1][0][0], nums_clone)
        #
        # # print(res[i][0][0])
        #
        # # x,y = 0,iにした場合
        # nums_clone = res[0][i-1][1].copy()
        # max_num = max([x[1] for x in nums_clone])
        # target_idx = min([x[0] for x in nums_clone if x[1] == max_num])
        # nums_clone.remove((target_idx, max_num))
        # res[0][i] = (max_num * abs(a - 1 - target_idx - (i - 1)) + res[0][i-1][0], nums_clone)
        #
        # # print(res[0][i][0])

        # print(sorted_nums)
        max_num = sorted_nums[0]
        sorted_nums = sorted_nums[1:]
        # x,y = i-j,j(0 ≤ j ≤ i)にした場合を考える
        # i - 1のresについてそれぞれ次の状態を考えていく
        # res[i-1][0], res[i-2][1], res[i-3][2], ... , res[i-1-j][j], ... , res[0][i-1]
        ls_j = []
        for j in range(i):
            # from i-j-1,j to i-j,j (最大活性のものを左に移動)
            max_num_idx_max = -1
            nums_clone = res[i - j - 1][j][1].copy()
            nums_clone.reverse()
            for x in nums_clone:
                if x[1] == max_num and x[2]:
                    max_num_idx_max = x[0]
                    break
            nums_clone.reverse()
            score_left = max_num * abs(max_num_idx_max - (i - j - 1)) + res[i - j - 1][j][0]
            nums_clone[max_num_idx_max] = (nums_clone[max_num_idx_max][0], nums_clone[max_num_idx_max][1], False)
            left = (score_left, nums_clone)
            # res[j-1][i-j+1] = (score_left, nums_clone)

            # from i-j-1,j to i-j-1,j+1 (最大活性のものを右に移動)
            max_num_idx_min = -1
            nums_clone = res[i - j - 1][j][1].copy()
            for x in nums_clone:
                if x[1] == max_num and x[2]:
                    max_num_idx_min = x[0]
                    break
            score_right = max_num * abs(a - 1 - max_num_idx_min - j) + res[i - j - 1][j][0]
            nums_clone[max_num_idx_min] = (nums_clone[max_num_idx_min][0], nums_clone[max_num_idx_min][1], False)
            right = (score_right, nums_clone)
            # res[j-1][i-j+1] = (score_right, nums_clone)

            ls_j.append((left, right))

        # iのres (res[i-j][j]) についてそれぞれleftとrightのどちらがより高いスコアかを考えて値を決定する
        for j in range(i + 1):
            # i,0は決定済
            if j == 0:
                res[i - j][j] = ls_j[0][0]
            # 0,iは決定済
            elif j == i:
                res[i - j][j] = ls_j[i - 1][1]
            else:
                # 木のイメージで左側から伸びてきた枝
                from_left = ls_j[j - 1][1]
                # 木のイメージで右側から伸びてきた枝
                from_right = ls_j[j][0]
                if from_left[0] < from_right[0]:
                    res[i - j][j] = from_right
                else:
                    res[i - j][j] = from_left
            #
            # nums_clone = res[j-1][i-j][1].copy()
            # max_num = max([x[1] for x in nums_clone])
            # target_idx = max([x[0] for x in nums_clone if x[1] == max_num])
            # nums_clone.remove((target_idx, max_num))
            # # from_a = (max_num * abs(a - 1 - min(max_num_idxes) - (i-j-1)) + res[j-1][i-j][0], res[j-1][i-j][1] + [(min(max_num_idxes), max_num)])
            # from_a = (max_num * abs(target_idx - (j-1)) + res[j-1][i-j][0], nums_clone)
            # # from j,i-j-1
            # nums_clone = res[j][i-j-1][1].copy()
            # max_num = max([x[1] for x in nums_clone])
            # target_idx = min([x[0] for x in nums_clone if x[1] == max_num])
            # nums_clone.remove((target_idx, max_num))
            # # from_b = (max_num * abs(max(max_num_idxes) - (j-1)) + res[j][i-j-1][0], res[j][i-j-1][1] + [(max(max_num_idxes), max_num)])
            # from_b = (max_num * abs(a - 1 - target_idx - (i-j-1)) + res[j][i-j-1][0], nums_clone)
            # if from_a < from_b:
            #     res[j][i-j] = from_b
            # else:
            #     res[j][i-j] = from_a
            # # print(res[j][i-j][0])

    if i == a:
        result = []
        for j in range(a + 1):
            result.append(res[j][i - j][0])
        # print(result)
        print(max(result))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
a = int(input())
# スペース区切りの整数の入力
strs = input().split()

nums = []
for i in range(a):
    nums.append((i, int(strs[i])))

# print(nums)

# res[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態の(スコア最大値, 移動済のものを除いたnums)とする
res = []
for i in range(a+1):
    ls = []
    for j in range(a+1):
        ls.append((0, []))
    res.append(ls)

for i in range(a+1):
    # print("i in range(a)")
    # print(i)
    # print(a)
    # print("i in range(a)")
    if i == 0:
        continue
    if i == 1:
        max_num = max([x[1] for x in nums])
        max_num_idxes = [x[0] for x in nums if x[1] == max_num]
        # x,y = 1,0にした場合
        nums_clone = nums.copy()
        nums_clone.remove((max(max_num_idxes), max_num))
        res[1][0] = (max_num * max(max_num_idxes), nums_clone)
        # x,y = 0,1にした場合
        nums_clone = nums.copy()
        nums_clone.remove((min(max_num_idxes), max_num))
        res[0][1] = (max_num * (a - 1 - min(max_num_idxes)), nums_clone)

        # print(res[1][0][0])
        # print(res[0][1][0])
    elif i == 2:
        # x,y = 2,0にした場合
        nums_clone = res[1][0][1].copy()
        # for x in res[1][0][1]:
        #     nums_clone.remove(x)
        max_num = max([x[1] for x in nums_clone])
        max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
        nums_clone.remove((max(max_num_idxes), max_num))
        res[2][0] = (max_num * abs(max(max_num_idxes) - 1) + res[1][0][0], nums_clone)

        # x,y = 0,2にした場合
        nums_clone = res[0][1][1].copy()
        max_num = max([x[1] for x in nums_clone])
        max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
        nums_clone.remove((min(max_num_idxes), max_num))
        res[0][2] = (max_num * abs(a - 1 - min(max_num_idxes) - 1) + res[0][1][0], nums_clone)

        # print(res[2][0][0])
        # print(res[0][2][0])

        # x,y = 1,1にした場合
        # from 1,0
        nums_clone = res[1][0][1].copy()
        max_num = max([x[1] for x in nums_clone])
        max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
        nums_clone.remove((min(max_num_idxes), max_num))
        from_1_0 = (max_num * abs(a - 1 - min(max_num_idxes)) + res[1][0][0], nums_clone)
        # from 0,1
        nums_clone = res[0][1][1].copy()
        max_num = max([x[1] for x in nums_clone])
        max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
        nums_clone.remove((max(max_num_idxes), max_num))
        from_0_1 = (max_num * abs(max(max_num_idxes)) + res[0][1][0], nums_clone)
        if from_1_0[0] < from_0_1[0]:
            res[1][1] = from_0_1
        else:
            res[1][1] = from_1_0

        # print(res[1][1][0])

    else:
        # x,y = i,0にした場合
        nums_clone = res[i-1][0][1].copy()
        max_num = max([x[1] for x in nums_clone])
        target_idx = max([x[0] for x in nums_clone if x[1] == max_num])
        nums_clone.remove((target_idx, max_num))
        res[i][0] = (max_num * abs(target_idx - (i - 1)) + res[i-1][0][0], nums_clone)

        # print(res[i][0][0])

        # x,y = 0,iにした場合
        nums_clone = res[0][i-1][1].copy()
        max_num = max([x[1] for x in nums_clone])
        target_idx = min([x[0] for x in nums_clone if x[1] == max_num])
        nums_clone.remove((target_idx, max_num))
        res[0][i] = (max_num * abs(a - 1 - target_idx - (i - 1)) + res[0][i-1][0], nums_clone)

        # print(res[0][i][0])

        # x,y = j,i-jにした場合
        for j in range(1, i):
            # from j-1,i-j
            nums_clone = res[j-1][i-j][1].copy()
            max_num = max([x[1] for x in nums_clone])
            target_idx = max([x[0] for x in nums_clone if x[1] == max_num])
            nums_clone.remove((target_idx, max_num))
            # from_a = (max_num * abs(a - 1 - min(max_num_idxes) - (i-j-1)) + res[j-1][i-j][0], res[j-1][i-j][1] + [(min(max_num_idxes), max_num)])
            from_a = (max_num * abs(target_idx - (j-1)) + res[j-1][i-j][0], nums_clone)
            # from j,i-j-1
            nums_clone = res[j][i-j-1][1].copy()
            max_num = max([x[1] for x in nums_clone])
            target_idx = min([x[0] for x in nums_clone if x[1] == max_num])
            nums_clone.remove((target_idx, max_num))
            # from_b = (max_num * abs(max(max_num_idxes) - (j-1)) + res[j][i-j-1][0], res[j][i-j-1][1] + [(max(max_num_idxes), max_num)])
            from_b = (max_num * abs(a - 1 - target_idx - (i-j-1)) + res[j][i-j-1][0], nums_clone)
            if from_a < from_b:
                res[j][i-j] = from_b
            else:
                res[j][i-j] = from_a
            # print(res[j][i-j][0])

    if i == a:
        result = []
        for j in range(a+1):
            result.append(res[j][i-j][0])
        # print(result)
        print(max(result))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
a = int(input())
# スペース区切りの整数の入力
strs = input().split()

nums = []
for i in range(a):
    nums.append((i, int(strs[i])))

# print(nums)

# res[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態の(スコア最大値, 移動済のもの)をタプル化したものとする
res = []
for i in range(a+1):
    ls = []
    for j in range(a+1):
        ls.append((0, []))
    res.append(ls)

for i in range(a+1):
    # print("i in range(a)")
    # print(i)
    # print(a)
    # print("i in range(a)")
    if i == 0:
        continue
    if i == 1:
        max_num = max([x[1] for x in nums])
        max_num_idxes = [x[0] for x in nums if x[1] == max_num]
        # x,y = 1,0にした場合
        res[1][0] = (max_num * max(max_num_idxes), [(max(max_num_idxes), max_num)])
        # x,y = 0,1にした場合
        res[0][1] = (max_num * (a - 1 - min(max_num_idxes)), [(min(max_num_idxes), max_num)])

        # print(res[1][0][0])
        # print(res[0][1][0])
    elif i == 2:
        # x,y = 2,0にした場合
        nums_clone = nums.copy()
        for x in res[1][0][1]:
            nums_clone.remove(x)
        max_num = max([x[1] for x in nums_clone])
        max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
        res[2][0] = (max_num * abs(max(max_num_idxes) - 1) + res[1][0][0], res[1][0][1] + [(max(max_num_idxes), max_num)])

        # x,y = 0,2にした場合
        nums_clone = nums.copy()
        for x in res[0][1][1]:
            nums_clone.remove(x)
        max_num = max([x[1] for x in nums_clone])
        max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
        res[0][2] = (max_num * abs(a - 1 - min(max_num_idxes) - 1) + res[0][1][0], res[0][1][1] + [(min(max_num_idxes), max_num)])

        # print(res[2][0][0])
        # print(res[0][2][0])

        # x,y = 1,1にした場合
        # from 1,0
        nums_clone = nums.copy()
        for x in res[1][0][1]:
            nums_clone.remove(x)
        max_num = max([x[1] for x in nums_clone])
        max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
        from_1_0 = (max_num * abs(a - 1 - min(max_num_idxes)) + res[1][0][0], res[1][0][1] + [(min(max_num_idxes), max_num)])
        # from 0,1
        nums_clone = nums.copy()
        for x in res[0][1][1]:
            nums_clone.remove(x)
        max_num = max([x[1] for x in nums_clone])
        max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
        from_0_1 = (max_num * abs(max(max_num_idxes)) + res[0][1][0], res[0][1][1] + [(max(max_num_idxes), max_num)])
        if from_1_0[0] < from_0_1[0]:
            res[1][1] = from_0_1
        else:
            res[1][1] = from_1_0

        # print(res[1][1][0])

    else:
        # x,y = i,0にした場合
        nums_clone = nums.copy()
        for x in res[i-1][0][1]:
            nums_clone.remove(x)
        max_num = max([x[1] for x in nums_clone])
        max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
        res[i][0] = (max_num * abs(max(max_num_idxes) - (i - 1)) + res[i-1][0][0], res[i-1][0][1] + [(max(max_num_idxes), max_num)])

        # print(res[i][0][0])

        # x,y = 0,iにした場合
        nums_clone = nums.copy()
        for x in res[0][i-1][1]:
            nums_clone.remove(x)
        max_num = max([x[1] for x in nums_clone])
        max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
        res[0][i] = (max_num * abs(a - 1 - min(max_num_idxes) - (i - 1)) + res[0][i-1][0], res[0][i-1][1] + [(min(max_num_idxes), max_num)])

        # print(res[0][i][0])

        # x,y = j,i-jにした場合
        for j in range(1, i):
            # from j-1,i-j
            nums_clone = nums.copy()
            for x in res[j-1][i-j][1]:
                nums_clone.remove(x)
            max_num = max([x[1] for x in nums_clone])
            max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
            # from_a = (max_num * abs(a - 1 - min(max_num_idxes) - (i-j-1)) + res[j-1][i-j][0], res[j-1][i-j][1] + [(min(max_num_idxes), max_num)])
            from_a = (max_num * abs(max(max_num_idxes) - (j-1)) + res[j-1][i-j][0], res[j-1][i-j][1] + [(max(max_num_idxes), max_num)])
            # from j,i-j-1
            nums_clone = nums.copy()
            for x in res[j][i-j-1][1]:
                nums_clone.remove(x)
            max_num = max([x[1] for x in nums_clone])
            max_num_idxes = [x[0] for x in nums_clone if x[1] == max_num]
            # from_b = (max_num * abs(max(max_num_idxes) - (j-1)) + res[j][i-j-1][0], res[j][i-j-1][1] + [(max(max_num_idxes), max_num)])
            from_b = (max_num * abs(a - 1 - min(max_num_idxes) - (i-j-1)) + res[j][i-j-1][0], res[j][i-j-1][1] + [(min(max_num_idxes), max_num)])
            if from_a < from_b:
                res[j][i-j] = from_b
            else:
                res[j][i-j] = from_a
            # print(res[j][i-j][0])

    if i == a:
        result = []
        for j in range(a+1):
            result.append(res[j][i-j][0])
        # print(result)
        print(max(result))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
# print(A)
A = [[A[i],i] for i in range(N)]
A.sort(reverse=True)
# print("A :",A)
dp = [[0]*(N+1) for _ in range(N+1)]
# print(dp)

#dp[x][y] : x人は Ai*(i-pi),y人は Ai*(pi-i)
#           piは 0,1,2...   piはN-1,N-2,N-3,,
dp[0][0] = 0
# y = 0
for x in range(1,N+1):
    dp[x][0] = dp[x-1][0]+A[x-1][0]*(A[x-1][1]-x+1)
    # print(x,dp)
# x = 0
for y in range(1,N+1):
    dp[0][y] = dp[0][y-1]+A[y-1][0]*(N-y - A[y-1][1])
    # print(x,dp)
    
for x in range(1,N):
    for y in range(1,N+1-x):
        dp[x][y] = max(dp[x-1][y] + A[x+y-1][0]*(A[x+y-1][1]+1 - x), dp[x][y-1] + A[x+y-1][0]*(N-y - A[x+y-1][1]))
# print(dp)

c = 0
for i in range(N):
    if c < dp[i][N-i]:
        c = dp[i][N-i]
print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys

def calc(A, j, L, R):
    a, i = A[j]
    J = j + 1
    if L == R:
        s = a * abs(L - i)
    else:
        s = a * abs(L - i) + calc(A, J, L + 1, R)
        t = a * abs(R - i) + calc(A, J, L, R - 1)
        if s < t:
            s = t
    return s


def main():
    N = int(input())

    sys.setrecursionlimit(N + 10)

    A = []
    for i, a in enumerate(map(int, input().split(' '))):
        A.append((a, i))
    A.sort(reverse=True)

    print(calc(A, 0, 0, N - 1))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import functools
import sys

sys.setrecursionlimit(10 ** 9)

input()

arr = list(sorted([(v, idx) for idx, v in enumerate(map(int, input().split()))], reverse=True))


@functools.lru_cache(maxsize=None)
def dp(l, r, idx):
    if idx == len(arr):
        return 0

    left = abs(arr[idx][1] - l) * arr[idx][0] + dp(l + 1, r, idx + 1)
    right = abs(arr[idx][1] - r) * arr[idx][0] + dp(l, r - 1, idx + 1)

    return max(left, right)


print(dp(0, len(arr) - 1, 0))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
for i in range(n):
    a[i] = (a[i], i+1)
a.sort(reverse=True, key=lambda x: x[0])

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

for i in range(1, n+1):
    ans = 0
    for x in range(i+1):
        y = i-x
        activity = a[i-1][0]
        ind = a[i-1][1]
        val1, val2 = 0, 0
        if y-1 >= 0:
            val1 = dp[x][y-1] + activity*(abs(n-(y-1)-ind))
        if x-1 >= 0:
            val2 = dp[x-1][y] + activity*(abs(ind-x))
        dp[x][y] = max(val1, val2)
        if i == n and dp[x][y] > ans:
            ans = dp[x][y]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
for i in range(n):
    a[i] = (a[i], i+1)
a.sort(reverse=True)

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

ans = 0
for i in range(1, n+1):
    for x in range(i+1):
        y = i-x
        activity = a[i-1][0]
        ind = a[i-1][1]
        val1, val2 = 0, 0
        if y-1 >= 0:
            val1 = dp[x][y-1] + activity*(abs(n-(y-1)-ind))
        if x-1 >= 0:
            val2 = dp[x-1][y] + activity*(abs(ind-x))
        dp[x][y] = max(val1, val2)
        if i == n and dp[x][y] > ans:
            ans = dp[x][y]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
	N = int(input())
	Als = [int(a) for a in input().split()]
	lst = []
	for i in range(N):
		lst.append([Als[i],i+1])

	lst.sort(reverse = True)

	DP = [[0] * (N+1) for _ in range(N+1)]

	ans = 0

	for i in range(1,N+1):
		a = lst[i-1][0]
		index = lst[i-1][1]
		vx = DP[i-1][0] + a * abs(index-i)
		vy = DP[0][i-1] + a * abs(index-(N-i+1))
		DP[i][0] = vx
		DP[0][i] = vy
		if ans < vx:
			ans = vx
		if ans < vy:
			ans = vy

	for i in range(1,N+1):
		for j in range(1,N+1):
			if i + j <= N:
				a = lst[i+j-1][0]
				index = lst[i+j-1][1]
				v = max(DP[i-1][j] + a * abs(index-i),DP[i][j-1] + a * abs(index-(N-j+1)))
				DP[i][j] = v
				if ans < v:
					ans = v
			else:
				break

	print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n=int(input())
a_=list(map(int,input().split()))
#n=4
#a_=[1,3,4,2]
a=[]
for i,ai in enumerate(a_):
      a.append([1+i,ai])
a.sort(key=lambda x:x[1],reverse=True)
dp=defaultdict(lambda:0)
dp[(0,1)]=max(a[0][1]*(n-a[0][0]),0)
dp[(1,0)]=max(a[0][1]*(a[0][0]-1),0)
for i in range(2,n+1):#i人目の幼児。a[i-1]
      for x in range(i+1):
            y=i-x
            if x==0:
                  dp[(x,y)]=dp[(x,y-1)]+a[i-1][1]*(n-a[i-1][0]-(y-1))
            elif y==0:
                  dp[(x,y)]=dp[(x-1,y)]+a[i-1][1]*(a[i-1][0]-1-(x-1))
            else:
                  dp[(x,y)]=max(dp[(x-1,y)]+a[i-1][1]*(a[i-1][0]-1-(x-1)),dp[(x,y-1)]+a[i-1][1]*(n-a[i-1][0]-(y-1)))
ans=0
for i in range(n+1):
      ans=max(ans,dp[(i,n-i)])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = sorted([(a, p) for p, a in enumerate(A)], reverse=True)
dp = [[0]*(i+1) for i in range(N+1)]
for z in range(N):
    for y in range(z+1):
        dp[z+1][y] = max(A[z][0]*(A[z][1]-(z-y))+dp[z][y],dp[z+1][y])
        dp[z+1][y+1]= A[z][0]*((N-y-1)-A[z][1])+dp[z][y]
print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A_list = map(int, input().split())

# [活発度, もとの番号] のリストを降順に並べる
A_list = [[A, index] for index, A in enumerate(A_list)]
A_list.sort(reverse=True)

# print(A_list)

dp = [[0 for i in range(N+1)] for j in range(N+1)]

# right = 0
for left in range(N):
    activity = A_list[left][0]
    distance_from_left = abs(left - A_list[left][1])
    dp[left + 1][0] = dp[left][0] + activity * distance_from_left

# left = 0
for right in range(N):
    activity = A_list[right][0]
    distance_from_right = abs(N - 1 - right - A_list[right][1])
    dp[0][right + 1] = dp[0][right] + activity * distance_from_right

for left in range(1, N + 1):
    for right in range(1, N - left + 1):
        activity = A_list[left + right - 1][0]
        distance_from_left = abs((left - 1) - A_list[left + right - 1][1])
        distance_from_right = abs((N - right) - A_list[left + right - 1][1])
        score_if_appended_to_left\
            = dp[left - 1][right] + activity * distance_from_left
        score_if_appended_to_right\
            = dp[left][right - 1] + activity * distance_from_right
        dp[left][right] = max(score_if_appended_to_left,
                              score_if_appended_to_right)
        # print(dp)
print(np.max(dp))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A_list = map(int, input().split())

# [活発度, もとの番号] のリストを降順に並べる
A_list = [[A, index] for index, A in enumerate(A_list)]
A_list.sort(reverse=True)

# print(A_list)

dp = np.zeros((N+1, N+1), int)
# print(dp)

# right = 0
for left in range(N):
    activity = A_list[left][0]
    distance_from_left = abs(left - A_list[left][1])
    dp[left + 1][0] = dp[left][0] + activity * distance_from_left

# left = 0
for right in range(N):
    activity = A_list[right][0]
    distance_from_right = abs(N - 1 - right - A_list[right][1])
    dp[0][right + 1] = dp[0][right] + activity * distance_from_right

for left in range(1, N + 1):
    for right in range(1, N - left + 1):
        activity = A_list[left + right - 1][0]
        distance_from_left = abs((left - 1) - A_list[left + right - 1][1])
        distance_from_right = abs((N - right) - A_list[left + right - 1][1])
        score_if_appended_to_left\
            = dp[left - 1][right] + activity * distance_from_left
        score_if_appended_to_right\
            = dp[left][right - 1] + activity * distance_from_right
        dp[left][right] = max(score_if_appended_to_left,
                              score_if_appended_to_right)
        # print(dp)
print(np.max(dp))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
table = []
 
for i, a in enumerate(A):
    table.append([a,i])
table.sort()
dp = np.zeros((N+1,N+1))
for i in range(1,N+1):
    baby,pos = table.pop()
    dp[i][0]=dp[i-1][0]+baby*abs(pos-i+1)
    dp[0][i] = dp[0][i-1] + baby * abs(pos-(N-i))
    for x in range(1,i):
        y = i-x
        dp[x][y]= max(dp[x-1][y] + baby * abs(pos-x+1),dp[x][y-1] + baby * abs(pos-(N-y)))
print(int(max(dp[k][N-k] for k in range(N+1))))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
table = []
 
for i, a in enumerate(A):
    table.append([a,i])
table.sort()
dp = [[0 for i in range(N+1)]for j in range(N+1)]
for i in range(1,N+1):
    baby,pos = table.pop()
    dp[i][0]=dp[i-1][0]+baby*abs(pos-i+1)
    dp[0][i] = dp[0][i-1] + baby * abs(pos-(N-i))
    for x in range(1,i):
        y = i-x
        dp[x][y]=  max(dp[x-1][y] + baby * abs(pos-x+1),dp[x][y-1] + baby * abs(pos-(N-y)))
print(max(dp[k][N-k] for k in range(N+1)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A_list = map(int, input().split())

# [活発度, もとの番号] のリストを降順に並べる
A_list = [[A, index] for index, A in enumerate(A_list)]
A_list.sort(reverse=True)

# print(A_list)

dp = np.zeros((N+1, N+1), int)
# print(dp)
for left in range(0, N):
    for right in range(0, N - left):
        # print(f'left, righte: { left, right }')
        # print(A_list[left + right - 1][0])
        activity = A_list[left + right][0]
        distance_from_left = A_list[left + right][1] - left
        # print(f'distance_from_left: { distance_from_left }')
        distance_from_right = (N - 1 - right) - A_list[left + right][1]
        # print(f'distance_from_right: { distance_from_right }')
        dp[left + 1][right]\
            = max(dp[left + 1][right],
                  dp[left][right] + activity * distance_from_left)
        dp[left][right + 1]\
            = max(dp[left][right + 1],
                  dp[left][right] + activity * distance_from_right)
        # print('dp---')
        # print(dp)
        # print('---dp')
# print(dp)
print(np.max(dp))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A_list = map(int, input().split())

# [活発度, もとの番号] のリストを降順に並べる
A_list = [[A, index] for index, A in enumerate(A_list)]
A_list.sort(reverse=True)

# print(A_list)

dp = np.zeros((N+2, N+2), int)
# print(dp)
for left in range(0, N):
    for right in range(0, N - left):
        # print(f'left, righte: { left, right }')
        # print(A_list[left + right - 1][0])
        activity = A_list[left + right][0]
        distance_from_left = A_list[left + right][1] - left
        # print(f'distance_from_left: { distance_from_left }')
        distance_from_right = (N - 1 - right) - A_list[left + right][1]
        # print(f'distance_from_right: { distance_from_right }')
        dp[left + 1][right]\
            = max(dp[left + 1][right],
                  dp[left][right] + activity * distance_from_left)
        dp[left][right + 1]\
            = max(dp[left][right + 1],
                  dp[left][right] + activity * distance_from_right)
        # print('dp---')
        # print(dp)
        # print('---dp')
# print(dp)
print(np.max(dp))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))

B=[(j,i) for i,j in enumerate(A)]
B.sort(reverse=True)

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

c=0
for v,k in B:
    for i in range(c+1):
        dp[i+1][c-i]=max(dp[i+1][c-i],dp[i][c-i]+abs(v*(k-i)))
        dp[i][c-i+1]=max(dp[i][c-i+1],dp[i][c-i]+abs(v*(N-(c-i)-k-1)))
    c+=1

ans=0
for i in range(N):
    ans=max(ans,dp[i][N-i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))

d={}

for i,j in enumerate(A):
    d[i]=j

d=sorted(d.items(),key=lambda x:x[1],reverse=True)

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

c=0
for k,v in d:
    for i in range(c+1):
        dp[i+1][c-i]=max(dp[i+1][c-i],dp[i][c-i]+abs(v*(k-i)))
        dp[i][c-i+1]=max(dp[i][c-i+1],dp[i][c-i]+abs(v*(N-(c-i)-k-1)))
    c+=1

ans=0
for i in range(N):
    ans=max(ans,dp[i][N-i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def get_result(data):
    N = data[0][0]
    A = data[1]
    dp = [[0]*(N+1) for _ in range(N+1)]
    B = [[A[i], i] for i in range(N)]
    B = sorted(B, reverse=True)
    for i in range(N):
        for j in range(N-i):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + B[i+j][0] * (B[i+j][1] - i))
            dp[i][j+1] = max(dp[i][j+1], dp[i][j] + B[i+j][0] * ((N-1-j) - B[i+j][1]))

    res = 0
    for i in range(N):
        res = max(res, dp[i][N-i])
    return res


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)