제출 #1281784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281784		shirokito	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	30 ms	3228 KiB

ho_t2

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

using ll = long long;

const int N = 2e5 + 24;

int n, k; string s; 
int pf[N][3];

void solve() {
	cin >> n >> k;
	cin >> s; s = "." + s;

	for (int i = 1; i <= n; i++) {
		pf[i][0] = pf[i - 1][0] + (s[i] == 'J');
		pf[i][1] = pf[i - 1][1] + (s[i] == 'O');
		pf[i][2] = pf[i - 1][2] + (s[i] == 'I');
	}

	int res = -1;

	for (int i = 1; i <= n; i++) {
		int pos = i; bool flag = 0;

		for (int j = 0; j < 3; j++) {
			int next_pos = -1;
			for (int l = pos, r = n; l <= r; ) {
				int mid = (l + r) / 2;
				if (pf[mid][j] - pf[pos - 1][j] >= k) {
					next_pos = mid;
					r = mid - 1;
				}
				else l = mid + 1;
			}

			if (next_pos == -1) {
				flag = 1; break;
			}

			pos = next_pos;
		}

		if (!flag && (res == -1 || res > (pos - i + 1) - 3 * k)) {
			res = (pos - i + 1) - 3 * k;
		} 
	}

	cout << res << '\n';
}

int main() {
	cin.tie(0) -> sync_with_stdio(0);

	int T = 1; // cin >> T;
	while (T--) {
		solve();
	}
}

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