oj.uz

답안 #1114638

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1114638 2024-11-19T09:47:12 Z AdamGS JJOOII 2 (JOI20_ho_t2) C++17
0 / 100
 2 ms 2552 KB 
#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));
	}
	
	cout << wynik;
	return 0;
}

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2552 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Incorrect 1 ms 2384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2552 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Incorrect 1 ms 2384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2552 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Incorrect 1 ms 2384 KB Output isn't correct
10 Halted 0 ms 0 KB -