제출 #1144934

#제출 시각아이디문제언어결과실행 시간메모리
1144934ezzzayJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
32 ms2916 KiB
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
int ps[N][3];
int cnt[3];
char s[N];
int n,k;
int fun(int x, int l){
	if(l>=n+1)return l;
	int lo=l,hi=n;
	while(hi>=lo){
		int mid=(hi+lo)/2;
		if(ps[mid][x]-ps[l-1][x] >=k)hi=mid-1;
		else lo=mid+1;
	}
	return lo;
}
signed main(){
    cin>>n>>k;
    map<char,int> mp;
    mp['J']=0;
    mp['O']=1;
    mp['I']=2;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=0;j<3;j++)ps[i][j]=ps[i-1][j];
        ps[i][mp[s[i]]]++;
    }
    int ans=1e9;
    for(int i=1;i<=n;i++){
    	int l=fun(0,i)+1;
    	l=fun(1,l)+1;
    	l=fun(2,l);
    	if(l<=n){
    		ans=min(ans,(l-i+1-3*k));
		}
	}
	if(ans==1e9)ans=-1;
	cout<<ans;
    
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...