제출 #680579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
680579		ethening	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	20 ms	11860 KiB

ho_t2

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int c2i(char c) {
	if (c == 'J') return 0;
	else if (c == 'O') return 1;
	else return 2;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, k;
	string s;

	cin >> n >> k;
	vector p = vector(n + 5, vector<int>(3, 0));
	cin >> s;

	for (int i = 0; i < n; i++) {
		if (i > 0) {
			for (int k = 0; k < 3; k++) {
				p[i][k] = p[i - 1][k];
			}
		}
		++p[i][c2i(s[i])];
	}

	auto rge_sum = [&](int l, int r, char c) {
		int ret = p[r][c2i(c)];
		if (l > 0) {
			ret -= p[l - 1][c2i(c)];
		}
		return ret;
	};

	int ans = -1;
	int jen = 0;
	int oen = 0;
	int ien = 0;
	for (int i = 0; i < n; i++) {
		if (jen < i) jen = i;
		while (jen < n && rge_sum(i, jen, 'J') < k) {
			++jen;
		}
		if (jen == n && rge_sum(i, jen, 'J') < k) break;

		if (oen <= jen) oen = jen + 1;
		while (oen < n && rge_sum(jen + 1, oen, 'O') < k) {
			++oen;
		}
		if (oen == n && rge_sum(jen + 1, oen, 'O') < k) break;

		if (ien <= oen) ien = oen + 1;
		while (ien < n && rge_sum(oen + 1, ien, 'I') < k) {
			++ien;
		}
		if (ien == n && rge_sum(oen + 1, ien, 'I') < k) break;
		
		int cost = ien - i + 1 - 3 * k;
		if (ans == -1 || cost < ans) ans = cost;
	}
	cout << ans << endl;
}

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