Submission #207037

#	Time	Username	Problem	Language	Result	Execution time	Memory
207037		YJU	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	16 ms	10244 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=1e6+4;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()

string s;
ll k,u[N],nxk[N],n,ans=(1LL<<60),nxt[3][N],r;
queue<ll> q[3];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>k>>s;
	REP(i,SZ(s))u[i]=(s[i]=='J'?0:(s[i]=='O'?1:2));
	REP(i,n+2)nxk[i]=n+1,nxt[0][i]=nxt[1][i]=nxt[2][i]=n+1;
	REP(i,SZ(s)){
		q[u[i]].push(i);
		if(SZ(q[u[i]])>=k){
			nxk[q[u[i]].front()]=i+1;
			q[u[i]].pop();
		}
	}
	for(ll i=n-1;i>=0;i--){
		REP(j,3)nxt[j][i]=nxt[j][i+1];
		nxt[u[i]][i]=i;
	}
	REP(i,n){
		if(u[i]==0){
			r=nxk[i];
			r=nxt[1][r];
			r=nxk[r];
			r=nxt[2][r];
			r=nxk[r];
			if(r==n+1)continue;
			ans=min(ans,(r-i-3*k));
		}
	}
	cout<<(ans==(1LL<<60)?-1:ans)<<"\n";
	return 0;
}

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