Submission #202949

#	Time	Username	Problem	Language	Result	Execution time	Memory
202949		mraron	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	82 ms	2952 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
int cnt[3][200001];
int n,k;
int until(int from, int typ) {
	int res=-1;
	for(int i=18;i>=0;i--) {
		int akt=res+(1<<i);
		if(from+akt>=n) continue ;
		if(cnt[typ][from+akt]-(from?cnt[typ][from-1]:0)<k) res=akt;
	}
	if(from+res+1!=n) return from+res+1;
	return -1;
}
int main() {
	string t;
	cin>>n>>k;
	cin>>t;
	for(int i=0;i<n;++i) {
		if(t[i]=='J') cnt[0][i]++;
		else if(t[i]=='O') cnt[1][i]++;
		else cnt[2][i]++;
	}
	
	for(int j=0;j<3;++j) for(int i=1;i<n;++i) cnt[j][i]+=cnt[j][i-1];
	int ans=1e9;
	for(int i=0;i<n;++i) {
		int jig=until(i,0);
		
		if(jig!=-1) {
			int oig=until(jig,1);
			if(oig!=-1) {
				int iig=until(oig,2);
				if(iig!=-1) {
					ans=min(ans, iig-i+1-3*k);
				}
			}
		}
	}
	if(ans==1e9) cout<<-1;
	else cout<<ans;
	return 0;
}

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