【集训队作业2018】line - 题目

小U最近锅多如狗，因为有一堆的人要找他调代码。一共有 $n$ 个人要找他办事。他们做了一道国家集训队的一道神题~~，要用到可持久化 Top cactus 等算法~~，但是他们都没有把代码调出来。他们分别编号为 $1, 2, \dots, n$ ，且编号从小到大排成一列。

小U想把他们按编号分成各批，然后从前往后（即编号从小到大）分批调代码。其中每一批人的编号是连续的一段。第 $i$ 个人调出代码需要 $t_{i}$ 个单位时间。而每一批蒟蒻需要把代码都调好，才能出来。也就是说，他们占用教室的时间为每个人调代码所需时间的最大值。

由于同学Gayfriends之间容易互相影响，每一批蒟蒻内编号最大的人，设编号为 $i$ ，不能与编号为 $l_{i}$ 的人在同一批，否则这一批的代码会调不出来。如果 $l_{i} = 0$ ，就意味着没有这个限制这位同学是个纯洁的好孩子。

而每位蒟蒻都会有不耐烦指数。第 $i$ 位蒟蒻每等待一个单位时间，他的不耐烦程度就会增加 $w_{i}$ 。等待时间指的是从他们排好队到这个蒟蒻进教室为止的这段时间，也就是排在他前面的每一批蒟蒻占用教室时间之和。

现在小U想让他们成功调出这道神题，并且不耐烦程度的和最小。可是他忙着帮助他们，就把这个任务交给了你。

第一行一个正整数 $n$ ，表示人数。

接下来 $n$ 行每行三个非负整数 $l_{i}, t_{i}, w_{i} $ ，意义如题面所述。

保证 $0 \leq l_{i} < i$ 。

仅一行，表示 $n$ 个人的最小不耐烦程度之和。

1
0 2426 8707

4
0 1929 401
1 7233 960
1 3564 9106
2 4746 182

21084798

本题有 5 个子任务。对于所有数据，有 $0 \leq t_{i}, w_{i} \leq 10^{9}$ ，且最终答案不大于 $10^{18}$ 。

Subtask 1 (9 pts): $1 \leq n \leq 10$ ；

Subtask 2 (10 pts): $1 \leq n \leq 2 000$ ；

Subtask 3 (18 pts): $1 \leq n \leq 100 000$ 且 $w_{i}$ ， $t_{i}$ 均为一定范围内等概率随机生成；

Subtask 4 (12 pts): $1 \leq n \leq 100 000$ 且 $t_{i} \leq t_{i + 1}$ ；

Subtask 5 (51 pts): $1 \leq n \leq 100 000$ 。

时间限制： $3 s$

空间限制： $512 MB$

Universal Online Judge