分数: 600 点
问题陈述
在 AtCoder, Inc. 开发的一款名为 Snuketoon 的游戏中,玩家扮演 Snuke 来躲避水枪的水。
平台由无限数线组成,Snuke 位于该点 0 在游戏开始时。
从游戏一开始,Snuke每秒可以做出三个动作之一:移动 1 向负方向移动 1 朝正方向,或保持静止。更正式地说,如果 Snuke 的位置是 p at t 秒 (t \geq 0, t 是一个整数)从游戏开始,他的位置为 t+1 秒即可 p-1, p,或 p+1.
Snuke 因被水枪浸湿而受到伤害。水枪射击 N 次,并且 i第一个镜头表示为 T_i, D_i,和 X_i 如下。
- At T_i 比赛开始后几秒,水从左边或右边射出。让 p 是Snuke当时的位置。如果他处于以下范围内,他会受到以下伤害。
- 当 D_i = 0,他采取 X_i - p 点伤害(如果他在范围内) p \lt X_i.
- 当 D_i = 1,他采取 p - X_i 点伤害(如果他在范围内) X_i \lt p.
高桥是一名职业玩家,他希望在比赛结束后将 Snuke 受到的总伤害降到最低 N第一个镜头,发布关于此游戏的推文。求游戏进行时 Snuke 受到的总伤害,以将其最小化。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq T_1 \lt T_2 \lt \dots \lt T_N \leq 10^9
- D_i (1 \leq i \leq N) is 0 or 1.
- -10^9 \leq X_i \leq 10^9 (1 \leq i \leq N)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N T_1 D_1 X_1 T_2 D_2 X_2 \vdots T_N D_N X_N
输出
打印玩游戏时 Snuke 受到的伤害点数,以将其最小化。
示例输入 1
3 1 0 3 3 1 0 4 0 6
示例输出 1
7
为了方便起见,让 t 表示从游戏开始起经过的秒数。在完成所有射击之前,Snuke 的最佳移动路线如下。
- 当 t = 0,Snuke 就在这个点上 0。他动了 1 正方向。
- 当 t = 1,Snuke 就在这个点上 1 并采取 2 第一次射击造成的伤害。他动了 1 负方向。
- 当 t = 2,Snuke 就在这个点上 0。他仍然一动不动。
- 当 t = 3,Snuke 就在这个点上 0 并且第二次射击不会造成任何伤害。他动了 1 正方向。
- 当 t = 4,Snuke 就在这个点上 1 并采取 5 第三次射击造成的伤害。
在这里,Snuke 总共需要 7 点伤害,所以你应该打印 7.
示例输入 2
3 1 0 1 6 1 1 8 0 -1
示例输出 2
0
示例输入 3
5 1 0 1000000000 2 1 -1000000000 3 0 1000000000 4 1 -1000000000 5 0 1000000000
示例输出 3
4999999997