← 返回题目
题库练习 「USACO 2024.12 Platinum」It's Mooin' Time
← 上一题 下一题 →

A6140 | 「USACO 2024.12 Platinum」It's Mooin' Time

时间限制3s
内存限制256MB
通过 / 提交0/0

题目描述

**题目译自 [USACO 2024 December Contest, Platinum](http://usaco.org/index.php?page=dec24results) Problem 2. [It's Mooin' Time](https://usaco.org/index.php?page=viewproblem2&cpid=1453)**

Bessie 有一个长度为 $N$（$1\le N\le 3\cdot 10^5$）的字符串，仅由字符 M 和 O 组成。对于字符串中的每个位置 $i$，需要花费 $c_i$ 来将该位置上的字符修改为另一种字符（$1\le c_i\le 10^8$）。

Bessie 认为，如果字符串包含更多长度为 $L$（$1\le L\le \min(N, 3)$）的哞叫会看起来更好。一个长度为 $L$ 的哞叫指的是一个 M 后面跟着 $L-1$ 个 O。

对于从 $1$ 到 $\lfloor N/L\rfloor$ 的每一个正整数 $k$，计算将字符串修改至包含至少 $k$ 个等于长度为 $L$ 的哞叫的子串的最小花费。

输入格式

输入的第一行包含 $L$ 和 $N$。

下一行包含 Bessie 的长为 $N$ 的字符串，仅由字符 M 和 O 组成。

下一行包含空格分隔的整数 $c_1\dots c_N$。

输出格式

输出 $\lfloor N/L\rfloor$ 行，依次包含每一个 $k$ 的答案。

输入输出样例

输入 #1
1 4
MOOO
10 20 30 40
输出 #1
0
20
50
90
输入 #2
3 4
OOOO
50 40 30 20
输出 #2
40
输入 #3
2 20
OOOMOMOOOMOOOMMMOMOO
44743602 39649528 94028117 50811780 97338107 30426846 94909807 22669835 78498782 18004278 16633124 24711234 90542888 88490759 12851185 74589289 54413775 21184626 97688928 10497142
输出 #3
0
0
0
0
0
12851185
35521020
60232254
99881782
952304708
输入 #4
3 20
OOOMOMOOOMOOOMMMOMOO
44743602 39649528 94028117 50811780 97338107 30426846 94909807 22669835 78498782 18004278 16633124 24711234 90542888 88490759 12851185 74589289 54413775 21184626 97688928 10497142
输出 #4
0
0
0
44743602
119332891
207066974
C++ 编辑器
输入
输出