Submission #1335986

#TimeUsernameProblemLanguageResultExecution timeMemory
1335986YSH2020JJOOII 2 (JOI20_ho_t2)C++20
100 / 100
10 ms2000 KiB
#include <bits/stdc++.h>
using namespace std;

int solve(int n, int t, string s) {
	//you want to trim the string so that it is as short as possible
	//we first find the positions of the joi
	vector<int> a;
	vector<int> b;
	vector<int> c ;
	for (int i = 0; i < n; i++) {
		if (s[i]=='J') a.push_back(i);
		else if (s[i]=='O') b.push_back(i);
		else c.push_back(i);
	}
	int ans = 2e9;
	if (b.size() < t || a.size() < t || c.size() < t) {return -1; return 0;}
	for (int i = 0; i <= (int)(b.size())-t; i++) {
		//you want to find the number of As before
		auto itr = lower_bound(a.begin(), a.end(), b[i])-a.begin();
		if (itr < t) continue;
		auto itr2 = lower_bound(c.begin(), c.end(), b[i+t-1])-c.begin();
		if (itr2+t-1 >= c.size()) continue;
		ans=min(ans,c[itr2+t-1]-a[itr-t]+1);
	}
	if (ans==2e9) return -1;
	else return ans-t*3;
}

int main() {
	int n; cin >> n;
	int t; cin >> t;
	string s; cin >> s;
	cout << solve(n,t,s);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...