问题 1324. -- 火聚聚铺地毯

1324: 火聚聚铺地毯

时间限制:1000 ms 内存限制:128 MB
提交:142 解决:40
[ 提交][ 状态][ 讨论版]

题目描述

火聚聚在准备一场晚宴，他的一个计划是在一段坐标为M到E（包含M和E）的路径中铺上红地毯，但是这段路径太长了，一张地毯可能不够，他可能得用若干地毯合起来才能把它铺满，他找到了一位神奇的地毯商，地毯商有N块神奇的地毯，每块地毯可以铺满坐标T1到T2的范围（包含T1T2），花费为S，地毯不能移动，火聚聚希望选取若干数量的地毯，使得在铺满整个范围（即范围内每个坐标都至少包含于一个地毯中）的情况下花费最少

输入

单组数据

第一行三个数字N, M, E(N <= 1e5 , 1 <= M <= E <= 1e18)

之后N行每行三个数字T1, T2, S(M <= T1 <= T2 <= E , S <= 1e4)

输出

一个数字，代表最小花费，如果无论如何都无法铺满，输出-1

（数据保证结果在int范围内）

样例输入

3 1 5 1 3 3 4 5 2 1 1 1

样例输出

5

提示

选用第一个区间覆盖了1, 2, 3三个点，第二个区间覆盖了4, 5两个点,第三个区间只覆盖了1点，没有必要选中，所以结果是2+3=5

来源

火辣鸡不会include

[ 提交][ 状态][ 讨论版]
Baidu
map