← 返回题目列表

AtCoder · awc0047_b

B. 单向街道上的道路封闭

中文机器翻译题面 查看原题

分数: 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