問題一覧 > 通常問題

No.2859 Falling Balls

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 19
作問者 : dyktr_06 / テスター : square1001
お気に入りにしたユーザー ProblemId : 10861 / 自分の提出
問題文最終更新日: 2024-08-25 10:08:19
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
yukicoder contest 442 MMA Contest 019 (順位表) の他の問題:

Problem Statement

Yakitori-kun is at coordinate $0$ on a number line at time $0$.

For each $t = 0, 1, 2, \dots$, letting $u$ be his coordinate at time $t$, Yakitori-kun moves to a coordinate between $u-K$ and $u+K$, inclusive, at exactly time $t+0.5$.

Now, $N$ balls will fall.

The $i$-th ball falls at coordinate $X_i$ at time $T_i$. If Yakitori-kun is at coordinate $X_i$ at exactly time $T_i$, he can catch the $i$-th ball, and catching it gives him a score of $C_i$.

Find the maximum score Yakitori-kun can obtain by acting appropriately.


Constraints

  • $1 \leq N \leq 2 \times 10^{5}$
  • $1 \leq K \leq 10^{9}$
  • $1 \leq T_i \leq 10^{9}$
  • $| X_i | \leq 10^{9}$
  • $1 \leq C_i \leq 10^{9}$
  • $(T_1, X_1), (T_2, X_2), \dots, (T_N, X_N)$ are all distinct.
  • All input values are integers.

Input

The input is given from standard input in the following format.

$N$ $K$ 
$T_1$ $T_2$ ... $T_N$ 
$X_1$ $X_2$ ... $X_N$ 
$C_1$ $C_2$ ... $C_N$ 

Output

Output the answer to the problem on a single line.

Sample

Sample 1
Input
3 2
1 2 3
-1 2 4
5 3 4
Output
7

For example, a score of $7$ can be achieved by acting as follows.

  • Move to coordinate $1$ at time $0.5$.
  • Move to coordinate $2$ at time $1.5$.
  • Catch the $2$-nd ball at time $2$, gaining a score of $3$.
  • Move to coordinate $4$ at time $2.5$.
  • Catch the $3$-rd ball at time $3$, gaining a score of $4$.
  • Make no moves from time $3.5$ onward.
Sample 2
Input
8 5
3 85 69 67 63 90 24 38
55 11 -18 -71 -96 -5 10 40
92 95 79 31 1 48 98 43
Output
363

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。