← 返回题目列表

AtCoder · arc026_3

C. 荧光灯

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

問題文

一所小学有一条很长的走廊。从东向西延伸,从西端延伸到东端 L 有米。 由于学校政策,根本没有窗户,所以走廊必须用荧光灯照明。

在这个走廊里 它有 N 荧光灯。 i 第一个荧光灯来自西端。 l_i 计点和 r_i 可以在米之间照明。 此外,打开不同荧光灯所需的成本也不同。 打开第 i 个荧光灯 c_i 费用为日元。

可以通过打开所有荧光灯来照亮整个走廊,但由于我没有钱,所以我想以尽可能小的成本照亮整个走廊。 从西端开始,在走廊的哪一点? 0 计点和 L 求打开荧光灯所需的最低成本,以便以米为单位的点之间的每个点都被至少一个荧光灯照亮。


入力

输入将以以下形式通过标准输入给出。

N L
l_1 r_1 c_1
l_2 r_2 c_2
:
l_N r_N c_N

约束中的描述不充分,因此已更正。 “荧光灯照射范围”→“表示荧光灯照射范围的整数”(21:20)

  • 1 第一行是一个整数,表示荧光灯的数量。 N (1 ≦ N ≦ 10^5) 和一个代表走廊长度的整数 一个整数,表示第L(1 ≦ L ≦ 10^5)用空格分隔。
  • 2 来自行 N 行数过多 i 在线i个荧光灯照射的范围 l_i, r_i (0 ≦ l_i < r_i ≦ L) 以及开启它的成本 c_i (1 ≦ c_i ≦ 10^5) 用空格分隔。
  • 打开所有荧光灯保证照亮整个走廊。

部分点

针对此问题设置了部分分数。 如果正确答案是满足

  • 1 ≦ N ≦ 3,000 ,1 ≦ L ≦ 3,000的数据集 如果正确答案是满足 60 分被给予。
  • 1 ≦ N ≦ 10^5 ,1 ≦ L ≦ 10^5的数据集,则进一步 给出 40 点。总共100点。

出力

打印一行照亮整个走廊所需的最低成本。 当第


入力例1

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

出力例1

5

1, 2, 4, 5个荧光灯打开时,总成本最小化。 从西端出发,除非你打开第


入力例2

8 10
0 2 1
2 3 1
0 4 1
0 2 1
3 7 1
0 10 1080
8 10 1
9 10 1

出力例2

1080

6号荧光灯。7计点和8仪表点之间的距离不会被照亮。 最好的打开方式是仅使用第 6个荧光灯。


入力例3

10 10
0 1 1
1 2 1
2 3 1
3 4 1
4 5 1
0 5 4
5 7 2
6 8 3
8 10 1
2 9 3

出力例3

6

入力例4

5 5
0 1 100000
1 2 100000
2 3 100000
3 4 100000
4 5 100000

出力例4

500000