まず黒の連結成分の個数で場合分けする。これをKとする
連結成分ごとに、a1, a2, .., amを使うとすると長さ[max(a1,a2, .., am), a1+a2+..+am]の連結成分が作れることに注目する。
すると、塗れる範囲というのはK次元平面上の長方形たちの和集合で表せることがわかる。
座圧をして根性をすると、これを長方形に分解できるので、長方形ごとに考えれば良い。
これはN個を[0, INF), [a, b), [1, INF), [c, d), [1, INF), [e, f), [0, INF)に割り当ててくださいという問題になる(K=3の場合)
これは包除なので、包除をすると解ける
