AT_past201912_n.整地

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

坐标轴上有 $n$ 个区间，每个区间均在左端点为 $0$ ，右端点为 $w$ 的线段内。第 $i$ 个区间的左右端点表示的数字分别为 $l_i$ 和 $r_i$ 。

现在你要去掉一部分区间，使得有一段长度为 $c$ 的线段没有被任何区间覆盖。第 $i$ 个区间删去的代价为 $p_i$ 。请输出你所花费的最小代价。

输入格式

第一行为三个整数 $n,w,c$ 。

接下来 $n$ 行，每行三个整数 $l_i,r_i,p_i$ 。

输出格式

一行一个整数，最小代价。（若不需要删去任何一个区间，输出0即可。）

数据规模与约定

$1 \le n \le 100000$ ， $10 \le w \le 10^9$ ， $1 \le c \le w$ ， $0 \le l_i \lt r_i \le w$ ， $1 \le p_i \le 10^9$ 。

输入输出样例

输入#1
```
3 10 5
1 3 100
8 10 123
4 6 3
```
输出#1
```
3
```

输入#2

22 30 10
0 30 1000000000
0 30 1000000000
0 30 1000000000
7 30 261806
6 19 1
5 18 1238738
12 28 84
10 14 5093
9 20 9
15 26 8739840
6 8 240568
14 19 198
2 4 1102
1 29 5953283
9 20 183233
9 13 44580
6 23 787237159
12 14 49
28 29 9020727
14 20 318783
2 19 9862194
9 30 166652

输出#2

3805189325

输入解题思路，AI测评打分。不知道怎么写?

首页