AT_abc217_h [ABC217H] Snuketoon

题目描述

AtCoder 公司开发的游戏《スヌケトゥーン》中，玩家需要操作すぬけ君躲避从水枪射来的水。

游戏的舞台是一条无限延伸的数轴，游戏开始时，すぬけ君位于 $0$ 点。
游戏开始后，すぬけ君每经过 $1$ 秒，可以选择以下三种操作之一：“向左移动 $1$ 单位”、“向右移动 $1$ 单位”或“不移动”。更严格地说，若すぬけ君在游戏开始后第 $t$ 秒（$t \geq 0$，$t$ 为整数）时位于 $p$ 点，则在第 $t+1$ 秒时，可以选择移动到 $p-1$、$p$ 或 $p+1$。

如果すぬけ君被水枪射出的水击中，则会受到伤害。水枪会发射 $N$ 次，第 $i$ 次发射由 $T_i, D_i, X_i$ 给出，具体如下：

• 从游戏开始后第 $T_i$ 秒，水枪会从左右任意一侧发射水。假设すぬけ君在第 $T_i$ 秒时位于 $p$ 点，则伤害的范围和数值如下：
  • 当 $D_i = 0$ 时，若 $p < X_i$，则会受到 $X_i - p$ 的伤害。
  • 当 $D_i = 1$ 时，若 $X_i < p$，则会受到 $p - X_i$ 的伤害。

职业玩家高桥君为了发布攻略信息，决定让すぬけ君在所有 $N$ 次水枪发射结束后所受的总伤害最小。请输出高桥君操作すぬけ君，使其总伤害最小的情况下，最终的总伤害。

输入格式

输入按以下格式从标准输入读入。

$N$ $T_1$ $D_1$ $X_1$ $T_2$ $D_2$ $X_2$ $\cdots$ $T_N$ $D_N$ $X_N$

输出格式

请输出高桥君操作すぬけ君，使其总伤害最小的情况下，最终的总伤害。

输入输出样例 #1

输入 #1

3
1 0 3
3 1 0
4 0 6

输出 #1

7

输入输出样例 #2

输入 #2

3
1 0 1
6 1 1
8 0 -1

输出 #2

0

输入输出样例 #3

输入 #3

5
1 0 1000000000
2 1 -1000000000
3 0 1000000000
4 1 -1000000000
5 0 1000000000

输出 #3

4999999997

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq T_1 < T_2 < \dots < T_N \leq 10^9$
• $D_i$（$1 \leq i \leq N$）为 $0$ 或 $1$
• $-10^9 \leq X_i \leq 10^9$（$1 \leq i \leq N$）
• 所有输入均为整数。

样例解释 1

为方便说明，令 $t$ 表示从游戏开始经过的秒数。すぬけ君在所有水枪发射结束前的最优移动如下：

• $t = 0$ 时，すぬけ君在 $0$ 点，选择向右移动 $1$ 单位。
• $t = 1$ 时，すぬけ君在 $1$ 点，受到第 $1$ 次水枪发射造成的 $2$ 点伤害。然后选择向左移动 $1$ 单位。
• $t = 2$ 时，すぬけ君在 $0$ 点，选择不移动。
• $t = 3$ 时，すぬけ君在 $0$ 点，未受到第 $2$ 次水枪发射的伤害。然后选择向右移动 $1$ 单位。
• $t = 4$ 时，すぬけ君在 $1$ 点，受到第 $3$ 次水枪发射造成的 $5$ 点伤害。

此时，すぬけ君总共受到 $7$ 点伤害，因此输出 $7$。

由 ChatGPT 4.1 翻译