問題一覧 > 通常問題

No.2644 Iro Iro-Iro

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 25
作問者 : cho435 / テスター : shobonvip noya2
お気に入りにしたユーザー ProblemId : 10656 / 自分の提出
問題文最終更新日: 2024-02-19 21:16:55
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
traP 作問ハッカソンコンテスト 002(day2) (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。