*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\).

Problem credits: Benjamin Qi

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

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 \(\lfloor N/L\rfloor\) lines, the answer for each \(k\) in increasing order.

riseoj 작성

출처 올림피아드 > USACO > 2024-2025 > December > Platinum