Submission #1335805

#TimeUsernameProblemLanguageResultExecution timeMemory
1335805sporknivesJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
26 ms4008 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
	int n,k; cin>>n>>k;
	string s; cin>>s;
	
	vector<int> jpos, opos, ipos;
	for(int i=0;i<n;i++) {
		if(s[i]=='J')jpos.push_back(i);
		if(s[i]=='O')opos.push_back(i);
		if(s[i]=='I')ipos.push_back(i);
	}
	
	int next_k[n]; memset(next_k, -1, sizeof(next_k));
	for(int i=0;i<n;i++) {
		if(s[i]=='J') {
			int idx = lower_bound(jpos.begin(), jpos.end(), i)-jpos.begin();
			if(idx+k-1<jpos.size()) next_k[i] = jpos[idx+k-1];
		}
		if(s[i]=='O') {
			int idx = lower_bound(opos.begin(), opos.end(), i)-opos.begin();
			if(idx+k-1<opos.size()) next_k[i] = opos[idx+k-1];
		}
		if(s[i]=='I') {
			int idx = lower_bound(ipos.begin(), ipos.end(), i)-ipos.begin();
			if(idx+k-1<ipos.size()) next_k[i] = ipos[idx+k-1];
		}
	}
	int ans=LLONG_MAX;
	for(int i=0;i<jpos.size();i++) {
		int jstart = jpos[i];
		if(next_k[jstart]==-1)break;
		int jend = next_k[jstart];
		if(lower_bound(opos.begin(),opos.end(),jend)==opos.end()) break;
		int ostart = *lower_bound(opos.begin(),opos.end(),jend);
		if(next_k[ostart]==-1)break;
		int oend = next_k[ostart];
		if(lower_bound(ipos.begin(),ipos.end(),oend)==ipos.end()) break;
		int istart = *lower_bound(ipos.begin(),ipos.end(),oend);
		if(next_k[istart]==-1)break;
		int iend = next_k[istart];
		
		ans = min(ans, iend-jstart+1-3*k);
	}
	if(ans==LLONG_MAX) cout<<-1;
	else cout<<ans;
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...