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$。