Submission #1034484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034484		shoryu386	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	20 ms	5608 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mx 1000007
#define inf LLONG_MAX/20
#define pi pair<int, int>
#define mp make_pair

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	int J[n];
	int O[n];
	int I[n];
	J[0] = 0;
	O[0] = 0;
	I[0] = 0;
	if(s[0] == 'J') J[0]++;
	else if(s[0] == 'O') O[0]++;
	else if(s[0] == 'I') I[0]++;
	for(int i = 1; i < n; i++){
		J[i] = J[i - 1];
		O[i] = O[i - 1];
		I[i] = I[i - 1];
		if(s[i] == 'J') J[i]++;
		else if(s[i] == 'O') O[i]++;
		else if(s[i] == 'I') I[i]++;
	}
	
	int ans = inf;
	for(int i = 0; i < n; i++){
		//fused the i=0 and i>0 cases together, so we repeat code less (and hence less likely to make mistake)
		int prevJ = 0;
		if (i != 0){
			prevJ = J[i-1];
		}
		
		//starting from index i, the number of Js that came before is J[i-1] (if i-1 exists, otherwise 0)
		int jay = lower_bound(J + i, J + n, k + prevJ) - J;
		if (jay == n) continue;
		
		//jay is now the last J that we take
		//so our next lower_bound starts one space after that
		//then the number of Os before we start taking Os is O[jay], since we start on jay+1
		int oou = lower_bound(O + jay + 1, O + n, k + O[jay]) - O;
		if(oou == n) continue;
		
		//oou is now the last O that we take
		//so our next lower_bound starts one space after that
		//then the number of Is before we start taking Is is I[oou], since we start on oou+1
		int aii = lower_bound(I + oou + 1, I + n, k + I[oou]) - I;
		if(aii == n) continue;
		
		//made a change here too; length of subarray from [l, r] is r-l+1, not r-l
		int cost = (aii - i + 1) - (3 * k);
		ans = min(cost, ans); 
	}
	if(ans == inf) ans = -1;
	cout << ans;
	return 0; 
}

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