Submission #834223

#	Time	Username	Problem	Language	Result	Execution time	Memory
834223		vjudge1	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	27 ms	3276 KiB

ho_t2

#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;
}

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