思路与做法

• 索引消模：用 $s2=s+s$，则 $A_{r,c}=s2[(n-r)+c]$，避免每格做取模。

• 最大矩形（全 $0$）：维护直方图高度 $H[c]$（当前行该列为 $0$ 则 $H[c]\leftarrow H[c]+1$，否则 $H[c]\leftarrow 0$），对每一行用单调栈在 $O(n)$ 求“柱状图最大矩形”，总 $O(n^2)$。

• 最大直角等腰三角形（全 $0$）：两向 $DP$，自底向上、滚动一行，空间 $O(n)$、时间 $O(n^2)$。

  • 向右下（顶点在左上）：

  

题目内容

给定一个长度为$n$的二进制字符串$s$，由$0$和$1$字符组成。我们需要构建一个行数为$n$，列数为$n$的方表，由$0$和$1$字符组成。第一行为原始字符串 $s$，第二行为字符串$s$向右循环移动一个，第三行为字符串$s$向右循环移动两个，以此类推。

求表中所有由$0$组成的三角形或矩形的最大面积值。

第一行是字符串$s$。

第二行是字符串$s$向右循环移动一个位置。

第$i$行是字符串$s$向右循环移动$i-1$个位置。

输入描述

输入一个长度为$n$的二进制字符串$s$，仅包含$0$和$1$字符，其中$1≤n≤5000$

输出描述

在一行上输出$n$个整数，代表对于每一个$i$的答案。

样例1

输入

00110			

输出

6

说明

在构造的方表中，最大由$0$组成的三角形面积为$6$，构造的表格如下:

$00110$

$00011$

$10001$

$11000$

$01100$