警告
在日本标准时间 2019 年 12 月 29 日凌晨 05:00 之前请勿提及此问题。如有违反,可要求赔偿。
考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
有一个宽度的门 W。下面,我们将这个门视为一个线段,并假设该线段上的一点的坐标为 0 和 W (含)。
我们有 N 石头散落在门上。的 i第石头 (1 \leq i \leq N) 占用该段 (l_i, r_i),并且成本 p_i 日元(日本货币)将其删除。多个棋子可能占据同一点。
你想让汽车通过这个门,通过移除一些石头,这样就会有一段长度 C 不与石头重叠。编写一个程序来找出这样做的最低金额。
约束
- 1 \leq N \leq 100000
- 10 \leq W \leq 10^9
- 1 \leq C \leq W
- 0 \leq l_i < r_i \leq W
- 1 \leq p_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N W C l_1 r_1 p_1 l_2 r_2 p_2 : l_N r_N p_N
输出
打印代表实现目标所需的最低金额的整数(或打印 0 如果不需要移除石头)。
示例输入 1
3 10 5 1 3 100 8 10 123 4 6 3
示例输出 1
3
如果我们移走第三块石头 3 日元,没有石头会与段重叠 [3, 8] 长度 5。这是最优的选择。
示例输入 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
金额可能不适合 32位整数类型。