/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君の住む街には、N 個の地点が一列に並んだ一本道があります。左から順に地点 1, 地点 2, \ldots, 地点 N と番号が付けられています。
隣り合う地点 i と地点 i + 1 (1 \leq i \leq N-1) の間の区間について、通行止めかどうかが整数 W_i によって表されます。W_i = 1 のとき、その区間は工事のため通行止めであり、通り抜けることができません。W_i = 0 のとき、その区間は自由に通行できます。
高橋君は M 枚の工事完了許可証を持っています。高橋君は移動を始める前に、通行止めの区間（W_i = 1 である区間）の中から最大 M 個まで区間を選び、選んだ各区間に許可証を 1 枚ずつ使用できます。許可証を使用された区間は通行止めが解除され、自由に通行できるようになります。同じ区間に 2 枚以上の許可証を使用することはできません。また、許可証の使用先はすべて移動開始前に決定し、移動中に追加で使用することはできません。
高橋君は地点 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}
- 1 行目には、地点の数を表す整数 N と、許可証の枚数を表す整数 M が、スペース区切りで与えられる。
- 2 行目には、隣接する地点間の通行止めの有無を表す N - 1 個の整数 W_1, W_2, \ldots, W_{N-1} が、スペース区切りで与えられる。N = 1 のとき区間は存在しないため、2 行目には何も出力されない（空行が与えられる）。
- W_i は地点 i と地点 i + 1 の間の区間が通行止めかどうかを表し、1 なら通行止め、0 なら通行可能であることを意味する。
出力
高橋君が許可証を最適に使用したとき、到達できる地点の数を 1 行で出力せよ。
入力例 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
Score : 300 pts
Problem Statement
In the town where Takahashi lives, there is a straight road with N points arranged in a line. They are numbered from left to right as point 1, point 2, \ldots, point N.
For each section between adjacent points i and i + 1 (1 \leq i \leq N-1), whether it is closed or not is represented by an integer W_i. When W_i = 1, the section is closed due to construction and cannot be passed through. When W_i = 0, the section can be freely traversed.
Takahashi has M construction completion permits. Before starting his journey, Takahashi can select up to M closed sections (sections where W_i = 1) and use one permit on each selected section. A section on which a permit is used has its closure lifted and becomes freely traversable. It is not possible to use two or more permits on the same section. Additionally, all permits must be assigned before the journey begins; no additional permits can be used during the journey.
Takahashi starts at point 1. He can travel between adjacent points any number of times in both directions through sections that are not closed (sections that originally have W_i = 0, as well as sections whose closure has been lifted by a permit).
When the sections to use permits on are chosen optimally, find the number of points that Takahashi can reach from point 1 (including point 1 itself).
Constraints
- 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)
- All input values are integers.
Input
N M
W_1 W_2 \ldots W_{N-1}
- The first line contains an integer N representing the number of points and an integer M representing the number of permits, separated by a space.
- The second line contains N - 1 integers W_1, W_2, \ldots, W_{N-1} representing whether each section between adjacent points is closed or not, separated by spaces. When N = 1, there are no sections, so the second line is empty (an empty line is given).
- W_i represents whether the section between point i and point i + 1 is closed: 1 means closed, and 0 means passable.
Output
Print in one line the number of points Takahashi can reach when he uses his permits optimally.
Sample Input 1
7 2 0 1 0 1 1 0
Sample Output 1
5
Sample Input 2
10 0 0 0 1 0 0 0 1 0 0
Sample Output 2
3
Sample Input 3
15 3 1 0 0 1 0 1 0 0 1 1 0 0 1 0
Sample Output 3
9