Submission #244876

#	Time	Username	Problem	Language	Result	Execution time	Memory
244876		maximath_1	JJOOII 2 (JOI20_ho_t2)	C++11	0 / 100	5 ms	384 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int cnt[3][200005], last[3][200005], n, k;
string s;

void proc(int id){
	int lf = 0;
	for(int rg = 1; rg <= n; rg ++){
		while(cnt[id][rg] - cnt[id][lf] >= k) lf ++;
		last[id][rg - 1] = lf - 1;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> k;
	cin >> s;
	for(int i = 0; i < n; i ++){
		if(s[i] == 'J') cnt[0][i + 1]++;
		if(s[i] == 'O') cnt[1][i + 1]++;
		if(s[i] == 'I') cnt[2][i + 1]++;
	}

	for(int i = 1; i <= n; i ++) for(int j = 0; j < 3; j ++)
		cnt[j][i] += cnt[j][i - 1];

	for(int i = 0; i < 3; i ++) proc(i);

	int ans = 2000000000;

	for(int i = 0; i < n; i ++){
		int nw = last[2][i] - 1;
		if(nw >= 0) nw = last[1][nw] - 1;
		else nw = -1000000;
		if(nw >= 0) nw = last[0][nw] - 1;
		else nw = -1000000;

		if(nw != -1000000)
			ans = min(ans, i - nw);
	}

	if(ans == 2000000000) ans = -1 + 3 * k;
	printf("%d\n", ans - 3 * k);
	return 0;
}

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