Submission #1279825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279825		cmiuc	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	9 ms	2288 KiB

ho_t2

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 2e5 + 10;
int J[N], I[N], a[N], inf = 1e9;

int main(){
	int n, k, Ans = N;
	cin>>n>>k;

	string s;
	cin>>s;
	s = '0' + s;

	J[0] = inf;
	for (int i=1, cnt = 0, l = 0;i<=n;i++){
		cnt += (s[i] == 'J');
		while (cnt - (s[l + 1] == 'J') >= k)
			l++, cnt -= (s[l] == 'J');
		J[i] = (cnt == k ? (i - l - k) : inf);
		J[i] = min(J[i], J[i-1] + 1);
	}

	I[n+1] = inf;
	for (int i=n, cnt = 0, r = n + 1;i>=1;i--){
		cnt += (s[i] == 'I');
		while (cnt - (s[r - 1] == 'I') >= k)
			r--, cnt -= (s[r] == 'I');
		I[i] = (cnt == k ? (r - i - k) : inf);
		I[i] = min(I[i], I[i+1] + 1);
	}

	for (int i=n, cnt = 0, r = n + 1;i>=1;i--){
		cnt += (s[i] == 'O');
		while (cnt - (s[r - 1] == 'O') >= k)
			r--, cnt -= (s[r] == 'O');
		if (cnt == k)
			Ans = min(Ans, r - i + J[i-1] + I[r] - k);
	}
	if (Ans == N)
		Ans = -1;
	cout<<Ans<<'\n';
}

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