Submission #842282

#TimeUsernameProblemLanguageResultExecution timeMemory
842282dong_liuJJOOII 2 (JOI20_ho_t2)C++17
100 / 100
6 ms3304 KiB
#include "bits/stdc++.h"
using namespace std;

const int N=2e5;
const string JOI="JOI";

int n,k;
string s;
int jmp[3][N+1];

int solve(int i) {
	i=jmp[0][i];
	i=jmp[1][i];
	i=jmp[2][i];
	return i==n?-1:i;
}

int main() {
	cin.tie(0)->sync_with_stdio(0),cin.exceptions(cin.failbit);
	cin>>n>>k>>s;
	for(int x=0;x<3;x++){
		jmp[x][n]=n;
		for(int i=0,j=0,c=0;i<n;i++){
			while(j<n&&c<k)c+=s[j++]==JOI[x];
			jmp[x][i]=c==k?j-1:n;
			c-=s[i]==JOI[x];
		}
	}
	int ans=n;
	for(int i=0;i<n;i++){
		int j=solve(i);
		if(j!=-1)ans=min(ans,j-i+1-k*3);
	}
	cout<<(ans==n?-1:ans)<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...