#P4935. [CEOI2023] Tricks of the Trade(机器人交易)
[CEOI2023] Tricks of the Trade(机器人交易)
「CEOI2023」Tricks of the Trade(机器人交易)
题目背景
你的艺术品盗窃生涯并没有想象中那么风光,于是你把目标转向了本届 CEOI 的一枚奖牌。你设法混入组委会的总部,拿到了存放奖牌的保险箱密码。接下来的行动需要雇一名助手,你打算先从柏林的一家商店购入可编程的扫地机器人,再转卖给其他选手筹钱。
题目描述
商店按顺序摆放着 个机器人,编号为 到 。购买第 个机器人的费用为 ,将它转卖给其他选手可以得到 。
你必须购买一段连续的机器人 ,满足 ,并从中恰好选出 个机器人卖出。其余已购买但未卖出的机器人没有收入。
设卖出的编号集合为 ,本次交易的利润为
请计算:
- 所有合法交易中的最大利润。利润可能为负数;不能选择不进行交易。
- 对每个机器人,判断是否存在至少一种达到最大利润的交易,使该机器人被卖出。
注意:第二问要求的是所有最优交易中卖出编号集合的并集,而不是输出某一个最优方案。因此,答案串中 1 的个数可能超过 。
输入格式
第一行两个整数 。
第二行 个整数 。
第三行 个整数 。
输出格式
第一行输出一个整数,表示最大利润。
第二行输出一个长度为 的 01 串。若存在某种最优交易会卖出第 个机器人,第 个字符为 1;否则为 0。
样例 1
5 3
3 5 2 3 6
2 1 5 2 3
-1
00111
买入第 到第 个机器人并全部卖出,支出 、收入 ,利润为 。任何其他合法交易的利润都更低。
样例 2
5 2
1 6 1 5 2
4 1 6 2 4
2
10111
卖出编号集合分别为 、 或 ,并购买覆盖这两个编号的最短区间,均可获得利润 。因此第二问的答案为 10111。
数据范围与计分
所有数据满足 ,。
| 子任务 | 附加限制 | 最大利润正确的分值 | 两问均正确的附加分值 |
|---|---|---|---|
| 1 | 5 | ||
| 2 | |||
| 3 | |||
| 4 | 10 | 15 | |
| 5 | 无附加限制 | 25 | 20 |
每一评分组采用组内取最低分的方式计分。只输出正确的第一行,也可以获得各子任务的“最大利润正确”部分分;要获得附加分,必须同时正确输出两行。