#1954. 封印
封印
封印
题目描述
标题: 封印 - Problem - QOJ.ac
#14577. 封印
你是一名大魔法师,现在遇到了 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
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 1
1 3 1
2 5 1
4 6 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
338