配点: 100 点
問題文
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 = 300.
- 31 \leq L_i \leq 62.
- S_{i, j} 是 0 或 通过替换 1.
关于测试用例生成
测试用例是根据以下步骤生成的。
- L_i 的值为31 以上 62 从以下整数中均匀随机选择。
- B ,0.15 以上 0.55 令其为基于以下均匀概率分布确定的随机值。
- 各 j (1 \leq j \leq L_i)独立 S_{i, j} 的值被确定。概率 B 出现 S_{i, j} = \ 1 和概率 1-B 出现 S_{i, j} = \ 0 变为。 (23:11更正)
- 已获得 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
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, L_i 不满足约束条件,因此不包含在用于评分的数据中。 )3 1101 011 10101
出力例 1
4 7 3
该输出对应的图如下所示。
从左数起,7 从厘米起 10 长度可达厘米 3 厘米部分呈现连续红色。另外,这是最大长度。因此,该输出的分数为 5 点。
这个输入示例是
它不包含在测试数据中,因为它不满足N = 300,31 \leq L_i \leq 62 条件。
用于评分的所有测试用例都是N = 300,31 \leq L_i \leq 62 满意。