luogu#P10784. 【MX-J1-T4】『FLA - III』Wrestle
【MX-J1-T4】『FLA - III』Wrestle
题目背景
在 2022 年末,疫情将西北某不知名知名学校的大多数学生关在家中上网课,安同学还不知道,他和语文老师的对决已然悄无声息地开始了——他每天早读和语文课都直接睡过去了。
安同学习惯起来穿好衣服、面对摄像头睡觉,摄像头只能拍到他的半个肩膀,就算被强制打开也不会暴露他在睡觉的事实,而且从来没有老师强制打开他的摄像头。而这个不凡的早晨,语文老师打开了他的摄像头,现在是早读时间,他在朦胧中被老师的关爱声叫醒,可惜为时已晚,老师已经愤怒。安同学决定假装网络卡顿,平复老师愤怒的心情。
老师,愤怒了!在安同学醒来后的某些时间段,她要呼叫他的真名,其余时间等他应答。与此同时安同学要打造网卡的假象,他可以在某些时间段内检查设备或者呼叫老师,其余时间静止或随机在画面中闪现,他在这些时间段内的行为称为表演。你的任务是帮助安同学在不激怒老师的情况下最大化表演时间。
因为安同学实在是太抽象了,原始题面受他影响变得也很抽象,这里只有形式化题面给你看。
题目描述
给定三个正整数 和两组线段。第一组线段有权值,共 条,是红色的;第二组线段没有权值,共 条,是蓝色的。这些线段位于同一个数轴。
-
使用 三个正整数表示一条从数轴上第 个整点覆盖到第 个整点,权值为 的红色线段。保证数轴上任意一个整点至多被红色线段覆盖一次。
-
使用 两个正整数表示一条从数轴上第 个整点覆盖到第 个整点,没有权值的蓝色线段。保证数轴上任意一个整点至多被蓝色线段覆盖一次。
如果一条红色线段从第 个整点覆盖到第 个整点,一条蓝色线段从第 个整点覆盖到第 个整点且 ,就认为这两条线段有交集,交集包含从第 个整点到第 个整点的全部 个整点。你可以选择一些蓝色线段,一种合法的选择方案必须符合以下条件:
-
题目给定的每条红色线段至多与你选择的 条蓝色线段有交集。
-
所有和你选择的蓝色线段有交集的红色线段权值之和不超过 。
选择方案合法时,你选择的蓝色线段和所有红色线段的交集至多能包含多少个整点?
输入格式
第一行输入三个正整数 。
接下来 行,第 行输入三个正整数 表示一条红色线段。
接下来 行,第 行输入两个正整数 表示一条蓝色线段。
保证数轴上任意一个整点至多被红色线段覆盖一次。保证数轴上任意一个整点至多被蓝色线段覆盖一次。
输出格式
输出一行一个整数表示答案。
2 3 23
7 18 7
63 71 2
77 86
13 19
63 71
15
4 5 7
59 65 7
39 42 1
43 51 2
19 33 2
14 25
71 81
6 11
59 69
83 92
7
4 8 45
80 94 22
60 67 2
35 44 45
7 14 5
82 86
2 3
58 63
48 50
73 80
25 45
11 19
93 94
13
提示
「样例解释 #1」
如图,选择输入的第 条蓝色线段和第 条蓝色线段。
第 条蓝色线段与第 条红色线段有交,交集包含从第 个整点到第 个整点的所有整点;第 条蓝色线段与第 条红色线段有交,交集包含从第 个整点到第 个整点的所有整点。
第 条红色线段仅与第 条蓝色线段有交,第 条红色线段仅与第 条蓝色线段有交;和被选择的蓝色线段有交的红色线段权值和为 ,方案合法。故答案为 。
「数据范围」
本题采用捆绑测试。
Subtask | 分值 | ||||
---|---|---|---|---|---|
#1 | |||||
#2 | |||||
#3 | |||||
#4 |
对于 的数据,,,,,,。保证数轴上任意一个整点至多被红色线段覆盖一次。保证数轴上任意一个整点至多被蓝色线段覆盖一次。