1472C.md (2671B)
1 Source: https://codeforces.com/problemset/problem/1472/C 2 3 C. Long Jumps 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Polycarp found under the Christmas tree an array $a$ of $n$ elements and instructions for playing with it: 22 23 * At first, choose index $i$ ($1 \leq i \leq n$) — starting position in the array. Put the chip at the index $i$ (on the value $a_i$). 24 * While $i \leq n$, add $a_i$ to your score and move the chip $a_i$ positions to the right (i.e. replace $i$ with $i + a_i$). 25 * If $i \gt n$, then Polycarp ends the game. 26 27 For example, if $n = 5$ and $a = [7, 3, 1, 2, 3]$, then the following game options are possible: 28 29 * Polycarp chooses $i = 1$. Game process: $i = 1 \overset{+7}{\longrightarrow} 8$. The score of the game is: $a_1 = 7$. 30 * Polycarp chooses $i = 2$. Game process: $i = 2 \overset{+3}{\longrightarrow} 5 \overset{+3}{\longrightarrow} 8$. The score of the game is: $a_2 + a_5 = 6$. 31 * Polycarp chooses $i = 3$. Game process: $i = 3 \overset{+1}{\longrightarrow} 4 \overset{+2}{\longrightarrow} 6$. The score of the game is: $a_3 + a_4 = 3$. 32 * Polycarp chooses $i = 4$. Game process: $i = 4 \overset{+2}{\longrightarrow} 6$. The score of the game is: $a_4 = 2$. 33 * Polycarp chooses $i = 5$. Game process: $i = 5 \overset{+3}{\longrightarrow} 8$. The score of the game is: $a_5 = 3$. 34 35 Help Polycarp to find out the maximum score he can get if he chooses the starting index in an optimal way. 36 37 Input 38 39 The first line contains one integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Then $t$ test cases follow. 40 41 The first line of each test case contains one integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the array $a$. 42 43 The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$) — elements of the array $a$. 44 45 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 46 47 Output 48 49 For each test case, output on a separate line one number — the maximum score that Polycarp can get by playing the game on the corresponding array according to the instruction from the statement. Note that Polycarp chooses any starting position from $1$ to $n$ in such a way as to maximize his result. 50 51 Example 52 53 Input 54 55 ``` 56 4 57 5 58 7 3 1 2 3 59 3 60 2 1 4 61 6 62 2 1000 2 3 995 1 63 5 64 1 1 1 1 1 65 ``` 66 67 Output 68 69 ``` 70 7 71 6 72 1000 73 5 74 ``` 75 76 Note 77 78 The first test case is explained in the statement. 79 80 In the second test case, the maximum score can be achieved by choosing $i = 1$. 81 82 In the third test case, the maximum score can be achieved by choosing $i = 2$. 83 84 In the fourth test case, the maximum score can be achieved by choosing $i = 1$.