P1360 [USACO07MAR] Gold Balanced Lineup G

Immortal $\mathsf E \color{red} \mathsf{ntropyIncreaser}$ has strong abilities in many aspects. Specifically, she has a total of $m$ abilities, numbered $1 \sim m$. Her abilities improve day by day. Each day, some abilities increase once. She records each day’s improvements with a single integer, called the ability upgrade number. For example, the number $13$ in binary is $1101$, and read from right to left, it indicates that abilities numbered $1, 3, 4$ each increased once that day. $\mathsf E \color{red} \mathsf{ntropyIncreaser}$ writes down the ability upgrade number for every day. If over a consecutive period each of her abilities increases the same number of times, she calls that period a balanced period. For example, if over $5$ consecutive days each ability increases $4$ times, then it is a balanced period of length $5$. Given the ability upgrade numbers for $n$ days, find the maximum length of a balanced period.

The first line contains two integers $n, m$, meaning there are $n$ days and $m$ abilities. The next $n$ lines each contain one integer, representing the ability upgrade number for days $1 \sim n$. After converting an ability upgrade number to binary, from right to left, each bit indicates whether the corresponding ability increased once that day.

Output a single integer, the maximum length of a balanced period.

Constraints - For $50\%$ of the testdata, $1 \le n \le 1000$. - For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le m \le 30$. Sample Explanation The abilities improved each day are as follows: | Day | Abilities improved | | :-----------: | :-----------: | | $1$ | $1, 2, 3$ | | $2$ | $2, 3$ | | $3$ | $1, 2, 3$ | | $4$ | $2$ | | $5$ | $1$ | | $6$ | $3$ | | $7$ | $2$ | Days $3$ through $6$ form the longest balanced period because, in those four days, each ability increased exactly $2$ times. Translated by ChatGPT 5