#P4935. [CEOI2023] Tricks of the Trade(机器人交易)

    ID: 4034 传统题 7000ms 2048MiB 尝试: 5 已通过: 1 难度: 10 上传者: 标签>组合数学CF3000构造数学模运算鸣谢alone_wolf提供翻译

[CEOI2023] Tricks of the Trade(机器人交易)

「CEOI2023」Tricks of the Trade(机器人交易)

题目背景

你的艺术品盗窃生涯并没有想象中那么风光,于是你把目标转向了本届 CEOI 的一枚奖牌。你设法混入组委会的总部,拿到了存放奖牌的保险箱密码。接下来的行动需要雇一名助手,你打算先从柏林的一家商店购入可编程的扫地机器人,再转卖给其他选手筹钱。

题目描述

商店按顺序摆放着 NN 个机器人,编号为 11 到 NN。购买第 ii 个机器人的费用为 cic_i,将它转卖给其他选手可以得到 sis_i。

你必须购买一段连续的机器人 [l,r][l,r],满足 r−l+1≥Kr-l+1\ge K,并从中恰好选出 KK 个机器人卖出。其余已购买但未卖出的机器人没有收入。

设卖出的编号集合为 SS,本次交易的利润为

∑i∈Ssi−∑i=lrci.\sum_{i\in S}s_i-\sum_{i=l}^{r}c_i.

请计算:

  1. 所有合法交易中的最大利润。利润可能为负数;不能选择不进行交易。
  2. 对每个机器人,判断是否存在至少一种达到最大利润的交易,使该机器人被卖出。

注意:第二问要求的是所有最优交易中卖出编号集合的并集,而不是输出某一个最优方案。因此,答案串中 1 的个数可能超过 KK。

输入格式

第一行两个整数 N,KN,K。

第二行 NN 个整数 c1,c2,…,cNc_1,c_2,\ldots,c_N。

第三行 NN 个整数 s1,s2,…,sNs_1,s_2,\ldots,s_N。

输出格式

第一行输出一个整数,表示最大利润。

第二行输出一个长度为 NN 的 01 串。若存在某种最优交易会卖出第 ii 个机器人,第 ii 个字符为 1;否则为 0。

样例 1

5 3
3 5 2 3 6
2 1 5 2 3
-1
00111

买入第 33 到第 55 个机器人并全部卖出,支出 1111、收入 1010,利润为 −1-1。任何其他合法交易的利润都更低。

样例 2

5 2
1 6 1 5 2
4 1 6 2 4
2
10111

卖出编号集合分别为 {1,3}\{1,3\}、{3,4}\{3,4\} 或 {3,5}\{3,5\},并购买覆盖这两个编号的最短区间,均可获得利润 22。因此第二问的答案为 10111。

数据范围与计分

所有数据满足 1≤K≤N≤250 0001\le K\le N\le250\,000,1≤ci,si≤1091\le c_i,s_i\le10^9。

子任务 附加限制 最大利润正确的分值 两问均正确的附加分值
1 N≤200N\le200 5
2 N≤6000N\le6000
3 K=2K=2
4 K≤200K\le200 10 15
5 无附加限制 25 20

每一评分组采用组内取最低分的方式计分。只输出正确的第一行,也可以获得各子任务的“最大利润正确”部分分;要获得附加分,必须同时正确输出两行。

CEOI 2023 原题面 PDF