{"problem":{"name":"[PA 2021] Wystawa","description":{"content":"给定长度为 $n$ 的序列 $a, b$。 你需要构造一个序列 $c$，构造方法为： - 选择 $k$ 个 $i$，令 $c_i \\leftarrow a_i$。 - 对于其他 $i$，令 $c_i \\leftarrow b_i$。 求序列 $c$ 的最大子段和的最小值，并给出一种方案。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":6000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9051"},"statements":[{"statement_type":"Markdown","content":"给定长度为 $n$ 的序列 $a, b$。\n\n你需要构造一个序列 $c$，构造方法为：\n\n- 选择 $k$ 个 $i$，令 $c_i \\leftarrow a_i$。\n- 对于其他 $i$，令 $c_i \\leftarrow b_i$。\n\n求序列 $c$ 的最大子段和的最小值，并给出一种方案。\n\n## Input\n\n第一行，两个整数 $n, k$；\n\n第二行，$n$ 个整数 $a_1, a_2, \\cdots, a_n$；\n\n第三行，$n$ 个整数 $b_1, b_2, \\cdots, b_n$。\n\n## Output\n\n第一行，一个整数，表示序列 $c$ 的最大子段和的最小值；\n\n第二行，一个长为 $n$ 的字符串 $s$，若令 $c_i \\leftarrow a_i$，$s_i = \\text{A}$；否则，$s_i = \\text{B}$。\n\n**如有多解，输出任意一组均可。**\n\n[samples]\n\n## Note\n\n对于 $100\\%$ 的数据，$1 \\leq n \\leq 10^5$，$0 \\leq k \\leq n$，$-10^9 \\leq a_i, b_i \\leq 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9051","tags":["动态规划 DP","贪心","二分","平衡树","2021","Special Judge","PA（波兰）"],"sample_group":[["6 2\n-1 7 0 2 -5 0\n3 1 4 -3 -3 12","4\nBBABBA"],["3 2\n-1 -4 -1\n-4 -2 -1","0\nAAB"]],"created_at":"2026-03-03 11:09:25"}}