제출 #1146737

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146737		Newtonabc	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	25 ms	5336 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int cj[N],co[N],ci[N],pj[N],po[N],pi[N];
int main(){
    int n,k;
    cin>>n >>k;
    string s;
    cin>>s;
    for(int i=0;i<n;i++){
        if(s[i]=='J') cj[i+1]++;
        else if(s[i]=='O') co[i+1]++;
        else ci[i+1]++;
    }
    for(int i=1;i<=n;i++) cj[i]+=cj[i-1],co[i]+=co[i-1],ci[i]+=ci[i-1];
    for(int i=n+1;i<=n+2;i++) pj[i]=po[i]=pi[i]=n+1;
    for(int i=1;i<=n;i++){
        int tmpj,tmpo,tmpi;
        tmpj=tmpo=tmpi=k;
        if(s[i-1]=='J') tmpj--;
        if(s[i-1]=='O') tmpo--;
        if(s[i-1]=='I') tmpi--;
        pj[i]=lower_bound(cj+i,cj+n+1,cj[i]+tmpj)-cj;
        po[i]=lower_bound(co+i,co+n+1,co[i]+tmpo)-co;
        pi[i]=lower_bound(ci+i,ci+n+1,ci[i]+tmpi)-ci;
    }
    int ans=INT_MAX;
    for(int i=1;i<=n;i++){
        int now=i;
        now=pj[now];
        now=po[now+1];
        now=pi[now+1];
        if(now!=n+1) ans=min(ans,now-i+1-3*k);
    }
    if(ans==INT_MAX) cout<<-1;
    else cout<<ans;
}

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