《封印》解题报告
题目大意
你是一名大魔法师,现在遇到了 \(n\) 只怪物,第 \(i\) 只怪物的出现时间为 \([l_i,r_i)\),有经验值 \(w_i\)。对于怪物 \(i\),你可以选择一个实数 \(k_i\in[l_i,r_i]\),并在 \([l_i,k_i)\) 时间内施展封印术控制这只怪物。特别地,如果 \(k_i=l_i\),表示你没有对这种怪物施展封印术。由于人是有极限的,在同一时刻,你最多对 \(K\) 个怪物施展法术,\(K\) 为给定常数。
由于你已经很久没有使用过封印术了,在 \(0\) 时刻你的熟练度为 \(0\)。对于怪物 \(i\),如果 \(k_i=r_i\),那么你就成功封印了这只怪物,所以在 \(r_i\) 时刻你的熟练度就会增加 \(w_i\);如果 \(k_i<r_i\),那么怪物就会在 \(k_i\) 时刻攻击你,使得熟练度重置为 \(0\)。
在任意时刻,设此时熟练度为 \(W\),你可以选择施展终极秘术,将时间线上的所有的 \(n\) 只怪物变成 \(W\) 枚金币,并带着它们离开。如果同一时刻发生多个事件(熟练度增加、熟练度重置、终极秘术),它们之间的生效顺序可以任意安排。
现在,请求出你最多能带着多少枚金币离开。
数据范围
对于所有数据,\(n,l_i,r_i,w_i,K\) 均为正整数,\(1\leq K\leq n\leq 3\times 10^5,1\leq w_i\leq10^9,1\leq l_i<r_i\leq 10^9\),且保证 \(l_1,l_2,\dots,l_n,r_1,r_2,\dots,r_n\) 为 \(2n\) 个不同正整数。
各子任务特殊约束及分值如下:
-
子任务 1(5 分):\(n\leq 20\);
-
子任务 2(15 分):\(n\leq 1000,w_i=1\);
-
子任务 3(15 分):\(n\leq 1000\) ;
-
子任务 4(30 分):\(w_i=1\) ;
-
子任务 5(35 分):无特殊性质。