Submission #201406

#	Time	Username	Problem	Language	Result	Execution time	Memory
201406		Noam527	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	15 ms	3076 KiB

ho_t2

#include <bits/stdc++.h>
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 4e18;
const int OO = 1;
const int OOO = 1;
using namespace std;

const string word = "JOI";

int n, k;
string s;
vector<int> nxt[3];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k >> s;
	for (int i = 0; i < 3; i++) {
		char need = word[i];
		nxt[i].resize(n, md);
		int p = 0, cnt = 0;
		while (p < n && cnt < k) {
			if (s[p] == need) cnt++;
			p++;
		}
		for (int j = 0; j < n; j++) {
			nxt[i][j] = p;
			if (s[j] == need) {
				if (p == n) break;
				while (p < n && s[p++] != need);
				if (p == n && s.back() != need) break;
			}
		}
	}
	int ans = md;
	for (int i = 0; i < n; i++) {
		int cur = i;
		for (int j = 0; j < 3 && cur <= n; j++)
			if (cur == n)
				cur = md;
			else
				cur = nxt[j][cur];
		if (cur <= n) ans = min(ans, cur - i - 3 * k);
	}
	cout << (ans == md ? -1 : ans) << '\n';
}

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