페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8189
서브태스크

It's Mooin' Time 3초 1024MB

문제

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

Bessie thinks the string will look better if it contains more moos of length L (1≤L≤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.


입력

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…c_N.


출력

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


부분문제

번호 점수 조건
#110점

L=3, N\le5,000

#220점

L=1

#330점

L=2

#440점

L=3


예제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

출처

USACO 2024 December Platinum

역링크 공식 문제집만