Submission #534417

#	Time	Username	Problem	Language	Result	Execution time	Memory
534417		alvingogo	JJOOII 2 (JOI20_ho_t2)	C++14	0 / 100	1 ms	460 KiB

ho_t2

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
//#define int long long
using namespace std;

int main(){
	AquA;
	int n,k;
	cin >> n >> k;
	string s;
	cin >> s;
	int ans=n-3*k;
	int maxx=-9487888;
	vector<int> pj(n),po(n);
	int l=-1,r=-1,cnt=0;
	while(r<n){
		r++;
		cnt+=(s[r]=='J');
		if(cnt>=k){
			/*
			if(l>=0){
				cnt--;
			}
			*/
			while(l<r){
				l++;
				if(s[l]=='J'){
					break;
				}
			}
			cnt--;
		}
		pj[r]=l;
	}
	l=-1;
	r=-1;
	cnt=0;
	while(r<n){
		r++;
		cnt+=(s[r]=='O');
		if(cnt>=k){
			/*
			if(l>=0){
				cnt--;
			}
			*/
			while(l<r){
				l++;
				if(s[l]=='O'){
					break;
				}
			}
			cnt--;
		}
		po[r]=l;
	}
	/*
	for(int i=0;i<n;i++){
		cout << pj[i] << " ";
	}
	cout << "\n";
	for(int i=0;i<n;i++){
		cout << po[i] << " ";
	}
	cout << "\n";
	*/
	int il=n,ir=n;
	cnt=0;
	//cout << "fwoqfoew" << endl;
	while(il>=0){
		il--;
		cnt+=(s[il]=='I');
		if(cnt>=k){
			while(ir>il){
				ir--;
				if(s[ir]=='I'){
					break;
				}
			}
			cnt--;
		}
		if(cnt==k-1){
			//cout << "fjqwjfwe" << endl;
			int h=n-1-ir;
			if(po[il]<0){
				break;
			}
			if(pj[po[il]]<0){
				break;
			}
			h+=pj[po[il]];
			maxx=max(maxx,h);
		}
	}
	if(maxx<0){
		cout << -1 << "\n";
	}
	else{
		cout << ans-maxx << "\n";
	}
	return 0;
}

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