Submission #276090

#	Time	Username	Problem	Language	Result	Execution time	Memory
276090		islingr	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	31 ms	3212 KiB

ho_t2

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

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define per(i, a, b) for (auto i = (b); i-- > (a); )
#define lb(x...) lower_bound(x)
#define ub(x...) upper_bound(x)

const int N = 1 << 18, inf = 1e9;
char s[N];
int ci[N], co[N], cj[N];

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);

	int n, k, res = inf; cin >> n >> k >> s;
	rep(i, 0, n) {
		cj[i + 1] = cj[i];
		co[i + 1] = co[i];
		ci[i + 1] = ci[i];
		if (s[i] == 'J') ++cj[i + 1];
		if (s[i] == 'O') ++co[i + 1];
		if (s[i] == 'I') ++ci[i + 1];
	}
	rep(l, 0, n) {
		int j = lb(cj + l, cj + n + 1, cj[l] + k) - cj;
		int o = lb(co + j, co + n + 1, co[j] + k) - co;
		int i = lb(ci + o, ci + n + 1, ci[o] + k) - ci;
		if (i == n + 1) break;
		res = min(res, i - l - 3 * k);
	}
	cout << (res < inf ? res : -1);
}

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