Submission #506162

#	Time	Username	Problem	Language	Result	Execution time	Memory
506162		thomas_li	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	43 ms	3192 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
const int MM = 2e5+5;
int n,k,psa[3][MM]; string s;
int f(char c){
	return (c == 'J' ? 0 : c == 'O' ? 1 : 2);
}
int next_k(int i, int j){
	if(i > n) return -1;
	int lo = i, hi = n;	
	while(lo < hi){
		int mid = (lo+hi)/2;
		if(psa[j][mid] - psa[j][i-1] >= k) hi = mid;
		else lo = mid+1;
	}
	if(psa[j][lo] - psa[j][i-1] < k) return -1;
	return lo;
}
int main(){
	cin >> n >> k >> s;
	s = ' ' + s;
	for(int i = 1; i <= n; i++){
		psa[0][i] += psa[0][i-1];
		psa[1][i] += psa[1][i-1];
		psa[2][i] += psa[2][i-1];
		psa[f(s[i])][i] += 1;
	}
	int ans = 1e9;
	for(int i = 1; i <= n; i++){
		int v = next_k(i,0),len = 0,p = i;
		if(v == -1) continue;	
		len += v - p+1;

		p = v+1;
		v = next_k(p,1);
		if(v == -1) continue;
		len += v - p+1;

		p = v+1;
		v = next_k(p,2);
		if(v == -1) continue;		
		len += v - p + 1;
		ans = min(ans,len - 3*k);
	}
	cout << (ans==1e9?-1:ans) << "\n";
}

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