Submission #509969

#TimeUsernameProblemLanguageResultExecution timeMemory
509969CSQ31JJOOII 2 (JOI20_ho_t2)C++17
100 / 100
13 ms2376 KiB
#include <bits/stdc++.h>
using namespace std;
int p[200001],q[200001];
int main()
{
	int n,k;
	string s;
	cin>>n>>k>>s;
	int cnt = 0;
	for(int l=0,r=0;r<n;r++){
		cnt+=s[r] == 'J';
		while(cnt >= k){
			if(cnt==k && s[l] == 'J')break;
			cnt-=s[l] == 'J';
			l++;
		}
		if(cnt == k)p[r] = r-l+1 - k;
		else p[r] = -1;
	}
	
	cnt = 0;
	for(int l=n-1,r=n-1;l>=0;l--){
		cnt+=s[l] == 'I';
		while(cnt >= k){
			if(cnt==k && s[r] == 'I')break;
			cnt-=s[r] == 'I';
			r--;
		}
		if(cnt == k)q[l] = r-l+1 - k;
		else q[l] = -1;
	}
	int ans = 1e9;
	cnt = 0;
	for(int l=0,r=0;r<n;r++){
		cnt+=s[r] == 'O';
		while(cnt >= k){
			if(cnt==k && s[l] == 'O')break;
			cnt-=s[l] == 'O';
			l++;
		}
		if(l && p[l-1] != -1 && r+1<n && q[r+1] != -1 && cnt == k){
			ans = min(ans,p[l-1] + q[r+1] + r-l+1-cnt);
		}
	}
	if(ans == 1e9)ans = -1;
	cout<<ans;

	
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...