Submission #509969

#	Time	Username	Problem	Language	Result	Execution time	Memory
509969		CSQ31	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	13 ms	2376 KiB

ho_t2

#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;

	
}

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