Submission #206695

#	Time	Username	Problem	Language	Result	Execution time	Memory
206695		Saboon	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	58 ms	3204 KiB

ho_t2

#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';
}

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