#P4388. JOI2012 invitation
JOI2012 invitation
[JOI 2012 春季合宿] Invitation 招待
题目描述
JOI 镇要开一场聚会。镇上有 只狗,编号为 至 ,还有 只猫,编号为 至 。你想邀请它们全都来参加。
共有 个好友小组。第 组包含编号从 到 的所有狗,以及编号从 到 的所有猫,友好度为 。一只动物可以属于多个小组,也可以不属于任何小组。
编号为 的狗已经受邀,不计幸福值。其余动物按以下规则邀请:
- 对每只尚未受邀的动物,查看它所属且已有至少一位成员受邀的所有小组。它这一轮的幸福值等于这些组中最高的友好度;若没有这样的组,幸福值为 。
- 邀请幸福值最高的一只。平局时狗优先于猫;种类也相同时,编号较小者优先。
- 如果所选动物的幸福值为 ,邀请失败。否则邀请这只动物并计入它此时的幸福值。若还有动物没受邀,重新计算下一轮。
判断能否邀请全部动物;如果可以,求所计入的幸福值之和。
输入格式
第一行三个整数 ,其中 、。
第二行一个整数 ()。
接下来 行,第 行为 ,满足 、、。两个编号区间都包含端点。
输出格式
输出一行一个整数:若能邀请所有动物,输出各轮计入的幸福值之和;否则输出 。
样例 #1
样例输入 #1
5 6 3
4
2 4 1 3 20
1 2 2 4 40
4 5 2 3 30
4 4 4 6 10
样例输出 #1
280
最初只有狗 3 受邀。第一轮,狗 2、狗 4、猫 1、猫 2 和猫 3 的幸福值都为 ,所以先邀请狗 2。下一轮狗 1、猫 2、猫 3 和猫 4 的幸福值都为 ,所以邀请狗 1。完整顺序如下:
| 动物 | 编号 | 幸福值 |
|---|---|---|
| 狗 | 3 | — |
| 2 | 20 | |
| 1 | 40 | |
| 猫 | 2 | |
| 3 | ||
| 4 | ||
| 狗 | 30 | |
| 5 | ||
| 猫 | 1 | 20 |
| 5 | 10 | |
| 6 |
总幸福值为 。
样例 #2
样例输入 #2
10 10 1
2
1 5 1 5 3
6 10 6 10 4
样例输出 #2
-1
邀请了编号 至 的狗和猫后,其余动物的幸福值都是 。按平局规则选到狗 6,此时邀请失败。
提示
原赛 30% 的分值满足 且 ;原赛 50% 的分值满足 。