Submission #243128

#	Time	Username	Problem	Language	Result	Execution time	Memory
243128		socho	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	41 ms	3356 KiB

ho_t2

#include "bits/stdc++.h"
using namespace std;
void fast() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}
void ran() {
	srand(chrono::steady_clock::now().time_since_epoch().count());
}
long long get_rand() {
	long long a = rand();
	long long b = rand();
	return a * (RAND_MAX + 1ll) + b; 
}
// #define endl '\n'
// #define double long double
// #define int long long
// int MOD = 1000 * 1000 * 1000 + 7;
// int MOD = 998244353;

int n, k;
string s;
const int MXN = 200005;
int pfJ[MXN];
int pfO[MXN];
int pfI[MXN];

int get(int pos) {
	// K Js then K Os then K Is
	// get the earliest position of that last I
	int x = pfJ[pos-1] + k;
	int l = lower_bound(pfJ, pfJ+n+1, x) - pfJ;
	if (l == n+1) return INT_MAX;
	int y = pfO[l] + k;
	l = lower_bound(pfO, pfO+n+1, y) - pfO;
	if (l == n+1) return INT_MAX;
	int z = pfI[l] + k;
	l = lower_bound(pfI, pfI+n+1, z) - pfI;
	if (l == n+1) return INT_MAX;
	return l;
	
}

signed main() {
	
	ran(); fast();
	
	cin >> n >> k >> s;
	
	for (int i=1; i<=n; i++) {
		pfJ[i] = pfJ[i-1];
		pfO[i] = pfO[i-1];
		pfI[i] = pfI[i-1];
		if (s[i-1] == 'J') pfJ[i]++;
		if (s[i-1] == 'O') pfO[i]++;
		if (s[i-1] == 'I') pfI[i]++;
	}
	for (int i=n+1; i<MXN; i++) {
		pfJ[i] = pfJ[i-1];
		pfO[i] = pfO[i-1];
		pfI[i] = pfI[i-1];
	}
	
	int mn = INT_MAX;
	
	for (int i=1; i<=n; i++) {
		// for every 'start'
		int e = get(i);
		if (e == INT_MAX) continue;
		// cout << i << ' ' << e << endl;
		mn = min(mn, e - i + 1 - 3 * k);
	}
	
	if (mn == INT_MAX) cout << -1 << endl;
	else cout << mn << endl;
	
}
	

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