#PQJ2557x14577. QOJ 2557_14577

    ID: 2834 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2026 互测堆贪心

QOJ 2557_14577

标题: 封印 - Problem - QOJ.ac

#14577. 封印

Statistics

你是一名大魔法师,现在遇到了 n 只怪物,第 i 只怪物的出现时间为 [li,ri),有经验值 wi。对于怪物 i,你可以选择一个实数 ki∈[li,ri],并在 [li,ki) 时间内施展封印术控制这只怪物。特别地,如果 ki=li,表示你没有对这种怪物施展封印术。由于人是有极限的,在同一时刻,你最多对 K 个怪物施展法术,K 为给定常数。

你有一个熟练度 W,由于已经很久没有使用过封印术了,在 0 时刻 W=0。对于怪物 i,如果 ki=ri,那么就成功封印了这只怪物,所以在 ri 时刻熟练度就会增加 wi;如果 ki<ri,那么怪物就会在 ki 时刻攻击你,使得熟练度重置为 0。

在任意时刻,你可以选择施展终极秘术,将时间线上的所有的 n 只怪物变成 W 枚金币,并带着它们离开。如果同一时刻发生多个事件(熟练度增加、熟练度重置、终极秘术),它们之间的生效顺序可以任意安排。

现在,请求出最多能带着多少枚金币离开。

输入格式

第一行两个正整数 n,K。

接下来 n 行,每行三个正整数 li,ri,wi,表示一只怪物。

输出格式

输出一行一个整数表示答案。

样例

样例输入 1

3 1
1 3 1
2 5 1
4 6 1

样例输出 1

2

样例输入 2

10 2
4 10 14
2 17 87
5 12 84
6 11 71
1 13 62
8 9 55
7 14 6
15 20 87
3 19 18
16 18 96

样例输出 2

338

样例 3

见附加文件中的 ex_seal3.in/ans,该样例符合子任务 5,6 的限制。

样例解释

对于样例 1,取 k1=3,k2=2,k3=6,那么 2 时刻 W 重置为 0,3 时刻 W 增加 1,6 时刻 W 增加 1,此时可以获得 2 枚金币。容易发现不可能获得 3 枚金币。

限制与约定

对于所有数据,n,li,ri,wi,K 均为正整数,1≤K≤n≤3×105,1≤wi≤109,1≤li<ri≤2n,且保证 l1,l2,…,ln,r1,r2,…,rn 构成 1∼2n 的排列。

各子任务特殊约束及分值如下:

子任务编号 n≤ 特殊性质 分值 子任务依赖 1 20 - 5 - 2 2500 wi=1 15 - 3 3×105 wi=1 20 2 4 2500 - 15 1,2 5 105 K≤30 20 - 6 3×105 - 25 3,4,5