Submission #1222546

#TimeUsernameProblemLanguageResultExecution timeMemory
1222546lukasuliashviliJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
11 ms3084 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a;i<b;++i)
int n,k,result;
string s;
signed main(){
    cin>>n>>k>>s;
    s='*'+s;
    vector<int> vec1,vec2,vec3;
    rep(i,1,n+1){
        if(s[i]=='J') vec1.push_back(i);
        if(s[i]=='O') vec2.push_back(i);
        if(s[i]=='I') vec3.push_back(i);
    }
    result=LLONG_MAX;
    rep(j,0,vec1.size()-k+1){
        int j_end=vec1[j+k-1];
        auto o_it=lower_bound(vec2.begin(),vec2.end(),j_end+1);
        if(o_it+k-1>=vec2.end()) continue;
        int o_end=*(o_it+k-1);
        auto i_it=lower_bound(vec3.begin(),vec3.end(),o_end+1);
        if(i_it+k-1>=vec3.end()) continue;
        int i_end=*(i_it+k-1);
        int length=i_end-vec1[j]+1;
        int cost=length-3*k;
        result=min(result,cost);
    }
    if(result==LLONG_MAX) cout<<-1<<endl;
    else cout<<result<<endl;
 
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...