Submission #887985

#TimeUsernameProblemLanguageResultExecution timeMemory
887985amirhoseinfar1385JJOOII 2 (JOI20_ho_t2)C++17
100 / 100
7 ms3304 KiB
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
int n,k;
string s;
int dpj[maxn],dpo[maxn],dpi[maxn];

int cal(int ind){
	if(dpj[ind]==-1||dpo[dpj[ind]]==-1){
		return -1;
	}
	return dpi[dpo[dpj[ind]]];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	cin>>s;
	deque<int>v;
	for(int i=n-1;i>=0;i--){
		if(s[i]=='J'){
			v.push_front(i);
		}
		if((int)v.size()>k){
			v.pop_back();
		}
		if((int)v.size()==k){
			dpj[i]=v.back();
		}
		else{
			dpj[i]=-1;
		}
	}
	v.clear();
	for(int i=n-1;i>=0;i--){
		if(s[i]=='O'){
			v.push_front(i);
		}
		if((int)v.size()>k){
			v.pop_back();
		}
		if((int)v.size()==k){
			dpo[i]=v.back();
		}
		else{
			dpo[i]=-1;
		}
	}
	v.clear();
	for(int i=n-1;i>=0;i--){
		if(s[i]=='I'){
			v.push_front(i);
		}
		if((int)v.size()>k){
			v.pop_back();
		}
		if((int)v.size()==k){
			dpi[i]=v.back();
		}
		else{
			dpi[i]=-1;
		}
	}
	int f=0,res=n+2;
	for(int i=0;i<n;i++){
		int z=cal(i);
		if(z!=-1){
		//	cout<<i<<" "<<z<<"\n";
			f=1;
			res=min(res,z-i+1);
		}
	}
	if(f==0){
		cout<<-1<<"\n";
	}
	else{
		res-=3*k;
		cout<<res<<"\n";
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...