Submission #956359

#TimeUsernameProblemLanguageResultExecution timeMemory
956359Dennis_JasonJJOOII 2 (JOI20_ho_t2)C++14
100 / 100
7 ms5336 KiB
#include <bits/stdc++.h>
#define NMAX 500001
#define pb push_back
#define MOD 1000000007
#define nl '\n'
#define INF 0x3f3f3f3f
#define pii pair<int,int>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int n,k,ans=INF;
string s;
int vj[NMAX],vo[NMAX],vi[NMAX],li,lo,lj;
int J='J'-'0';
int O='O'-'0';
int I='I'-'0';

signed main() {
    cin>>n>>k;

    cin>>s;
    for(int i=0;i<n;++i)
    {
        if(s[i]=='I')
            vi[++li]=i;
        if(s[i]=='J')
            vj[++lj]=i;
        if(s[i]=='O')
            vo[++lo]=i;
       // cout<<s[i];
    }

    int pj=1,po=1,pi=1;
    while(pj+k-1<=lj&& po+k-1<=lo&& pi+k-1<=li)
    {
       while(po+k-1<=lo&& vo[po]<=vj[pj+k-1])
           po++;
       if(po+k-1<=lo)
           while(pi+k-1<=li && vi[pi]<=vo[po+k-1])
               pi++;
       if(pj+k-1<=lj && po+k-1<=lo && pi+k-1<=li)
       {
           ans=min(ans,(vi[pi+k-1]-vj[pj]+1)-3*k);
       }
        pj++;
    }
    if(ans==INF)
        cout<<-1;
    else
        cout<<ans;


    return 0;

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...