Submission #1114675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114675		AdamGS	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	8 ms	5116 KiB

ho_t2

#include <iostream>

using namespace std;

const int MAXN = 200001;

int n, k;

int prefi_J[MAXN];
int prefi_O[MAXN];
int prefi_I[MAXN];

int wystepowanie_J[MAXN];
int wystepowanie_O[MAXN];
int wystepowanie_I[MAXN]; //na jakim indeksie najwczesniej wystepuje wartosc i

char slowo[MAXN];

int zrob(int ktore_j) { //ile trzeba bedzie uzyc operacji 3 typu pesymistycznie zakładając ze pierwsze J w wyrazie bedzie ktore_j w calym wyrazie
	int aktl_ind = wystepowanie_J[ktore_j + k];
	int ile_O_przed = prefi_O[aktl_ind];
	aktl_ind++;
	if ((prefi_O[n] - ile_O_przed) < k) {
		return 1000000000;
	}
	int ktore_o = ile_O_przed + k;
	aktl_ind = wystepowanie_O[ktore_o];
	int ile_i_przed = prefi_I[aktl_ind];
	aktl_ind++;
	if ((prefi_I[n] - ile_i_przed) < k) {
		return 1000000000;
	}
	int ktore_i = ile_i_przed + k;
	aktl_ind = wystepowanie_I[ktore_i];
	int ile_liter = aktl_ind - (wystepowanie_J[ktore_j + 1] - 1);
	ile_liter -= (3 * k);
	return ile_liter;
}
	
	
int main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;
	
	for (int i = 1; n >= i; i++) {
		cin >> slowo[i];
		prefi_J[i] = prefi_J[i - 1];
		prefi_I[i] = prefi_I[i - 1];
		prefi_O[i] = prefi_O[i - 1];
		if (slowo[i] == 'J') {
			prefi_J[i]++;
			wystepowanie_J[prefi_J[i]] = i;
		} else if (slowo[i] == 'O') {
			prefi_O[i]++;
			wystepowanie_O[prefi_O[i]] = i;
		} else {
			prefi_I[i]++;
			wystepowanie_I[prefi_I[i]] = i;
		}
	}
	
	if (prefi_J[n] < k) {
		cout << -1;
		return 0;
	}
	int wynik = 1000000000;
	for (int i = 0; (prefi_J[n] - k) >= i; i++) {
		wynik = min(wynik, zrob(i));
	}
	if (wynik == 1000000000) wynik = -1;
	cout << wynik;
	return 0;
}

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