1820B.md (3112B)
1 Source: https://codeforces.com/problemset/problem/1820/B 2 3 B. JoJo's Incredible Adventures 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Did you think there was going to be a JoJo legend here? But no, that was me, Dio! 22 23 Given a binary string $s$ of length $n$, consisting of characters 0 and 1. Let's build a square table of size $n \times n$, consisting of 0 and 1 characters as follows. 24 25 In the first row of the table write the original string $s$. In the second row of the table write cyclic shift of the string $s$ by one to the right. In the third row of the table, write the cyclic shift of line $s$ by two to the right. And so on. Thus, the row with number $k$ will contain a cyclic shift of string $s$ by $k$ to the right. The rows are numbered from $0$ to $n - 1$ top-to-bottom. 26 27 In the resulting table we need to find the rectangle consisting only of ones that has the largest area. 28 29 We call a rectangle the set of all cells $(i, j)$ in the table, such that $x_1 \le i \le x_2$ and $y_1 \le j \le y_2$ for some integers $0 \le x_1 \le x_2 \lt n$ and $0 \le y_1 \le y_2 \lt n$. 30 31 Recall that the cyclic shift of string $s$ by $k$ to the right is the string $s_{n-k+1} \ldots s_n s_1 s_2 \ldots s_{n-k}$. For example, the cyclic shift of the string "01011" by $0$ to the right is the string itself "01011", its cyclic shift by $3$ to the right is the string "01101". 32 33 Input 34 35 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. The description of test cases follows. 36 37 The first and the only line of each test case contains a single binary string $s$ ($1 \le \lvert s \rvert \le 2 \cdot 10^5$), consisting of characters 0 and 1. 38 39 It is guaranteed that the sum of string lengths $|s|$ over all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, output a single integer — the maximum area of a rectangle consisting only of ones. If there is no such rectangle, output $0$. 44 45 Example 46 47 Input 48 49 ``` 50 5 51 52 0 53 54 1 55 56 101 57 58 011110 59 60 101010 61 ``` 62 63 Output 64 65 ``` 66 0 67 1 68 2 69 6 70 1 71 ``` 72 73 Note 74 75 In the first test case, there is a table $1 \times 1$ consisting of a single character 0, so there are no rectangles consisting of ones, and the answer is $0$. 76 77 In the second test case, there is a table $1 \times 1$, consisting of a single character 1, so the answer is $1$. 78 79 In the third test case, there is a table: 80 81 | | | | 82 | --- | --- | --- | 83 | 1 | 0 | 1 | 84 | 1 | 1 | 0 | 85 | 0 | 1 | 1 | 86 87 In the fourth test case, there is a table: 88 89 | | | | | | | 90 | --- | --- | --- | --- | --- | --- | 91 | 0 | 1 | 1 | 1 | 1 | 0 | 92 | 0 | 0 | 1 | 1 | 1 | 1 | 93 | 1 | 0 | 0 | 1 | 1 | 1 | 94 | 1 | 1 | 0 | 0 | 1 | 1 | 95 | 1 | 1 | 1 | 0 | 0 | 1 | 96 | 1 | 1 | 1 | 1 | 0 | 0 | 97 98 In the fifth test case, there is a table: 99 100 | | | | | | | 101 | --- | --- | --- | --- | --- | --- | 102 | 1 | 0 | 1 | 0 | 1 | 0 | 103 | 0 | 1 | 0 | 1 | 0 | 1 | 104 | 1 | 0 | 1 | 0 | 1 | 0 | 105 | 0 | 1 | 0 | 1 | 0 | 1 | 106 | 1 | 0 | 1 | 0 | 1 | 0 | 107 | 0 | 1 | 0 | 1 | 0 | 1 | 108 109 Rectangles with maximum area are shown in bold.