某天,偉杰在老家倉庫發現了一個保險箱
上面寫著如果想知道保險箱的密碼,就要獲得遊戲的最大得分
並且在一旁有張 $n$ 個格子的紙,每格上面有個正整數
紙上還附了該遊戲的規則:
1. 首先選擇一個格子 $i$ 作為起點 (該格的數字為 $a_i$),放上一個硬幣
2. 當 $i \le n$,可得到分數 $a_i$,並且將硬幣往右移動 $a_i$ 格 (就是移到位置 $i + a_i$)
3. 重複第 2 步的動作直到 $i > n$
舉例來說,假設 $n = 4$ 且 $a = [5, 1, 2, 4]$ 則偉杰有這些選擇:
偉杰表示:要一個個去試也太麻煩了吧,還不如寫個程式去算來得快
第一列給定 $n$ 表示紙上總共有 $n$ 個格子 ($1 \le n \le 10^6$)
接著下一列有 $n$ 個正整數 $a_1, a_2, \cdots , a_n$ 表示格子上的數字 ($1 \le a_i \le 10^9$)
輸出該遊戲的最大得分
第 1 筆測資:偉杰選 $i = 2$ 作為起點
第 2 筆測資:偉杰選 $i = 1$ 作為起點
第 3 筆測資:偉杰選 $i = 1$ 作為起點
Codeforces 1472C Long Jumps
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~9 | $n \le 100, a_i \le {n\over 5}$ | 20 |
2 | 10~19 | $n \le 100$ | 20 |
3 | 0~45 | $n \le 10^6$ | 60 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 | |
13 | 1000 | 65536 | 65536 | |
14 | 1000 | 65536 | 65536 | |
15 | 1000 | 65536 | 65536 | |
16 | 1000 | 65536 | 65536 | |
17 | 1000 | 65536 | 65536 | |
18 | 1000 | 65536 | 65536 | |
19 | 1000 | 65536 | 65536 | |
20 | 1000 | 65536 | 65536 | |
21 | 1000 | 65536 | 65536 | |
22 | 1000 | 65536 | 65536 | |
23 | 1000 | 65536 | 65536 | |
24 | 1000 | 65536 | 65536 | |
25 | 1000 | 65536 | 65536 | |
26 | 1000 | 65536 | 65536 | |
27 | 1000 | 65536 | 65536 | |
28 | 1000 | 65536 | 65536 | |
29 | 1000 | 65536 | 65536 | |
30 | 1000 | 65536 | 65536 | |
31 | 1000 | 65536 | 65536 | |
32 | 1000 | 65536 | 65536 | |
33 | 1000 | 65536 | 65536 | |
34 | 1000 | 65536 | 65536 | |
35 | 1000 | 65536 | 65536 | |
36 | 1000 | 65536 | 65536 | |
37 | 1000 | 65536 | 65536 | |
38 | 1000 | 65536 | 65536 | |
39 | 1000 | 65536 | 65536 | |
40 | 1000 | 65536 | 65536 | |
41 | 1000 | 65536 | 65536 | |
42 | 1000 | 65536 | 65536 | |
43 | 1000 | 65536 | 65536 | |
44 | 1000 | 65536 | 65536 | |
45 | 1000 | 65536 | 65536 |