24691번 - Gross LCS 다국어언어 제한

Note that the memory limit is unusually low.

Let $\operatorname{LCS}(A, B)$ denote the length of the longest common subsequence of integer sequences $A = \langle a_1, a_2, \ldots, a_n \rangle$ and $B = \langle b_1, b_2, \ldots, b_m \rangle$.

For an integer $x$, let $A + x$ denote the sequence $\langle a_1 + x, a_2 + x, \ldots, a_n + x \rangle$.

You are given two integer sequences $A$ and $B$. Find the sum of $\operatorname{LCS}(A + x, B)$ over all integers $x$ from $-10^{100}$ to $10^{100}$.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 4000$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^8 \le a_i \le 10^8$).

The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($-10^8 \le b_i \le 10^8$).

Print the sum of $\operatorname{LCS}(A + x, B)$ over all integers $x$ from $-10^{100}$ to $10^{100}$.

An integer sequence $P$ is a subsequence of an integer sequence $Q$ if $P$ can be obtained from $Q$ by deletion of several (possibly zero or all) elements. The longest common subsequence of sequences $A$ and $B$ is the longest sequence $C$ that is a subsequence of both $A$ and $B$.

In the example test:

• $\operatorname{LCS}(A - 5, B) = \operatorname{LCS}(\langle 0, 0, 3 \rangle, \langle 3, 6, 3, 6 \rangle)$ = 1;
• $\operatorname{LCS}(A - 2, B) = \operatorname{LCS}(\langle 3, 3, 6 \rangle, \langle 3, 6, 3, 6 \rangle)$ = 3;
• $\operatorname{LCS}(A + 1, B) = \operatorname{LCS}(\langle 6, 6, 9 \rangle, \langle 3, 6, 3, 6 \rangle)$ = 2;
• $\operatorname{LCS}(A + x, B) = 0$ for any $x \notin \{ -5, -2, 1 \}$.

Therefore the answer is $1 + 3 + 2 = 6$.