제출 #207837

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
207837		pavement	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	34 ms	3064 KiB

ho_t2

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

int N, K, A = 1e9, C[5][200005];
char S[200005];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> K;
	for (int i = 1; i <= N; i++) cin >> S[i];
	for (int i = N; i >= 1; i--) {
		C[1][i] = C[1][i + 1];
		C[2][i] = C[2][i + 1];
		C[3][i] = C[3][i + 1];
		if (S[i] == 'J') C[1][i]++;
		else if (S[i] == 'O') C[2][i]++;
		else C[3][i]++;
	}
	for (int i = 1; i <= N; i++) {
		int lo = 1, hi = i - K + 1, ans = -1, cans;
		while (lo <= hi) {
			int mid = (lo + hi) >> 1;
			if (C[3][mid] - C[3][i + 1] >= K) ans = mid, lo = mid + 1;
			else hi = mid - 1;
		}
		if (ans == -1) continue;
		lo = 1, hi = ans - K + 1, cans = ans, ans = -1;
		while (lo <= hi) {
			int mid = (lo + hi) >> 1;
			if (C[2][mid] - C[2][cans + 1] >= K) ans = mid, lo = mid + 1;
			else hi = mid - 1;
		}
		if (ans == -1) continue;
		lo = 1, hi = ans - K + 1, cans = ans, ans = -1;
		while (lo <= hi) {
			int mid = (lo + hi) >> 1;
			if (C[1][mid] - C[1][cans + 1] >= K) ans = mid, lo = mid + 1;
			else hi = mid - 1;
		}
		if (ans == -1) continue;
		A = min(A, i - ans + 1);
	}
	cout << (A == 1e9 ? -1 : A - 3 * K) << '\n';
}

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