Submission #842282

#	Time	Username	Problem	Language	Result	Execution time	Memory
842282		dong_liu	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	6 ms	3304 KiB

ho_t2

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

const int N=2e5;
const string JOI="JOI";

int n,k;
string s;
int jmp[3][N+1];

int solve(int i) {
	i=jmp[0][i];
	i=jmp[1][i];
	i=jmp[2][i];
	return i==n?-1:i;
}

int main() {
	cin.tie(0)->sync_with_stdio(0),cin.exceptions(cin.failbit);
	cin>>n>>k>>s;
	for(int x=0;x<3;x++){
		jmp[x][n]=n;
		for(int i=0,j=0,c=0;i<n;i++){
			while(j<n&&c<k)c+=s[j++]==JOI[x];
			jmp[x][i]=c==k?j-1:n;
			c-=s[i]==JOI[x];
		}
	}
	int ans=n;
	for(int i=0;i<n;i++){
		int j=solve(i);
		if(j!=-1)ans=min(ans,j-i+1-k*3);
	}
	cout<<(ans==n?-1:ans)<<'\n';
}

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