Submission #292341

#TimeUsernameProblemLanguageResultExecution timeMemory
292341matheo_apdJJOOII 2 (JOI20_ho_t2)C++17
100 / 100
19 ms3244 KiB
#include <bits/stdc++.h>
using namespace std;
#define maxn 200005
#define j 0
#define o 1
#define i 2 //cuidado com os nomekkkkkk
int pref[3][maxn];
int n, k, minimo = maxn, pj = 1, po = 1, pi = 1, p0 = 1;
string s; //vou testar se o tamanho da string aguenta maxn caras

void joi(){
	while(pref[j][po-1] - pref[j][pj-1] < k){
		po++;
		if(po > n) return;
	}
	while(pref[o][pi-1] - pref[o][po-1] < k){
		pi++;
		if(pi > n) return;
	}
	while(pref[i][p0-1] - pref[i][pi-1] < k){
		p0++;
		if(p0 > n+1) return;
	}
}

int solve(){
	for(pj = 1; pj < n; pj++){

		joi();
		if(p0 > n+1 or pi > n or po > n) break;
		minimo = min(minimo, p0 - pj - 3*k);
	}
	if(minimo == maxn) return -1;
	return minimo;
}

int main(){
	cin >> n >> k >> s;
	s = " " + s;
	for(int cont = 1; cont <= n; cont++){

		for(int letter = j; letter <= i; letter++)
			pref[letter][cont] = pref[letter][cont-1];

		if(s[cont] == 'J')
			pref[j][cont]++;
		if(s[cont] == 'O')
			pref[o][cont]++;
		if(s[cont] == 'I')
			pref[i][cont]++; 
	}
	cout << solve() << endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...