Submission #1335797

#TimeUsernameProblemLanguageResultExecution timeMemory
1335797gelastropodJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
20 ms3016 KiB
#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N, K, ans = -1; cin >> N >> K;
	string s; cin >> s;
	vector<vector<int>> idxs(3);
	for (int i = 0; i < N; i++) {
		if (s[i] == 'J') idxs[0].push_back(i);
		else if (s[i] == 'O') idxs[1].push_back(i);
		else idxs[2].push_back(i);
	}
	if (min(idxs[0].size(), min(idxs[1].size(), idxs[2].size())) < K) {
		cout << "-1\n";
		return 0;
	}
	for (int i = 0; i <= N; i++) {
		auto iter0 = lower_bound(idxs[0].begin(), idxs[0].end(), i);
		if (idxs[0].end() - iter0 < K) break;
		int lb = *iter0;
		iter0 += K - 1;
		auto iter1 = lower_bound(idxs[1].begin(), idxs[1].end(), *iter0);
		if (idxs[1].end() - iter1 < K) break;
		iter1 += K - 1;
		auto iter2 = lower_bound(idxs[2].begin(), idxs[2].end(), *iter1);
		if (idxs[2].end() - iter2 < K) break;
		iter2 += K - 1;
		ans = max(ans, lb + N - 1 - *iter2);
	}
	if (ans == -1) cout << ans << '\n';
	else cout << N - 3 * K - ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...