Submission #834223

#TimeUsernameProblemLanguageResultExecution timeMemory
834223vjudge1JJOOII 2 (JOI20_ho_t2)C++17
100 / 100
27 ms3276 KiB
#include <bits/stdc++.h>
using namespace std;

int N, K, ans=1e9;
string S, T="JOI";
int psum[3][200100];

int binser(int start, int id) {
	int L=start, R=N;
	int res = 0;
	while(L<=R) {
		int mid = (L+R)/2;
		if (psum[id][mid]-psum[id][start-1] >= K) {
			res = mid;
			R = mid-1;
		} else {
			L = mid+1;
		}
	}
	return res;
}

int main () {
	cin >> N >> K;
	cin >> S;
	S = "."+S;
	for(int i=1; i<=N; i++) {
		for(int j=0; j<=2; j++) {
			psum[j][i] = psum[j][i-1] + (S[i]==T[j]);
		}
	}
	for(int i=1; i<=N; i++) {
		int x = i-1;
		bool valid = true;
		for(int j=0; j<=2; j++) {
			x = binser(x+1,j);
			if (x==0) {
				valid = false;
				break;
			}
		}
		if (!valid) continue;
		ans = min(ans, x-i+1-3*K);
	}
	if (ans==1e9) ans = -1;
	cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...