제출 #1000015

#제출 시각아이디문제언어결과실행 시간메모리
1000015IWTIMJJOOII 2 (JOI20_ho_t2)C++17
100 / 100
20 ms8768 KiB
# include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double 
const int N = 1e6 + 5;
int t,n,k,prefo[N],prefj[N],prefi[N],st,l,r,idx,mid,ans;
string s;
signed main() {
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	cin>>s;
	s="@"+s;
	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');
	}
	ans=1e9;
	for (int i=1;i<=n;i++) {
		st=i;
		l=i; r=n;
		idx=-1;
		while(l<=r){
			mid=(l+r)/2;
			if(prefj[mid]-prefj[st-1]>=k){
				idx=mid;
				r=mid-1;
			}
			else{
				l=mid+1;
			}
		}
		if (idx==-1) break;
		st=idx+1;
		l=st; r=n;
		idx=-1;
		while(l<=r){
			mid=(l+r)/2;
			if(prefo[mid]-prefo[st-1]>=k){
				idx=mid;
				r=mid-1;
			}
			else{
				l=mid+1;
			}
		}
		if(idx==-1) break;
		st=idx+1;
		l=st; r=n;
		idx=-1;
		while(l<=r){
			mid=(l+r)/2;
			if(prefi[mid]-prefi[st-1]>=k){
				idx=mid;
				r=mid-1;
			}
			else{
				l=mid+1;
			}
		}
		if(idx==-1) break;
		ans=min(ans, idx-i+1-3*k);
	}
	if (ans==1e9) cout<<-1;
	else cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...