Submission #1270393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270393		WH8	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	17 ms	5340 KiB

ho_t2

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

#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second

signed main(){
	string s; int n,k;cin>>n>>k>>s;
	vector<int> sj(n,0),so(n, 0), si(n, 0);
	for(int i=0;i<n;i++){
		char c=s[i];
		if(c=='J'){
			sj[i]++;
		}
		if(c=='O'){
			so[i]++;
		}
		else if(c=='I')si[i]++;
		if(i>=1)sj[i]+=sj[i-1], si[i]+=si[i-1], so[i]+=so[i-1];
	}
	int ans=1e9;
	for(int i=0;i<n;i++){
		if(s[i]=='J' and sj[i]>=k){
			int f=lower_bound(sj.begin(),sj.end(), sj[i]-k+1)-sj.begin();
			int a=lower_bound(so.begin(),so.end(), so[i]+k)-so.begin();
			if(a>=n)break;
			int b=lower_bound(si.begin(),si.end(),si[a]+k)-si.begin();
			if(b>=n)break;
			//~ printf("%lld %lld %lld\n", f,a,b);
			ans=min(ans, b-f+1-3*k);
		}
	}
	if(ans >=1e9)cout<<-1;
	else cout<<ans;
	
	
}

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