Submission #1326503

#TimeUsernameProblemLanguageResultExecution timeMemory
1326503joacruJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
6 ms1224 KiB
#include <bits/stdc++.h>

#define forn(i,n) for(int i=0;i<int(n);++i)
#define fort(i,n) for(int i=0;i<=int(n);++i)
#define fori(i,a,n) for(int i=a;i<int(n);++i)
#define forit(i,a,n) for(int i=a;i<=int(n);++i)
#define ALL(v) v.begin(),v.end()
#define SZ(v) (int)v.size()

#define DBG(a) cerr<<#a<<" = "<<(a)<<endl
#define DBGA(a) cerr<<#a<<" = "<<(a)<<", ";
#define DBG2(a,b) do{DBGA(a)DBG(b);}while(0)
#define DBG3(a,b,c) do{DBGA(a)DBGA(b)DBG(c);}while(0)
#define DBG4(a,b,c,d) do{DBGA(a)DBGA(b)DBGA(c)DBG(d);}while(0)

#define LINE cerr<<"===================================="<<endl

using namespace std;

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
	os<<"[";
	forn(i,v.size()){
		if(i) os<<" ";
		os<<v[i];
	}
	os<<"]";
	return os;
}

typedef long long ll;
typedef long double ld;

void solve(){
	
	int n, k;
	string s;
	cin>>n>>k>>s;
	
	deque<int> J, O, I;
	forn(i,n){
		if(s[i] == 'J') J.push_back(i);
		else if(s[i] == 'O') O.push_back(i);
		else I.push_back(i);
	}
	
	int ans = 2*n;
	forn(i,n){
		if(J.front() < i) J.pop_front();
		if(O.front() < i) O.pop_front();
		if(I.front() < i) I.pop_front();
		if(SZ(J) < k) break;
		while(SZ(O) && O.front() <  J[k-1]) O.pop_front();
		if(SZ(O) < k) break;
		while(SZ(I) && I.front() < O[k-1]) I.pop_front();
		if(SZ(I) < k) break;
		int cost = I[k-1] - i + 1 - 3*k;
		ans = min(ans, cost);
	}
	
	if(ans == 2*n) ans = -1;
	cout<<ans<<"\n";
}

int main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	#ifdef LOCAL
		assert(freopen("input.in", "r", stdin));
		//~ freopen("output.out", "w", stdout);
	#endif
	
	#ifdef LOCAL
	int tcs; cin>>tcs;
	while(tcs--)
	#endif
	solve();

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...