No.2644 Iro Iro-Iro
Problem Statement
In this problem, a color is represented by a 3-dimensional vector $(C,M,Y)$, and it always satisfies $0 \leq C \leq 100, 0 \leq M \leq 100, 0 \leq Y \leq 100$.
There are $N$ colors. The $i\ (1 \leq i \leq N)$-th color is $(A_i, B_i, C_i)$.
You are given $M$ operations. The $j\ (1 \leq j \leq M)$-th operation uses $X_j, Y_j, Z_j$ and does the following.
- For every $i\ (1 \leq i \leq N)$, create a new color $(A_i + X_j, B_i + Y_j, C_i + Z_j)$.
- This operation produces $N$ new colors.
You want to make the number of distinct colors, counting both the colors before the operation and the new colors after the operation, as large as possible.
When you may choose and perform exactly one of the $M$ operations, what is the maximum possible number of distinct colors?
It is guaranteed that, in the given input, the conditions on colors are also satisfied after the operation.
Constraints
- All input values are integers.
- $ 1 \leq N, M \leq 2 \times 10^5 $
- $ 0 \leq A_i, B_i, C_i \leq 100 \ (1 \leq i \leq N)$
- $ -100 \leq X_i, Y_i, Z_i \leq 100 \ (1 \leq i \leq M)$
- $ (A_i, B_i, C_i) \neq (A_j, B_j, C_j)\ (i \neq j) $
- $ (X_i, Y_i, Z_i) \neq (X_j, Y_j, Z_j)\ (i \neq j) $
-
For all $i, j \ (1 \leq i \leq N, 1 \leq j \leq M)$:
- $0 \leq A_i + X_j \leq 100$
- $0 \leq B_i + Y_j \leq 100$
- $0 \leq C_i + Z_j \leq 100$
Input
$N\ M$ $A_1\ B_1\ C_1$ $A_2\ B_2\ C_2$ $\vdots$ $A_N\ B_N\ C_N$ $X_1\ Y_1\ Z_1$ $X_2\ Y_2\ Z_2$ $\vdots$ $X_M\ Y_M\ Z_M$
Output
Print the maximum number of distinct colors when performing exactly $1$ operation.
Sample
Sample 1
Input
5 3 2 2 2 3 4 5 4 2 3 1 4 4 6 2 4 1 2 3 2 0 1 1 -2 -2
Output
9
Performing the $1$-st operation results in $9$ distinct colors, the $2$-nd results in $7$, and the $3$-rd results in $8$, so print $9$, the maximum among these.
Sample 2
Input
6 2 3 2 3 3 3 4 4 2 4 2 4 2 2 5 3 3 4 3 -1 2 -1 0 1 1
Output
10
Sample 3
Input
15 10 4 3 4 2 3 2 3 4 3 2 4 2 3 4 2 4 4 4 3 5 3 2 4 5 4 5 4 3 4 5 2 3 4 4 2 2 2 4 4 2 2 5 4 3 2 0 0 0 1 2 -1 2 0 2 2 -1 0 1 1 1 0 0 2 -1 0 -1 0 1 0 -1 2 1 -2 1 0
Output
29
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2