#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ff first
#define ss second
using namespace std;
vector <int> j,o,i;
int n,m,k,ans,a[200001],ph[200001],sh[200001];
string s;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
cin>>s;
s=' '+s;
/*if(m*3>n){
cout<<-1;
return 0;
}
*/
for(k=1; k<=n; k++){
ph[k]=ph[k-1];
if(s[k]=='J')ph[k]++,j.pb(k);
if(s[k]=='I')i.pb(k);
if(s[k]=='O')o.pb(k);
}
for(k=n; k>0; k--){
sh[k]=sh[k+1];
if(s[k]=='I')sh[k]++;
}
if((int)j.size()<m || (int)o.size()<m || (int)i.size()<m)
{
cout<<-1;
return 0;
}
//cout<<"GIO"; return 0;
int ans=10000000;
for(k=0; k<=(int)o.size()-m; k++){
//cout<<sh[o[k]]<<" "<<ph[o[k]]<<'\n';
if(sh[o[k]]<m)break;
if(ph[o[k]]>m)break;
int pos1=lower_bound(j.begin(),j.end(),o[k])-1-j.begin();
int pos2=lower_bound(i.begin(),i.end(),o[k+m-1])-i.begin();
int sz=j[pos1]-j[pos1-m+1]-m;
if(pos1<m-1 || pos2>(int)i.size()-m)continue;
//cout<<pos1+1<<" "<<pos2+1<<'\n';
sz++; //cout<<sz<<'\n';
sz+=i[pos2+m-1]-i[pos2]-m+1; //cout<<sz<<'\n';
sz+=o[k+m-1]-o[k]-m+1; //ans=min(ans,sz); //cout<<ans<<'\n';
ans=min(ans,i[pos2+m-1]-j[1+pos1-m]+1-3*m);
}
if(ans==10000000)cout<<-1;
else cout<<ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
