User's AC Ratio

88.9% (16/18)

Submission's AC Ratio

51.3% (20/39)

Description

某天,偉杰在老家倉庫發現了一個保險箱
上面寫著如果想知道保險箱的密碼,就要獲得遊戲的最大得分
並且在一旁有張 $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]$ 則偉杰有這些選擇:

  • 偉杰先選 $i = 1$,則過程為 $i = 1 \overset{+5}{\longrightarrow} 6$,得分為 $a_1 = 5$
  • 偉杰先選 $i = 2$,則過程為 $i = 2 \overset{+1}{\longrightarrow} 3 \overset{+2}{\longrightarrow} 5$,得分為 $a_2 + a_3 = 3$
  • 偉杰先選 $i = 3$,則過程為 $i = 3 \overset{+2}{\longrightarrow} 5$,得分為 $a_3 = 2$
  • 偉杰先選 $i = 4$,則過程為 $i = 4 \overset{+4}{\longrightarrow} 8$,得分為 $a_4 = 4$

偉杰表示:要一個個去試也太麻煩了吧,還不如寫個程式去算來得快

Input Format

第一列給定 $n$ 表示紙上總共有 $n$ 個格子 ($1 \le n \le 10^6$)
接著下一列有 $n$ 個正整數 $a_1, a_2, \cdots , a_n$ 表示格子上的數字 ($1 \le a_i \le 10^9$)

Output Format

輸出該遊戲的最大得分

Sample Input 1

6
2 1000 2 3 995 1

Sample Output 1

1000

Sample Input 2

5
7 3 1 2 3

Sample Output 2

7

Sample Input 3

4
1 1 1 1

Sample Output 3

4

Hints

第 1 筆測資:偉杰選 $i = 2$ 作為起點
第 2 筆測資:偉杰選 $i = 1$ 作為起點
第 3 筆測資:偉杰選 $i = 1$ 作為起點

Problem Source

Codeforces 1472C Long Jumps

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 3
1 1000 65536 65536 1 3
2 1000 65536 65536 1 3
3 1000 65536 65536 1 3
4 1000 65536 65536 1 3
5 1000 65536 65536 1 3
6 1000 65536 65536 1 3
7 1000 65536 65536 1 3
8 1000 65536 65536 1 3
9 1000 65536 65536 1 3
10 1000 65536 65536 2 3
11 1000 65536 65536 2 3
12 1000 65536 65536 2 3
13 1000 65536 65536 2 3
14 1000 65536 65536 2 3
15 1000 65536 65536 2 3
16 1000 65536 65536 2 3
17 1000 65536 65536 2 3
18 1000 65536 65536 2 3
19 1000 65536 65536 2 3
20 1000 65536 65536 3
21 1000 65536 65536 3
22 1000 65536 65536 3
23 1000 65536 65536 3
24 1000 65536 65536 3
25 1000 65536 65536 3
26 1000 65536 65536 3
27 1000 65536 65536 3
28 1000 65536 65536 3
29 1000 65536 65536 3
30 1000 65536 65536 3
31 1000 65536 65536 3
32 1000 65536 65536 3
33 1000 65536 65536 3
34 1000 65536 65536 3
35 1000 65536 65536 3
36 1000 65536 65536 3
37 1000 65536 65536 3
38 1000 65536 65536 3
39 1000 65536 65536 3
40 1000 65536 65536 3
41 1000 65536 65536 3
42 1000 65536 65536 3
43 1000 65536 65536 3
44 1000 65536 65536 3
45 1000 65536 65536 3