제출 #821611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
821611		vjudge1	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	9 ms	11792 KiB

ho_t2

#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define int long long
//#define ld long double
using namespace std;
using ll=long long;
const int inf = 1e18;
const int MN =200005;
const int mod=1e9+7;
int n,k;
string s;
int posj[MN], poso[MN], posi[MN];
int lj[MN], li[MN], lo[MN],valj[MN], vali[MN], valo[MN];
void solve() {
	cin>>n>>k>>s;
	int cnti=0,cntj=0,cnto=0;
	for (int i=0; i<n; i++) {
		if(i>0) {
			valo[i]=valo[i-1];
			valj[i]=valj[i-1];
			vali[i]=vali[i-1];
		}
		
		if(s[i]=='O') cnto++,poso[cnto]=i, valo[i]=cnto;
		if(s[i]=='J') cntj++,posj[cntj]=i, valj[i]=cntj;
		if(s[i]=='I') cnti++,posi[cnti]=i, vali[i]=cnti;
	}
	for (int i=0; i<n; i++) {
		if(valj[i]<k) lj[i]=-1;
		else lj[i]=posj[valj[i]-k+1];
		if(valo[i]<k) lo[i]=-1;
		else lo[i]=poso[valo[i]-k+1];
		if(vali[i]<k) li[i]=-1;
		else li[i]=posi[vali[i]-k+1];
	}
//	for (int i=0; i<n; i++) {
//		cout<<lj[i]<<" "<<lo[i]<<" "<<li[i]<<"\n";
//	}
	int ans=inf;
	for (int r=n-1; r>=0; r--) {
		if(s[r]!='I') continue;
		int l;
		l=li[r];
		if(l==-1) continue;
		l=lo[l];
		if(l==-1) continue;
		l=lj[l];
		if(l==-1) continue;
//		cout<<l<<" "<<r<<"\n";
		ans=min(ans,r-l+1-3*k);
	}
	if(ans==inf) cout<<-1;
	else cout<<ans;
}
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
//	freopen(".inp", "r", stdin);
//	freopen(".out", "w", stdout);
	int t=1;
//	cin>>t;
	while(t--) {
		solve();
	}
		
}

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