「2017 山东一轮集训 Day7」养猫

传统 1000 ms 512 MiB

$201$ 通过 $470$ 提交

题目描述

你养了一只猫，为了让它快乐地成长，你需要合理地安排它每天的作息时间。假设一天分为 $n$ 个时刻，猫在每个时刻要么是吃东西，要么是睡觉。在第 $i$ 个时刻，假如猫是去吃东西，那么它能获得愉悦值 $e_i$，假如是去睡觉，那么能获得的愉悦值为 $s_i$。

猫要成长，不仅仅需要快乐，还需要健康的作息。经过研究，对于每一个连续的长度为 $k$ 的作息区间，即所有的时刻区间 $[i, i + k - 1], 1 \leq i \leq n − k + 1$，猫都要至少有 $\text{ms}$ 的时刻用来睡觉，$\text{me}$ 的时刻用来吃东西，这样猫才能健康成长。

现在你想合理地安排一天中的这 $n$ 个时刻，使得猫在能健康成长的前提下，获得尽量多的愉悦值。

输入格式

第一行四个整数 $n, k, \text{ms}, \text{me}$。 第二行包含 $n$ 个整数，代表 $s_i$。 第三行包含 $n$ 个整数，代表 $e_i$。

输出格式

第一行一个整数，代表猫能获得的愉悦值。 第二行 $n$ 个字符，可以为 $\texttt{S}$ 或 $\texttt{E}$，代表猫在某个时刻是在睡觉（$\texttt{S}$）还是在吃东西（$\texttt{E}$）。

样例

输入

5 4 2 2
4 8 6 2 2
4 6 9 6 0

输出

29
SSEES

数据范围与提示

• 对于 $20\%$ 的数据，$n \leq 20$；
• 对于 $40\%$ 的数据，$n \leq 100$；
• 另外有 $20\%$ 的数据，$\text{ms} = 0$；
• 对于 $100\%$ 的数据，$1 \leq k \leq n \leq 1000$； $0 \leq \text{ms}, \text{me}, \text{ms} + \text{me} \leq k$； $0 \leq e_i, s_i \leq 10^9$；
• 对于每个测试点，假如你回答对了第一行，那么你能获得 $40\%$ 的分数，假如你两行都正确，那么你能获得 $100\%$ 的分数。