分数: 300 分
问题陈述
在高桥居住的小镇上,有一条笔直的道路, N 点排列成一条线。它们从左到右编号为点 1,点 2, \ldots,点 N.
对于相邻点之间的每个部分 i 和 i + 1 (1 \leq i \leq N-1),是否关闭用整数表示 W_i。当 W_i = 1,该路段因施工封闭,无法通行。当 W_i = 0,该部分可以自由遍历。
高桥有 M 施工竣工许可证。在开始他的旅程之前,高桥可以选择最多 M 封闭部分(其中的部分 W_i = 1)并在每个选定的部分使用一个许可证。使用许可证的路段将解除封闭并可自由通行。不能在同一路段使用两个或多个许可证。此外,所有许可证必须在旅程开始前分配;旅途中不能使用额外的许可证。
高桥从点开始 1。他可以通过未封闭的路段(最初有的路段)在两个方向上在相邻点之间移动任意次数 W_i = 0,以及已通过许可证解除关闭的路段)。
当使用许可证的路段被选择为最佳时,求出高桥从点出发可以到达的点数 1 (包括点 1 本身)。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq N - 1
- W_i \in \{0, 1\} (1 \leq i \leq N-1)
- 所有输入值均为整数。
输入
N M
W_1 W_2 \ldots W_{N-1}
- 第一行包含一个整数 N 表示点数和一个整数 M 代表许可证数量,以空格分隔。
- 第二行包含 N - 1 整数 W_1, W_2, \ldots, W_{N-1} 表示相邻点之间的每个部分是否闭合,以空格分隔。当 N = 1,没有任何部分,因此第二行是空的(给出了一个空行)。
- W_i 表示是否是点之间的部分 i 和点 i + 1 已关闭: 1 表示关闭,并且 0 表示还可以。
输出
在一行中打印高桥在最佳使用许可时可以达到的分数。
样本输入 1
7 2 0 1 0 1 1 0
示例输出 1
5
示例输入 2
10 0 0 0 1 0 0 0 1 0 0
示例输出 2
3
示例输入 3
15 3 1 0 0 1 0 1 0 0 1 1 0 0 1 0
示例输出 3
9