Submission #842280

#	Time	Username	Problem	Language	Result	Execution time	Memory
842280		dong_liu	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	0 ms	348 KiB

ho_t2

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

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

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

int test(int i) {
	for(int x=0;x<3;x++)for(int j=0;j<k;j++){
		i=nxt[i][x];
		if(i==n)return -1;
		i++;
	}
	return i;
}

int main() {
	cin.tie(0)->sync_with_stdio(0),cin.exceptions(cin.failbit);
	cin>>n>>k>>s;
	nxt[n][0]=nxt[n][1]=nxt[n][2]=n;
	for(int i=n-1;i>=0;i--)for(int j=0;j<3;j++)nxt[i][j]=s[i]==JOI[j]?i:nxt[i+1][j];
	if(test(0)==-1){
		cout<<-1<<'\n';
		return 0;
	}
	int low=0,hi=n-1;
	while(low<hi){
		int mid=(low+hi)/2+1;
		if(test(mid)!=-1)low=mid;
		else hi=mid-1;
	}
	cout<<(test(low)-low-k*3)<<'\n';
}

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