Submission #876645

#	Time	Username	Problem	Language	Result	Execution time	Memory
876645		serifefedartar	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	6 ms	3620 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 21;
const ll MAXN = 2e5 + 100;

string s;
int toJ[MAXN], toO[MAXN], toI[MAXN];
int main() {
	fast
	int N, K;
	cin >> N >> K >> s;
	s = "#" + s;

	int r = 1;
	int cnt = (s[1] == 'J');
	for (int l = 1; l <= N; l++) {
		while (cnt < K && r < N) {
			r++;
			if (s[r] == 'J')
				cnt++;
		}

		if (cnt == K)
			toJ[l] = r + 1;
		else
			toJ[l] = -1;
		if (s[l] == 'J')
			cnt--;
	}
	r = 1;
	cnt = (s[1] == 'O');
	for (int l = 1; l <= N; l++) {
		while (cnt < K && r < N) {
			r++;
			if (s[r] == 'O')
				cnt++;
		}

		if (cnt == K)
			toO[l] = r + 1;
		else
			toO[l] = -1;
		if (s[l] == 'O')
			cnt--;
	}
	r = 1;
	cnt = (s[1] == 'I');
	for (int l = 1; l <= N; l++) {
		while (cnt < K && r < N) {
			r++;
			if (s[r] == 'I')
				cnt++;
		}

		if (cnt == K)
			toI[l] = r + 1;
		else
			toI[l] = -1;
		if (s[l] == 'I')
			cnt--;
	}

	int ans = 1e9;
	for (int i = 1; i <= N; i++) {
		int now = toJ[i];
		if (now == -1 || now > N)
			continue;
		now = toO[now];
		if (now == -1 || now > N)
			continue;
		now = toI[now];
		if (now == -1)
			continue;
		ans = min(ans, now - i);
	}

	if (ans == 1e9)
		cout << "-1\n";
	else
		cout << ans - 3*K << "\n";
}

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