#PU1453. USACO 2024 December Contest, Platinum — Problem 2. It's Mooin' Time
USACO 2024 December Contest, Platinum — Problem 2. It's Mooin' Time
USACO 2024 December Contest, Platinum — Problem 2. It's Mooin' Time
题目描述
Note: The time limit for this problem is 3s, 1.5x the default. Bessie has a string of length () consisting solely of the characters M and O. For each position of the string, there is a cost to change the character at that position to the other character (). Bessie thinks the string will look better if it contains more moos of length (). A moo of length is an M followed by Os. For each positive integer from to inclusive, compute the minimum cost to change the string to contain at least substrings equal to a moo of length .
输入格式
The first line contains and . The next line contains Bessie's length- string, consisting solely of Ms and Os. The next line contains space-separated integers .
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
1 4
MOOO
10 20 30 40
0
20
50
90
样例 2
3 4
OOOO
50 40 30 20
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
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
0
0
0
44743602
119332891
207066974