제출 #1325567

#제출 시각아이디문제언어결과실행 시간메모리
1325567JuanJLJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
24 ms4672 KiB
#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i=  a; i<b; i++)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
using namespace std;
typedef long long ll;

#ifdef D
	#define debug(x) cout << x
#else
	#define debug(x) //nothing
#endif

#define INF ((ll)1000000000)


int main(){
	ll n, k; cin>>n>>k;
	string s; cin>>s;
	
	vector<ll> rs(n);
	forn(i,0,n){
		if(s[i]=='J') rs[i]=0;
		else if(s[i]=='O') rs[i]=1;
		else rs[i]=2;
	}

	vector<vector<ll>> his(3);

	debug("precalculo listo\n");
	ll res=-1;
	for(int i = n-1; i>=0; i--){
		his[rs[i]].pb(i);
	}
	forn(i,0,3) sort(ALL(his[i]));

	forn(i,0,n){
		ll last = i;
		forn(j,0,3){
			ll ind = lower_bound(ALL(his[j]),last)-his[j].begin();
			ind+=k-1;
			debug("toca en "<<j<<" "<<last<<" "<<ind<<'\n');
			if(ind>=SZ(his[j])) last=INF;
			else last=his[j][ind];
		}
		debug("para "<<i<<" "<<last<<'\n');
		if(last!=INF){
			if(res==-1 || res>((last+1)-i)-3*k){
				res=((last+1)-i)-3*k;
			}
		}
	}
	cout<<res<<'\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...