Submission #206695

#TimeUsernameProblemLanguageResultExecution timeMemory
206695SaboonJJOOII 2 (JOI20_ho_t2)C++14
100 / 100
58 ms3204 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int maxn = 4e5 + 10;

int n, k;
int J[maxn], O[maxn], I[maxn];

int nex(int t, int par[]){
	int lo = t - 1, hi = n;
	while (hi - lo > 1){
		int mid = (lo + hi) >> 1;
		if (par[mid + 1] - par[t] >= k)
			hi = mid;
		else
			lo = mid;
	}
	return hi;
}

int main(){
	ios_base::sync_with_stdio(false);
	string s;
	cin >> n >> k;
	cin >> s;
	for (int i = 0; i < n; i++){
		J[i + 1] = J[i] + (s[i] == 'J');
		O[i + 1] = O[i] + (s[i] == 'O');
		I[i + 1] = I[i] + (s[i] == 'I');
	}
	int answer = -1;
	for (int i = 0; i < n; i++){
		int t = nex(i, J);
			t = nex(t, O);
			t = nex(t, I);
		if (t >= n)
			break;
		if (answer == -1 or answer > (t - i + 1 - 3 * k))
			answer = t - i + 1 - 3 * k;
	}
	cout << answer << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...