#include <bits/stdc++.h>
using namespace std;
#define int long long
main(){
//given a string, find the shortest substring with K level JOI as a subsequence
//two pointer?
//but how delete
//if we can compute the closest index in which we can find K 'J's, K 'O's, and K 'I's quickly, then
int n, k; cin >> n >> k;
string s; cin >> s;
int l = 0, r = -1, jcount = 0;
int jc[n], oc[n], ic[n];
for (int x = 0; x < n; x++) jc[x] = LLONG_MAX/3, oc[x] = LLONG_MAX/3, ic[x] = LLONG_MAX/3;
while (l != n-1){
if (jcount >= k) jc[l] = min(jc[l], r);
if (jcount >= k){
if (s[l] == 'J') jcount--;
l++;
}
else if (r != n){
r++;
if (r != n && s[r] == 'J') jcount++;
}
else break;
if (jcount >= k) jc[l] = min(jc[l], r);
}
l = 0, r = -1, jcount = 0;
while (l != n-1){
if (jcount >= k) oc[l] = min(oc[l], r);
if (jcount >= k){
if (s[l] == 'O') jcount--;
l++;
}
else if (r != n){
r++;
if (r != n && s[r] == 'O') jcount++;
}
else break;
if (jcount >= k) oc[l] = min(oc[l], r);
}
l = 0, r = -1, jcount = 0;
while (l != n-1){
if (jcount >= k) ic[l] = min(ic[l], r);
if (jcount >= k){
if (s[l] == 'I') jcount--;
l++;
}
else if (r != n){
r++;
if (r != n && s[r] == 'I') jcount++;
}
else break;
if (jcount >= k) ic[l] = min(ic[l], r);
}
/*
for (int x = 0; x < n; x++) cerr << jc[x] << ' ';
cerr << '\n';
for (int x = 0; x < n; x++) cerr << oc[x] << ' ';
cerr << '\n';
for (int x = 0; x < n; x++) cerr << ic[x] << ' ';
cerr << '\n';
*/
int ans = LLONG_MAX/3;
for (int x = 0; x < n; x++){
int cur = jc[x];
if (cur >= n) continue;
cur = oc[cur];
if (cur >= n) continue;
cur = ic[cur];
//cout << x << " " << cur << '\n';
ans = min(cur - x + 1, ans);
}
if (ans > LLONG_MAX/5) cout << -1;
else cout << ans - 3*k;
}
Compilation message
ho_t2.cpp:6:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
6 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
0 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
212 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
1 ms |
340 KB |
Output is correct |
| 26 |
Correct |
1 ms |
260 KB |
Output is correct |
| 27 |
Correct |
1 ms |
340 KB |
Output is correct |
| 28 |
Correct |
1 ms |
340 KB |
Output is correct |
| 29 |
Correct |
1 ms |
340 KB |
Output is correct |
| 30 |
Correct |
1 ms |
340 KB |
Output is correct |
| 31 |
Correct |
0 ms |
212 KB |
Output is correct |
| 32 |
Correct |
1 ms |
340 KB |
Output is correct |
| 33 |
Correct |
1 ms |
340 KB |
Output is correct |
| 34 |
Correct |
1 ms |
340 KB |
Output is correct |
| 35 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
0 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
212 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
1 ms |
340 KB |
Output is correct |
| 26 |
Correct |
1 ms |
260 KB |
Output is correct |
| 27 |
Correct |
1 ms |
340 KB |
Output is correct |
| 28 |
Correct |
1 ms |
340 KB |
Output is correct |
| 29 |
Correct |
1 ms |
340 KB |
Output is correct |
| 30 |
Correct |
1 ms |
340 KB |
Output is correct |
| 31 |
Correct |
0 ms |
212 KB |
Output is correct |
| 32 |
Correct |
1 ms |
340 KB |
Output is correct |
| 33 |
Correct |
1 ms |
340 KB |
Output is correct |
| 34 |
Correct |
1 ms |
340 KB |
Output is correct |
| 35 |
Correct |
1 ms |
340 KB |
Output is correct |
| 36 |
Correct |
11 ms |
4972 KB |
Output is correct |
| 37 |
Correct |
15 ms |
5220 KB |
Output is correct |
| 38 |
Correct |
11 ms |
5220 KB |
Output is correct |
| 39 |
Correct |
13 ms |
5168 KB |
Output is correct |
| 40 |
Correct |
14 ms |
5348 KB |
Output is correct |
| 41 |
Correct |
15 ms |
5220 KB |
Output is correct |
| 42 |
Correct |
15 ms |
5220 KB |
Output is correct |
| 43 |
Correct |
8 ms |
3428 KB |
Output is correct |
| 44 |
Correct |
10 ms |
4196 KB |
Output is correct |
| 45 |
Correct |
11 ms |
5220 KB |
Output is correct |
| 46 |
Correct |
12 ms |
5220 KB |
Output is correct |
| 47 |
Correct |
11 ms |
5220 KB |
Output is correct |
| 48 |
Correct |
12 ms |
5324 KB |
Output is correct |
| 49 |
Correct |
9 ms |
3684 KB |
Output is correct |
| 50 |
Correct |
12 ms |
5220 KB |
Output is correct |
| 51 |
Correct |
12 ms |
5220 KB |
Output is correct |
| 52 |
Correct |
9 ms |
5092 KB |
Output is correct |
| 53 |
Correct |
10 ms |
5220 KB |
Output is correct |
| 54 |
Correct |
8 ms |
5220 KB |
Output is correct |
| 55 |
Correct |
9 ms |
5220 KB |
Output is correct |
| 56 |
Correct |
8 ms |
5236 KB |
Output is correct |
