Public Judge

pjudge

Time Limit: 4 s Memory Limit: 512 MB Total points: 100

# 21809. 【PR #12】划分序列

Statistics

题目描述

有一个长度为 $n$ 的序列 $a$。

设一个区间的价值为此区间的 $\operatorname{mex}$ 值乘上区间元素总和。其中 $\operatorname{mex}$ 值定义为该集合中不属于集合的最小非负整数,例如 $\operatorname{mex}(0,1,3,5)=2$。

你需要将数组划分成若干非空区间,其中每个区间的长度不超过 $k$。一个划分方案的价值为每个区间的价值之和。

你需要找到满足题意的划分方案下的最大价值。

输入格式

第一行包含两个整数:$n,k$,表示数组的长度、子数组长度的上限。

第二行包含 $n$ 个整数,第 $i$ 个整数为 $a_i$($0 \leq a_i \leq n$)。

输出格式

输出一个非负整数,表示最大的价值。

样例输入 1

5 3
3 4 0 0 3

样例输出 1

10

样例输入 2

8 4
0 1 2 0 3 1 4 1

样例输出 2

26

样例输入 3

10 5
0 2 0 1 2 1 0 2 2 1

样例输出 3

33

样例 4/5

见下发文件。

数据范围

对于全部数据,满足 $2\le n\le 2\times 10^5,1\le k\le n,0\le a_i\le n$。

子任务编号 $n\le $ 特殊性质 分数
1 $10$ 4
2 $5000$ 8
3 $2\times 10^4$ 8
4 $2\times 10^5$ A 24
5 $2\times 10^5$ B 20
6 $1\times 10^5$ 16
7 $2\times 10^5$ 20

特殊性质 A:$a_i\le 10$。

特殊性质 B:数据满足在 $a_i$ 在 $[0,n]$ 内随机生成。