USACO

USACO 2024 December Contest, Platinum

Problem 2. It's Mooin' Time

Contest has ended.

Log in to allow submissions in analysis mode

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

Bessie has a string of length $N$ ( $1\le N\le 3\cdot 10^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\le c_i\le 10^8$ ).

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

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

INPUT FORMAT (input arrives from the terminal / stdin):

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 (print output to the terminal / stdout):

Output

$\lfloor N/L\rfloor$ lines, the answer for each

$k$ in increasing order.

SAMPLE INPUT:

1 4
MOOO
10 20 30 40

SAMPLE OUTPUT:

SAMPLE INPUT:

3 4
OOOO
50 40 30 20

SAMPLE OUTPUT:

SAMPLE INPUT:

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:

SAMPLE INPUT:

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:

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

Contest has ended. No further submissions allowed.