407769: GYM102891 F Alarm Clocks

You are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. Initially $$$a_i = 5 \cdot 10^5 + 1$$$ and $$$1 \leq b_i \leq 5 \cdot 10^5$$$ holds for every $$$i$$$ from $$$1$$$ to $$$n$$$. Additionally, you are given a non-negative integer $$$k$$$ such that $$$2k+1 \leq n$$$.

You can make some operations on the array $$$a$$$. In an operation, you can select two positive integers $$$x,v$$$ such that $$$k+1 \leq x \leq n-k$$$, $$$1 \leq v \leq 5 \cdot 10^5$$$, and set $$$a_i$$$ to $$$\min(a_i,v)$$$ for every $$$i$$$ from $$$x-k$$$ to $$$x+k$$$.

After performing some operations, you hope $$$a_i \leq b_i$$$ holds for every $$$i$$$ from $$$1$$$ to $$$n$$$, but you would like to maximize the sum of all elements in $$$a$$$ at the same time. What is the maximum possible sum you can achieve after performing some operations?

The first line contains two integers $$$n, k$$$ ($$$1 \leq n \leq 3000$$$, $$$k \geq 0$$$, $$$2k+1 \leq n$$$).

The second line contain $$$n$$$ integers $$$b_1, b_2, \cdots, b_n$$$ ($$$1 \leq b_i \leq 5 \cdot 10^5$$$).

Print an integer — The maximum possible sum of all elements in $$$a$$$.

• Subtask 1 (7 points): $$$\forall 1 \leq i < n$$$, $$$a_i \leq a_{i+1}$$$.
• Subtask 2 (14 points): $$$1 \leq a_i \leq 2$$$.
• Subtask 3 (16 points): $$$1 \leq n \leq 100$$$.
• Subtask 4 (24 points): $$$1 \leq n \leq 500$$$.
• Subtask 5 (39 points): No additional constraints.

5 1
3 1 2 5 4

11

1 0
12

12

16 3
10 2 17 26 2 23 31 13 9 21 4 4 12 13 19 10

80