제출 #237165

#제출 시각아이디문제언어결과실행 시간메모리
237165wwddJJOOII 2 (JOI20_ho_t2)C++14
100 / 100
33 ms3212 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INFL = 1e18;
const int MN = 200100;
int pr[3][MN];
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	ll n,k;
	cin >> n >> k;
	string s;
	cin >> s;
	pr[0][0] = pr[0][1] = pr[0][2] = 0;
	for(int i=0;i<n;i++) {
		for(int j=0;j<3;j++) {
			pr[j][i+1] = pr[j][i];
		}
		if(s[i] == 'J') {
			pr[0][i+1]++;
		} else if(s[i] == 'O') {
			pr[1][i+1]++;
		} else {
			pr[2][i+1]++;
		}
	}
	ll res = -1;
	for(int i=0;i<n;i++) {
		int u = i;
		for(int j=0;j<3;j++) {
			u = lower_bound(pr[j]+u,pr[j]+n+1,pr[j][u]+k)-pr[j];
		}
		if(u <= n) {
			res = max(res,i+n-u);
		}
	}
	if(res == -1) {
		cout << -1 << '\n';
	} else {
		ll ans = n-3*k-res;
		cout << ans << '\n';
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...