codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.