/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
L 個の椅子が左右一列に並んでおり、これから N 組の人が訪れて、順に座っていきます。 ただし、各組は 1 人組または 2 人組であり、i 番目には a_i 人組が訪れます。 また、訪れる人数の合計は L に等しいです。
それぞれの組は、椅子の列の中でまだ人が座っていない部分のうち、 組の全員が連続して座れるところをランダムに選び、その部分を占有して座ります。 ただし、組の全員が連続して座れる場所が無い場合は、座ることができずに帰ってしまいます。
このとき、「誰も帰らずに N 組全員が座ることができる」と確実に言えるかどうか判定してください。
制約
- 1\leq N\leq 2\times 10^5
- 1\leq a_i\leq 2
- L=a_1 +a_2 +\ldots +a_N
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N L a_1 a_2 \ldots a_N
出力
「誰も帰らずに N 組全員が座ることができる」と確実に言える場合は Yes 、そうでない場合は No を出力せよ。
入力例 1
2 4 2 2
出力例 1
No
椅子に左から 1,2,3,4 と番号がついているとします。
最初の 2 人組が椅子 2,3 に座った場合、後から来る 2 人組は座ることができずに帰ってしまいます。
したがって、全員が座ることができない場合がありますので、No と答えてください。
入力例 2
3 4 1 2 1
出力例 2
Yes
どのような座り方を考えても、全員が確実に椅子に座ることができます。
Score : 400 points
Problem Statement
There is a row of L chairs. Now, N groups of people will come and take seats in order. Each group consists of one or two people, and the i-th group to come consists of a_i people. The total number of people equals L.
Each group will randomly choose unoccupied chairs where all group members can sit consecutively, and occupy those chairs. However, if there are not enough consecutive unoccupied chairs, they will leave without taking seats.
Determine whether it is guaranteed that all N groups can take seats.
Constraints
- 1\leq N\leq 2\times 10^5
- 1\leq a_i\leq 2
- L=a_1 +a_2 +\ldots +a_N
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N L a_1 a_2 \ldots a_N
Output
If it is guaranteed that all N groups can take seats, print Yes; otherwise, print No.
Sample Input 1
2 4 2 2
Sample Output 1
No
Let us number the chairs 1, 2, 3, 4 from left to right.
If the first group of two people takes chairs 2 and 3, the next group of two people cannot take seats and will leave.
Thus, it is not guaranteed that all N groups can take seats, so you should print No.
Sample Input 2
3 4 1 2 1
Sample Output 2
Yes
No matter what chairs they choose, everyone can always take a seat.