import std; void main () { int N, M; readln.read(N, M); string S = readln.chomp; solve(N, M, S); } void solve (int N, int M, string S) { /* 'x'や'o'のあるところで区切って良い。本質的に、区切られた文字は3種類のみ 1. x --- x 2. x --- o 3. o --- o このうち、最も優先すべきはタイプ3で、かつ-の長さが奇数のもの。これは最高効率で埋めることができる可能性がある。 次に優先度が高いのが長さ2以上の2と、3かつ-の長さが偶数のもの。これらは確実に1個で2つの祝日を生み出せる。 次に優先度が高いのが長さ3以上の1 一番優先度が低いのが長さ2以下の1と長さ1の2 これらを守って処理すれば必ず最高効率になるはず ↑間違っていた。タイプ3で長さが奇数のものは短いものから潰すべき */ /* 区間分割 */ auto T = new BinaryHeap!(Array!int, "ab") T2; int l = 0; int r = 0; while (true) { if (S.length <= l) break; if (S[l] == '-') { int type = 0; r = l; if (0 < r && S[r-1] == 'o') type++; while (true) { if (r == S.length || S[r] == 'x') { break; } if (S[r] == 'o') { type++; break; } r++; } if (type == 2 && (r-l) % 2 == 1) T2.insert(r-l); else T[type].insert(r-l); l = r; } l++; } int ans = 0; foreach (c; S) if (c == 'o') ans++; /* 処理 */ while (0 < M || !T2.empty) { // dbg /* foreach (t; T) writeln(t.dup); writeln("ans: ", ans); writeln("M: ", M); writeln(""); */ if (!T2.empty) { auto head = T2.front; T2.removeFront; if (head == 1) { ans++; continue; } if (head/2 <= M) { ans += head; M -= head/2; } else { ans += 2*M; M = 0; } continue; } if (!T[2].empty) { auto head = T[2].front; T[2].removeFront; if (head/2 <= M) { ans += head; M -= head/2; } else { ans += 2*M; M = 0; } continue; } if (!T[1].empty && 2 <= T[1].front) { auto head = T[1].front; T[1].removeFront; if (head/2 <= M) { ans += 2*(head/2); M -= head/2; head -= 2*(head/2); if (0 < head) T[1].insert(head); } else { ans += 2*M; M = 0; head -= 2*M; if (0 < head) T[1].insert(head); } continue; } if (!T[0].empty && 3 <= T[0].front) { auto head = T[0].front; T[0].removeFront; ans++; M--; head--; T[1].insert(head); continue; } /* 優先度最悪 */ if (!T[1].empty && T[1].front == 1) { auto head = T[1].front; T[1].removeFront; ans++; M--; continue; } if (!T[0].empty && T[0].front <= 2) { auto head = T[0].front; T[0].removeFront; if (head <= M) { ans += head; M -= head; } else { ans += M; head -= M; M = 0; if (0 < head) T[1].insert(head); } continue; } /* 何も選べない */ break; } writeln(ans); } void read(T...)(string S, ref T args) { auto buf = S.split; foreach (i, ref arg; args) { arg = buf[i].to!(typeof(arg)); } }