import java.io.*;
import java.util.*;
public class ho_t2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
PrintWriter pw = new PrintWriter(System.out);
String s = br.readLine();
ArrayList<Integer> J = new ArrayList<Integer>();
ArrayList<Integer> O = new ArrayList<Integer>();
ArrayList<Integer> I = new ArrayList<Integer>();
for(int i = 0; i < n; i++) {
if(s.charAt(i) == 'J') J.add(i);
else if(s.charAt(i) == 'O') O.add(i);
else I.add(i);
}
if(J.size() < k || O.size() < k || I.size() < k) {
pw.println(-1);
pw.close();
return;
}
int[] jPrefix = new int[J.size()];
int[] oPrefix = new int[O.size()];
int[] iPrefix = new int[I.size()];
for(int i = 1; i < J.size(); i++) jPrefix[i] = jPrefix[i - 1] + J.get(i) - J.get(i - 1) - 1;
for(int i = 1; i < O.size(); i++) oPrefix[i] = oPrefix[i - 1] + O.get(i) - O.get(i - 1) - 1;
for(int i = 1; i < I.size(); i++) iPrefix[i] = iPrefix[i - 1] + I.get(i) - I.get(i - 1) - 1;
int ans = n + 1;
for(int i = 0; i < J.size() - k + 1; i++) {
int cur = 0;
int add = k - 1;
int max = J.get(i + add);
cur += jPrefix[i + add] - jPrefix[i];
int left = 0;
int right = O.size();
while(left < right) {
int mid = left + (right - left) / 2;
if(O.get(mid) < max) {
left = mid + 1;
}
else {
right = mid;
}
}
if(O.size() - left < k) {
continue;
}
cur += O.get(left) - J.get(i + add) - 1;
cur += oPrefix[left + add] - oPrefix[left];
int val = O.get(left + add);
int og = left;
left = 0;
right = O.size();
while(left < right) {
int mid = left + (right - left) / 2;
if(I.get(mid) < val) {
left = mid + 1;
}
else {
right = mid;
}
}
if(I.size() - left < k) {
continue;
}
cur += I.get(left) - O.get(og + add) - 1;
cur += iPrefix[left + add] - iPrefix[left];
ans = Math.min(ans, cur);
}
if(ans == n + 1) {
pw.println(-1);
}
else {
pw.println(ans);
}
pw.close();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
55 ms |
8432 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
55 ms |
8432 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
55 ms |
8432 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |