CF1497D Genius

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.

N/A

N/A

In the first test case optimal sequence of solving problems is as follows: 1. $ 1 \rightarrow 2 $ , after that total score is $ 5 $ and $ \text{IQ} = 2 $ 2. $ 2 \rightarrow 3 $ , after that total score is $ 10 $ and $ \text{IQ} = 4 $ 3. $ 3 \rightarrow 1 $ , after that total score is $ 20 $ and $ \text{IQ} = 6 $ 4. $ 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. $ 1 \rightarrow 2 $ , after that total score is $ 5 $ and $ \text{IQ} = 2 $ 2. $ 2 \rightarrow 3 $ , after that total score is $ 10 $ and $ \text{IQ} = 4 $ 3. $ 3 \rightarrow 4 $ , after that total score is $ 15 $ and $ \text{IQ} = 8 $ 4. $ 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. $ 1 \rightarrow 3 $ , after that total score is $ 17 $ and $ \text{IQ} = 6 $ 2. $ 3 \rightarrow 4 $ , after that total score is $ 35 $ and $ \text{IQ} = 8 $ 3. $ 4 \rightarrow 2 $ , after that total score is $ 42 $ and $ \text{IQ} = 12 $