Submission #211467

#	Time	Username	Problem	Language	Result	Execution time	Memory
211467		brcode	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	19 ms	5580 KiB

ho_t2

#include <iostream>

using namespace std;
const int MAXN = 5e5+5;
int indj[MAXN];
int indo[MAXN];
int indi[MAXN];
int prefj[MAXN];
int prefo[MAXN];
int prefi[MAXN];
int ans = 1e9;
int main(){
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    s = '#'+s;
    for(int i=0;i<=n;i++){
        indj[i] = 1e9;
        indo[i] = 1e9;
        indi[i] = 1e9;
    }
    for(int i=1;i<=n;i++){
        prefj[i] = prefj[i-1]+(s[i]=='J');
        prefo[i] = prefo[i-1]+(s[i]=='O');
        prefi[i] = prefi[i-1]+(s[i]=='I');
        //cout<<prefj[i]<<" "<<prefo[i]<<" "<<prefi[i]<<endl;
        indj[prefj[i]] = min(indj[prefj[i]],i);
        indo[prefo[i]] = min(indo[prefo[i]],i);
        indi[prefi[i]] = min(indi[prefi[i]],i);
    }
    for(int i=1;i<=n;i++){
        int nxt = indj[prefj[i-1]+k];
        //cout<<nxt<<endl;
        if(nxt>n){
            break;
        }
        int nxt2 = indo[prefo[nxt]+k];
        
        if(nxt2>n){
            break;
        }
        int r = indi[prefi[nxt2]+k];
        if(r>n){
            break;
        }
        
        ans = min(ans,n-(3*k)-(i-1)-(n-r));
    }
    if(ans == 1e9){
        cout<<-1<<endl;
        return 0;
    }
    cout<<ans<<endl;
}

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