Submission #202050

#	Time	Username	Problem	Language	Result	Execution time	Memory
202050		khohko	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	22 ms	3848 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ARRS ((ll)(4e5+100))
#define fr first
#define sc second
#define pb push_back
#define MX ((ll)(1e9+100))
#define MAX ((ll)(1e18+100))

ll n;
pair<ll,ll> a[ARRS];
ll b[ARRS];
ll ans[ARRS];
ll pl[ARRS];
ll pr[ARRS];
int main(){
	ll n,m;
	string s;
	cin>>n>>m;
	cin>>s;
	ll l=0,r=0,c=0;
	for(r=0; r<n&&c!=m; r++){
		c+=s[r]=='J';
		pl[r]=MAX;
	}
	if(c<m){
		cout<<-1;
		return 0;
	}
	while(s[l]!='J')l++;
	for(;r<n;r++){
		pl[r]=r-l-m;
		if(s[r]=='J'){
			l++;
			while(s[l]!='J')l++;
		}
	}
	reverse(s.begin(),s.end());
	l=0,r=0,c=0;
	for(r=0; r<n&&c!=m; r++){
		c+=s[r]=='I';
		pr[n-r-1]=MAX;
	}
	if(c<m){
		cout<<-1;
		return 0;
	}
	while(s[l]!='I')l++;
	for(;r<n;r++){
		pr[n-r-1]=r-l-m;
		if(s[r]=='I'){
			l++;
			while(s[l]!='I')l++;
		}
	}
	reverse(s.begin(),s.end());
	l=0,r=0,c=0;
	for(r=0; r<n&&c!=m; r++){
		c+=s[r]=='O';
	}
	if(c<m){
		cout<<-1;
		return 0;
	}
	while(s[l]!='O')l++;
	ll mn=MAX;
	for(;r<n;r++){
		mn=min(mn, pl[l]+pr[r-1]+r-l-m);
		if(s[r]=='O'){
			l++;
			while(s[l]!='O')l++;
		}
	}
 
	if(mn==MAX)
		cout<<-1<<endl;
	else
		cout<<mn<<endl;
}

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