310338: CF1820B. JoJo's Incredible Adventures

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. JoJo's Incredible Adventurestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Did you think there was going to be a JoJo legend here? But no, that was me, Dio!

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.

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.

In the resulting table we need to find the rectangle consisting only of ones that has the largest area.

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 < n$ and $0 \le y_1 \le y_2 < n$.

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".

Input

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.

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.

It is guaranteed that the sum of string lengths $|s|$ over all test cases does not exceed $2 \cdot 10^5$.

Output

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$.

ExampleInput
5
0
1
101
011110
101010
Output
0
1
2
6
1
Note

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$.

In the second test case, there is a table $1 \times 1$, consisting of a single character 1, so the answer is $1$.

In the third test case, there is a table:

101
110
011

In the fourth test case, there is a table:

011110
001111
100111
110011
111001
111100

In the fifth test case, there is a table:

101010
010101
101010
010101
101010
010101

Rectangles with maximum area are shown in bold.

Input

题意翻译

#### 题目描述 给定一个长度为 $n$ 的二进制字符串 $s$,构建一个 $n \times n$ 的方格表。首行写下原始字符串 $s$,次行右移一个字符的循环移位字符串 $s$,第三行右移两个字符的循环移位字符串 $s$,以此类推。因此,第 $k$ 行包含一个从 $s$ 右移 $k$ 个字符的循环移位字符串。行从上到下编号 $0$ 至 $n-1$。 在生成的表中,需要找到只由数字 $1$ 构成的矩形并计算其面积,返回最大的面积。 注意:字符串 $s$ 向右循环移动 $k$ 位是指将其最后 $k$ 个字符移动到前面,即字符串 $s_{n-k+1} \cdots s_n \; s_1 \cdots s_{n-k}$。 #### 输入格式 第一行的正整数 $t$ ($1\leq t\leq 2\times10^4$) 是测试用例的数量。 对于每个测试用例,只有一行,是一个只由零和一组成的二进制字符串。 保证所有测试用例中字符总数之和不超过 $2\times 10^5$。 #### 输出格式 对于每个测试用例,输出一个整数:只由数字 $1$ 构成的矩形的最大面积。如果不存在这样的矩形,则输出 $0$。

Output

题目大意:给定一个长度为n的二进制字符串s,由字符'0'和'1'组成。根据s构建一个n×n的方形表,表的第一行是原始字符串s,第二行是s向右循环移动一次的结果,第三行是s向右循环移动两次的结果,以此类推。在得到的表中,需要找到只由'1'组成的面积最大的矩形。

输入数据格式:每个测试用例包含多个测试案例。第一行包含一个整数t(1≤t≤2×10^4)——测试案例的数量。接下来是每个测试案例的描述。每个测试案例的第一行(也是唯一一行)包含一个二进制字符串s(1≤|s|≤2×10^5),由字符'0'和'1'组成。

输出数据格式:对于每个测试案例,输出一个整数——只由'1'组成的最大矩形的面积。如果没有这样的矩形,输出0。

示例输入输出已在题目中给出,这里不再重复。题目大意:给定一个长度为n的二进制字符串s,由字符'0'和'1'组成。根据s构建一个n×n的方形表,表的第一行是原始字符串s,第二行是s向右循环移动一次的结果,第三行是s向右循环移动两次的结果,以此类推。在得到的表中,需要找到只由'1'组成的面积最大的矩形。 输入数据格式:每个测试用例包含多个测试案例。第一行包含一个整数t(1≤t≤2×10^4)——测试案例的数量。接下来是每个测试案例的描述。每个测试案例的第一行(也是唯一一行)包含一个二进制字符串s(1≤|s|≤2×10^5),由字符'0'和'1'组成。 输出数据格式:对于每个测试案例,输出一个整数——只由'1'组成的最大矩形的面积。如果没有这样的矩形,输出0。 示例输入输出已在题目中给出,这里不再重复。

加入题单

上一题 下一题 算法标签: