제출 #1151667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151667		nguyn	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	5 ms	3600 KiB

ho_t2

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

#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

const int N = 2e5 + 5; 

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

deque<int> q[3];
string t; 

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n >> k;
	cin >> s;
	s = " " + s;
	t = "JOI";  
	int ans = n + 1; 
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++) {
			lef[i][j] = lef[i - 1][j]; 
			if (s[i] != t[j]) continue; 
			q[j].push_front(i); 
			while(q[j].size() > k) q[j].pop_back(); 
			if (q[j].size() == k) lef[i][j] = q[j].back();
			else {
				lef[i][j] = 0; 
			} 
//			for (auto it : q) cout << it << ' '; 
//			cout << s[i] << ' ' << t[j] << ' ' << lef[i][j] << '\n';
		}
		int l = i;
		bool ok = 1;  
		for (int j = 2; j >= 0; j--) {
			if (lef[l][j] > 0) {
				l = lef[l][j]; 
			}
			else {
				ok = 0;
				break; 
			}
		}
		if (ok) {
//			cout << l << ' ' << i << endl;
			ans = min(ans, i - l + 1); 
		}
	}
	if (ans == n + 1) {
		cout << -1;
	}
	else cout << ans - 3 * k; 
}

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