#PU1453. USACO 2024 December Contest, Platinum — Problem 2. It's Mooin' Time

    ID: 1339 传统题 3000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:dec24来源:usaco.orgscoring:equal_test_cases二分答案线段树

USACO 2024 December Contest, Platinum — Problem 2. It's Mooin' Time

USACO 2024 December Contest, Platinum — Problem 2. It's Mooin' Time

题目描述

Note: The time limit for this problem is 3s, 1.5x the default. Bessie has a string of length NN (1≤N≤3⋅1051\le N\le 3\cdot 10^5) consisting solely of the characters M and O. For each position ii of the string, there is a cost cic_i to change the character at that position to the other character (1≤ci≤1081\le c_i\le 10^8). Bessie thinks the string will look better if it contains more moos of length LL (1≤L≤min⁡(N,3)1\le L\le \min(N, 3)). A moo of length LL is an M followed by L−1L-1 Os. For each positive integer kk from 11 to ⌊N/L⌋\lfloor N/L\rfloor inclusive, compute the minimum cost to change the string to contain at least kk substrings equal to a moo of length LL.

输入格式

The first line contains LL and NN. The next line contains Bessie's length-NN string, consisting solely of Ms and Os. The next line contains space-separated integers c1…cNc_1\dots c_N.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 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