| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 55 | 43 | 39 | 82.979% |
You are given an array of $N$ integers: $[A_1, A_2, \dots , A_N ]$.
A subsequence can be derived from an array by removing zero or more elements without changing the order of the remaining elements. For example, $[2, 1, 2],ドル $[3, 3],ドル $[1],ドル and $[3, 2, 1, 3, 2]$ are subsequences of array $[3, 2, 1, 3, 2],ドル while $[1, 2, 3]$ is not a subsequence of array $[3, 2, 1, 3, 2]$.
A subsequence is microwavable if the subsequence consists of at most two distinct values and each element differs from its adjacent elements. For example, $[2, 1, 2],ドル $[3, 2, 3, 2],ドル and $[1]$ are microwavable, while $[3, 3]$ and $[3, 2, 1, 3, 2]$ are not microwavable.
Denote a function $f(x, y)$ as the length of the longest microwavable subsequence of array $A$ such that each element within the subsequence is either $x$ or $y$. Find the sum of $f(x, y)$ for all 1ドル ≤ x < y ≤ M$.
The first line consists of two integers $N$ $M$ (1ドル ≤ N, M ≤ 300,円 000$).
The second line consists of $N$ integers $A_i$ (1ドル ≤ A_i ≤ M$).
Output a single integer representing the sum of $f(x, y)$ for all 1ドル ≤ x < y ≤ M$.
5 4 3 2 1 3 2
13
The value of $f(1, 2)$ is 3ドル,ドル taken from the subsequence $[2, 1, 2]$ that can be obtained by removing $A_1$ and $A_4$. The value of $f(1, 3)$ is 3ドル,ドル taken from the subsequence $[3, 1, 3]$ that can be obtained by removing $A_2$ and $A_5$. The value of $f(2, 3)$ is 4ドル,ドル taken from the subsequence $[3, 2, 3, 2]$ that can be obtained by removing $A_3$. The value of $f(1, 4),ドル $f(2, 4),ドル and $f(3, 4)$ are all 1ドル$.
3 3 1 1 1
2
The value of $f(1, 2)$ and $f(1, 3)$ are both 1ドル,ドル while the value of $f(2, 3)$ is 0ドル$.