480 人解决,779 人已尝试。
604 份提交通过,共有 3570 份提交。
3.0 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
丽娃河是华师大著名的风景线。但由于学校财政紧缺,丽娃河边的路灯年久失修,一到晚上就会出现走在河边要打着手电的情况,不仅非常不方便,而且影响安全:已经发生了大大小小的事故多起。
方便起见,丽娃河可以看成是从 $1$ 到 $n$ 的一条数轴。为了美观,路灯只能安装在整数点上,每个整数点只能安装一盏路灯。经专业勘测,有 $m$ 个区间特别容易发生事故,所以至少要安装一定数量的路灯,
请问至少还要安装多少路灯。
第一行一个整数 $T$ $(1 \leq T \leq 300)$,表示测试数据组数。
对于每组数据:
第一行三个整数 $n, m, k$ $(1 \leq n \leq 10^3, 1 \leq m \leq 10^3, 1 \leq k \leq n)$。
第二行 $k$ 个不同的整数用空格隔开,表示这些位置一开始就有路灯。
接下来 $m$ 行表示约束条件。第 $i$ 行三个整数 $l_i, r_i, t_i$ 表示:第 $i$ 个区间 $[l_i, r_i]$ 至少要安装 $t_i$ 盏路灯 $(1 \leq l_i \leq r_i \leq n, 1 \leq t_i \leq n)$。
对于每组数据,输出 Case x: y
。其中 x 表示测试数据编号(从 1 开始),y 表示至少要安装的路灯数目。如果无解,y 为 $-1$。
3 5 1 3 1 3 5 2 3 2 5 2 3 1 3 5 2 3 2 3 5 3 5 2 3 1 3 5 2 3 2 4 5 1
Case 1: 1 Case 2: 2 Case 3: 1
因为今天不是满月,所以狼人没有出现。
480 人解决,779 人已尝试。
604 份提交通过,共有 3570 份提交。
3.0 EMB 奖励。