#CW12. 最优移动(move)

    ID: 238 传统题 4000ms 512MiB 尝试: 2 已通过: 1 难度: 4 上传者: 标签>成外联盟2026动态规划单调性DP数据结构单调队列

最优移动(move)

题目描述

数轴上,有 1,2,…,n1,2,\ldots,n 总共 nn 个点。

有 mm 个事件,第 ii 次发生在时间 tit_i,点 aia_i 上。

如果你在第 ii 次事件发生时位于点 xx,你将获得收益 bi−∣ai−x∣b_i - |a_i-x|。

注意,mm 次收益你都必须获得,即使它可能是负的。另外,tit_i 不保证互不相同。

你可以在单位时间间隔内,在数轴上移动最多 dd 单位长度,但禁止移动到 [1,n][1,n] 的范围以外,你可以在初始时刻(时间等于 11 时)处于范围内的任意整数点上。

求按照最优的方式移动,能获得的最大总收益是多少。

输入格式

第一行包含三个整数 n,m,dn, m, d。

接下来 mm 行,每行包含三个整数 ai,bi,tia_i, b_i, t_i。

保证满足 ti≤ti+1t_i \le t_{i+1}。

输出格式

输出一个整数,表示最大的总收益。

样例 1 输入

50 3 1
49 1 1
26 1 4
6 1 10

样例 1 输出

-31

样例 2 输入

10 2 1
1 1000 4
9 1000 4

样例 2 输出

1992

数据范围

对于所有测试数据,保证:1≤n≤1500001 \le n \le 150000,1≤m≤3001 \le m \le 300,1≤d≤n1 \le d \le n,1≤ai≤n1 \le a_i \le n,1≤bi≤1091 \le b_i \le 10^9,1≤ti≤1091 \le t_i \le 10^9。

测试点 n≤n \le m≤m \le 特殊性质
1∼41 \sim 4 1010 55 无
5∼65 \sim 6 10001000 100100 tn≤100t_n \le 100
7∼107 \sim 10 无
11∼1211 \sim 12 5000050000 200200
13∼1413 \sim 14 150000150000 300300 d=1d=1,ti=it_i=i
15∼2015 \sim 20 无