Submission #716200

#	Time	Username	Problem	Language	Result	Execution time	Memory
716200		gghx	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	14 ms	5404 KiB

ho_t2

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

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll n,k;
	cin>>n>>k;
	char arr[n];
	for(int i=0;i<n;i++) cin>>arr[i];
	ll j[n], o[n], ik[n];
	fill(j,j+n,0);
	fill(o,o+n,0);
	fill(ik,ik+n,0);
	ll pointerj=-1;
	ll countj=0;
	while(countj<k && pointerj<n){
		pointerj++;
		if(pointerj==n){
			cout<<-1;
			return 0;
		}
		if(arr[pointerj]=='J') countj++;
	}
	j[0]=pointerj;
	for(int i=1;i<n;i++){
		if(arr[i-1]!='J') j[i]=j[i-1]; 
		else{
			while(pointerj<n){
				pointerj++;
				if(pointerj==n) j[i]=-1;
				if(arr[pointerj]=='J') break;
			}
			if(pointerj!=n) j[i]=pointerj;
			else j[i]=-1;
		}
	}
	ll pointero=-1;
	ll counto=0;
	while(counto<k && pointero<n){
		pointero++;
		if(pointero==n){
			cout<<-1;
			return 0;
		}
		if(arr[pointero]=='O') counto++;
	}
	o[0]=pointero;
	for(int i=1;i<n;i++){
		if(arr[i-1]!='O') o[i]=o[i-1]; 
		else{
			while(pointero<n){
				pointero++;
				if(pointero==n) o[i]=-1;
				if(arr[pointero]=='O') break;
			}
			if(pointero!=n) o[i]=pointero;
			else o[i]=-1;
		}
	}
	ll pointeri=-1;
	ll counti=0;
	while(counti<k && pointeri<n){
		pointeri++;
		if(pointeri==n){
			cout<<-1;
			return 0;
		}
		if(arr[pointeri]=='I') counti++;
	}
	ik[0]=pointeri;
	for(int i=1;i<n;i++){
		if(arr[i-1]!='I') ik[i]=ik[i-1]; 
		else{
			while(pointeri<n){
				pointeri++;
				if(pointeri==n) ik[i]=-1;
				if(arr[pointeri]=='I') break;
			}
			if(pointeri!=n) ik[i]=pointeri;
			else ik[i]=-1;
		}
	}
	ll ans=1e18;
	if(j[0]==-1){
		cout<<-1;
		return 0;
	}
	if(o[j[0]]==-1){
		cout<<-1;
		return 0;
	}
	if(ik[o[j[0]]]==-1){
		cout<<-1;
		return 0;
	}
	for(int i=0;i<n;i++){
		if(arr[i]!='J') continue;
		ll t=j[i];
		if(t==-1) continue;
		ll r=o[t];
		if(r==-1) continue;
		ll x=ik[r];
		if(x==-1) continue;
		ans=min(ans,x-i+1-3*k);
	}
	cout<<ans;
}

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