Submission #702510

#	Time	Username	Problem	Language	Result	Execution time	Memory
702510		1075508020060209tc	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	35 ms	8636 KiB

ho_t2

//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int n;int K;
string s;
int psj[200005];
int pso[200005];
int psi[200005];

int dpj[200005];
int dpi[200005];


signed main(){
cin>>n>>K>>s;
s="*"+s;

for(int i=1;i<=n;i++){
    psj[i]=psj[i-1];
    pso[i]=pso[i-1];
    psi[i]=psi[i-1];
    if(s[i]=='I'){
        psi[i]++;
    }
    if(s[i]=='O'){
        pso[i]++;
    }
    if(s[i]=='J'){
        psj[i]++;
    }
}

for(int i=1;i<=n;i++){
        dpj[i]=1e16;
    if(s[i]!='J'){continue;}
    if(psj[i]<K){continue;}
    int l=0;int r=i;
    while(l<r){
        int mi=l+(r-l+1)/2;
        if(mi==0||(mi!=0&&psj[i]-psj[mi-1]>=K)){
            l=mi;
        }else{
            r=mi-1;
        }
    }
    if(l!=0){
        dpj[i]=i-l+1-K;
    }
}


for(int i=1;i<=n;i++){
        dpi[i]=1e16;
    if(s[i]!='I'){continue;}
    if(psi[n]-psi[i-1]<K){continue;}
    int l=i+K-1;int r=n+1;
    while(l<r){
        int mi=l+(r-l)/2;
        if(mi==n+1||(mi!=n+1&&psi[mi]-psi[i-1]>=K)){
            r=mi;
        }else{
            l=mi+1;
        }
    }
    if(l!=n+1){
        dpi[i]=l-i+1-K;
    }
}
dpj[0]=1e16;
int ans=1e16;
int mnv=1e16;
int lit=0;
for(int i=1;i<=n;i++){
    if(dpi[i]<=n&&pso[i-1]>=K){

     while(lit+1<=n&&pso[i-1]-pso[lit+1]>=K){
            lit++;
            mnv=min(mnv,dpj[lit]-lit);
     }
     ans=min(ans,dpi[i]+i-1+mnv-K);


    }

}
/*
for(int i=1;i<=n;i++){
    if(dpj[i]>n){dpj[i]=-1;}
    if(dpi[i]>n){dpi[i]=-1;}
    cout<<dpj[i]<<" ";
}cout<<endl;
for(int i=1;i<=n;i++){
    cout<<dpi[i]<<" ";
}*/
if(ans>n){
    cout<<-1<<endl;return 0;
}
cout<<ans<<endl;


}

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