CF1687A The Enchanted Forest

The enchanted forest got its name from the magical mushrooms growing here. They may cause illusions and generally should not be approached. —Perfect Memento in Strict Sense Marisa comes to pick mushrooms in the Enchanted Forest. 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 $ . Marisa can start out at any point in the forest on minute $ 0 $ . Each minute, the followings happen in order: - She moves from point $ x $ to $ y $ ( $ |x-y|\le 1 $ , possibly $ y=x $ ). - She collects all mushrooms on point $ y $ . - A new mushroom appears on each point in the forest. Note that she cannot collect mushrooms on minute $ 0 $ . Now, Marisa wants to know the maximum number of mushrooms she can pick after $ k $ minutes.

N/A

N/A

Test case 1: 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. It can be shown that it is impossible to collect more than $ 12 $ mushrooms. Test case 2: This is one of her possible moving path: $ 2 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 $ It can be shown that it is impossible to collect more than $ 37 $ mushrooms.