Genius (Codeforces 1497D)
Tags: DP, bitmasks

Please note the non-standard memory limit.There are $$$n$$$ problems numbered with integers from $$$1$$$ to $$$n$$$. $$$i$$$-th problem has the complexity $$$c_i = 2^i$$$, tag $$$tag_i$$$ and score $$$s_i$$$.After solving the problem $$$i$$$ it's allowed to solve problem $$$j$$$ if and only if $$$\text{IQ} < |c_i - c_j|$$$ and $$$tag_i \neq tag_j$$$. After solving it your $$$\text{IQ}$$$ changes and becomes $$$\text{IQ} = |c_i - c_j|$$$ and you gain $$$|s_i - s_j|$$$ points.Any problem can be the first. You can solve problems in any order and as many times as you want.Initially your $$$\text{IQ} = 0$$$. Find the maximum number of points that can be earned.

Input: The first line contains a single integer $$$t$$$ $$$(1 \le t \le 100)$$$  — the number of test cases. The first line of each test case contains an integer $$$n$$$ $$$(1 \le n \le 5000)$$$  — the number of problems.The second line of each test case contains $$$n$$$ integers $$$tag_1, tag_2, \ldots, tag_n$$$ $$$(1 \le tag_i \le n)$$$  — tags of the problems.The third line of each test case contains $$$n$$$ integers $$$s_1, s_2, \ldots, s_n$$$ $$$(1 \le s_i \le 10^9)$$$  — scores of the problems.It's guaranteed that sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output: For each test case print a single integer  — the maximum number of points that can be earned.

Note: In the first test case optimal sequence of solving problems is as follows:   $$$1 \rightarrow 2$$$, after that total score is $$$5$$$ and $$$\text{IQ} = 2$$$  $$$2 \rightarrow 3$$$, after that total score is $$$10$$$ and $$$\text{IQ} = 4$$$  $$$3 \rightarrow 1$$$, after that total score is $$$20$$$ and $$$\text{IQ} = 6$$$  $$$1 \rightarrow 4$$$, after that total score is $$$35$$$ and $$$\text{IQ} = 14$$$ In the second test case optimal sequence of solving problems is as follows:   $$$1 \rightarrow 2$$$, after that total score is $$$5$$$ and $$$\text{IQ} = 2$$$  $$$2 \rightarrow 3$$$, after that total score is $$$10$$$ and $$$\text{IQ} = 4$$$  $$$3 \rightarrow 4$$$, after that total score is $$$15$$$ and $$$\text{IQ} = 8$$$  $$$4 \rightarrow 1$$$, after that total score is $$$35$$$ and $$$\text{IQ} = 14$$$ In the third test case optimal sequence of solving problems is as follows:   $$$1 \rightarrow 3$$$, after that total score is $$$17$$$ and $$$\text{IQ} = 6$$$  $$$3 \rightarrow 4$$$, after that total score is $$$35$$$ and $$$\text{IQ} = 8$$$  $$$4 \rightarrow 2$$$, after that total score is $$$42$$$ and $$$\text{IQ} = 12$$$ 

Sample Inputs:
5
4
1 2 3 4
5 10 15 20
4
1 2 1 2
5 10 15 20
4
2 2 4 1
2 8 19 1
2
1 1
6 9
1
1
666

Sample Outputs:
35
30
42
0
0

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
ans = []
for _ in range(t):
    n = int(input())
    tag = list(map(int, input().split()))
    s = list(map(int, input().split()))
    (dp, dp0) = ([0.0] * n, [0.0] * n)
    for i in range(1, n):
        (ti, si, ma) = (tag[i], s[i], 0)
        for j in range(i - 1, -1, -1):
            (tj, sj) = (tag[j], s[j])
            d = abs(si - sj) + 0.0
            dp0[j] = dp[j]
            if ti ^ tj:
                dp0[j] = max(dp0[j], ma + d)
                ma = max(ma, dp[j] + d)
        dp0[i] = ma
        (dp, dp0) = (dp0, dp)
    ans0 = int(max(dp))
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
from sys import stdin
input = stdin.readline

def D708():
    t = int(input())
    for _ in range(t):
        n = int(input())
        tags = list(map(int, input().split()))
        s = list(map(int, input().split()))
        dp = [0] * n
        for j in range(1, n):
            for i in range(j - 1, -1, -1):
                if tags[i] != tags[j]:
                    score = abs(s[i] - s[j])
                    (dpi, dpj) = (dp[i], dp[j])
                    dp[i] = max(dp[i], dpj + score)
                    dp[j] = max(dp[j], dpi + score)
        print(max(dp))
D708()

Solution (Python):
def solve():
    n = int(input())
    c = list(map(int, input().split()))
    s = list(map(int, input().split()))
    ans = 0
    dp = [0] * n
    for i in range(n):
        for j in range(i - 1, -1, -1):
            if c[i] != c[j]:
                tmp = dp[j]
                dp[j] = max(dp[j], dp[i] + abs(s[i] - s[j]))
                dp[i] = max(dp[i], tmp + abs(s[i] - s[j]))
    return max(dp)
for i in range(int(input())):
    print(solve())