#P9404. [POI 2020/2021 R3] Surowa zima
[POI 2020/2021 R3] Surowa zima
题目背景
译自 XXVIII Olimpiada Informatyczna - III etap Surowa zima。
d1t3。
题目描述
有一条长 米的道路(数轴)。路上有 个充电站。每天整条路上(坐标 )都会落满雪。
有一台机器能扫雪。充一次电可以扫至多 米的雪。扫雪是和移动同时进行的,详见样例解释。机器一秒能移动一米,充电不消耗时间。
简单来说,移动不扫雪不消耗电,需要一秒;移动并扫雪消耗最大电量的 ,需要一秒;扫雪必须移动。
给出每天机器的初始位置,机器初始没电,问每天清除所有雪的最少时间。终点任意。
带修,即充电站可能损坏或修好(第一天之前都是好的),但保证每天都至少有一个好的充电站(所以不会无解)。
输入格式
第一行四个整数 。
第二行 个整数 ,表示充电站的位置,保证 。
接下来 行,描述 天的事件:
- 第一行三个整数 ,分别表示昨晚修好的充电站数量,损坏的数量,和机器的初始位置。
- 第二行 个整数,表示被修好的充电站编号。
- 第三行 个整数,表示损坏的充电站编号。
输出格式
行,每行一个整数,表示每天的答案。
提示
样例解释:。 表示移动, 表示移动并扫雪。
对于所有数据,,,,,。
子任务编号 | 附加限制 | 分数 |
---|---|---|
1 | , | 10 |
2 | ,, | 12 |
3 | , | 8 |
4 | ||
5 | , | 20 |
6 | 18 | |
7 | 24 |