codeforces-scrape

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

1687A.md (2662B)


      1 Source: https://codeforces.com/problemset/problem/1687/A
      2 
      3 A. The Enchanted Forest
      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 The enchanted forest got its name from the magical mushrooms growing here. They may cause illusions and generally should not be approached.
     22 
     23 —Perfect Memento in Strict Sense
     24 
     25 Marisa comes to pick mushrooms in the Enchanted Forest.
     26 
     27 The Enchanted forest can be represented by $n$ points on the $X$-axis numbered $1$ through $n$. Before Marisa started, her friend, Patchouli, used magic to detect the initial number of mushroom on each point, represented by $a_1,a_2,\ldots,a_n$.
     28 
     29 Marisa can start out at any point in the forest on minute $0$. Each minute, the followings happen in order:
     30 
     31 * She moves from point $x$ to $y$ ($|x-y|\le 1$, possibly $y=x$).
     32 * She collects all mushrooms on point $y$.
     33 * A new mushroom appears on each point in the forest.
     34 
     35 Note that she cannot collect mushrooms on minute $0$.
     36 
     37 Now, Marisa wants to know the maximum number of mushrooms she can pick after $k$ minutes.
     38 
     39 Input
     40 
     41 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.
     42 
     43 The first line of each test case contains two integers $n$, $k$ ($1 \le n \le 2 \cdot 10 ^ 5$, $1\le k \le 10^9$) — the number of positions with mushrooms and the time Marisa has, respectively.
     44 
     45 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$) — the initial number of mushrooms on point $1,2,\ldots,n$.
     46 
     47 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10 ^ 5$.
     48 
     49 Output
     50 
     51 For each test case, print the maximum number of mushrooms Marisa can pick after $k$ minutes.
     52 
     53 Example
     54 
     55 Input
     56 
     57 ```
     58 4
     59 
     60 5 2
     61 
     62 5 6 1 2 3
     63 
     64 5 7
     65 
     66 5 6 1 2 3
     67 
     68 1 2
     69 
     70 999999
     71 
     72 5 70000
     73 
     74 1000000000 1000000000 1000000000 1000000000 1000000000
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 12
     81 37
     82 1000000
     83 5000349985
     84 ```
     85 
     86 Note
     87 
     88 Test case 1:
     89 
     90 Marisa can start at $x=2$. In the first minute, she moves to $x=1$ and collect $5$ mushrooms. The number of mushrooms will be $[1,7,2,3,4]$. In the second minute, she moves to $x=2$ and collects $7$ mushrooms. The numbers of mushrooms will be $[2,1,3,4,5]$. After $2$ minutes, Marisa collects $12$ mushrooms.
     91 
     92 It can be shown that it is impossible to collect more than $12$ mushrooms.
     93 
     94 Test case 2:
     95 
     96 This is one of her possible moving path:
     97 
     98 $2 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$
     99 
    100 It can be shown that it is impossible to collect more than $37$ mushrooms.