配点: 100 点
問題文
JOI花园是垂直的 N 行,横 N 它的形状为正方形,分为网格状的柱子。 从上面 i 行目 (1 \leqq i \leqq N),从左起 j 列目 (1 \leqq j \leqq N) 方格是除法。 它被称为 (i, j) 。
JOI花园的土壤不是很肥沃,所以每个地块都有特定的 1 不同颜色的花朵,最大 1 只能种植书籍。
具体来说,该部分 (i, j) 有
直到 A_{i, j} = R 时为红色,
黄色时A_{i, j} = Y ,A_{i, j} = B 当蓝色的花朵最大时 1 只能种植书籍。
K主任是这个花园的管理者,为了让花园在航拍时看起来更好,他计划按照以下程序种植花卉。
- 尺寸的整数 确定 r 。然而 必须满足 0 \leqq r \leqq \frac{N-1}{2} 。 代表
- 中心的隔间 从红色、黄色和蓝色中选择 (x, y) 。然而 必须满足 r+1 \leqq x \leqq N-r,r+1 \leqq y \leqq N-r 。 代表
- 色 c_0, c_1, c_2, \dots, c_r 。
- 各部分
关于 (x', y') ,d = |x'-x| + |y'-y| 按照以下规则种植花卉。然而,
表示|t| 是
您也可以写 t 表示绝对值。
- d \leqq r ,然后分区 (x', y') 有颜色 种植 c_d 花。 请勿在
- d > r ,然后分区 (x', y') 内种花。
给定有关花园大小和每个地块中可以种植的花朵颜色的信息,编写一个程序来找出 K 主席可以种植的最大花朵数量。
制約
- 3 \leqq N \leqq 3\,500.
- A_{i, j} 是
您也可以写
R,Y,B(1 \leqq i \leqq N, 1 \leqq j \leqq N). - N 是整数。
小課題
- (4 点) N = 3.
- (13 点) N \leqq 50.
- (17 点) N \leqq 800.
- (14 点) A_{i, j} \neq
R小于 (i, j) (1 \leqq i \leqq N, 1 \leqq j \leqq N) 是 5 或更少。 - (16 点)哪个 (i, j) (1 \leqq i \leqq N-1, 1 \leqq j \leqq N-1)也,
在A_{i, j},A_{i, j+1},A_{i+1, j},A_{i+1, j+1} 中
您可以确定是否有
R是 在 3 或更多。 - (36 点)没有额外的限制。
入力
输入按以下格式给出。
N
A_{1,1}A_{1,2}\cdotsA_{1,N}
A_{2,1}A_{2,2}\cdotsA_{2,N}
\vdots
A_{N,1}A_{N,2}\cdotsA_{N,N}
出力
K 设置主席可以种植的最大鲜花数量。 1 请按行输出。
入力例 1
3 RYR YBY BYY
出力例 1
5
r = 1,(x, y) = (2, 2) 和 是c_0 为蓝色, 如果您选择黄色作为c_1 ,它将如下所示: 5 你可以种植真花。然而,背景颜色表示每个地块中可以种植的花朵的颜色。

6 无法种植多于一朵花,所以5 。 你只需要砍掉
此输入示例是一个小作业。 1, 2, 3, 6 满足约束。
入力例 2
9 YYRYBBBYR BYYRRBYBB RBRRBRBBY RYRBRYRBR YYBRYYYRB RRYBRYRBR RBYRBRBRB BRYYRBBBR RBBBYBRRY
出力例 2
25
r = 3,(x, y) = (5, 6) 和 是c_0 ,c_1 ,c_2 为红色, 如果选择蓝色为c_3 ,如下图。 25 你可以种植真花。然而,背景颜色表示每个地块中可以种植的花朵的颜色。

26 无法种植多于一朵花,所以25 。 你只需要砍掉
此输入示例是一个小作业。 2, 3, 6 满足约束。
入力例 3
6 RBYRBY BYRBYR YRBYRB RBYRBY BYRBYR YRBYRB
出力例 3
1
此输入示例是一个小作业。 2, 3, 6 满足约束。
入力例 4
20 RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRBRRRRRRRRRRRRYRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRYRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRYRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRBR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR
出力例 4
85
此输入示例是一个小作业。 2, 3, 4, 5, 6 满足约束。
入力例 5
10 RRRRRRRRRR RYRRRRRRRR RRRRYRRRRR RBRRRRRRRR RRRRRRRRYR RBRRRRRRRR RRRRBRRRRR RBRRRRRRRR RRRRRRRRYR RRRRRRRRRR
出力例 5
25
此输入示例是一个小作业。 2, 3, 5, 6 满足约束。