P9732 [CEOI 2023] Trade

译自 CEOI2023 Day2 T1 [Trade](https://www.ceoi2023.de/wp-content/uploads/2023/09/4-trade.pdf)。

有 $n$ 个机器人排成一排，第 $i$ 个机器人的购买价是 $c_i$ 欧元，卖出价是 $s_i$ 欧元。 给定 $1\le k\le n$，你需要购买一段长度至少为 $k$ 的区间中所有的机器人，然后选择其中的恰好 $k$ 个机器人来卖出。 你需要求出： 1. 你能够得到的最大收益； 2. 在收益最大化的前提下，哪些机器人可以在某种最优方案中被卖出。

第一行包含两个整数 $n,k$。 第二行 $n$ 个正整数 $c_1,\dots,c_n$。 第三行 $n$ 个正整数 $s_1,\dots,s_n$。

第一行输出一个整数表示最大收益。 第二行输出一个 $01$ 串，第 $i$ 位输出 $1$ 表示第 $i$ 个机器人可以在某种最优方案中被卖出，反之第 $i$ 位输出 $0$。

样例一中最优方案是购买第 $3\sim 5$ 个机器人然后将它们卖出，但仍然会亏损 $1$ 欧元。 样例二中最大收益为 $2$ 欧元，可以购买 $1,2,3$ 并卖出 $1,3$，也可以购买 $3,4$ 并卖出 $3,4$，也可以购买 $3,4,5$ 并卖出 $3,5$，因此 $1,3,4,5$ 都有可能在某种最优方案中被卖出，输出 `10111`。 ### 数据规模与约定 对于全部数据，$1\le k\le n \le 250000$，$1\le c_i,s_i\le 10^9$。 - Subtask 1（5+5 points）：$n \le 200$。 - Subtask 2（5+5 points）：$n \le 6000$。 - Subtask 3（5+5 points）：$k=2$。 - Subtask 4（10+15 points）：$k\le 200$。 - Subtask 5（25+20 points）：无特殊限制。 在每个子任务中，如果第一行的输出正确，可以获得子任务前半部分的分数，如果第二行的输出也正确，可以获得子任务全部的分数。