It's Mooin' Time

题目描述

注意：本题时间限制为 3s，是默认时间限制的 1.5 倍。 Bessie 有一个长度为 $N$（$1\le N\le 3\cdot 10^5$）的字符串，只由字符 M 和 O 组成。对于字符串的每个位置 $i$，将该位置的字符改成另一个字符需要花费 $c_i$（$1\le c_i\le 10^8$）。 Bessie 认为如果字符串中包含更多长度为 $L$ 的 moo，它会看起来更好（$1\le L\le \min(N, 3)$）。长度为 $L$ 的 moo 定义为一个 M，后面跟着 $L-1$ 个 O。 对于每个正整数 $k$，从 $1$ 到 $\lfloor N/L\rfloor$（含端点），计算将字符串修改为至少包含 $k$ 个等于长度为 $L$ 的 moo 的子串时所需的最小总代价。

输入格式

第一行包含 $L$ 和 $N$。 第二行包含 Bessie 的长度为 $N$ 的字符串，只由 M 和 O 组成。 第三行包含以空格分隔的整数 $c_1\dots c_N$。

输出格式

输出 $\lfloor N/L\rfloor$ 行，按 $k$ 从小到大依次输出每个 $k$ 的答案。

1 4
MOOO
10 20 30 40

0
20
50
90

3 4
OOOO
50 40 30 20

40

2 20
OOOMOMOOOMOOOMMMOMOO
44743602 39649528 94028117 50811780 97338107 30426846 94909807 22669835 78498782 18004278 16633124 24711234 90542888 88490759 12851185 74589289 54413775 21184626 97688928 10497142

0
0
0
0
0
12851185
35521020
60232254
99881782
952304708

3 20
OOOMOMOOOMOOOMMMOMOO
44743602 39649528 94028117 50811780 97338107 30426846 94909807 22669835 78498782 18004278 16633124 24711234 90542888 88490759 12851185 74589289 54413775 21184626 97688928 10497142

0
0
0
44743602
119332891
207066974

提示

SCORING: Input 5: $L=3, N\le 5000$ Input 6: $L=1$ Inputs 7-10: $L=2$ Inputs 11-18: $L=3$ Problem credits: Benjamin Qi

标签: USACO|2024|Platinum

来源

USACO|2024|Platinum