题目描述
题目译自 PA 2021 Runda 3 Wystawa
给定长度为 n 的序列 {ai} 与 {bi} ,你需要构造一个序列 c ,使得 ci=ai 或 ci=bi ,并且 ci=ai 的位置个数恰好为 k 。
记序列 c 的最大子段和为 s ,求 max(s,0) 的最小值,并给出一种方案。
输入格式
第一行两个正整数 n,k,表示序列长度和使用 {ai} 中的数个数的限制。
第二行 n 个整数 ai 。
第三行 n 个整数 bi 。
输出格式
第一行一个整数,表示 max(s,0) 的最小值。
第二行一个长为 n 的字符串,若 ci=ai ,则 si=A ,若 ci=bi ,则 si=B 。
数据范围与提示
1≤n≤105 ,0≤k≤n
∣ai∣≤109 ,∣bi∣≤109