← 返回题目列表

Codeforces · 1662/J

J. 训练营

中文机器翻译题面 查看原题

您正在组织一个训练营,向年幼的孩子教授算法。有 $$$n^2$$$ 孩子,按 $$$n$$$ 网格组织在 $$$n$$$ 中。每个孩子的年龄在 $$$1$$$ 到 $$$n$$$ 岁之间(含),且同一行或同一列的任意两个孩子年龄不同。

您想要准确选择 $$$n$$$ 个孩子参加编程竞赛,每行只有一个孩子,每列只有一个孩子。此外,未被选中的孩子必须比在其行和列中选择的两个孩子都大,或者比在其行和列中选择的两个孩子都小(否则他们会抱怨)。请注意,始终可以选择满足这些要求的 $$$n$$$ 孩子(例如,选择年龄相同的 $$$n$$$ 孩子)。

在训练营期间,您观察到有些孩子擅长编程,而另一些则不擅长。在满足所有要求的情况下,您最多可以选择多少个擅长编程的孩子?

输入

第一行包含 $$$n$$$ ($$$1 \leq n \leq 128$$$) — 网格的大小。

以下 $$$n$$$ 行描述了孩子们的年龄。具体来说,第 $$$i$$$ 行包含 $$$n$$$ 整数 $$$a_{i,1}, \, a_{i,2}, \, \dots, \, a_{i, n}$$$ ($$$1 \le a_{i,j} \le n$$$) — 其中 $$$a_{i,j}$$$ 是第 $$$i$$$ 行中孩子的年龄,第 $$$j$$$ 列。保证同一行或同一列上的两个孩子具有不同的年龄,即 $$$a_{i,j} \ne a_{i,j'}$$$ 对于任何 $$$1\le i\le n$$$、$$$1\le j < j'\le n$$$ 和 $$$a_{i,j} \ne a_{i',j}$$$ 对于任何 $$$1\le i < i'\le n$$$,$$$1\le j\le n$$$。

以下 $$$n$$$ 行描述了孩子们的编程技能。具体来说,第 $$$i$$$ 行包含 $$$n$$$ 整数 $$$c_{i,1}, \, c_{i,2}, \, \dots, \, c_{i, n}$$$ ($$$c_{i,j} \in \{0, \, 1\}$$$) — 其中 $$$c_{i,j}=1$$$ 如果孩子在$$$i$$$第行和$$$j$$$第列擅长编程,否则$$$c_{i,j}=0$$$。

输出

打印在满足所有要求的情况下您可以选择的擅长编程的孩子的最大数量。

示例

输入 #1

3
1 2 3
3 1 2
2 3 1
1 0 0
0 0 1
0 0 0

输出 #1

1

输入 #2

4
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
1 1 1 0
0 0 1 0
1 1 0 1
0 0 0 1

输出 #2

2

注意

在第一个示例中,不可能选择擅长编程的两个孩子(在 $$$1$$$ 行和 $$$1$$$ 列,以及 $$$2$$$ 行和 $$$3$$$ 列),因为这样你就必须选择 $$$3$$$ 行和 $$$2$$$ 列中的孩子,在这种情况下,两个孩子会抱怨($$$1$$$ 行中的孩子)和列 $$$2$$$,以及行 $$$3$$$ 和列 $$$1$$$)。

通过选择 $$$1$$$ 岁的 $$$3$$$ 孩子来实现包含擅长编程的 $$$1$$$ 孩子的有效选择。

在第二个样本中,满足要求的 $$$n$$$ 个孩子有 $$$10$$$ 个有效选择,每个孩子都恰好选择了 $$$2$$$ 擅长编程的孩子。