제출 #1144932

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144932		ezzzay	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	31 ms	2888 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
int sf[N][3];
int ps[N][3];
int cnt[3];
int dp[N];
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;
		//cout<<mid<<" "<<ps[mid][x]-ps[l-1][x]<<endl;
		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);
    	l++;
    	l=fun(1,l);
    	l++;
    	l=fun(2,l);
    	if(l<=n){
    		ans=min(ans,(l-i+1-3*k));
		}
	}
	if(ans==1e9)ans=-1;
	cout<<ans;
    
}

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