Submission #1085574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085574		4QT0R	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	23 ms	3220 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;

char wej[200003];
vector<int> pref[3];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n,k;
	cin >> n >> k;
	pref[0].resize(n+1);
	pref[1].resize(n+1);
	pref[2].resize(n+1);
	for (int i = 1; i<=n; i++){
		cin >> wej[i];
		pref[0][i]=pref[0][i-1];
		pref[1][i]=pref[1][i-1];
		pref[2][i]=pref[2][i-1];
		if (wej[i]=='J')pref[0][i]++;
		else if (wej[i]=='O')pref[1][i]++;
		else pref[2][i]++;
	}
	int ans=n+1;
	for (int i = 1; i<=n+1-3*k; i++){
		int p0=i,p1=lower_bound(pref[0].begin()+p0,pref[0].end(),pref[0][i-1]+k)-pref[0].begin();
		if (p1>n)continue;
		int p2=lower_bound(pref[1].begin()+p1,pref[1].end(),pref[1][p1-1]+k)-pref[1].begin();
		if (p2>n)continue;
		int p3=lower_bound(pref[2].begin()+p2,pref[2].end(),pref[2][p2-1]+k)-pref[2].begin();
		if (p3>n)continue;
		ans=min(ans,p3-p0+1-3*k);
	}
	if (ans>n)cout << "-1\n";
	else cout << ans << '\n';
}

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