题目内容

考古学家发现了一串长度为 $n$ 的符号 $s$，仅由 0 和 1 组成。将 $s$ 作为第一行；之后对于每一行，将上一行整体向右平移一位，并把最右侧的字符移到最左侧，从而得到一个 $n \times n$ 的方格表。行列编号均从 $0$ 开始。

在方格表中，字符 0 表示可用格子，字符 1 表示不可用格子。现在要选取一个完全由可用格子组成的区域。允许的区域形状只有以下两类：

• 矩形：选择连续的行区间和连续的列区间，构成一个子矩形。
• 直角三角形：选择一个起始格子 $(r,c)$ 和边长 $k$。向右扩展表示对每个 $0 \le d < k$，行 $r+d$ 上从列 $c$ 到列 $c+d$ 的 $d+1$ 个格子均为 0；向左扩展表示对每个 $0 \le d < k$，行 $r+d$ 上从列 $c-d$ 到列 $c$ 的 $d+1$ 个格子均为 0。

区域面积按其中包含的 0 格子数计算，直角三角形面积为 $k(k+1)/2$。求所有可行区域的最大面积。