It's Mooin' Time | Code Joint

**Note: The time limit for this problem is 3s, 1.5x the default.**

Bessie has a string of length $N$ ( $1 \leq N \leq 3 \cdot 1 0^{5}$ ) consisting solely of the characters M and O. For each position $i$ of the string, there is a cost $c_{i}$ to change the character at that position to the other character ( $1 \leq c_{i} \leq 1 0^{8}$ ).

Bessie thinks the string will look better if it contains more moos of length $L$ ( $1 \leq L \leq min (N, 3)$ ). A moo of length $L$ is an M followed by $L - 1$ Os.

For each positive integer $k$ from $1$ to $⌊ N / L ⌋$ inclusive, compute the minimum cost to change the string to contain at least $k$ substrings equal to a moo of length $L$ .

SCORING:

Input 5: $L = 3, N \leq 5000$
Input 6: $L = 1$
Inputs 7-10: $L = 2$
Inputs 11-18: $L = 3$

Problem credits: Benjamin Qi

Source: USA Computing Olympiad.

Input Format

The first line contains $L$ and $N$ .

The next line contains Bessie's length- $N$ string, consisting solely of Ms and Os.

The next line contains space-separated integers $c_{1} \dots c_{N}$ .

Output Format

Output $⌊ N / L ⌋$ lines, the answer for each $k$ in increasing order.

Sample Input 1

1 4 MOOO 10 20 30 40

Sample Output 1

0 20 50 90

Sample Input 2

3 4 OOOO 50 40 30 20

Sample Output 2

40

Sample Input 3

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

Sample Output 3

0 0 0 0 0 12851185 35521020 60232254 99881782 952304708

Sample Input 4

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

Sample Output 4

0 0 0 44743602 119332891 207066974

Submit

Language