\(S\) を反転しておきます． 101010... という形の文字列を，よい文字列と呼ぶことにします．

\(S\) の部分列として，最大のよい文字列を取り出してみます． 明らかに，この部分列の長さが，最初に黒板に書いてあった整数の最大値の上限です． これを一般化してみます．

同じ操作を繰り返すことを考えます． つまり，\(S\) から最大のよい部分列を取り出し，その要素を \(S\) から消す，という操作を，\(S\) が空になるまで繰り返します． 例えば，\(S=\)1110001101 の場合，10101,101,10 が取り出せます．

こうして取り出した部分列の長さを，\(l_1 \geq l_2 \geq \cdots \geq l_n\) とします． ここで，最初に黒板に書いてあった整数を，\(x_1 \geq x_2 \geq \cdots \geq x_m\) とします． まず，\(\sum l_i = \sum x_i\) が必要です． また，全ての \(i\) (\(1 \leq i \leq m\))について，以下の両方が成り立つ必要があります．

• \(\sum_{j=1}^{i} \lceil l_j/2 \rceil \geq \sum_{j=1}^{i} \lceil x_j/2 \rceil\) （先頭 \(i\) 項の含む 1 の個数の制約）
• \(\sum_{j=1}^{i} \lfloor l_j/2 \rfloor \geq \sum_{j=1}^{i} \lfloor x_j/2 \rfloor\)（先頭 \(i\) 項の含む 0 の個数の制約）

これは，次のように証明できます． \(S\) から disjoint によい部分列を \(i\) 個取り出すとき，そこに含まれる 0 (or 1) の個数を最大化しろ，という問題を考えます． するとこれは，上で述べた，最長の部分列を一つずつ取っていく，という貪欲な操作で最適解が得られるとわかります． よって，上記の必要条件が示せました．

上の必要条件は，実は十分条件でもあります（証明は後述）． ここまで分かればあとは DP ができます． \(x\) を値の大きい方から決めていくことにします． 状態としては，(列の長さ，最後の要素，\(\sum \lceil x_i/2 \rceil\)，\(\sum \lfloor x_i/2 \rfloor\)) を取れば良いです． (列の長さ，最後の要素) の組み合わせは高々 \(O(|S|\log|S|)\) 通りしか考慮しなくてよいので，状態は \(O(|S|^3\log |S|)\) 個です． 遷移は累積和で高速化でき，全体で \(O(|S|^3\log |S|)\) 時間で計算できます．

上記の必要条件が十分条件であることを示します． まず，以下の補題を示します．

補題: \(2\) つの（空かも知れない）よい文字列 \(a,b (|a| \leq |b|)\)があったとする． この \(2\) つをマージして（マージソートでのマージをイメージしてください）できる任意の文字列 \(w\) について，\(w\) を \(2\) つのよい文字列 \(c,d\) に分解することができる．ただし，\(c,d\) は次の条件を満たす．

• \(|a| \leq |c| \leq |d| \leq |b|\)
• 0,1 の個数が全体で保たれている．つまり，\(\lceil |a|/2 \rceil + \lceil |b|/2 \rceil = \lceil |c|/2 \rceil + \lceil |d|/2 \rceil\) かつ，\(\lfloor |a|/2 \rfloor + \lfloor |b|/2 \rfloor = \lfloor |c|/2 \rfloor + \lfloor |d|/2 \rfloor\)

例えば，\(a=\)10\(,b=\)10101 のとき，\(w\) としては，1010110 や 1101001 などがありえますが，どのような形であっても，\(c=\)101\(,d=\)1010 に分解できます．

これは次のように証明できます，\(w\) から最長のよい部分列を取り出し，これを \(p\) とします． また，\(w\) から \(p\) を削除して残ったものを \(q\) とします． ここで，\(q\) はよい文字列です（そうでないと，\(w\) が \(2\) つのよい文字列に分解できるという前提に矛盾するため）． 明らかに，\(|b| \leq |p|\) です． ここで，\(p\) が上述の貪欲法によって \(w\) から取り出されるものとして，\(w\) の中で \(p\) と \(q\) に対応する要素がどう並ぶかを観察すると，これらをうまく組み替えることで \(c,d\) が得られることが示せます（詳細は省略しますが，あとは場合分けするだけです）．

あとは，この補題を繰り返し適用することで，\(l \rightarrow x\) の変換が可能であることを示します． 明らかに \(n \leq m\) です． なので，\(l\) の末尾に \(0\) を追加することで，\(n=m\) を仮定します．

以下に，\(l\) を \(x\) に変換する手順を示します． この手順の最中は常に，全ての \(i\) について，\(\sum_{j=1}^{i} \lceil l_j/2 \rceil \geq \sum_{j=1}^{i} \lceil x_j/2 \rceil\) と \(\sum_{j=1}^{i} \lfloor l_j/2 \rfloor \geq \sum_{j=1}^{i} \lfloor x_j/2 \rfloor\) が成り立ちます． ただし，途中で \(l\) が広義単調減少でなくなる可能性があることに留意してください．

• \(l_i < x_i\) なる最小の \(i\) を見つける．存在しない場合は \(l=x\) である．
• \(j<i,l_j \geq x_j+2\) を満たす \(j\) が存在する場合: \(l_i < x_i \leq x_j \leq l_j - 2\) なので，補題を適用し，\(l_j,l_i\) を，\(l_j-2,l_i+2\) で置き換える
• 存在しない場合: \(j<i, l_j = x_j+1, l_j \neq l_i \mod 2\) を満たす \(j\) が必ず存在する．存在しない場合，\(l\) の先頭 \(i\) 項に含まれる 0 または 1 の量が \(x\) に比べて strict に小さいことになり，前提に矛盾する．\(l_i < x_i \leq x_j \leq l_j - 1\) なので，補題を適用し，\(l_j,l_i\) を \(l_j-1,l_i+1\) で置き換える．

明らかにこの手順は有限回で停止します． よって示されました．