#include <bits/stdc++.h>
#define N 200005
#define int long long
using namespace std;
void ck(string s,int k){
int cnt = 0;
for(auto u:s){
if(u == 'J' && cnt < k)cnt++;
if(u == 'O' && cnt >= k && cnt < 2*k)cnt++;
if(u == 'I' && cnt >= 2*k && cnt < 3*k)cnt++;
}
if(cnt != 3*k){
cout << -1 << endl;
exit(0);
}
}
int J[N],O[N],I[N];
void solve(){
int n,k;
cin >> n >> k;
string s;
cin >> s;
ck(s,k);
s = "."+s;
for(int i=0;i<N;i++){
J[i] = O[i] = I[i] = N-1;
}
queue<int> J_J,O_O,I_I;
for(int i=n;i>=1;i--){
if(s[i] == 'J')J_J.push(i);
if(s[i] == 'O')O_O.push(i);
if(s[i] == 'I')I_I.push(i);
if(J_J.size() > k)J_J.pop();
if(O_O.size() > k)O_O.pop();
if(I_I.size() > k)I_I.pop();
if(J_J.size() == k)J[i] = J_J.front() + 1;
if(O_O.size() == k)O[i] = O_O.front() + 1;
if(I_I.size() == k)I[i] = I_I.front() + 1;
}
int maxi = 0;
for(int i=1;i<=n;i++){
maxi = max(maxi,i+n-I[O[J[i]]]);
}
cout << n - 3*k - maxi;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t=1;
//cin>>t;
while(t--){
solve();
}
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}
Compilation message
ho_t2.cpp: In function 'void solve()':
ho_t2.cpp:33:23: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
33 | if(J_J.size() > k)J_J.pop();
| ~~~~~~~~~~~^~~
ho_t2.cpp:34:23: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
34 | if(O_O.size() > k)O_O.pop();
| ~~~~~~~~~~~^~~
ho_t2.cpp:35:23: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
35 | if(I_I.size() > k)I_I.pop();
| ~~~~~~~~~~~^~~
ho_t2.cpp:36:23: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
36 | if(J_J.size() == k)J[i] = J_J.front() + 1;
| ~~~~~~~~~~~^~~~
ho_t2.cpp:37:23: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
37 | if(O_O.size() == k)O[i] = O_O.front() + 1;
| ~~~~~~~~~~~^~~~
ho_t2.cpp:38:23: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
38 | if(I_I.size() == k)I[i] = I_I.front() + 1;
| ~~~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4920 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4936 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Correct |
3 ms |
4928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4920 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4936 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Correct |
3 ms |
4928 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4924 KB |
Output is correct |
18 |
Correct |
3 ms |
4940 KB |
Output is correct |
19 |
Correct |
3 ms |
4924 KB |
Output is correct |
20 |
Correct |
3 ms |
4940 KB |
Output is correct |
21 |
Correct |
3 ms |
4924 KB |
Output is correct |
22 |
Correct |
3 ms |
4940 KB |
Output is correct |
23 |
Correct |
3 ms |
4940 KB |
Output is correct |
24 |
Correct |
3 ms |
4940 KB |
Output is correct |
25 |
Correct |
3 ms |
4928 KB |
Output is correct |
26 |
Correct |
3 ms |
4940 KB |
Output is correct |
27 |
Correct |
3 ms |
4940 KB |
Output is correct |
28 |
Correct |
1 ms |
204 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
204 KB |
Output is correct |
32 |
Correct |
1 ms |
204 KB |
Output is correct |
33 |
Correct |
3 ms |
4940 KB |
Output is correct |
34 |
Correct |
3 ms |
4940 KB |
Output is correct |
35 |
Correct |
3 ms |
4940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4920 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4936 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Correct |
3 ms |
4928 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4924 KB |
Output is correct |
18 |
Correct |
3 ms |
4940 KB |
Output is correct |
19 |
Correct |
3 ms |
4924 KB |
Output is correct |
20 |
Correct |
3 ms |
4940 KB |
Output is correct |
21 |
Correct |
3 ms |
4924 KB |
Output is correct |
22 |
Correct |
3 ms |
4940 KB |
Output is correct |
23 |
Correct |
3 ms |
4940 KB |
Output is correct |
24 |
Correct |
3 ms |
4940 KB |
Output is correct |
25 |
Correct |
3 ms |
4928 KB |
Output is correct |
26 |
Correct |
3 ms |
4940 KB |
Output is correct |
27 |
Correct |
3 ms |
4940 KB |
Output is correct |
28 |
Correct |
1 ms |
204 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
204 KB |
Output is correct |
32 |
Correct |
1 ms |
204 KB |
Output is correct |
33 |
Correct |
3 ms |
4940 KB |
Output is correct |
34 |
Correct |
3 ms |
4940 KB |
Output is correct |
35 |
Correct |
3 ms |
4940 KB |
Output is correct |
36 |
Correct |
10 ms |
5352 KB |
Output is correct |
37 |
Correct |
10 ms |
5328 KB |
Output is correct |
38 |
Correct |
11 ms |
5456 KB |
Output is correct |
39 |
Incorrect |
10 ms |
5472 KB |
Output isn't correct |
40 |
Halted |
0 ms |
0 KB |
- |