codeforces-scrape

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

1320A.md (2437B)


      1 Source: https://codeforces.com/problemset/problem/1320/A
      2 
      3 A. Journey Planning
      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 Tanya wants to go on a journey across the cities of Berland. There are $n$ cities situated along the main railroad line of Berland, and these cities are numbered from $1$ to $n$.
     22 
     23 Tanya plans her journey as follows. First of all, she will choose some city $c_1$ to start her journey. She will visit it, and after that go to some other city $c_2 \gt c_1$, then to some other city $c_3 \gt c_2$, and so on, until she chooses to end her journey in some city $c_k \gt c_{k - 1}$. So, the sequence of visited cities $[c_1, c_2, \dots, c_k]$ should be strictly increasing.
     24 
     25 There are some additional constraints on the sequence of cities Tanya visits. Each city $i$ has a beauty value $b_i$ associated with it. If there is only one city in Tanya's journey, these beauty values imply no additional constraints. But if there are multiple cities in the sequence, then for any pair of adjacent cities $c_i$ and $c_{i + 1}$, the condition $c_{i + 1} - c_i = b_{c_{i + 1}} - b_{c_i}$ must hold.
     26 
     27 For example, if $n = 8$ and $b = [3, 4, 4, 6, 6, 7, 8, 9]$, there are several three possible ways to plan a journey:
     28 
     29 * $c = [1, 2, 4]$;
     30 * $c = [3, 5, 6, 8]$;
     31 * $c = [7]$ (a journey consisting of one city is also valid).
     32 
     33 There are some additional ways to plan a journey that are not listed above.
     34 
     35 Tanya wants her journey to be as beautiful as possible. The beauty value of the whole journey is the sum of beauty values over all visited cities. Can you help her to choose the optimal plan, that is, to maximize the beauty value of the journey?
     36 
     37 Input
     38 
     39 The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of cities in Berland.
     40 
     41 The second line contains $n$ integers $b_1$, $b_2$, ..., $b_n$ ($1 \le b_i \le 4 \cdot 10^5$), where $b_i$ is the beauty value of the $i$-th city.
     42 
     43 Output
     44 
     45 Print one integer — the maximum beauty of a journey Tanya can choose.
     46 
     47 Examples
     48 
     49 Input
     50 
     51 ```
     52 6
     53 10 7 1 9 10 15
     54 ```
     55 
     56 Output
     57 
     58 ```
     59 26
     60 ```
     61 
     62 Input
     63 
     64 ```
     65 1
     66 400000
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 400000
     73 ```
     74 
     75 Input
     76 
     77 ```
     78 7
     79 8 9 26 11 12 29 14
     80 ```
     81 
     82 Output
     83 
     84 ```
     85 55
     86 ```
     87 
     88 Note
     89 
     90 The optimal journey plan in the first example is $c = [2, 4, 5]$.
     91 
     92 The optimal journey plan in the second example is $c = [1]$.
     93 
     94 The optimal journey plan in the third example is $c = [3, 6]$.