제출 #1325620

#제출 시각아이디문제언어결과실행 시간메모리
1325620crispxxJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
12 ms9276 KiB
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int ind[256];

const int inf = 1e9 + 5;

bool chmin(int &a, const int &b) {
	return a > b ? a = b, true : false;
}

bool chmax(int &a, const int &b) {
	return a < b ? a = b, true : false;
}

void solve() {
	int n, k; cin >> n >> k;
	
	string s; cin >> s;
	
	ind['J'] = 0;
	ind['O'] = 1;
	ind['I'] = 2;
	
	vector<array<int, 3>> pref(n + 1);
	
	for(int i = 0; i < n; i++) {
		pref[i + 1] = pref[i];
		pref[i + 1][ind[s[i]]]++;
	}
	
	vector<array<int, 3>> ptr(n + 1);
	
	for(int i = 1; i <= n; i++) {
		ptr[i] = ptr[i - 1];
		for(int j = 0; j < 3; j++) {
			while(ptr[i][j] < n && pref[i][j] - pref[ ptr[i][j] ][j] >= k) {
				ptr[i][j]++;
			}
		}
	}
	
	vector<array<int, 5>> mxp(n + 1, {-inf, -inf, -inf, -inf, -inf});
	
	int ans = inf;
	
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 5; j++) {
			mxp[i][j] = mxp[i - 1][j];
		}
		
		if(s[i - 1] == 'J' && ptr[i][0] > 0) {
			chmax(mxp[i][0], ptr[i][0]);
		}
		
		if(s[i - 1] == 'O') {
			chmax(mxp[i][1], mxp[i][0]);
			if(ptr[i][1] > 0) chmax(mxp[i][2], mxp[ ptr[i][1] ][1]);
		}
		
		if(s[i - 1] == 'I') {
			chmax(mxp[i][3], mxp[i][2]);
			if(ptr[i][2] > 0) chmax(mxp[i][4], mxp[ ptr[i][2] ][3]);
			if(mxp[i][4] > 0) chmin(ans, i - mxp[i][4] + 1);
		}
		
	}
	
	if(ans == inf) {
		cout << -1 << '\n';
		return;
	}
	
	cout << ans - 3 * k << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...