AT_pakencamp_2019_day4_h 板の重なり

[problemUrl]: https://atcoder.jp/contests/pakencamp-2019-day4/tasks/pakencamp_2019_day4_h $ N $ 枚の板があり，それぞれ板 $ 1 $，板 $ 2 $，...，板 $ N $ と番号づけられております． 板 $ i $ の長さは $ L_i $ センチメートルであり，左から数えて，$ j-1 $ センチメートルから $ j $ センチメートルまでの区間は，色 $ S_{i,\ j} $ で塗られております．$ S_{i,\ j}\ =\ 0 $ のとき透明，$ S_{i,\ j}\ =\ 1 $ のとき赤です． さて，あなたは $ N $ 枚の板を適当な位置に置き，重ねることができます． 「$ i $ 枚目の板は，左端が原点から $ m_i $ センチメートルの位置に来るように置く」とするとき，各板について，$ m_i $ は $ 0 $ 以上 $ 10\ 000 $ 以下の整数で決めることができます． 重なっている板を上から見ると，板の赤い部分が $ 1 $ 枚以上重なっている部分は，赤く見えます． 上から見たときの，連続する「赤く見える部分」の長さの最大が，できるだけ大きくなるような置き方を，一つ求めてください．ただし，最適なものを求める必要はありません．

入力は以下の形式で標準入力から与えられます． > $ N $ $ s_{1,1} $$ s_{1,2} $$ s_{1,3} $...$ s_{1,L_{1}} $ $ s_{2,1} $$ s_{2,2} $$ s_{2,3} $...$ s_{2,L_{2}} $ $ s_{3,1} $$ s_{3,2} $$ s_{3,3} $...$ s_{3,L_{3}} $ : $ s_{N,1} $$ s_{N,2} $$ s_{N,3} $...$ s_{N,L_{N}} $

以下の形式で出力してください． > $ m_1 $ $ m_2 $ $ m_3 $ : $ m_N $ ただし，$ m_i $ は $ 0 $ 以上 $ 10\ 000 $ 以下の整数でなければなりません．

### 制約 - $ N\ =\ 300 $． - $ 31\ \leq\ L_i\ \leq\ 62 $． - $ S_{i,\ j} $ は $ 0 $ または $ 1 $． ### テストケース生成について テストケースは，以下のステップに基づいて生成されます． 1. $ L_i $ の値を，$ 31 $ 以上 $ 62 $ 以下の整数の中から，一様ランダムに選ぶ． 2. $ B $ を，$ 0.15 $ 以上 $ 0.55 $ 以下の一様な確率分布に基づいて決定された，ランダムな値とする． 3. 各 $ j $ ($ 1\ \leq\ j\ \leq\ L_i $) について独立に $ S_{i,\ j} $ の値が決められる．確率 $ B $ で $ S_{i,\ j}\ = $$ \ 1 $ となり，確率 $ 1-B $ で $ S_{i,\ j}\ = $$ \ 0 $ となる．(23:11 訂正) 4. 得られた $ S_{i,\ 1},\ S_{i,\ 2},\ S_{i,\ 3},\ ...,\ S_{i,\ L_i} $ が全部 $ 0 $ の場合は，ステップ 1. からやり直す． ### 得点 提出に対する得点は，以下のように決定されます． - 採点に使われる $ 10 $ 個のテストケースのうち，$ 1 $ つでも条件を満たさない出力（$ 0\ \leq\ m_i\ \leq\ 10\ 000 $ を満たさない，不正な出力フォーマットなど）があれば，$ 0 $ 点となります． - そうでない場合，$ i $ 個目のテストケースの得点を $ a_i $ 点とするとき，提出に対する得点は $ \frac{a_{1}+a_{2}+a_{3}+...+a_{10}}{10} $ 点を小数点以下切り捨てた値となります． なお，各テストケースに対する得点は，以下のようになります．**（$ 100 $ 点を超える場合があります．）**ただし，連続する「赤く見える部分」の長さの最大を $ D $ とします． - $ D\ \leq\ 199 $ のとき，$ 5 $ 点． - $ 200\ \leq\ D\ \leq\ 4\ 209 $ のとき，$ 100\ -\ 30log_2(\frac{4810\ -\ D}{600}) $ 点を小数点以下切り捨てた得点． - $ 4\ 210\ \leq\ D $ のとき，$ 100\ +\ \frac{D\ -\ 4\ 210}{10} $ 点． ### 入出力例 例えば，以下の入力例を考えましょう．($ N,\ L_i $ が制約の条件を満たさないため，採点に用いられるデータには含まれません．) ``` 3 1101 011 10101 ``` ### Sample Explanation 1 この出力に対応する図は，以下のようになります． !\[\](https://img.atcoder.jp/pakencamp-2019-day4/6a2283a760876712290562a19564a2fa.png) 左から数えて，$ 7 $ センチメートルから $ 10 $ センチメートルまでの，長さ $ 3 $ センチメートルの区間が，連続して赤く見えます．また，これが最大の長さです．そのため，この出力をした場合のスコアは $ 5 $ 点となります． なお，この入力例は，$ N\ =\ 300 $，$ 31\ \leq\ L_i\ \leq\ 62 $ の条件を満たさないため，テストデータには含まれません． 採点に用いられるすべてのテストケースは，$ N\ =\ 300 $，$ 31\ \leq\ L_i\ \leq\ 62 $ を満たします．