Submission #1346800

#TimeUsernameProblemLanguageResultExecution timeMemory
1346800jellybeanJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
7 ms5052 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define dd(x) cout<<#x<<" is "<<x<<endl;
#define dd2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
typedef pair<int,int> pii;

struct dat{
	int l,r;
} os[200005];

signed main(){
	
	int n,k; cin>>n>>k;
	string s; cin>>s;
	deque<int> js, is, oids;
	
	for(int i=0; i<n; i++){
		if(s[i] == 'J'){
			js.pb(i);
			if(js.size() > k) js.pop_front();
		}
		if(s[i] == 'O'){
			os[i].l = (js.size() == k)? js.front() : -1;
			oids.pb(i);
		}
	}
	
	for(int i=n-1; i>=0; i--){
		if(s[i] == 'I'){
			is.push_front(i);
			if(is.size() > k) is.pop_back();
		}
		if(s[i] == 'O'){
			os[i].r = (is.size() == k)? is.back() : -1;
		}
	}
	
	int ans = LLONG_MAX, num = oids.size();
	for(int x=0; x<=num-k; x++){
		int i=oids[x], j=oids[x+k-1];
		if(os[i].l == -1 or os[j].r == -1) continue;
		ans = min(ans,os[j].r - os[i].l + 1 - 3*k);
	}
	
	cout<< ((ans==LLONG_MAX)? -1 : ans);
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...