Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB

#2807. 瘟疫爆发(plague)

Statistics

【题目描述】

古老的 A 国爆发了一场瘟疫。
A 国有 $n$ 座城市,从 $1$ 到 $n$ 编号,这场瘟疫对第 $i$ 座城市有一个适应度 $a_i$,这个值越大,瘟疫对这座城市造成的伤害就越大。
这 $n$ 座城市的排布可以视作一条直线,于是对于 $1 < i < n$,$i$ 号城市和 $i − 1$ 号城
市与 $i + 1$ 号城市相邻;$1$ 号城市仅与 $2$ 号城市相邻;$n$ 号城市仅与 $n − 1$ 号城市相邻。
这场瘟疫初始在至多 $m$ 座城市里爆发,一座被瘟疫感染的城市有可能把瘟疫扩散到
与其相邻的城市。一场瘟疫的最终适应度是其感染的每座城市的适应度之和。
具体的扩散情况没有被记录,你想知道这场瘟疫可以带来的最大的伤害,即它能达成的最大的最终适应度。
注意,适应度 $a_i$ 可以是负数,瘟疫也可能初始不感染任何一座城市。

【输入格式】

从文件 $plague.in$ 中读入数据。
第一行两个整数 $n$, $m$。
第二行 n 个整数 $a{_{1}{_{\cdots}{_n}}}$。

由于本题输入量较大,我们在对应文件夹内下发了 IO.cpp。注释的两行仅能在使用 文件读入输出时使用,但会大大加快读入速度。

【输出格式】

输出到文件 $plague.out$ 中。 一行一个整数表示答案。

【样例 1 输入】

5 3    
1 ‐1 1 ‐1 1

【样例 1 输出】

3

【样例 1 解释】

当瘟疫初始在第 $1, 3, 5$ 座城市爆发,都不向相邻城市扩散时取得最大适应度 $1 + 1 + 1 = 3$。

【样例 2、3】

见 /ex_plague2.in、/ex_plague3.in 与 /ex_plague2.out、/ex_plague3.out。

【测试点约束】

对于所有测试点,$1 ≤ m ≤ n ≤ 6 × 10^6,|ai| ≤ 10^8。$
每个测试点的具体限制见下表:

测试点编号 $n ≤$ 分值
1 $500$ 10
2 $5000$ 10
3 $5000$ 10
4 $10^5$ 15
5 $10^5$ 15
6 $6*10^6$ 40