Submission #520918

#	Time	Username	Problem	Language	Result	Execution time	Memory
520918		AdamGS	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	9 ms	3160 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
int nxt[LIM][3];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, k;
	string s;
	cin >> n >> k >> s;
	int a=0, b=0, c=0;
	for(auto i : s) {
		if(a<k) {
			if(i=='J') ++a;
		} else if(b<k) {
			if(i=='O') ++b;
		} else {
			if(i=='I') ++c;
		}
	}
	if(c<k) {
		cout << -1 << '\n';
		return 0;
	}
	string x="JOI";
	rep(i, 3) {
		int l=-1, ile=0;
		rep(j, n) {
			while(l<n-1 && ile<k) {
				++l;
				if(s[l]==x[i]) ++ile;
			}
			if(ile==k) nxt[j][i]=l;
			else nxt[j][i]=-1;
			if(s[j]==x[i]) --ile;
		}
	}
	int ans=n;
	rep(i, n) {
		int a=nxt[i][0];
		if(a!=-1 && a<n-1) {
			a=nxt[a+1][1];
			if(a!=-1 && a<n-1) {
				a=nxt[a+1][2];
				if(a!=-1) {
					ans=min(ans, a-i+1-3*k);
				}
			}
		}
	}
	cout << ans << '\n';
}

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