Submission #237165

#	Time	Username	Problem	Language	Result	Execution time	Memory
237165		wwdd	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	33 ms	3212 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INFL = 1e18;
const int MN = 200100;
int pr[3][MN];
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	ll n,k;
	cin >> n >> k;
	string s;
	cin >> s;
	pr[0][0] = pr[0][1] = pr[0][2] = 0;
	for(int i=0;i<n;i++) {
		for(int j=0;j<3;j++) {
			pr[j][i+1] = pr[j][i];
		}
		if(s[i] == 'J') {
			pr[0][i+1]++;
		} else if(s[i] == 'O') {
			pr[1][i+1]++;
		} else {
			pr[2][i+1]++;
		}
	}
	ll res = -1;
	for(int i=0;i<n;i++) {
		int u = i;
		for(int j=0;j<3;j++) {
			u = lower_bound(pr[j]+u,pr[j]+n+1,pr[j][u]+k)-pr[j];
		}
		if(u <= n) {
			res = max(res,i+n-u);
		}
	}
	if(res == -1) {
		cout << -1 << '\n';
	} else {
		ll ans = n-3*k-res;
		cout << ans << '\n';
	}
}

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