P8484 「HGOI-1」Mole
题目背景
$\text{brealid}$ 觉得普通的打地鼠游戏太过于 $\text{simple}$ 了。所以,她设计了一款全新的打地鼠游戏。
题目描述
在长度为 $l$ 的游戏窗口上,有一个长为 $t$ 的地鼠序列 $(l \le t)$,初始序列左端与窗口左端对齐,接下来序列每秒移动一个单位长度,(即最左端的地鼠离开窗口,最右端的地鼠进入窗口),向左滚动直至玩家结束游戏或者序列最右端与窗口最右端重合(即任何时刻窗口内均应有 $l$ 只地鼠)。
游戏开始的第一秒序列不会移动,不难发现游戏最多会进行 $(t-l+1)$ 秒。
序列 $T$ 中的每一只地鼠都有自己的高度 $h_i$,玩家每次可以选择击打一只地鼠,玩家可以获得与地鼠高度 $h_i$ 数值相同的金币奖励,同时地鼠 $i$ 的高度 $h_i$ 会减一。
经过调研,$\text{brealid}$ 控制了游戏运行速度,使得玩家在地鼠序列移动一个单位长度的同时**最多只能打击一次**(也可以不打)。
现在 $\text{brealid}$ 告诉了你某一次游戏的窗口长度 $l$、序列长度 $t$ 以及某一局游戏中生成的地鼠高度序列 $T$。我们可爱的 $\text{brealid}$ 想要知道,她在**任意时刻**结束游戏所能得到的**最多金币**,即在第 $1,2,\cdots (t-l+1)$ 秒时停止游戏分别可以获得的最多金币。
输入格式
无
输出格式
无
说明/提示
#### 样例解释
第一秒:锤 $2$,答案加 $3$。
第二秒:锤 $2$,答案加 $2$。
第三秒:随便锤一个,答案加 $1$。
第四秒:再随便锤一个(非 $0$ 的),答案加 $1$。
第五秒:锤 $9$,答案加 $5$。
第六秒:锤 $9$,答案加 $4$。
#### 数据范围
本题采用**捆绑测试**,共有 $4$ 个 $\text{subtask}$,最终分数为所有 $\text{subtask}$ 分数之和。
$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|}\hline
\textbf{Task} & \textbf{Score} & l\le t\le \cr\hline
1 & 10 & 10 \cr\hline
2 & 20 & 500 \cr\hline
3 & 30 & 5000 \cr\hline
4 & 40 & 10^6 \cr\hline
\end{array}
$$
对于 $100\%$ 的数据,$1\le l\le t\le 10^6$,$|h_i|\le 10^9$。