레이팅 미적용*참고: 이 문제의 시간 제한은 기본의 1.5배인 3초이다.*
베시는 문자 M과 O로만 이루어진 길이 \(N\)(\(1\le N\le 3\cdot 10^5\))의 문자열을 가지고 있다. 문자열의 각 위치 \(i\)에 대해, 그 위치의 문자를 다른 문자로 바꾸는 데 비용 \(c_i\)(\(1\le c_i\le 10^8\))가 든다.
베시는 길이 \(L\)(\(1\le L\le \min(N, 3)\))의 음머(moo)가 더 많이 들어 있을수록 문자열이 더 보기 좋다고 생각한다. 길이 \(L\)의 음머는 M 하나 뒤에 O가 \(L-1\)개 이어진 것이다.
\(1\)부터 \(\lfloor N/L\rfloor\)까지의 각 양의 정수 \(k\)에 대해, 길이 \(L\)의 음머와 같은 부분 문자열이 최소 \(k\)개 포함되도록 문자열을 바꾸는 최소 비용을 계산하여라.
문제 제공: Benjamin Qi
배점
- 입력 5: \(L=3, N\le 5000\)
- 입력 6: \(L=1\)
- 입력 7-10: \(L=2\)
- 입력 11-18: \(L=3\)
문제 제공: Benjamin Qi
첫째 줄에 \(L\)과 \(N\)이 주어진다.
다음 줄에 M과 O로만 이루어진 베시의 길이 \(N\) 문자열이 주어진다.
다음 줄에 공백으로 구분된 정수 \(c_1\dots c_N\)이 주어진다.
\(\lfloor N/L\rfloor\)개의 줄에, 각 \(k\)에 대한 답을 오름차순으로 출력한다.
1 4
MOOO
10 20 30 400
20
50
903 4
OOOO
50 40 30 20402 20
OOOMOMOOOMOOOMMMOMOO
44743602 39649528 94028117 50811780 97338107 30426846 94909807 22669835 78498782 18004278 16633124 24711234 90542888 88490759 12851185 74589289 54413775 21184626 97688928 104971420
0
0
0
0
12851185
35521020
60232254
99881782
9523047083 20
OOOMOMOOOMOOOMMMOMOO
44743602 39649528 94028117 50811780 97338107 30426846 94909807 22669835 78498782 18004278 16633124 24711234 90542888 88490759 12851185 74589289 54413775 21184626 97688928 104971420
0
0
44743602
119332891
207066974riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > December > Platinum