#P1360. [USACO07MAR] Gold Balanced Lineup G

    ID: 404 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>前缀和离散化进制队列USACO2007

[USACO07MAR] Gold Balanced Lineup G

题目描述

神仙 EntropyIncreaser\mathsf E \color{red} \mathsf{ntropyIncreaser} 在许多方面都有着很强的能力。具体的说,他总共有 mm 种能力,并将这些能力编号为 1m1 \sim m

他的能力是一天一天地提升的,每天都会有一些能力得到一次提升,她对每天的能力提升都用一个数字表示,称之为能力提升数字,比如数字 1313,转化为二进制为 11011101,并且从右往左看,表示他的编号为 1,3,41,3,4 的能力分别得到了一次提升。

EntropyIncreaser\mathsf E \color{red} \mathsf{ntropyIncreaser} 把每天表示能力提升的数字的记了下来,如果在连续的一段时间内,她的每项能力都提升了相同的次数,她就会称这段时间为一个均衡时期,比如在连续 55 天内,她的每种能力都提升了 44 次,那么这就是一个长度为 55 的均衡时期。

于是,问题来了,给出 EntropyIncreaser\mathsf E \color{red} \mathsf{ntropyIncreaser} nn 天的能力提升数字,请求出均衡时期的最大长度。

输入格式

第一行有两个整数 n,mn,m,表示有 nn 天,mm 种能力。

接下来有 nn 行,每行有一个整数,分别表示第 1n1\sim n 天的能力提升数字。

能力提升数字转化为二进制后,从右到左的每一位表示对应的能力是否在当天得到了一次提升。

输出格式

输出只有一个整数,表示长度最大的均衡时期的长度。

7 3
7
6
7
2
1
4
2
4

提示

【数据范围】
对于 50%50\% 的数据,1n10001\le n \le 1000
对于 100%100\% 的数据,1n1051\le n \le 10^51m301\le m \le 30

【样例解释】

每天被提升的能力种类分别为:

天数 提升的能力
11 1,2,31,2,3
22 2,32,3
33 1,2,31,2,3
44 22
55 11
66 33
77 22

第三天到第六天为长度最长的均衡时期,因为这四天每种能力分别提升了 22 次。