爆破计划

题目背景

美好的一天，生电大佬小

k

正在挖矿...

题目描述

小

k

需要在一个由

n

个连续矿洞组成的峡谷中爆破开采矿物。第

i

个矿洞中的矿物价值为

v_i

，但引爆

TNT

时会触发连锁反应。具体地，对于每

1

个单位时间：

若在矿洞 $i$ 放置 $TNT$ 并引爆，会波及 $[i−k,i+k]$ 范围内的所有矿洞（超出边界则截断），且后续 $10$ 个单位时间内无法在同一波及范围内再次爆破。
每次爆破的基础成本为 $c$ ，但可通过优化降低实际成本：若当前爆破点 $v_i$ 与上一次爆破点 $v_j$ 的距离满足 $|v_i−v_j| > k$ ，则获得 $(i−j)^2$ 的效率增益，实际成本为 $c − (v_i−v_j)^2$ 。

现在，给定矿洞序列

v_1

v_2

...

v_n

、基础成本

c

、波及半径

k

，求小

k

能获得的最大净收益

m

（既指可获得的最大矿物价值之和

s

− 总爆破成本

f

）。

输入格式

第

1

行，输入矿洞个数

n

, 波及半径

k

, 基础成本

c

。

第

2

行，输入

n

个正整数

v_1

v_2

...

v_n

，表示第

1

到

n

个矿洞中，第

i

个矿洞的价值为

v_i

。

输出格式

仅一行，一个正整数

m

, 表示小

k

可获得的最大净收益。

输入输出样例 #1

输入 #1

CPP

5 1 10
3 5 2 8 4

输出 #1

CPP

说明/提示

对于

100\%

的数据，

1 ≤ k ≤ n ≤ 2×10^5

1 ≤ c ≤ 10^9

0 ≤ v_i ≤ 10^6

。

帮我写一下自己想的这道题（代码到时候私信我）

讨论操作