AtCoder Beginner Contest 124：D - Handstand
問題
解法
まず，最も長くなるような 1 の連続する部分列をただ 1 つ作るのが最適になる．なぜならば，わざわざ間に 0 をいくつか挟み複数の 1 が連続する部分を作るのであれば，複数の 1 の部分のうち最も長いものの両端の 0 の部分を 1 にするとより長い 1 の連続する部分列を作れるから．また，1 を反転させたり，0 の部分列の中の一部しか反転させないのは明らかに無意味．よって，複数ある 0 の部分列のうち最大 K 個を丸ごと反転させることだけを考えればよい．
ここで，複数ある 0 の部分列を列挙しておく．具体的には，そのような部分列の左端と右端の index を std::pair で持っておく．次に，どの部分列から反転をさせていくかを考える．これを決めれば，決めた部分列から数えて最大 K 個を反転させるので最後に反転させる部分列の位置も一意に定まる．あとは，反転させた部分列のうち一番左の区間の左端と一番右の区間の右端の間の長さと，それぞれより左・右にある 1 の部分列の長さを足せば，このときの最大の 1 の部分列の長さが求まる．これらの max を答えにすればよい．O(|S|)．
解答
