← 返回题目列表

AtCoder · past201912_n

N. 土地清理

中文机器翻译题面 查看原题

警告

在日本标准时间 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位整数类型。