Submission #1119776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119776		staszic_ojuz	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	1 ms	340 KiB

ho_t2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin>>n>>k;
    string str;
    cin>>str;
    vector<int> vect(n, -1);
    int nOfJ=0, s=0, e=0;
    while (e<n){
        if (str[e]=='J') nOfJ++;
        if (nOfJ==k){
            nOfJ--;
            while (str[s]!='J') s++;
            vect[s]=e;
            s++;
        }
        e++;
    }
    s=0;
    e=0;
    int nOfO=0;
    while (e<n){
        if (str[e]=='O') nOfO++;
        if (nOfO==k){
            nOfO--;
            while (str[s]!='O') s++;
            vect[s]=e;
            s++;
        }
        e++;
    }
    s=0;
    e=0;
    int nOfI=0;
    while (e<n){
        if (str[e]=='I') nOfI++;
        if (nOfI==k){
            nOfI--;
            while (str[s]!='I') s++;
            vect[s]=e;
            s++;
        }
        e++;
    }
    int best=-1;
    for (int i=0;i<n;i++){
        if (str[i]!='J'||vect[i]==-1) continue;
        int current;
        bool found=false;
        for (current=vect[i];current<n;current++){
            if (str[current]=='O'&&vect[current]!=-1){
                found=true;
                current=vect[current];
                break;
            }
        }
        if (!found) continue;
        found=false;
        for (;current<n;current++){
            if (str[current]=='I'&&vect[current]!=-1){
                found=true;
                current=vect[current];
                break;
            }
        }
        if (!found) continue;
        best=max(best, current-i+1-3*k);
        /*if (best<current-i+1-3*k){
            cout<<i<<" "<<best<<" "<<current-i+1-3*k<<'\n';
            best=current-i+1-3*k;
        }*/
    }
    cout<<best<<'\n';
    return 0;
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 12
• Subtask 3: 0 / 87