#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
#define deb(x) cout<<#x<<": "<<x<<endl
int iceil(int a, int b) {
return (a + b - 1) / b;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.precision(20);
#ifdef strawberryshaker2005
freopen("input.txt", "r", stdin);
#endif
int n,k;
cin>>n>>k;
string s;
cin>>s;
vector<int> js,os,is,fj,fo,fi;
for(int i=0;i<n;i++){
if(s[i]=='J') js.push_back(i);
if(s[i]=='O') os.push_back(i);
if(s[i]=='I') is.push_back(i);
}
fj.push_back(0);
for(int i=1;i<js.size();i++){
fj.push_back(fj[i-1]+(js[i]-js[i-1]-1));
}
fo.push_back(0);
for(int i=1;i<os.size();i++){
fo.push_back(fo[i-1]+(os[i]-os[i-1]-1));
}
fi.push_back(0);
for(int i=1;i<is.size();i++){
fi.push_back(fi[i-1]+(is[i]-is[i-1]-1));
}
int ans=mod;
for(int i=0;i<fj.size();i++){
int temp=0;
int ostart=mod,istart=mod;
if(i+k-1<fj.size()){
ostart=js[i+k-1]+1;
temp+=fj[i+k-1]-fj[i];
}
else break;
if(ostart+k-1<n){
int real_ostart=0;
if(lower_bound(os.begin(),os.end(),ostart)==os.end()) break;
else real_ostart=distance(os.begin(),lower_bound(os.begin(),os.end(),ostart));
//deb(real_ostart);
temp+=fo[real_ostart+k-1]-fo[real_ostart];
istart=os[real_ostart+k-1]+1;
}
else break;
//deb(temp);
if(istart+k-1<n){
int real_istart=0;
if(lower_bound(is.begin(),is.end(),istart)==is.end()) break;
else real_istart=distance(is.begin(),lower_bound(is.begin(),is.end(),istart));
temp+=fi[real_istart+k-1]-fi[real_istart];
}
else break;
ans=min(ans,temp);
}
if(ans==mod) cout<<"-1\n";
else cout<<ans<<endl;
return(0);
}
Compilation message
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:34:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i=1;i<js.size();i++){
| ~^~~~~~~~~~
ho_t2.cpp:38:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i=1;i<os.size();i++){
| ~^~~~~~~~~~
ho_t2.cpp:42:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i=1;i<is.size();i++){
| ~^~~~~~~~~~
ho_t2.cpp:46:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i=0;i<fj.size();i++){
| ~^~~~~~~~~~
ho_t2.cpp:49:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | if(i+k-1<fj.size()){
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
