Submission #534424

#	Time	Username	Problem	Language	Result	Execution time	Memory
534424		alvingogo	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	8 ms	2404 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+1),po(n+1);
	int l=-1,r=-1,cnt=0;
	while(r<n){
		r++;
		cnt+=(s[r]=='J');
		if(cnt>=k){
			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){
			while(l<r){
				l++;
				if(s[l]=='O'){
					break;
				}
			}
			cnt--;
		}
		po[r]=l;
	}
	int il=n,ir=n;
	cnt=0;
	while(il>=0){
		il--;
		cnt+=(s[il]=='I');
		int flag=0;
		if(cnt==k){
			flag=1;
			while(ir>il){
				ir--;
				if(s[ir]=='I'){
					break;
				}
			}
			cnt--;
		}
		if(flag){
			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: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87