D. Permutation - 2022 年上海市大学生程序设计竞赛 - 十月赛

仪表盘所有提交榜单题解

单点时限: 5.0 sec

内存限制: 512 MB

Given three permutations of length $n$:

Find three subsequences:

The following conditions are satisfied:

Three subsequences with equal length;
$i_1 < i_2 < \cdots < i_m$，$j_1 < j_2 < \cdots < j_m$，$k_1 < k_2 < \cdots < k_m$;
For any $t \in [1, m]$ that satisfies $a_{i_t} = b_{j_t} \times c_{k_t}$ holds or $b_{j_t} = a_{i_t} \times c_{k_t}$ holds or $c_{k_t} = a_{i_t} \times b_{j_t}$.

Find the length of the longest subsequence that can be selected to satisfy the condition.

The first line of an integer $n$ represents the length of the arrangement.

The next three rows of $n$ integers each represent the permutations $A, B$ and $C$ respectively.

One integer in a row represents the length of the longest subsequence.

Input

6
1 2 3 4 5 6
3 4 2 1 6 5
2 4 3 5 6 1

Output

$1 \le n \le 20000$, $1 \le a_i, b_i, c_i \le n$.

Note that for any $1\le i,j\le n,i\ne j$, $\ a_i\ne a_j, b_i\ne b_j , c_i\ne c_j$ holds.

Sample explanation:

A legal subsequence is taken as

1 2 5
4 6 5
4 3 1

NaN

比赛状态发生变化，点 OK 刷新。

OK

2022 年上海市大学生程序设计竞赛 - 十月赛