Submission #1224788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224788		LM1	JJOOII 2 (JOI20_ho_t2)	C++20	0 / 100	0 ms	324 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>
#define fr(i,ii,iii) for(int i=ii;i<iii;i++)
const int N=2e5+5;
int n,k,c[N],pr[N],sf[N];
int cc[N],cpr[N],csf[N];
string a;
int ans=N;
int main(){
	ios_base::sync_with_stdio(NULL);cin.tie(NULL);
	cin>>n>>k>>a;
	a="@"+a;
	fr(i,1,n+1){
		cc[i]=cpr[i]=csf[i]=-1;
	}
	fr(i,1,n+1){
		c[i]=c[i-1]+(a[i]=='O');
		if(cc[c[i]]==-1)cc[c[i]]=i;
	}
	fr(i,1,n+1){
		pr[i]=pr[i-1]+(a[i]=='J');
		if(cpr[pr[i]]==-1)cpr[pr[i]]=i;
	}
	for(int i=n;i>=1;i--){
		sf[i]=sf[i+1]+(a[i]=='I');
		if(csf[sf[i]]==-1)csf[sf[i]]=i;
	}
	//fr(i,1,n+1)cout<<c[i]<<" ";cout<<"\n";
	//fr(i,1,n+1)cout<<pr[i]<<" ";cout<<"\n";
	//fr(i,1,n+1)cout<<sf[i]<<" ";cout<<"\n";
	//fr(i,5,6){
	fr(i,1,n+1){
		//cout<<"\n";
		//cout<<i<<" -i\n";
		if(a[i]!='O')continue;
		int o=c[i];
		if(o+k-1<0)continue;
		int o1=cc[o+k-1];
		//cout<<o1<<" -o1\n";
		if(o1==-1)continue;
		int j=pr[i-1];
		int j1=cpr[j-k+1];
		if(j-k<0)continue;
		//cout<<j1<<" -j1\n";
		if(j1==-1)continue;
		int l=sf[o1+1];
		int l1=csf[l-k+1];
		//cout<<l1<<" -l1\n";
		if(l1==-1)continue;
		int ins=(o1-i+1)-k;
		int left=i-j1-k;
		int right=l1-o1-k;
		//cout<<left<<" "<<ins<<" "<<right<<"\n";
		ans=min(ans,ins+left+right);
	}
	if(ans==N)cout<<-1;
	else cout<<ans;
}

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