#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 $M$ s and $O$ s.

The next line contains space-separated integers $c_1…c_N$ .

출력

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

부분문제

번호	점수	조건
#1	10점	$L=3, N\le5,000$
#2	20점	$L=1$
#3	30점	$L=2$
#4	40점	$L=3$

예제1

입력

1space_bar 4keyboard_return
MOOOkeyboard_return
10space_bar 20space_bar 30space_bar 40

출력

0keyboard_return
20keyboard_return
50keyboard_return
90

예제2

입력

3space_bar 4keyboard_return
OOOOkeyboard_return
50space_bar 40space_bar 30space_bar 20

출력

예제3

입력

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

출력

0keyboard_return
0keyboard_return
0keyboard_return
0keyboard_return
0keyboard_return
12851185keyboard_return
35521020keyboard_return
60232254keyboard_return
99881782keyboard_return
952304708

예제4

입력

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

출력

0keyboard_return
0keyboard_return
0keyboard_return
44743602keyboard_return
119332891keyboard_return
207066974

출처

USACO 2024 December Platinum

역링크 공식 문제집만

로그인해야 코드를 작성할 수 있어요.

#8189 upload -회 done -회 how_to_reg -명 call_split 서브태스크

It's Mooin' Time timer 3초 memory 1024MB

문제 picture_in_picture_alt text_fields

입력

출력

부분문제

예제1

예제2

예제3

예제4

출처

역링크 공식 문제집만

#8189
서브태스크

It's Mooin' Time 3초 1024MB

문제