102745: [AtCoder]ABC274 F - Fishing
Description
Score : $500$ points
Problem Statement
On a number line, there are $N$ fish swimming.
Fish $i$, which has a weight of $W_i$, is at the coordinate $X_i$ at time $0$ and moves at a speed of $V_i$ in the positive direction.
Takahashi will choose an arbitrary real number $t$ greater than or equal to $0$ and do the following action at time $t$ just once.
Action: Choose an arbitrary real number $x$. Catch all fish whose coordinates are between $x$ and $x+A$, inclusive.
Find the maximum total weight of fish that he can catch.
Constraints
- $1 \leq N \leq 2000$
- $1 \leq A \leq 10^4$
- $1 \leq W_i\leq 10^4$
- $0 \leq X_i\leq 10^4$
- $1 \leq V_i\leq 10^4$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $A$ $W_1$ $X_1$ $V_1$ $W_2$ $X_2$ $V_2$ $\vdots$ $W_N$ $X_N$ $V_N$
Output
Print the answer.
Sample Input 1
3 10 100 0 100 1 10 30 10 20 10
Sample Output 1
111
At time $0.25$, fish $1$, $2$, and $3$ are at the coordinates $25$, $17.5$, and $22.5$, respectively. Thus, the action done at this time with $x=16$ catches all the fish.
Sample Input 2
3 10 100 100 100 1 10 30 10 20 10
Sample Output 2
100
One optimal choice is to do the action at time $0$ with $x=100$.
Sample Input 3
4 10 1000 100 10 100 99 1 10 0 100 1 1 1
Sample Output 3
1110
One optimal choice is to do the action at time $1$ with $x=100$.
Input
题意翻译
### 题目描述 有 $n$ 条鱼在数轴上移动。 第 $i$ 条鱼在时刻 $0$ 时在位置 $x_i$ 处，价值为 $w_i$，将会以每时刻 $t_i$ 的速度向数轴正方向前进。 你是一个渔夫，你有感应河流的能力，你已经知晓所有鱼的 $x,w,t$ 属性。 你会选择一个时刻 $t$，在位置 $x$ 撒下一张长度为 $a$ 的网，所有在时刻 $t$ 时处于区间 $[x,x+a]$ 的鱼都会被你捕获。 你想求出你撒一次网能捕获的鱼的价值和的最大值。 ### 输入格式 第一行两个整数 $n,a$，含义如题中所述。 接下来 $n$ 行，第 $i+1$ 行三个整数，表示第 $i$ 条鱼的 $w,x,t$ 属性。 ### 输出格式 一行一个整数，表示答案。 ### 数据范围与提示 对于所有数据，$1\leq n\leq 2\times 10^3,1\leq a,w_i,x_i,t_i\leq 10^4$。 Translate by Zek3L.Output
问题描述
在数轴上有N条鱼正在游动。
重量为$W_i$的第i条鱼在时间0时处于坐标$X_i$，以速度$V_i$向正方向游动。
高桥将在大于等于0的任意实数$t$时刻选择一次动作。
动作：选择任意实数$x$。捕获坐标在$x$和$x+A$之间的所有鱼（包括$x$和$x+A$）。
求他能捕获的最大总重量。
约束条件
- $1 \leq N \leq 2000$
- $1 \leq A \leq 10^4$
- $1 \leq W_i\leq 10^4$
- $0 \leq X_i\leq 10^4$
- $1 \leq V_i\leq 10^4$
- 输入中的所有值都是整数。
输入
输入通过标准输入给出，格式如下：
$N$ $A$ $W_1$ $X_1$ $V_1$ $W_2$ $X_2$ $V_2$ $\vdots$ $W_N$ $X_N$ $V_N$
输出
打印答案。
样例输入1
3 10 100 0 100 1 10 30 10 20 10
样例输出1
111
在时间$0.25$时，鱼1、2和3分别处于坐标$25$、$17.5$和$22.5$。因此，在这个时刻执行动作，选择$x=16$可以捕获所有鱼。
样例输入2
3 10 100 100 100 1 10 30 10 20 10
样例输出2
100
一种最优选择是在时间$0$执行动作，选择$x=100$。
样例输入3
4 10 1000 100 10 100 99 1 10 0 100 1 1 1
样例输出3
1110
一种最优选择是在时间$1$执行动作，选择$x=100$。