Submission #1182166

#TimeUsernameProblemLanguageResultExecution timeMemory
1182166pythontestJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
8 ms1804 KiB
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int n,k;
void balansuj(vector<int> &zrodlo, vector<int> &ujscie, int &zp, int &up){
    if(zp+k-1>=zrodlo.size()){
        up=ujscie.size();
        return;
    }
    while(up<ujscie.size()&&ujscie[up]<zrodlo[zp+k-1]) up++;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin>>n>>k>>s;
    int b=0,e=0,res=n+1;
    vector<int> jq,oq,iq;
    int jp=0,op=0,ip=0;

    while(b<=e){
        if(jq.size()-jp>=k&&oq.size()-op>=k&&iq.size()-ip>=k){
            res=min(res,e-b-3*k);
            if(s[b]=='J') jp++;
            else if(s[b]=='O'&&op<oq.size()&&oq[op]==b) op++;
            else if(ip<iq.size()&&iq[ip]==b) ip++;
            balansuj(jq,oq,jp,op);
            balansuj(oq,iq,op,ip);
            b++;
        }
        else{
            if(e==n) break;
            if(s[e]=='J') jq.push_back(e);
            else if(s[e]=='O') oq.push_back(e);
            else iq.push_back(e);
            balansuj(jq,oq,jp,op);
            balansuj(oq,iq,op,ip);
            e++;
        }
    }
    if(res==n+1) printf("-1");
    else printf("%d",res);
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...